Любая булева функция может иметь много представлений в виде ДНФ и КНФ. Особое место среди этих представлений занимают совершенные ДНФ (СДНФ) и совершенные КНФ (СКНФ).
Совершенная дизъюнктивная нормальная форма (СДНФ) – это ДНФ, в которой в каждый конъюнктивный одночлен каждая переменная хi из набора f (х 1, х 2,..., хп)входит ровно один раз, причем входит либо сама хi либо ее отрицание .
Конструктивно СДНФ для каждой формулы алгебры высказываний, приведенной к ДНФ, можно определить так:
Совершенной дизъюнктивной нормальной формой (СДНФ) формулы алгебры высказываний называется ее ДНФ, обладающая следующими свойствами:
1. ДНФ не содержит двух одинаковых конъюнкций.
2. Ни одна конъюнкция не содержит одновременно двух одинаковых переменных.
3. Ни одна конъюнкция не содержит одновременно некоторую переменную и ее отрицание.
4. Каждая конъюнкция содержит либо переменную хi либо ее отрицание для всех переменных, входящих в формулу.
Конструктивно СКНФ для каждой формулы алгебры высказываний, приведенной к КНФ, можно определить так:
|
|
Совершенной конъюнктивной нормальной формой (СКНФ) данной формулы алгебры высказываний называется такая ее КНФ, которая удовлетворяет следующим свойствам:
1. КНФ не содержит двух одинаковых дизъюнкций.
2. Ни одна из дизъюнкций не содержит одновременно двух одинаковых переменных.
3. Ни одна из дизъюнкций не содержит одновременно некоторую переменную и ее отрицание.
4. Каждая дизъюнкция СКНФ содержит либо переменную хi либо ее отрицание для всех переменных, входящих в формулу.
Каждая булева функция от n переменных, отличная от константы 0, имеет единственную СДНФ. Каждая булева функция от п переменных, отличная от константы 1, имеет единственную СКНФ.