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

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

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

${\displaystyle (A\vee B)\wedge (\neg B\vee C\vee \neg D)\wedge (D\vee \neg E),}$

${\displaystyle A\wedge B.}$

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

${\displaystyle \neg (B\vee C),}$

${\displaystyle (A\wedge B)\vee C,}$

${\displaystyle A\wedge (B\vee (D\wedge E)).}$

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

${\displaystyle \neg B\wedge \neg C,}$

${\displaystyle (A\vee C)\wedge (B\vee C),}$

${\displaystyle A\wedge (B\vee D)\wedge (B\vee E).}$

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

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

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

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

${\displaystyle (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-КНФ формул может быть решена за линейное время.

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

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

${\displaystyle (A\vee B)\wedge (\neg B\vee C\vee \neg D)\wedge (D\vee \neg E);}$

${\displaystyle (A\vee B)\wedge ({\overline {B}}\vee C\vee {\overline {D}})\wedge (D\vee {\overline {E}});}$

${\displaystyle (A\vee B)\cdot ({\overline {B}}\vee C\vee {\overline {D}})\cdot (D\vee {\overline {E}});}$

${\displaystyle (A\vee B)({\overline {B}}\vee C\vee {\overline {D}})(D\vee {\overline {E}});}$

${\displaystyle (A+B)({\overline {B}}+C+{\overline {D}})(D+{\overline {E}}).}$

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

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

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

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