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

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

Примеры

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

[math]\displaystyle{ A \lor B }[/math]

[math]\displaystyle{ (A \land B) \lor \overline{A} }[/math]

[math]\displaystyle{ (A \land B \land \overline{C}) \lor (\overline{D} \land E \land F) \lor (C \land D) \lor B }[/math]

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

[math]\displaystyle{ \overline{(A \lor B)} }[/math]

[math]\displaystyle{ A \lor (B \land (C \lor D)) }[/math]

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

[math]\displaystyle{ \overline{A} \land \overline{B} }[/math]

[math]\displaystyle{ A \lor (B \land C) \lor (B \land D). }[/math]

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

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

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

[math]\displaystyle{ A \rightarrow B = \neg A \vee B }[/math]

[math]\displaystyle{ A \leftrightarrow B = (A \wedge B) \vee (\neg A \wedge \neg B) }[/math]

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

[math]\displaystyle{ \neg (A \vee B) = \neg A \wedge \neg B }[/math]

[math]\displaystyle{ \neg (A \wedge B) = \neg A \vee \neg B }[/math]

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

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

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

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

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

[math]\displaystyle{ F = \neg ((\neg X \vee Y) \vee \neg (\neg Y \vee Z)) }[/math]

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

[math]\displaystyle{ F = (\neg \neg X \wedge \neg Y) \wedge (\neg Y \vee Z) = (X \wedge \neg Y) \wedge (\neg Y \vee Z) }[/math]

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

[math]\displaystyle{ F = (X \wedge \neg Y \wedge \neg Y) \vee (X \wedge \neg Y \wedge Z) }[/math]

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

[math]\displaystyle{ F = (X \wedge \neg Y ) \vee (X \wedge \neg Y \wedge Z) }[/math]

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

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

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

[math]\displaystyle{ (A \land B) \lor (\neg B \land C) \lor (B \land \neg C) }[/math]

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

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

[math]\displaystyle{ Z \vee \neg Z = 1 }[/math],

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

[math]\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 = }[/math]

[math]\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 = }[/math]

[math]\displaystyle{ = XYZ \vee X \neg YZ \vee XY \neg Z \vee X \neg Y \neg Z \vee \neg X \neg Y \neg Z }[/math]

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

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

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

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

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

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

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

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

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

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

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

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

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

[math]\displaystyle{ (A \land B \land \overline{C}) \lor (\overline{D} \land E \land F) \lor (C \land D) \lor B; }[/math]

[math]\displaystyle{ (A \cdot B \cdot \overline{C}) \lor (\overline{D} \cdot E \cdot F) \lor (C \cdot D) \lor B; }[/math]

[math]\displaystyle{ AB\overline{C} \lor \overline{D}EF \lor CD \lor B; }[/math]

[math]\displaystyle{ AB\overline{C} + \overline{D}EF + CD + B. }[/math]

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

См. также

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

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

Литература

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

Ссылки

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