Дизъюнктивная нормальная форма

Дизъюнкти́вная норма́льная фо́рма (ДНФ) в булевой логике — нормальная форма, в которой булева формула имеет вид дизъюнкции конъюнкций литералов. Любая булева формула может быть приведена к ДНФ.^[1] Для этого можно использовать закон двойного отрицания, закон де Моргана, закон дистрибутивности. Дизъюнктивная нормальная форма удобна для автоматического доказательства теорем.

Примеры

Формулы в ДНФ:

${\displaystyle A\lor B}$

${\displaystyle (A\land B)\lor \neg A}$

${\displaystyle (A\land B\land \neg C)\lor (\neg D\land E\land F)\lor (C\land D)\lor B}$

Формулы не в ДНФ:

${\displaystyle \neg (A\lor B)}$

${\displaystyle A\lor (B\land (C\lor D))}$

Но последние две формулы эквивалентны следующим формулам в ДНФ:

${\displaystyle \neg A\land \neg B}$

${\displaystyle A\lor (B\land C)\lor (B\land D).}$

Построение ДНФ

Алгоритм построения ДНФ

1) Избавиться от всех логических операций, содержащихся в формуле, заменив их основными: конъюнкцией, дизъюнкцией, отрицанием. Это можно сделать, используя равносильные формулы:

${\displaystyle A\rightarrow B=\neg A\vee B}$

${\displaystyle A\leftrightarrow B=(A\wedge B)\vee (\neg A\wedge \neg B)}$

2) Заменить знак отрицания, относящийся ко всему выражению, знаками отрицания, относящимися к отдельным переменным высказываниям на основании формул:

${\displaystyle \neg (A\vee B)=\neg A\wedge \neg B}$

${\displaystyle \neg (A\wedge B)=\neg A\vee \neg B}$

3) Избавиться от знаков двойного отрицания.

4) Применить, если нужно, к операциям конъюнкции и дизъюнкции свойства дистрибутивности и формулы поглощения.

Пример построения ДНФ

Приведем к ДНФ формулу ${\displaystyle F=\neg ((X\rightarrow Y)\vee \neg (Y\rightarrow Z))}$

Выразим логическую операцию → через ${\displaystyle \vee \wedge \neg }$

${\displaystyle F=\neg ((\neg X\vee Y)\vee \neg (\neg Y\vee Z))}$

В полученной формуле перенесем отрицание к переменным и сократим двойные отрицания:

${\displaystyle F=(\neg \neg X\wedge \neg Y)\wedge (\neg Y\vee Z)=(X\wedge \neg Y)\wedge (\neg Y\vee Z)}$

Используя закон дистрибутивности, получаем:

${\displaystyle F=(X\wedge \neg Y\wedge \neg Y)\vee (X\wedge \neg Y\wedge Z)}$

Используя идемпотентность конъюкции, получаем ДНФ:

${\displaystyle F=(X\wedge \neg Y)\vee (X\wedge \neg Y\wedge Z)}$

k-дизъюнктивная нормальная форма

k-дизъюнктивной нормальной формой называют дизъюнктивную нормальную форму, в которой каждая конъюнкция содержит ровно k литералов.

Например, следующая формула записана в 2-ДНФ:

${\displaystyle (A\land B)\lor (\neg B\land C)\lor (B\land \neg C)}$

Переход от ДНФ к СДНФ

Если в какой-то простой конъюнкции недостаёт переменной, например, Z, вставляем в неё выражение

${\displaystyle Z\vee \neg Z=1}$,

после чего раскрываем скобки (при этом повторяющиеся дизъюнктные слагаемые не пишем, так как ${\displaystyle Z\vee Z=Z}$ по закону идемпотентности). Например:

${\displaystyle X\vee \neg Y\neg Z=X(Y\vee \neg Y)(Z\vee \neg Z)\vee (X\vee \neg X)\neg Y\neg Z=}$

${\displaystyle XYZ\vee X\neg YZ\vee XY\neg Z\vee X\neg Y\neg Z\vee X\neg Y\neg Z\vee \neg X\neg Y\neg Z=}$

${\displaystyle =XYZ\vee X\neg YZ\vee XY\neg Z\vee X\neg Y\neg Z\vee \neg X\neg Y\neg Z}$

Таким образом, из ДНФ получили СДНФ.

Формальная грамматика, описывающая ДНФ

Следующая формальная грамматика описывает все формулы, приведенные к ДНФ:

<ДНФ> → <конъюнкт>

<ДНФ> → <ДНФ> ∨ <конъюнкт>

<конъюнкт> → <литерал>

<конъюнкт> → (<конъюнкт> ∧ <литерал>)

<литерал> → <терм>

<литерал> → ¬<терм>

где <терм> обозначает произвольную булеву переменную.

См. также

• Конъюнктивная нормальная форма
• Совершенная дизъюнктивная нормальная форма
• Совершенная конъюнктивная нормальная форма

• Конъюнктивный одночлен
• Дизъюнктивный одночлен

Примечания

Литература

• Ю.И. Галушкина, А.Н. Марьямов: Конспект лекций по дискретной математике - 2-е изд., испр. - М.: Айрис-пресс, 2008. - 176 с. - (Высшее образование).

Ссылки

• ДНФ, СДНФ, КНФ, СКНФ
• Disjunctive Normal Form
• Дизъюнктивная и Конъюнктивная нормальные формы
• Определение ДНФ и КНФ