Дизъюнктивная нормальная форма (ДНФ)
Формула G имеет дизъюнктивную нормальную форму, если она является элементарной конъюнкцией или дизъюнкцией элементарных конъюнкций. Например, (X Теорема: Для всякой формулы F существует формула G, равносильная F и имеющая ДНФ. Алгоритм приведения к ДНФ 1. Исключить из исходной формулы эквиваленцию ( F 2. Занести отрицание к атомарным формулам с помощью следующих законов:
3. Если формула содержит подформулу вида Н 1 Нормальные формы в логике высказываний. Алгоритм преобразования формулы в конъюнктивную нормальную форму (КНФ) Литерал – атомарная формула (кроме логических 1 и 0) или ее отрицание. Элементарной дизъюнкцией (дизъюнктом) называется литерал или дизъюнкция литералов.
|
Y) 
(
X 
Z).
) и импликацию (
).
G; 
G; 
