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