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

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

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

Определение

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

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

1. DNF → ( Союз ) DNF ${\displaystyle \vee }$
2. DNF → ( Союз )
3. Союз → Буквальный союз ${\displaystyle \wedge }$
4. Союз → Буквальный
5. Литерал → Переменная ${\displaystyle \neg }$
6. Литерал → Переменная

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

Например, все следующие формулы представлены в DNF:

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

Формула представлена ​​в DNF, но не в полной DNF; эквивалентная версия в полной DNF — . ${\displaystyle A\lor B}$ ${\displaystyle (A\land B)\lor (A\land \lnot B)\lor (\lnot A\land B)}$

Следующие формулы не входят в DNF: ^[5]

• ${\displaystyle \neg (A\lor B)}$, так как ИЛИ вложено в НЕ
• ${\displaystyle \neg (A\land B)\lor C}$, так как AND вложен в NOT
• ${\displaystyle A\lor (B\land (C\lor D))}$, так как ИЛИ вложено в И

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

В классической логике каждая пропозициональная формула может быть преобразована в ДНФ ^[6] ...

Карта Карно дизъюнктивной нормальной формы (¬ A ∧¬ B ∧¬ D ) ∨ (¬ A ∧ B ∧ C ) ∨ ( A ∧ B ∧ D ) ∨ ( A ∧¬ B ∧¬ C )

Карта Карно дизъюнктивной нормальной формы (¬ A ∧ C ∧¬ D ) ∨ ( B ∧ C ∧ D ) ∨ ( A ∧¬ C ∧ D ) ∨ (¬ B ∧¬ C ∧¬ D ) . Несмотря на различную группировку, те же поля содержат «1», что и в предыдущей карте.

... синтаксическими средствами

Преобразование включает использование логических эквивалентностей , таких как исключение двойного отрицания , законы Де Моргана и распределительный закон . Формулы, построенные из примитивных связок ^[7], могут быть преобразованы в DNF с помощью следующей канонической системы переписывания терминов : ^[8] ${\displaystyle \{\land ,\lor ,\lnot \}}$

${\displaystyle {\begin{array}{rcl}(\lnot \lnot x)&\rightsquigarrow &x\\(\lnot (x\lor y))&\rightsquigarrow &((\lnot x)\land (\lnot y))\\(\lnot (x\land y))&\rightsquigarrow &((\lnot x)\lor (\lnot y))\\(x\land (y\lor z))&\rightsquigarrow &((x\land y)\lor (x\land z))\\((x\lor y)\land z)&\rightsquigarrow &((x\land z)\lor (y\land z))\\\end{array}}}$

... семантическими средствами

Полную ДНФ формулы можно прочитать из ее таблицы истинности . ^[9] Например, рассмотрим формулу

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

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

• Полный эквивалент DNF : ${\displaystyle \phi }$

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

• Полный эквивалент DNF : ${\displaystyle \lnot \phi }$

${\displaystyle (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)}$

Замечание

Пропозициональная формула может быть представлена ​​одной и только одной полной DNF. ^[12] Напротив, возможны несколько простых DNF. Например, применяя правило три раза, полную DNF выше можно упростить до . Однако существуют также эквивалентные формулы DNF, которые не могут быть преобразованы одна в другую этим правилом, см. рисунки для примера. ${\displaystyle ((a\land b)\lor (\lnot a\land b))\rightsquigarrow b}$ ${\displaystyle \phi }$ ${\displaystyle (\lnot p\land \lnot q)\lor (\lnot p\land r)\lor (\lnot q\land r)}$

Теорема о дизъюнктивной нормальной форме

Это теорема о том, что все непротиворечивые формулы в пропозициональной логике могут быть преобразованы в дизъюнктивную нормальную форму. ^{[13] [14] [15] [16]} Это называется теоремой о дизъюнктивной нормальной форме . ^{[13] [14] [15] [16]} Формальное утверждение выглядит следующим образом:

