Формулы х и 
будем называть литералами, т.е. литерал – это или х, или .
Если в ДНФ каждое элементарное произведение содержит все элементарные высказывания, но только в виде единственного литерала, то ДНФ называется совершенной дизъюнктивной нормальной формой (СДНФ).
Например: 
=pqr 
r является ДНФ, но не является СДНФ, т.к. во второе элементарно произведение не входит ни р, ни 
.
Формула 
= pqr r – СДНФ.
Формула 
= pqr rq – не СДНФ, т.к. во втором элементарном произведении содержится два литерала.
Теорема. Любаяформула, отличная от 0, представима в виде СДНФ.
Доказательство:
Пусть Ф – формула, содержащая n литералов. Пусть ДНФ содержит элементарное произведение без литерала 
. 
= 
, 
- литералы. Введем дизъюнкцию 
, которая равна 1. Получим = ( )=(по первому закону дистрибутивности)= 
.
Теперь каждое из элементарных произведений содержит все литералы. Поступая аналогично с другими элементарными произведениями, и, заменяя р нулем, получим СДНФ.
Что и требовалось доказать.
Пример 1.
Пусть = pqr q – ДНФ.
Приведем к СДНФ. Добавим 1 в виде дизъюнкции r 
. Получим =pqr q (r ) 
pqr qr q - СДНФ.
Если каждая элементарная сумма КНФ формулы содержит все литералы по одному разу, то такая форма называется совершенной конъюнктивной нормальной формой (СКНФ).
Теорема. Любая формула может быть приведена к СКНФ.
Доказательство:
Если элементарная сумма не содержит литерал , то можно в нее ввести конъюнкцию и воспользоваться вторым законом дистрибутивности.
Пример 2. Пусть =(p q r) ( q) – КНФ.
Приведем к СКНФ. Добавим 0 в виде r . Получим
=(p q r) ( q r ) (p q r) ( q r) ( q )
это – СКНФ.
Восстановление формул.
Каждой формуле соответствует таблица истинности, следовательно, каждой таблице истинности соответствует некоторая формула. Возникает задача - для заданной таблицы истинности восстановить формулу, которой она соответствует. Этого можно достичь двумя способами:
|
|
С помощью СКНФ или с помощью ДНФ.
1. СКНФ.
В таблице истинности выделяются строки, в которых формула ложна. Каждой такой строке будет соответствовать единственная элементарная сумма КНФ. В эту сумму высказывание истинное будет входить с отрицанием, а высказывание, которое ложно - без отрицания. Это объясняется тем, что элементарная сумма должна быть ложной, а если в нее будут входить истинное высказывание, то она ложной не будет. Составляя СКНФ из этих строк, мы получим исходную формулу.
Пример: дана таблица
| р | q | r | Ф | |
Так как во 2-ой строке функция ложна, то должна быть ложна элементарная сумма. А элементарная сумма ложна тогда, когда каждый ее член равен 0.
Т. к. р=1, 
=0; и в дизъюнкцию должно входить .
Т. к. q=1, =0; и в дизъюнкцию должно входить .
r=0- без отрицания.
Получим: r.
Аналогично
Для 4-ой строки: р
Для 7-ой строки: 
. Тогда
Ф=( r)(р )( ).
2. СДНФ.
В таблице истинности выделяются строки, в которых формула истинна. Каждой такой строке поставим в соответствие элементарное произведение, которое должно быть истинно. В это произведение истинные высказывания входят без отрицания, а ложные - с отрицанием. Затем составляется дизъюнкция элементарных произведений.
|
|
Для нашего примера:
Ф = рqr р r р q