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

4. Переход от КНФ к СКНФ 
Если в простой дизъюнкции не хватает какой-то переменной (например, z, то добавляем в нее выражение :
(это не меняет самой дизъюнкции), после чего раскрываем скобки с использованием 
распределительного закона): 
Таким образом, из КНФ получена СКНФ. 
5. Формальная грамматика, описывающая КНФ
Следующая формальная грамматика описывает все формулы, приведенные к КНФ: 
<КНФ> → <дизъюнкт> 
<КНФ> → <КНФ> 
∧
<дизъюнкт> 
<дизъюнкт> → <литерал> 
<дизъюнкт> → (<дизъюнкт> 
∨
<литерал>) 
<литерал> → <терм> 
<литерал> → ¬<терм> 
где <терм> обозначает произвольную булеву переменную. 
6. Задача выполнимости формулы в КНФ 
В теории вычислительной сложности важную роль играет задача выполнимости булевых формул в 
конъюнктивной нормальной форме. Согласно теореме Кука, эта задача NP-полна, и она сводится к задаче о 
выполнимости формул в 3-КНФ, которая сводится и к которой в свою очередь сводятся другие NP-полные 
задачи. 
 
 
 
 

---

ДНФ . Дизъюнктивная нормальная форма (ДНФ)
Назовем 
элементарной конъюнкцией формулу,
которая имеет вид 
где 
k >
1 и каждый из 
конъюнктивных элементов А
г
, А
ъ
..., 
А
к
является либо 
логической переменной, либо отрицанием логической переменной. 
Пример 2.12 
Формулы 
х
л 
у,
л 
х
2
л 
х
3
л х
4
— примеры элементарных конъюнкций. ? 
Дизъюнктивная нормальная форма
(ДНФ) формулы логики высказываний 
представляет собой дизъюнкцию элементарных конъюнкций, т.е. имеет вид 
где 
т >
1 и все подформулы 
А
ь
 А
ъ
 А
т
— элементарные конъюнкции. 
Пример 2.13 
Как следует из закона 24, формула (А л В) v (А л В) является ДНФ формулы 
АеэВ. ? 
Пусть некоторая формула уже приведена к нормальной форме. Для того 
чтобы эта форма представляла собой ДНФ, т.е. «дизъюнкцию конъюнкций», 
она не должна содержать подформул вида (В v 
С)
л А или Aa(BvC). 
Если такие подформулы имеются, то для получения ДНФ к 
алгоритму 
приведения
в утверждении выше нужно добавить еще один шаг. 
Шаг 4. Каждую подформулу вида (BvC)aA заменяем согласно закону 
коммутативности 17 формулой Aa(BvC). Каждую подформулу вида Ал (В v 
С) заменяем согласно закону дистрибутивности 21 формулой (AaB)v(AaC), 
получая «дизъюнкцию конъюнкций».