Теорема о дизъюнктивной нормальной форме: Предположим, что есть предложение на пропозициональном языке с буквами предложений, которое мы обозначим через . Если не является противоречием, то оно истинностно-функционально эквивалентно дизъюнкции конъюнкций вида , где , и . ^[14] ${\displaystyle X}$ ${\displaystyle {\mathcal {L}}}$ ${\displaystyle n}$ ${\displaystyle A_{1},...,A_{n}}$ ${\displaystyle X}$ ${\displaystyle \pm A_{1}\land ...\land \pm A_{n}}$ ${\displaystyle +A_{i}=A_{i}}$ ${\displaystyle -A_{i}=\neg A_{i}}$

Доказательство следует из процедуры, приведенной выше для генерации DNF из таблиц истинности . Формально доказательство выглядит следующим образом:

Предположим, что есть предложение в пропозициональном языке, буквы предложения которого . Для каждой строки таблицы истинности ' выпишите соответствующую конъюнкцию , где определено как , если принимает значение в этой строке, и есть , если принимает значение в этой строке; аналогично для , , и т. д. ( алфавитный порядок в конъюнкциях совершенно произволен; вместо этого можно выбрать любой другой). Теперь сформируйте дизъюнкцию всех этих конъюнкций, которые соответствуют строкам таблицы истинности '. Эта дизъюнкция является предложением в , ^[17] которое по приведенным выше рассуждениям является истинностно-функционально эквивалентным . Эта конструкция, очевидно, предполагает, что принимает значение по крайней мере в одной строке своей таблицы истинности; если нет, т. е. если является противоречием , то эквивалентно , что, конечно, также является предложением в . ^[14] ${\displaystyle X}$ ${\displaystyle A,B,C,\ldots }$ ${\displaystyle X}$ ${\displaystyle \pm A\land \pm B\land \pm C\land \ldots }$ ${\displaystyle \pm A}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle T}$ ${\displaystyle \neg A}$ ${\displaystyle A}$ ${\displaystyle F}$ ${\displaystyle \pm B}$ ${\displaystyle \pm C}$ ${\displaystyle A,B,C,\ldots }$ ${\displaystyle T}$ ${\displaystyle X}$ ${\displaystyle {\mathcal {L}}[A,B,C,\ldots ;\land ,\lor ,\neg ]}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle T}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle A\land \neg A}$ ${\displaystyle {\mathcal {L}}[A,B,C,\ldots ;\land ,\lor ,\neg ]}$

Эта теорема является удобным способом вывести множество полезных металогических результатов в пропозициональной логике, таких как, тривиально , результат о том, что набор связок является функционально полным . ^[14] ${\displaystyle \{\land ,\lor ,\neg \}}$

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

Любая пропозициональная формула строится из переменных, где . ${\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}$имеет непустые подмножества. ^[18] ${\displaystyle (2^{2n}-1)}$

Это максимальное количество союзов, которое может иметь DNF. ^[12]

Полная ДНФ может иметь до конъюнкций, по одной на каждую строку таблицы истинности. ${\displaystyle 2^{n}}$

Пример 1

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

Самая длинная возможная ДНФ имеет союзы: ^[12] ${\displaystyle 2^{(2\times 2)}-1=15}$

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

Самая длинная возможная полная ДНФ имеет 4 союза: они подчеркнуты.

Эта формула является тавтологией .

Пример 2

Каждая ДНФ формулы eg имеет союзы. ${\displaystyle (X_{1}\lor Y_{1})\land (X_{2}\lor Y_{2})\land \dots \land (X_{n}\lor Y_{n})}$ ${\displaystyle 2^{n}}$

Сложность вычислений

Проблема выполнимости булевых формул в конъюнктивной нормальной форме является NP-полной . По принципу двойственности , таковой является и проблема фальсифицируемости в DNF-формулах. Следовательно, co-NP-трудно решить, является ли DNF-формула тавтологией .

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

Варианты

Важным вариантом, используемым при изучении вычислительной сложности, является k-DNF . Формула находится в k-DNF , если она находится в DNF и каждая конъюнкция содержит не более k литералов. ^[19]

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

