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

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

Определение [ править ]

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

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

ДНФ → ( Союз ) $\vee$ ДНФ
ДНФ → ( Союз )
Союз → Буквальный $\wedge$ Соединение
Союз → Буквальный
Буквальный → $\neg$ Переменная
Литерал → Переменная

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

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

$(A\land \neg B\land \neg C)\lor (\neg D\land E\land F\land D\land F)$
$(A\land B)\lor (C)$
$(A\land B)$
$(A)$

Формула $A\lor B$ находится в DNF, но не в полном DNF; эквивалентная версия с полным DNF: $(A\land B)\lor (A\land \lnot B)\lor (\lnot A\land B)$ .

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

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

Преобразование в DNF [ править ]

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

... синтаксическими средствами [ править ]

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

{\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] Например, рассмотрим формулу

\phi =((\lnot (p\land q))\leftrightarrow (\lnot r\uparrow (p\oplus q)))

. ^[10]

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

$p$	$q$	$r$	$\lnot$	$(p\land q)$	$\leftrightarrow$	$\lnot r$	$\uparrow$	$(p\oplus q)$
Т	Т	Т	Ф	Т	Ф	Ф	Т	Ф
Т	Т	Ф	Ф	Т	Ф	Т	Т	Ф
Т	Ф	Т	Т	Ф	Т	Ф	Т	Т
Т	Ф	Ф	Т	Ф	Ф	Т	Ф	Т
Ф	Т	Т	Т	Ф	Т	Ф	Т	Т
Ф	Т	Ф	Т	Ф	Ф	Т	Ф	Т
Ф	Ф	Т	Т	Ф	Т	Ф	Т	Ф
Ф	Ф	Ф	Т	Ф	Т	Т	Т	Ф

Полный DNF-эквивалент $\phi$ является

