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

Стандартная форма булевой функции

В булевой логике формула находится в конъюнктивной нормальной форме ( CNF ) или клаузальной нормальной форме , если она представляет собой соединение одного или нескольких предложений , где предложение является дизъюнкцией литералов ; иначе говоря, это произведение сумм или И из ИЛИ . Как каноническая нормальная форма , она полезна в автоматизированном доказательстве теорем и теории цепей .

В автоматизированном доказательстве теорем понятие « клаузальная нормальная форма » часто используется в более узком смысле, означая конкретное представление формулы КНФ в виде набора наборов литералов.

Определение

Логическая формула считается находящейся в КНФ, если она представляет собой конъюнкцию одной или нескольких дизъюнкций одного или нескольких литералов . Как и в дизъюнктивной нормальной форме (ДНФ), единственными пропозициональными операторами в КНФ являются or ( ), и ( ), а не ( ). Оператор not может использоваться только как часть литерала, то есть он может предшествовать только пропозициональной переменной . ${\displaystyle \vee }$ ${\displaystyle \wedge }$ ${\displaystyle \neg }$

Ниже приведена контекстно-свободная грамматика для CNF:

1. КНФ → ( Дизъюнкция ) КНФ ${\displaystyle \land }$
2. CNF → ( Дизъюнкция )
3. Дизъюнкция → Буквальная дизъюнкция ${\displaystyle \lor }$
4. Дизъюнкция → Буквальный
5. Литерал → Переменная ${\displaystyle \neg }$
6. Литерал → Переменная

Где Variable — любая переменная.

Все следующие формулы в переменных , и находятся в конъюнктивной нормальной форме: ${\displaystyle A,B,C,D,E}$ ${\displaystyle F}$

• ${\displaystyle (A\lor \neg B\lor \neg C)\land (\neg D\lor E\lor F\lor D\lor F)}$
• ${\displaystyle (A\lor B)\land (C)}$
• ${\displaystyle (A\lor B)}$
• ${\displaystyle (A)}$

Следующие формулы не находятся в конъюнктивной нормальной форме: ^[1]

• ${\displaystyle \neg (A\land B)}$, поскольку оператор AND вложен в оператор NOT
• ${\displaystyle \neg (A\lor B)\land C}$, поскольку оператор OR вложен в оператор NOT
• ${\displaystyle A\land (B\lor (D\land E))}$, поскольку оператор AND вложен в оператор OR

Преобразование в CNF

В классической логике каждую пропозициональную формулу можно преобразовать в эквивалентную формулу в КНФ. ^[2] Это преобразование основано на правилах логической эквивалентности : исключении двойного отрицания , законах Де Моргана и распределительном законе .

Основной алгоритм

Алгоритм вычисления CNF-эквивалента данной пропозициональной формулы основан на дизъюнктивной нормальной форме (DNF) : шаг 1. ^[3] Затем преобразуется в путем замены И на ИЛИ и наоборот, при этом отрицая все литералы. Убрать все . ^[2] ${\displaystyle \phi }$ ${\displaystyle \lnot \phi }$
${\displaystyle \lnot \phi _{DNF}}$ ${\displaystyle \phi _{CNF}}$ ${\displaystyle \lnot \lnot }$

Преобразование синтаксическими средствами

Преобразуйте формулу высказывания в КНФ . ${\displaystyle \phi }$

Шаг 1 : Преобразуйте его отрицание в дизъюнктивную нормальную форму. ^[3]

${\displaystyle \lnot \phi _{DNF}=(C_{1}\lor C_{2}\lor \ldots \lor C_{i}\lor \ldots \lor C_{m})}$, ^[4]

где каждый представляет собой соединение литералов . ^[5] ${\displaystyle C_{i}}$ ${\displaystyle l_{i1}\land l_{i2}\land \ldots \land l_{in_{i}}}$

