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

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

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

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

 
 
 

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

 
 
 

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

 
 
 

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

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

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

 
 

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

 
 

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

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

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

Приведем к КНФ формулу

 

Преобразуем формулу   к формуле, не содержащей  :

 

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

 

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

 

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

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

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

 

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

Если в простой дизъюнкции не хватает какой-то переменной (например, z), то добавляем в неё выражение :  (это не меняет самой дизъюнкции), после чего раскрываем скобки с использованием распределительного закона:

 

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

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

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

<КНФ> → <дизъюнкт>
<КНФ> → <КНФ> ∧ <дизъюнкт>
<дизъюнкт> → <литерал>;
<дизъюнкт> → (<дизъюнкт> ∨ <литерал>)
<литерал> → <терм>
<литерал> → ¬<терм>

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

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

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

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

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

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

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

 
 
 
 
 

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

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

ПримечанияПравить

  1. Поздняков С.Н., Рыбин С.В. Дискретная математика. — С. 303.

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

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

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