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

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

Определение

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

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

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

Где 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:

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

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

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

Отображение Карно дизъюнктивной нормальной формы (¬ 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», что и на предыдущей карте.

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

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

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

... смысловыми средствами

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

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

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

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

Примечание

Пропозициональная формула может быть представлена ​​одной и только одной полной ДНФ. Напротив, несколько простых могут быть возможны ДНФ. Например, применяя правило $((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)$. Однако существуют и эквивалентные формулы ДНФ, которые не могут быть преобразованы одна в другую по этому правилу, пример см. на рисунках.

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

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

Теорема о дизъюнктивной нормальной форме: предположим, что $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}$.

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

Предполагать $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 ]$, что, согласно приведенным выше рассуждениям, функционально эквивалентно истинности $X$. Эта конструкция, очевидно, предполагает, что $X$ принимает значение $T$ хотя бы в одной строке таблицы истинности; если $X$ нет, то есть, если $X$ противоречие то , $X$ эквивалентно $A\land \neg A$, что, конечно, также является предложением в ${\mathcal {L}}[A,B,C,\ldots ;\land ,\lor ,\neg ]$.

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

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

Любая формула высказывания строится из $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)$ непустые подмножества.

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

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

Пример 1

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

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

${\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 литералов.

См. также

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

Ссылки

• Арора, Санджив; Барак, Вооз (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 .