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

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

ПримерыПравить

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

$A\vee <!--\; \vee \; -->B$$A\lor B$ 

$(A\wedge <!--\; \wedge \; -->B)\vee <!--\; \vee \; -->\stackrel{¯<!--\; ¯\; -->}{A}$$(A\land B)\lor {\overline {A}}$ 

$(A\wedge <!--\; \wedge \; -->B\wedge <!--\; \wedge \; -->\stackrel{¯<!--\; ¯\; -->}{C})\vee <!--\; \vee \; -->(\stackrel{¯<!--\; ¯\; -->}{D}\wedge <!--\; \wedge \; -->E\wedge <!--\; \wedge \; -->F)\vee <!--\; \vee \; -->(C\wedge <!--\; \wedge \; -->D)\vee <!--\; \vee \; -->B$$(A\land B\land {\overline {C}})\lor ({\overline {D}}\land E\land F)\lor (C\land D)\lor B$ 

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

$\stackrel{¯<!--\; ¯\; -->}{(A\vee <!--\; \vee \; -->B)}$${\overline {(A\lor B)}}$ 

$A\vee <!--\; \vee \; -->(B\wedge <!--\; \wedge \; -->(C\vee <!--\; \vee \; -->D))$$A\lor (B\land (C\lor D))$ 

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

$\stackrel{¯<!--\; ¯\; -->}{A}\wedge <!--\; \wedge \; -->\stackrel{¯<!--\; ¯\; -->}{B}$${\overline {A}}\land {\overline {B}}$ 

$A\vee <!--\; \vee \; -->(B\wedge <!--\; \wedge \; -->C)\vee <!--\; \vee \; -->(B\wedge <!--\; \wedge \; -->D).$$A\lor (B\land C)\lor (B\land D).$ 

Построение ДНФПравить

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

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

$A\to <!--\; \to \; -->B=\mathrm{\neg <!--\; \neg \; -->}A\vee <!--\; \vee \; -->B$$A\rightarrow B=\neg A\vee B$ 

$A\leftrightarrow <!--\; \leftrightarrow \; -->B=(A\wedge <!--\; \wedge \; -->B)\vee <!--\; \vee \; -->(\mathrm{\neg <!--\; \neg \; -->}A\wedge <!--\; \wedge \; -->\mathrm{\neg <!--\; \neg \; -->}B)$$A\leftrightarrow B=(A\wedge B)\vee (\neg A\wedge \neg B)$ 

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

$\mathrm{\neg <!--\; \neg \; -->}(A\vee <!--\; \vee \; -->B)=\mathrm{\neg <!--\; \neg \; -->}A\wedge <!--\; \wedge \; -->\mathrm{\neg <!--\; \neg \; -->}B$$\neg (A\vee B)=\neg A\wedge \neg B$ 

$\mathrm{\neg <!--\; \neg \; -->}(A\wedge <!--\; \wedge \; -->B)=\mathrm{\neg <!--\; \neg \; -->}A\vee <!--\; \vee \; -->\mathrm{\neg <!--\; \neg \; -->}B$$\neg (A\wedge B)=\neg A\vee \neg B$ 

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

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

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

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

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

$F=\mathrm{\neg <!--\; \neg \; -->}((\mathrm{\neg <!--\; \neg \; -->}X\vee <!--\; \vee \; -->Y)\vee <!--\; \vee \; -->\mathrm{\neg <!--\; \neg \; -->}(\mathrm{\neg <!--\; \neg \; -->}Y\vee <!--\; \vee \; -->Z))$$F=\neg ((\neg X\vee Y)\vee \neg (\neg Y\vee Z))$ 

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

$F=(\mathrm{\neg <!--\; \neg \; -->}\mathrm{\neg <!--\; \neg \; -->}X\wedge <!--\; \wedge \; -->\mathrm{\neg <!--\; \neg \; -->}Y)\wedge <!--\; \wedge \; -->(\mathrm{\neg <!--\; \neg \; -->}Y\vee <!--\; \vee \; -->Z)=(X\wedge <!--\; \wedge \; -->\mathrm{\neg <!--\; \neg \; -->}Y)\wedge <!--\; \wedge \; -->(\mathrm{\neg <!--\; \neg \; -->}Y\vee <!--\; \vee \; -->Z)$$F=(\neg \neg X\wedge \neg Y)\wedge (\neg Y\vee Z)=(X\wedge \neg Y)\wedge (\neg Y\vee Z)$ 

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

$F=(X\wedge <!--\; \wedge \; -->\mathrm{\neg <!--\; \neg \; -->}Y\wedge <!--\; \wedge \; -->\mathrm{\neg <!--\; \neg \; -->}Y)\vee <!--\; \vee \; -->(X\wedge <!--\; \wedge \; -->\mathrm{\neg <!--\; \neg \; -->}Y\wedge <!--\; \wedge \; -->Z)$$F=(X\wedge \neg Y\wedge \neg Y)\vee (X\wedge \neg Y\wedge Z)$ 

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