• Алгебраическая нормальная форма – XOR предложений AND
• Каноническая форма Блейка – DNF, включающая все простые импликанты
  • Алгоритм Куайна–Маккласки – алгоритм вычисления простых импликант
• Двойственность конъюнкции/дизъюнкции
• Логика высказываний
• Таблица истинности

Примечания

1. Пост 1921 г.
2. Дэйви и Пристли 1990, стр. 153.
3. Грис и Шнайдер 1993, с. 67.
4. Уайтситт 2012, стр. 33–37.
5. Однако они находятся в отрицательной нормальной форме .
6. Дэйви и Пристли 1990, стр. 152-153.
7. Формулы с другими связками можно сначала привести к отрицательной нормальной форме .
8. Дершовиц и Жуанно 1990, с. 270, п.5.1.
9. Соболев 2020.
10. = (( НЕ (p И q)) ЕСЛИ (( НЕ r) НЕ-И (p XOR q))) ${\displaystyle \phi }$
11. нравится ${\displaystyle (a\land b)\lor (b\land a)\lor (a\land b\land b)}$
12. Предполагается, что повторения и вариации ^[11], основанные на коммутативности и ассоциативности и , не происходят. ${\displaystyle \lor }$ ${\displaystyle \land }$
13. Halbeisen, Lorenz; Kraph, Regula (2020). Теоремы Гёделя и аксиомы Цермело: прочный фундамент математики . Cham: Birkhäuser. стр. 27. ISBN 978-3-030-52279-7.
14. Хаусон, Колин (1997). Логика с деревьями: введение в символическую логику . Лондон; Нью-Йорк: Routledge. стр. 41. ISBN 978-0-415-13342-5.
15. Cenzer, Douglas; Larson, Jean; Porter, Christopher; Zapletal, Jindřich (2020). Теория множеств и основы математики: введение в математическую логику . Нью-Джерси: World Scientific. стр. 19–21. ISBN 978-981-12-0192-9.
16. Halvorson, Hans (2020). Как работает логика: руководство пользователя . Princeton Oxford: Princeton University Press. стр. 195. ISBN 978-0-691-18222-3.
17. То есть язык с пропозициональными переменными и связками . ${\displaystyle A,B,C,\ldots }$ ${\displaystyle \{\land ,\lor ,\neg \}}$
18. ${\displaystyle \left|{\mathcal {P}}(L)\right|=2^{2n}}$
19. Арора и Барак 2009.

Ссылки

• Arora, Sanjeev; Barak, Boaz (20 апреля 2009 г.). Computational Complexity: A Modern Approach . Cambridge University Press . стр. 579. doi :10.1017/CBO9780511804090. ISBN 9780521424264.
• Дэви, BA; Пристли, HA (1990). Введение в решетки и порядок . Cambridge Mathematical Textbooks. Cambridge University Press.
• Дершовиц, Нахум ; Жуанно, Жан-Пьер (1990). «Системы переписывания». В Van Leeuwen, Jan (ред.). Формальные модели и семантика . Справочник по теоретической информатике. Том B. Elsevier . С. 243–320. ISBN 0-444-88074-7.
• Грайс, Дэвид; Шнайдер, Фред Б. (22 октября 1993 г.). Логический подход к дискретной математике. Springer Science & Business Media. ISBN 978-0-387-94115-8.
• Гильберт, Дэвид ; Аккерман, Вильгельм (1999). Принципы математической логики. Американское математическое общество. ISBN 978-0-8218-2024-7.
• Howson, Colin (11 октября 2005 г.) [1997]. Логика с деревьями: введение в символическую логику. Routledge. ISBN 978-1-134-78550-6.
• Пост, Эмиль (июль 1921 г.). «Введение в общую теорию элементарных предложений». American Journal of Mathematics . 43 (3): 163–185. doi :10.2307/2370324. JSTOR  2370324.
• Соболев, СК (2020) [1994], "Дизъюнктивная нормальная форма", Энциклопедия математики , EMS Press
• Уайтситт, Дж. Элдон (24 мая 2012 г.) [1961]. Булева алгебра и ее приложения. Courier Corporation. ISBN 978-0-486-15816-7.