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

Эта статья поднимает множество проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалить эти сообщения-шаблоны ) Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален. Найти источники:  «Дизъюнктивная нормальная форма»  -  новости  · газеты  · книги  · ученый  · JSTOR ( ноябрь 2010 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон ) Эта статья включает в себя список литературы , связанной литературы или внешних ссылок , но ее источники остаются неясными, поскольку в ней отсутствуют встроенные цитаты . Пожалуйста, помогите улучшить эту статью, добавив более точные цитаты. ( Ноябрь 2010 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

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

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

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

1. дизъюнкция → ( конъюнкция дизъюнкция )${\ displaystyle \ vee}$
2. дизъюнкция → конъюнкция
3. соединение → ( буквальное соединение )${\ Displaystyle \ клин}$
4. союз → буквальный
5. литерал → переменная${\ displaystyle \ neg}$
6. литерал → переменная

Где переменная - это любая переменная.

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

• ${\ Displaystyle (А \ земля \ нег В \ земля \ нег С) \ лор (\ нег D \ земля Е \ земля F)}$
• ${\ Displaystyle (А \ земля В) \ лор С}$
• ${\ displaystyle A \ land B}$
• ${\ displaystyle A}$

Однако следующих формул нет в DNF:

• ${\ Displaystyle \ neg (А \ лор В)}$, поскольку ИЛИ вложено в НЕ
• ${\ Displaystyle \ neg (А \ земля В) \ лор С}$, поскольку И вложено в НЕ
• ${\ Displaystyle А \ лор (В \ земля (С \ лор D))}$, поскольку ИЛИ вложено в И

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

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

Преобразование формулы в DNF включает использование логических эквивалентностей , таких как исключение двойного отрицания , законы Де Моргана и закон распределения .

Все логические формулы можно преобразовать в эквивалентную дизъюнктивную нормальную форму. ^{[1] : 152–153} Однако в некоторых случаях преобразование в DNF может привести к экспоненциальному взрыву формулы. Например, ДНФ логической формулы следующего вида имеет 2 ⁿ членов:

${\displaystyle (X_{1}\lor Y_{1})\land (X_{2}\lor Y_{2})\land \dots \land (X_{n}\lor Y_{n})}$

Любая конкретная логическая функция может быть представлена ​​одной и только одной ^{[примечание 1]} полной дизъюнктивной нормальной формой, одной из канонических форм . Напротив, две разные простые дизъюнктивные нормальные формы могут обозначать одну и ту же булеву функцию, см. Рисунки.

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

Булева задача выполнимости на кнф формулах NP-трудная ; по принципу двойственности , то же самое и с проблемой опровержимости формул ДНФ. Следовательно, трудно решить, является ли формула ДНФ тавтологией .

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

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

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

• Алгебраическая нормальная форма - другие нормальные формы для логических формул
• Логика высказываний
• Алгоритм Куайна – Маккласки - получает минимальную DNF для заданной логической функции.
• Таблица истинности

Заметки [ править ]

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

• Дэвид Гильберт; Вильгельм Акерманн (1999). Принципы математической логики . American Mathematical Soc. ISBN 978-0-8218-2024-7.
• Дж. Элдон Уайтситт (24 мая 2012 г.). Булева алгебра и ее приложения . Курьерская корпорация. ISBN 978-0-486-15816-7.
• Колин Хоусон (11 октября 2005 г.). Логика с деревьями: введение в символическую логику . Рутледж. ISBN 978-1-134-78550-6.
• Дэвид Грис; Фред Б. Шнайдер (22 октября 1993 г.). Логический подход к дискретной математике . Springer Science & Business Media. С. 67–. ISBN 978-0-387-94115-8.

Внешние ссылки [ править ]

• "Дизъюнктивная нормальная форма" , Энциклопедия математики , EMS Press , 2001 [1994]