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


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

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

Содержание

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

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

\neg A \wedge (B \vee C)
(A \vee B) \wedge (\neg B \vee C \vee \neg D) \wedge (D \vee \neg E)
A \wedge B

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

\neg (B \vee C)
(A \wedge B) \vee C
A \wedge (B \vee (D \wedge E)).

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

\neg B \wedge \neg C
(A \vee C) \wedge (B \vee C)
A \wedge (B \vee D) \wedge (B \vee E).

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

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

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

A \rightarrow B = \neg A \vee B
A \leftrightarrow B = (A \wedge B) \vee (\neg A \wedge \neg B)

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

\neg (A \vee B) = \neg A \wedge \neg B
\neg (A \wedge B) = \neg A \vee \neg B

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

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

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

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

 F = ( X \rightarrow Y ) \wedge (( \neg Y \rightarrow Z ) \rightarrow \neg X )

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

 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 = ( \neg X \vee Y) \wedge ((\neg Y \wedge \neg Z) \vee \neg X) = (\neg X \vee Y) \wedge ((\neg Y \wedge \neg Z) \vee \neg X)

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

F = (\neg X \vee Y) \wedge (\neg X \vee \neg Y) \wedge (\neg X \vee \neg Z)

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

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

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

(A \or B) \and (\neg B \or C) \and (B \or \neg C)

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

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

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

См. также

Примечания

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

Литература

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

Ссылки


Wikimedia Foundation. 2010.

Смотреть что такое "Конъюнктивная нормальная форма" в других словарях:

  • конъюнктивная нормальная форма — — [http://www.iks media.ru/glossary/index.html?glossid=2400324] Тематики электросвязь, основные понятия EN conjunctive normal formCNF …   Справочник технического переводчика

  • КОНЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА — пропозициональная формула, имеющая вид (*) где каждое С ij, i=1, . . ., п;j=1, . . ., mi, есть либо переменная, либо отрицание переменной. К. н. ф. (*) является тавтологией тогда и только тогда, когда для любого iсреди С i1, . . ., Cimi.… …   Математическая энциклопедия

  • конъюнктивная нормальная форма (КНФ) — — [http://www.iks media.ru/glossary/index.html?glossid=2400324] Тематики электросвязь, основные понятия EN standard product of sums …   Справочник технического переводчика

  • K-конъюнктивная нормальная форма — (k КНФ) в булевой логике нормальная форма, в которой булева формула имеет вид конъюнкции нескольких дизъюнктов, каждый из которых содержит ровно k литералов. Например, следующая формула записана в 2 КНФ …   Википедия

  • Нормальная форма (математика) — У этого термина существуют и другие значения, см. Нормальная форма (значения). Нормальная форма  в математике простейший либо канонический вид, к которому объект приводится эквивалентными преобразованиями[1]. Содержание 1 Жорданова… …   Википедия

  • Нормальная форма (значения) — Нормальная форма: Нормальная форма в базах данных  свойство отношения в реляционной модели данных. Нормальная форма в математике  в каком либо смысле простейший либо канонический вид, к которому объект приводится преобразованиями,… …   Википедия

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

  • СОВЕРШЕННАЯ НОРМАЛЬНАЯ ФОРМА — совершенная дизъюнктивная или совершенная конъюнктивная нормальная форма (см. Булевых функций нормальные формы) …   Математическая энциклопедия

  • Булева функция — В данной статье или разделе имеется список источников или внешних ссылок, но источники отдельных утверждений остаются неясными из за отсутствия сносок …   Википедия

  • Булевы выражения — В теории дискретных функциональных систем булевой функцией называют функцию типа , где булево множество, а n неотрицательное целое число, которое называют арностью или местностью функции. Элементы 1 (единица) и 0 (ноль) стандартно интерпретируют… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.