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