Шаг 2 : Отрицание . Затем перейдите внутрь, применяя (обобщенные) эквиваленты Де Моргана до тех пор, пока это станет невозможно. ${\displaystyle \lnot \phi _{DNF}}$ ${\displaystyle \lnot }$

${\displaystyle {\begin{aligned}\phi &\leftrightarrow \lnot \lnot \phi _{DNF}\\&=\lnot (C_{1}\lor C_{2}\lor \ldots \lor C_{i}\lor \ldots \lor C_{m})\\&\leftrightarrow \lnot C_{1}\land \lnot C_{2}\land \ldots \land \lnot C_{i}\land \ldots \land \lnot C_{m}&&{\text{// (generalized) D.M.}}\end{aligned}}}$

где
${\displaystyle {\begin{aligned}\lnot C_{i}&=\lnot (l_{i1}\land l_{i2}\land \ldots \land l_{in_{i}})\\&\leftrightarrow (\lnot l_{i1}\lor \lnot l_{i2}\lor \ldots \lor \lnot l_{in_{i}})&&{\text{// (generalized) D.M.}}\end{aligned}}}$

Шаг 3 : Удалите все двойные отрицания.

Пример

Преобразуйте формулу высказывания в КНФ . ^[6] ${\displaystyle \phi =((\lnot (p\land q))\leftrightarrow (\lnot r\uparrow (p\oplus q)))}$

(Полный) ДНФ-эквивалент его отрицания равен ^[3]
${\displaystyle \lnot \phi _{DNF}=(p\land q\land r)\lor (p\land q\land \lnot r)\lor (p\land \lnot q\land \lnot r)\lor (\lnot p\land q\land \lnot r)}$

${\displaystyle {\begin{aligned}\phi &\leftrightarrow \lnot \lnot \phi _{DNF}\\&=\lnot \{(p\land q\land r)\lor (p\land q\land \lnot r)\lor (p\land \lnot q\land \lnot r)\lor (\lnot p\land q\land \lnot r)\}\\&\leftrightarrow {\underline {\lnot (p\land q\land r)}}\land {\underline {\lnot (p\land q\land \lnot r)}}\land {\underline {\lnot (p\land \lnot q\land \lnot r)}}\land {\underline {\lnot (\lnot p\land q\land \lnot r)}}&&{\text{// generalized D.M. }}\\&\leftrightarrow (\lnot p\lor \lnot q\lor \lnot r)\land (\lnot p\lor \lnot q\lor \lnot \lnot r)\land (\lnot p\lor \lnot \lnot q\lor \lnot \lnot r)\land (\lnot \lnot p\lor \lnot q\lor \lnot \lnot r)&&{\text{// generalized D.M. }}(4\times )\\&\leftrightarrow (\lnot p\lor \lnot q\lor \lnot r)\land (\lnot p\lor \lnot q\lor r)\land (\lnot p\lor q\lor r)\land (p\lor \lnot q\lor r)&&{\text{// remove all }}\lnot \lnot \\&=\phi _{CNF}\end{aligned}}}$

Преобразование семантическими средствами

Эквивалент формулы в CNF может быть получен из ее таблицы истинности . Еще раз рассмотрим формулу

${\displaystyle \phi =((\lnot (p\land q))\leftrightarrow (\lnot r\uparrow (p\oplus q)))}$. ^[6]

Соответствующая таблица истинности

Эквивалент CNF ${\displaystyle \phi }$

${\displaystyle (\lnot p\lor \lnot q\lor \lnot r)\land (\lnot p\lor \lnot q\lor r)\land (\lnot p\lor q\lor r)\land (p\lor \lnot q\lor r)}$

Каждая дизъюнкция отражает присвоение переменных, значение которых равно F(alse). Если в таком присваивании переменная ${\displaystyle \phi }$
${\displaystyle V}$

• равно T(rue), то в дизъюнкции устанавливается литерал , ${\displaystyle \lnot V}$
• является F(alse), то литерал устанавливается в дизъюнкцию. ${\displaystyle V}$

Другие подходы

Поскольку все пропозициональные формулы можно преобразовать в эквивалентную формулу в конъюнктивной нормальной форме, доказательства часто основаны на предположении, что все формулы являются КНФ. Однако в некоторых случаях это преобразование в CNF может привести к экспоненциальному взрыву формулы. Например, перевод формулы, отличной от CNF

${\displaystyle (X_{1}\wedge Y_{1})\vee (X_{2}\wedge Y_{2})\vee \ldots \vee (X_{n}\wedge Y_{n})}$

в CNF создает формулу с предложениями: ${\displaystyle 2^{n}}$

${\displaystyle (X_{1}\vee X_{2}\vee \ldots \vee X_{n})\wedge (Y_{1}\vee X_{2}\vee \ldots \vee X_{n})\wedge (X_{1}\vee Y_{2}\vee \ldots \vee X_{n})\wedge (Y_{1}\vee Y_{2}\vee \ldots \vee X_{n})\wedge \ldots \wedge (Y_{1}\vee Y_{2}\vee \ldots \vee Y_{n}).}$

Каждое предложение содержит либо или для каждого . ${\displaystyle X_{i}}$ ${\displaystyle Y_{i}}$ ${\displaystyle i}$

Существуют преобразования в КНФ, которые избегают экспоненциального увеличения размера, сохраняя выполнимость , а не эквивалентность . ^{[7] [8]} Эти преобразования гарантированно только линейно увеличивают размер формулы, но вводят новые переменные. Например, приведенную выше формулу можно преобразовать в CNF, добавив переменные следующим образом: ${\displaystyle Z_{1},\ldots ,Z_{n}}$

${\displaystyle (Z_{1}\vee \ldots \vee Z_{n})\wedge (\neg Z_{1}\vee X_{1})\wedge (\neg Z_{1}\vee Y_{1})\wedge \ldots \wedge (\neg Z_{n}\vee X_{n})\wedge (\neg Z_{n}\vee Y_{n}).}$

Интерпретация удовлетворяет этой формуле только в том случае , если хотя бы одна из новых переменных верна. Если эта переменная равна , то оба значения и также верны. Это означает, что каждая модель , удовлетворяющая этой формуле, также удовлетворяет исходной. С другой стороны, только некоторые модели исходной формулы удовлетворяют этому требованию: поскольку они не упоминаются в исходной формуле, их значения не имеют отношения к ее удовлетворению, чего не происходит в последней формуле. Это означает, что исходная формула и результат перевода равновыполнимы, но не эквивалентны . ${\displaystyle Z_{i}}$ ${\displaystyle X_{i}}$ ${\displaystyle Y_{i}}$ ${\displaystyle Z_{i}}$

Альтернативный перевод — преобразование Цейтина — включает также придаточные . С этими пунктами формула подразумевает ; эта формула часто считается «определяющей» как имя для . ${\displaystyle Z_{i}\vee \neg X_{i}\vee \neg Y_{i}}$ ${\displaystyle Z_{i}\equiv X_{i}\wedge Y_{i}}$ ${\displaystyle Z_{i}}$ ${\displaystyle X_{i}\wedge Y_{i}}$

Максимальное количество дизъюнкций

Рассмотрим пропозициональную формулу с переменными . ${\displaystyle n}$ ${\displaystyle n\geq 1}$

Возможны литералы: . ${\displaystyle 2n}$ ${\displaystyle L=\{p_{1},\lnot p_{1},p_{2},\lnot p_{2},\ldots ,p_{n},\lnot p_{n}\}}$

${\displaystyle L}$имеет непустые подмножества. ^[9] ${\displaystyle (2^{2n}-1)}$

Это максимальное количество дизъюнкций, которое может иметь КНФ. ^[11]

Все комбинации истинностных функций могут быть выражены с помощью дизъюнкций, по одной на каждую строку таблицы истинности. В примере ниже они подчеркнуты. ${\displaystyle 2^{n}}$

Пример

Рассмотрим формулу с двумя переменными и . ${\displaystyle p}$ ${\displaystyle q}$

Самая длинная КНФ имеет дизъюнкции: ^[11] ${\displaystyle 2^{(2\times 2)}-1=15}$

${\displaystyle {\begin{array}{lcl}(\lnot p)\land (p)\land (\lnot q)\land (q)\land \\(\lnot p\lor p)\land {\underline {(\lnot p\lor \lnot q)}}\land {\underline {(\lnot p\lor q)}}\land {\underline {(p\lor \lnot q)}}\land {\underline {(p\lor q)}}\land (\lnot q\lor q)\land \\(\lnot p\lor p\lor \lnot q)\land (\lnot p\lor p\lor q)\land (\lnot p\lor \lnot q\lor q)\land (p\lor \lnot q\lor q)\land \\(\lnot p\lor p\lor \lnot q\lor q)\end{array}}}$

Эта формула противоречит .

Вычислительная сложность

Важный набор проблем вычислительной сложности включает в себя поиск таких присвоений переменным булевой формулы, выраженных в конъюнктивной нормальной форме, чтобы формула была истинной. Проблема k -SAT — это проблема поиска удовлетворяющего назначения булевой формуле, выраженной в КНФ, в которой каждая дизъюнкция содержит не более k переменных. 3-SAT является NP-полной (как и любая другая задача k -SAT с k > 2), тогда как известно, что 2-SAT имеет решения за полиномиальное время . Как следствие ^[12] задача преобразования формулы в ДНФ с сохранением выполнимости является NP-трудной ; двойственно , преобразование в CNF с сохранением достоверности также является NP-трудным; следовательно, преобразование с сохранением эквивалентности в DNF или CNF снова является NP-трудным.

Типичные проблемы в этом случае связаны с формулами в «3CNF»: конъюнктивной нормальной форме с не более чем тремя переменными на конъюнкт. Примеры таких формул, встречающиеся на практике, могут быть очень большими, например, со 100 000 переменных и 1 000 000 конъюнктов.

Формула в CNF может быть преобразована в равновыполнимую формулу в « k CNF» (для k ≥3) путем замены каждого конъюнкта с более чем k переменными двумя конъюнктами и с Z новой переменной и повторения так часто, как это необходимо. ${\displaystyle X_{1}\vee \ldots \vee X_{k}\vee \ldots \vee X_{n}}$ ${\displaystyle X_{1}\vee \ldots \vee X_{k-1}\vee Z}$ ${\displaystyle \neg Z\vee X_{k}\lor \ldots \vee X_{n}}$

Логика первого порядка

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

См. пример ниже.

Преобразование из логики первого порядка

Чтобы преобразовать логику первого порядка в CNF: ^[14]

1. Привести отрицание к нормальной форме .
   1. Устраните последствия и эквивалентности: повторно замените на ; заменить . _ В конечном итоге это устранит все появления и . ${\displaystyle P\rightarrow Q}$ ${\displaystyle \lnot P\lor Q}$ ${\displaystyle P\leftrightarrow Q}$ ${\displaystyle (P\lor \lnot Q)\land (\lnot P\lor Q)}$ ${\displaystyle \rightarrow }$ ${\displaystyle \leftrightarrow }$
   2. Переместите НОТ внутрь, неоднократно применяя закон Де Моргана . В частности, замените на ; заменить ; _ и замените на ; заменить ; _ с . После этого a может встречаться только непосредственно перед символом-предикатом. ${\displaystyle \lnot (P\lor Q)}$ ${\displaystyle (\lnot P)\land (\lnot Q)}$ ${\displaystyle \lnot (P\land Q)}$ ${\displaystyle (\lnot P)\lor (\lnot Q)}$ ${\displaystyle \lnot \lnot P}$ ${\displaystyle P}$ ${\displaystyle \lnot (\forall xP(x))}$ ${\displaystyle \exists x\lnot P(x)}$ ${\displaystyle \lnot (\exists xP(x))}$ ${\displaystyle \forall x\lnot P(x)}$ ${\displaystyle \lnot }$
2. Стандартизируйте переменные
   1. Для предложений, подобных которым дважды используется одно и то же имя переменной, измените имя одной из переменных. Это позволит избежать путаницы при удалении кванторов. Например, переименован в . ${\displaystyle (\forall xP(x))\lor (\exists xQ(x))}$ ${\displaystyle \forall x[\exists y\mathrm {Animal} (y)\land \lnot \mathrm {Loves} (x,y)]\lor [\exists y\mathrm {Loves} (y,x)]}$ ${\displaystyle \forall x[\exists y\mathrm {Animal} (y)\land \lnot \mathrm {Loves} (x,y)]\lor [\exists z\mathrm {Loves} (z,x)]}$
3. Сколемизировать высказывание
   1. Переместить квантификаторы наружу: несколько раз заменить на ; заменить ; _ заменить ; _ заменить . _ Эти замены сохраняют эквивалентность, поскольку предыдущий шаг стандартизации переменных гарантировал, что это не произойдет в . После этих замен квантификатор может встречаться только в начальном префиксе формулы, но никогда внутри , или . ${\displaystyle P\land (\forall xQ(x))}$ ${\displaystyle \forall x(P\land Q(x))}$ ${\displaystyle P\lor (\forall xQ(x))}$ ${\displaystyle \forall x(P\lor Q(x))}$ ${\displaystyle P\land (\exists xQ(x))}$ ${\displaystyle \exists x(P\land Q(x))}$ ${\displaystyle P\lor (\exists xQ(x))}$ ${\displaystyle \exists x(P\lor Q(x))}$ ${\displaystyle x}$ ${\displaystyle P}$ ${\displaystyle \lnot }$ ${\displaystyle \land }$ ${\displaystyle \lor }$
   2. Повторно замените на , где — новый символ -арной функции, так называемая « функция Скулема ». Это единственный шаг, который сохраняет только выполнимость, а не эквивалентность. Он устраняет все экзистенциальные кванторы. ${\displaystyle \forall x_{1}\ldots \forall x_{n}\;\exists y\;P(y)}$ ${\displaystyle \forall x_{1}\ldots \forall x_{n}\;P(f(x_{1},\ldots ,x_{n}))}$ ${\displaystyle f}$ ${\displaystyle n}$
4. Отбросьте все кванторы универсальности.
5. Распределите OR внутри AND: многократно замените на . ${\displaystyle P\lor (Q\land R)}$ ${\displaystyle (P\lor Q)\land (P\lor R)}$

Пример

Например, формула «Любой, кто любит всех животных, в свою очередь любим кем-то» преобразуется в CNF (а затем в форму предложения в последней строке) следующим образом (выделение редексов правил замены в ): ${\displaystyle {\color {red}{\text{red}}}}$

Неформально функцию Скулема можно рассматривать как выдающую человека, которого любят, и одновременно выдающую животное (если оно есть), которое не любит. Третья последняя строка снизу читается как « не любит животное , или его любят » . ${\displaystyle g(x)}$ ${\displaystyle x}$ ${\displaystyle f(x)}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle f(x)}$ ${\displaystyle x}$ ${\displaystyle g(x)}$

Вторая последняя строка сверху — это CNF. ${\displaystyle (\mathrm {Animal} (f(x))\lor \mathrm {Loves} (g(x),x))\land (\lnot \mathrm {Loves} (x,f(x))\lor \mathrm {Loves} (g(x),x))}$

Смотрите также

• Алгебраическая нормальная форма
• Дизъюнктивная нормальная форма
• Предложение Хорна . Предложение Хорна представляет собой дизъюнктивное предложение ( дизъюнкция литералов ) не более чем с одним положительным, то есть неотрицательным , литералом.
• Алгоритм Куайна – Маккласки

Примечания

1. Однако они находятся в отрицательной нормальной форме .
2. Хаусон 2005, стр. 46.
3. см. Дизъюнктивную нормальную форму # Преобразование в DNF
4. максимальное количество союзов для ${\displaystyle 1\leq m\leq }$ ${\displaystyle \phi }$
5. максимальное количество литералов для ${\displaystyle 1\leq in_{i}\leq }$ ${\displaystyle \phi }$
6. = (( NOT (p AND q)) IFF (( NOT r) NAND (p XOR q))) ${\displaystyle \phi }$
7. Цейтин 1968.
8. Джексон и Шеридан 2004.
9. ${\displaystyle \left|{\mathcal {P}}(L)\right|=2^{2n}}$
10. лайк ${\displaystyle (a\land b)\lor (b\land a)\lor (a\land b\land b)}$
11. Предполагается, что повторы и вариации ^[10] на основе коммутативности и ассоциативности и не встречаются. ${\displaystyle \lor }$ ${\displaystyle \land }$
12. так как одним из способов проверки КНФ на выполнимость является преобразование ее в ДНФ , выполнимость которой можно проверить за линейное время
13. максимальное количество дизъюнкций максимальное количество литералов ${\displaystyle 1\leq m\leq }$
    ${\displaystyle 1\leq in_{i}\leq }$
14. Рассел и Норвиг 2010, стр. 345–347, 9.5.1 Конъюнктивная нормальная форма для логики первого порядка.

Рекомендации

• Эндрюс, Питер Б. (2013). Введение в математическую логику и теорию типов: к истине через доказательство . ISBN 9401599343.

• Хаусон, Колин (11 октября 2005 г.) [1997]. Логика с деревьями: введение в символическую логику. Рутледж. ISBN 978-1-134-78550-6.

• Джексон, Пол; Шеридан, Дэниел (10 мая 2004 г.). «Преобразование форм предложений для логических схем» (PDF) . В Хоосе, Хольгер Х.; Митчелл, Дэвид Г. (ред.). Теория и приложения проверки выполнимости . 7-я Международная конференция по теории и приложениям проверки выполнимости, SAT. Пересмотренные избранные статьи. Конспекты лекций по информатике. Том. 3542. Ванкувер, Британская Колумбия, Канада: Springer 2005. стр. 183–198. дои : 10.1007/11527695_15. ISBN 978-3-540-31580-3.

• Кляйне Бюнинг, Ганс; Леттманн, Теодор (28 августа 1999 г.). Пропозициональная логика: дедукция и алгоритмы. Издательство Кембриджского университета . ISBN 978-0-521-63017-7.

• Рассел, Стюарт ; Норвиг, Питер , ред. (2010) [1995]. Искусственный интеллект: современный подход (PDF) (3-е изд.). Река Аппер-Седл, Нью-Джерси: Прентис-Холл. ISBN 978-0-13-604259-4. Архивировано (PDF) из оригинала 31 августа 2017 года.

• Цейтин, Григорий С. (1968). «О сложности вывода в исчислении высказываний» (PDF) . В Слисенко А.О. (ред.). Структуры в конструктивной математике и математической логике, часть II, Семинары по математике (перевод с русского) . Математический институт им. Стеклова. стр. 115–125.

• Уайтситт, Дж. Элдон (24 мая 2012 г.) [1961]. Булева алгебра и ее приложения. Курьерская корпорация. ISBN 978-0-486-15816-7.

Внешние ссылки

• «Конъюнктивная нормальная форма», Математическая энциклопедия , EMS Press , 2001 [1994]

• «Java-инструмент для преобразования таблицы истинности в CNF и DNF». Университет Марбурга . Проверено 31 декабря 2023 г.