$F=(X\wedge <!--\; \wedge \; -->\mathrm{\neg <!--\; \neg \; -->}Y)\vee <!--\; \vee \; -->(X\wedge <!--\; \wedge \; -->\mathrm{\neg <!--\; \neg \; -->}Y\wedge <!--\; \wedge \; -->Z)$$F=(X\wedge \neg Y)\vee (X\wedge \neg Y\wedge Z)$ 

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

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

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

$(A\wedge <!--\; \wedge \; -->B)\vee <!--\; \vee \; -->(\mathrm{\neg <!--\; \neg \; -->}B\wedge <!--\; \wedge \; -->C)\vee <!--\; \vee \; -->(B\wedge <!--\; \wedge \; -->\mathrm{\neg <!--\; \neg \; -->}C)$$(A\land B)\lor (\neg B\land C)\lor (B\land \neg C)$ 

Переход от ДНФ к СДНФПравить

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

$Z\vee <!--\; \vee \; -->\mathrm{\neg <!--\; \neg \; -->}Z=1$$Z\vee \neg Z=1$ ,

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

$X\vee <!--\; \vee \; -->\mathrm{\neg <!--\; \neg \; -->}Y\mathrm{\neg <!--\; \neg \; -->}Z=X(Y\vee <!--\; \vee \; -->\mathrm{\neg <!--\; \neg \; -->}Y)(Z\vee <!--\; \vee \; -->\mathrm{\neg <!--\; \neg \; -->}Z)\vee <!--\; \vee \; -->(X\vee <!--\; \vee \; -->\mathrm{\neg <!--\; \neg \; -->}X)\mathrm{\neg <!--\; \neg \; -->}Y\mathrm{\neg <!--\; \neg \; -->}Z=$$X\vee \neg Y\neg Z=X(Y\vee \neg Y)(Z\vee \neg Z)\vee (X\vee \neg X)\neg Y\neg Z=$ 

$XYZ\vee <!--\; \vee \; -->X\mathrm{\neg <!--\; \neg \; -->}YZ\vee <!--\; \vee \; -->XY\mathrm{\neg <!--\; \neg \; -->}Z\vee <!--\; \vee \; -->X\mathrm{\neg <!--\; \neg \; -->}Y\mathrm{\neg <!--\; \neg \; -->}Z\vee <!--\; \vee \; -->X\mathrm{\neg <!--\; \neg \; -->}Y\mathrm{\neg <!--\; \neg \; -->}Z\vee <!--\; \vee \; -->\mathrm{\neg <!--\; \neg \; -->}X\mathrm{\neg <!--\; \neg \; -->}Y\mathrm{\neg <!--\; \neg \; -->}Z=$$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=$ 

$=XYZ\vee <!--\; \vee \; -->X\mathrm{\neg <!--\; \neg \; -->}YZ\vee <!--\; \vee \; -->XY\mathrm{\neg <!--\; \neg \; -->}Z\vee <!--\; \vee \; -->X\mathrm{\neg <!--\; \neg \; -->}Y\mathrm{\neg <!--\; \neg \; -->}Z\vee <!--\; \vee \; -->\mathrm{\neg <!--\; \neg \; -->}X\mathrm{\neg <!--\; \neg \; -->}Y\mathrm{\neg <!--\; \neg \; -->}Z$$=XYZ\vee X\neg YZ\vee XY\neg Z\vee X\neg Y\neg Z\vee \neg X\neg Y\neg Z$ 

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

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

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

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

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

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

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

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

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

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

Особенности обозначенийПравить

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

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

$(A\wedge <!--\; \wedge \; -->B\wedge <!--\; \wedge \; -->\stackrel{¯<!--\; ¯\; -->}{C})\vee <!--\; \vee \; -->(\stackrel{¯<!--\; ¯\; -->}{D}\wedge <!--\; \wedge \; -->E\wedge <!--\; \wedge \; -->F)\vee <!--\; \vee \; -->(C\wedge <!--\; \wedge \; -->D)\vee <!--\; \vee \; -->B;$$(A\land B\land {\overline {C}})\lor ({\overline {D}}\land E\land F)\lor (C\land D)\lor B;$ 

$(A\cdot <!--\; \cdot \; -->B\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{C})\vee <!--\; \vee \; -->(\stackrel{¯<!--\; ¯\; -->}{D}\cdot <!--\; \cdot \; -->E\cdot <!--\; \cdot \; -->F)\vee <!--\; \vee \; -->(C\cdot <!--\; \cdot \; -->D)\vee <!--\; \vee \; -->B;$$(A\cdot B\cdot {\overline {C}})\lor ({\overline {D}}\cdot E\cdot F)\lor (C\cdot D)\lor B;$ 

$AB\stackrel{¯<!--\; ¯\; -->}{C}\vee <!--\; \vee \; -->\stackrel{¯<!--\; ¯\; -->}{D}EF\vee <!--\; \vee \; -->CD\vee <!--\; \vee \; -->B;$$AB{\overline {C}}\lor {\overline {D}}EF\lor CD\lor B;$ 

$AB\stackrel{¯<!--\; ¯\; -->}{C}+\stackrel{¯<!--\; ¯\; -->}{D}EF+CD+B.$$AB{\overline {C}}+{\overline {D}}EF+CD+B.$ 

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

См. такжеПравить

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

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

ЛитератураПравить

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

СсылкиПравить

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