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

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

Примеры и контрпримеры

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

<math>\neg A \wedge (B \vee C),</math>

<math>(A \vee B) \wedge (\neg B \vee C \vee \neg D) \wedge (D \vee \neg E),</math>

<math>A \wedge B.</math>

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

<math>\neg (B \vee C),</math>

<math>(A \wedge B) \vee C,</math>

<math>A \wedge (B \vee (D \wedge E)).</math>

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

<math>\neg B \wedge \neg C,</math>

<math>(A \vee C) \wedge (B \vee C),</math>

<math>A \wedge (B \vee D) \wedge (B \vee E).</math>

Построение КНФ

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

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

<math>A \rightarrow B = \neg A \vee B,</math>

<math>A \leftrightarrow B = (\neg A \vee B) \wedge (A \vee \neg B).</math>

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

<math>\neg (A \vee B) = \neg A \wedge \neg B,</math>

<math>\neg (A \wedge B) = \neg A \vee \neg B.</math>

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

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

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

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

<math> F = ( X \rightarrow Y ) \wedge (( \neg Y \rightarrow Z ) \rightarrow \neg X ).</math>

Преобразуем формулу <math>F</math> к формуле, не содержащей <math>\rightarrow</math>:

<math> 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 ).</math>

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

<math> F = ( \neg X \vee Y) \wedge ((\neg Y \wedge \neg Z) \vee \neg X).</math>

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

<math>F = (\neg X \vee Y) \wedge (\neg X \vee \neg Y) \wedge (\neg X \vee \neg Z).</math>

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

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

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

<math>(A \or B) \and (\neg B \or C) \and (B \or \neg C).</math>

Переход от КНФ к СКНФ

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

<math>(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).</math>

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

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

Литература

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

Ссылки

• [dvo.sut.ru/libr/himath/w163rabk/3.htm ДНФ, СДНФ, КНФ, СКНФ]
• [all4study.ru/matematika/dizyunktivnaya-i-konyunktivnaya-normalnye-formy-razlozhenie-funkcii-po-komponentam.html Дизъюнктивная и Конъюнктивная нормальные формы]

Отрывок, характеризующий Конъюнктивная нормальная форма

– Merci, merci, mon vieux, le reste?.. – повторил француз, улыбаясь, и, достав ассигнацию, дал Каратаеву, – mais le reste… [Спасибо, спасибо, любезный, а остаток то где?.. Остаток то давай.]
Пьер видел, что Платон не хотел понимать того, что говорил француз, и, не вмешиваясь, смотрел на них. Каратаев поблагодарил за деньги и продолжал любоваться своею работой. Француз настаивал на остатках и попросил Пьера перевести то, что он говорил.
– На что же ему остатки то? – сказал Каратаев. – Нам подверточки то важные бы вышли. Ну, да бог с ним. – И Каратаев с вдруг изменившимся, грустным лицом достал из за пазухи сверточек обрезков и, не глядя на него, подал французу. – Эхма! – проговорил Каратаев и пошел назад. Француз поглядел на полотно, задумался, взглянул вопросительно на Пьера, и как будто взгляд Пьера что то сказал ему.
– Platoche, dites donc, Platoche, – вдруг покраснев, крикнул француз пискливым голосом. – Gardez pour vous, [Платош, а Платош. Возьми себе.] – сказал он, подавая обрезки, повернулся и ушел.
– Вот поди ты, – сказал Каратаев, покачивая головой. – Говорят, нехристи, а тоже душа есть. То то старички говаривали: потная рука торовата, сухая неподатлива. Сам голый, а вот отдал же. – Каратаев, задумчиво улыбаясь и глядя на обрезки, помолчал несколько времени. – А подверточки, дружок, важнеющие выдут, – сказал он и вернулся в балаган.


Прошло четыре недели с тех пор, как Пьер был в плену. Несмотря на то, что французы предлагали перевести его из солдатского балагана в офицерский, он остался в том балагане, в который поступил с первого дня.
В разоренной и сожженной Москве Пьер испытал почти крайние пределы лишений, которые может переносить человек; но, благодаря своему сильному сложению и здоровью, которого он не сознавал до сих пор, и в особенности благодаря тому, что эти лишения подходили так незаметно, что нельзя было сказать, когда они начались, он переносил не только легко, но и радостно свое положение. И именно в это то самое время он получил то спокойствие и довольство собой, к которым он тщетно стремился прежде. Он долго в своей жизни искал с разных сторон этого успокоения, согласия с самим собою, того, что так поразило его в солдатах в Бородинском сражении, – он искал этого в филантропии, в масонстве, в рассеянии светской жизни, в вине, в геройском подвиге самопожертвования, в романтической любви к Наташе; он искал этого путем мысли, и все эти искания и попытки все обманули его. И он, сам не думая о том, получил это успокоение и это согласие с самим собою только через ужас смерти, через лишения и через то, что он понял в Каратаеве. Те страшные минуты, которые он пережил во время казни, как будто смыли навсегда из его воображения и воспоминания тревожные мысли и чувства, прежде казавшиеся ему важными. Ему не приходило и мысли ни о России, ни о войне, ни о политике, ни о Наполеоне. Ему очевидно было, что все это не касалось его, что он не призван был и потому не мог судить обо всем этом. «России да лету – союзу нету», – повторял он слова Каратаева, и эти слова странно успокоивали его. Ему казалось теперь непонятным и даже смешным его намерение убить Наполеона и его вычисления о кабалистическом числе и звере Апокалипсиса. Озлобление его против жены и тревога о том, чтобы не было посрамлено его имя, теперь казались ему не только ничтожны, но забавны. Что ему было за дело до того, что эта женщина вела там где то ту жизнь, которая ей нравилась? Кому, в особенности ему, какое дело было до того, что узнают или не узнают, что имя их пленного было граф Безухов?
Теперь он часто вспоминал свой разговор с князем Андреем и вполне соглашался с ним, только несколько иначе понимая мысль князя Андрея. Князь Андрей думал и говорил, что счастье бывает только отрицательное, но он говорил это с оттенком горечи и иронии. Как будто, говоря это, он высказывал другую мысль – о том, что все вложенные в нас стремленья к счастью положительному вложены только для того, чтобы, не удовлетворяя, мучить нас. Но Пьер без всякой задней мысли признавал справедливость этого. Отсутствие страданий, удовлетворение потребностей и вследствие того свобода выбора занятий, то есть образа жизни, представлялись теперь Пьеру несомненным и высшим счастьем человека. Здесь, теперь только, в первый раз Пьер вполне оценил наслажденье еды, когда хотелось есть, питья, когда хотелось пить, сна, когда хотелось спать, тепла, когда было холодно, разговора с человеком, когда хотелось говорить и послушать человеческий голос. Удовлетворение потребностей – хорошая пища, чистота, свобода – теперь, когда он был лишен всего этого, казались Пьеру совершенным счастием, а выбор занятия, то есть жизнь, теперь, когда выбор этот был так ограничен, казались ему таким легким делом, что он забывал то, что избыток удобств жизни уничтожает все счастие удовлетворения потребностей, а большая свобода выбора занятий, та свобода, которую ему в его жизни давали образование, богатство, положение в свете, что эта то свобода и делает выбор занятий неразрешимо трудным и уничтожает самую потребность и возможность занятия.