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

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

Примеры и контрпримеры Править

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

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

$(A\vee <!--\; \vee \; -->B)\wedge <!--\; \wedge \; -->(\mathrm{\neg <!--\; \neg \; -->}B\vee <!--\; \vee \; -->C\vee <!--\; \vee \; -->\mathrm{\neg <!--\; \neg \; -->}D)\wedge <!--\; \wedge \; -->(D\vee <!--\; \vee \; -->\mathrm{\neg <!--\; \neg \; -->}E),$$(A\vee B)\wedge (\neg B\vee C\vee \neg D)\wedge (D\vee \neg E),$ 

$A\wedge <!--\; \wedge \; -->B.$$A\wedge B.$ 

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

$\mathrm{\neg <!--\; \neg \; -->}(B\vee <!--\; \vee \; -->C),$$\neg (B\vee C),$ 

$(A\wedge <!--\; \wedge \; -->B)\vee <!--\; \vee \; -->C,$$(A\wedge B)\vee C,$ 

$A\wedge <!--\; \wedge \; -->(B\vee <!--\; \vee \; -->(D\wedge <!--\; \wedge \; -->E)).$$A\wedge (B\vee (D\wedge E)).$ 

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

$\mathrm{\neg <!--\; \neg \; -->}B\wedge <!--\; \wedge \; -->\mathrm{\neg <!--\; \neg \; -->}C,$$\neg B\wedge \neg C,$ 

$(A\vee <!--\; \vee \; -->C)\wedge <!--\; \wedge \; -->(B\vee <!--\; \vee \; -->C),$$(A\vee C)\wedge (B\vee C),$ 

$A\wedge <!--\; \wedge \; -->(B\vee <!--\; \vee \; -->D)\wedge <!--\; \wedge \; -->(B\vee <!--\; \vee \; -->E).$$A\wedge (B\vee D)\wedge (B\vee E).$ 

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

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

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

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

$A\leftrightarrow <!--\; \leftrightarrow \; -->B=(\mathrm{\neg <!--\; \neg \; -->}A\vee <!--\; \vee \; -->B)\wedge <!--\; \wedge \; -->(A\vee <!--\; \vee \; -->\mathrm{\neg <!--\; \neg \; -->}B).$$A\leftrightarrow B=(\neg A\vee B)\wedge (A\vee \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=(X\to <!--\; \to \; -->Y)\wedge <!--\; \wedge \; -->((\mathrm{\neg <!--\; \neg \; -->}Y\to <!--\; \to \; -->Z)\to <!--\; \to \; -->\mathrm{\neg <!--\; \neg \; -->}X).$$F=(X\rightarrow Y)\wedge ((\neg Y\rightarrow Z)\rightarrow \neg X).$ 

Преобразуем формулу $F$$F$  к формуле, не содержащей $\to <!--\; \to \; -->$$\rightarrow$ :

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

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

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

По закону дистрибутивности получим КНФ:

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

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

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

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

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

A≡((x→y)→!x)→(x→(y&x));

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

Если в простой дизъюнкции не хватает какой-то переменной (например, z), то добавляем в неё выражение :$Z\wedge <!--\; \wedge \; -->\mathrm{\neg <!--\; \neg \; -->}Z=0$$Z\wedge \neg Z=0$  (это не меняет самой дизъюнкции), после чего раскрываем скобки с использованием распределительного закона:

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

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

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

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

<КНФ> → <дизъюнкт>

<КНФ> → <КНФ> ∧ <дизъюнкт>

<дизъюнкт> → <литерал>;

<дизъюнкт> → (<дизъюнкт> ∨ <литерал>)

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

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

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

Задача выполнимости формулы в КНФ Править

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

Задача о выполнимости 2-КНФ формул может быть решена за линейное время.

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

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

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

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

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

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

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

$(A+B)(\stackrel{¯<!--\; ¯\; -->}{B}+C+\stackrel{¯<!--\; ¯\; -->}{D})(D+\stackrel{¯<!--\; ¯\; -->}{E}).$$(A+B)({\overline {B}}+C+{\overline {D}})(D+{\overline {E}}).$ 

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

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

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

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

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

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

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