(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-эквивалент $\lnot \phi$ является

(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)

Примечание [ править ]

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

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

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

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

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

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

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

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

Любая формула высказывания строится из $n$ переменные, где $n\geq 1$ .

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

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

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

Полный DNF может иметь до $2^{n}$ союзы, по одному на каждую строку таблицы истинности.

Пример 1

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

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

{\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

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

Вычислительная сложность [ править ]

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

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

Варианты [ править ]

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

См. также [ править ]

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

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

^ Сообщение 1921 года .
^ Дэйви и Пристли 1990 , с. 153.
^ Грис и Шнайдер 1993 , с. 67.
^ Уайтситт 2012 , стр. 33–37.
^ Однако они находятся в отрицательной нормальной форме .
^ Дэйви и Пристли 1990 , с. 152-153.
^ Формулы с другими связками можно сначала привести к нормальной форме отрицания .
^ Дершовиц и Жуанно 1990 , с. 270, п.5.1.
^ Sobolev 2020 .
^ $\phi$ = (( NOT (p AND q)) IFF (( NOT r) NAND (p XOR q)))
^ лайк $(a\land b)\lor (b\land a)\lor (a\land b\land b)$
^ Перейти обратно: ^а ^б ^с Предполагается, что повторы и вариации ^[11] основе коммутативности и ассоциативности на $\lor$ и $\land$ не происходят.
^ Перейти обратно: ^а ^б Хальбайзен, Лоренц; Краф, Регула (2020). Теоремы Гёделя и аксиомы Цермело: прочный фундамент математики . Чам: Биркхойзер. п. 27. ISBN 978-3-030-52279-7 .
^ Перейти обратно: ^а ^б ^с ^д ^Это Хаусон, Колин (1997). Логика с деревьями: введение в символическую логику . Лондон; Нью-Йорк: Рутледж. п. 41. ИСБН 978-0-415-13342-5 .
^ Перейти обратно: ^а ^б Цензер, Дуглас; Ларсон, Джин; Портер, Кристофер; Заплетал, Йиндржих (2020). Теория множеств и основы математики: введение в математическую логику . Нью-Джерси: World Scientific. стр. 19–21. ISBN 978-981-12-0192-9 .
^ Перейти обратно: ^а ^б Халворсон, Ганс (2020). Как работает логика: руководство пользователя . Принстон Оксфорд: Издательство Принстонского университета. п. 195. ИСБН 978-0-691-18222-3 .
^ То есть язык с пропозициональными переменными $A,B,C,\ldots$ и связи $\{\land ,\lor ,\neg \}$ .
^ $\left|{\mathcal {P}}(L)\right|=2^{2n}$
^ Арора и Барак 2009 .

Ссылки [ править ]

Арора, Санджив; Барак, Вооз (20 апреля 2009 г.). Вычислительная сложность: современный подход . Издательство Кембриджского университета . п. 579. дои : 10.1017/CBO9780511804090 . ISBN 9780521424264 .
Дэйви, бакалавр; Пристли, ХА (1990). Введение в решетки и порядок . Кембриджские математические учебники. Издательство Кембриджского университета.
Дершовиц, Нахум ; Жуанно, Жан-Пьер (1990). «Переписать системы». В Ван Лювене, Ян (ред.). Формальные модели и семантика . Справочник по теоретической информатике. Том. Б. Эльзевир . стр. 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 .
Хаусон, Колин (11 октября 2005 г.) [1997]. Логика с деревьями: введение в символическую логику . Рутледж. ISBN 978-1-134-78550-6 .
Пост, Эмиль (июль 1921 г.). «Введение в общую теорию элементарных предложений». Американский журнал математики . 43 (3): 163–185. дои : 10.2307/2370324 . JSTOR 2370324 .
Соболев С.К. (2020) [1994], «Дизъюнктивная нормальная форма» , Энциклопедия Математики , EMS Press
Уайтситт, Дж. Элдон (24 мая 2012 г.) [1961]. Булева алгебра и ее приложения . Курьерская корпорация. ISBN 978-0-486-15816-7 .

[FOOTNOTEPost1921-1] Сообщение 1921 года .

[FOOTNOTEDaveyPriestley1990153-2] Дэйви и Пристли 1990 , с. 153.

[FOOTNOTEGriesSchneider199367-3] Грис и Шнайдер 1993 , с. 67.

[FOOTNOTEWhitesitt201233–37-4] Уайтситт 2012 , стр. 33–37.

[5] Однако они находятся в отрицательной нормальной форме .

[FOOTNOTEDaveyPriestley1990152-153-6] Дэйви и Пристли 1990 , с. 152-153.

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

[FOOTNOTEDershowitzJouannaud1990270Sect.5.1-8] Дершовиц и Жуанно 1990 , с. 270, п.5.1.

[FOOTNOTESobolev2020-9] Sobolev 2020 .

[10] $\phi$ = (( NOT (p AND q)) IFF (( NOT r) NAND (p XOR q)))

[11] лайк $(a\land b)\lor (b\land a)\lor (a\land b\land b)$

[noreps-12] Перейти обратно: ^а ^б ^с Предполагается, что повторы и вариации ^[11] основе коммутативности и ассоциативности на $\lor$ и $\land$ не происходят.

[:0-13] Перейти обратно: ^а ^б Хальбайзен, Лоренц; Краф, Регула (2020). Теоремы Гёделя и аксиомы Цермело: прочный фундамент математики . Чам: Биркхойзер. п. 27. ISBN 978-3-030-52279-7 .

[:13-14] Перейти обратно: ^а ^б ^с ^д ^Это Хаусон, Колин (1997). Логика с деревьями: введение в символическую логику . Лондон; Нью-Йорк: Рутледж. п. 41. ИСБН 978-0-415-13342-5 .

[:1-15] Перейти обратно: ^а ^б Цензер, Дуглас; Ларсон, Джин; Портер, Кристофер; Заплетал, Йиндржих (2020). Теория множеств и основы математики: введение в математическую логику . Нью-Джерси: World Scientific. стр. 19–21. ISBN 978-981-12-0192-9 .

[:2-16] Перейти обратно: ^а ^б Халворсон, Ганс (2020). Как работает логика: руководство пользователя . Принстон Оксфорд: Издательство Принстонского университета. п. 195. ИСБН 978-0-691-18222-3 .

[17] То есть язык с пропозициональными переменными $A,B,C,\ldots$ и связи $\{\land ,\lor ,\neg \}$ .

[18] $\left|{\mathcal {P}}(L)\right|=2^{2n}$

[FOOTNOTEAroraBarak2009-19] Арора и Барак 2009 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[11]

v т Это Нормальные формы в логике
Логика высказываний	Нормальная форма отрицания Конъюнктивная нормальная форма Дизъюнктивная нормальная форма Алгебраическая нормальная форма ( полином Жегалкина ) Каноническая форма Блейка Каноническая нормальная форма Оговорка о роге
Логика предикатов	Шолем нормальная форма Гербрандизация Пренекс нормальная форма
Другой	Бета-нормальная форма Модальная клаузальная форма Нормальная форма (естественная дедукция)