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

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

Примеры

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

$A\vee B$

$(A\wedge B)\vee \bar{A}$

$(A\wedge B\wedge \bar{C})\vee (\bar{D}\wedge E\wedge F)\vee (C\wedge D)\vee B$

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

$\overline{(A\vee B)}$

$A\vee (B\wedge (C\vee D))$

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

$\bar{A}\wedge \bar{B}$

$A\vee (B\wedge C)\vee (B\wedge D).$

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

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

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

$A\to B=\mathrm{\neg }A\vee B$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$(A\wedge B)\vee (\mathrm{\neg }B\wedge C)\vee (B\wedge \mathrm{\neg }C)$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Особенности обозначений

Следует отметить, что для удобства восприятия в качестве обозначения конъюнкции и дизъюнкции часто используют символы арифметического умножения и сложения, при этом символ умножения часто опускается. В этом случае формулы булевой алгебры выглядят как алгебраические полиномы, что более привычно для глаза, однако иногда может привести к недоразумениям.

Например, следующие записи эквивалентны:

$(A\wedge B\wedge \bar{C})\vee (\bar{D}\wedge E\wedge F)\vee (C\wedge D)\vee B;$

$(A\cdot B\cdot \bar{C})\vee (\bar{D}\cdot E\cdot F)\vee (C\cdot D)\vee B;$

$AB\bar{C}\vee \bar{D}EF\vee CD\vee B;$

$AB\bar{C}+\bar{D}EF+CD+B.$

По этой причине ДНФ в русскоязычной литературе иногда называют «суммой произведений», что является калькой с английского термина «sum of products».

См. также

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

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

Литература

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

Ссылки

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