Правило получения СДНФ формулы А с помощью равносильных преобразований

1. Для формулы А получаем ДНФ А.

2. Из ДНФ А путем равносильных преобразований получаем СДНФ, последовательно добиваясь выполнения четырех свойств СДНФ А:

1) Пусть В есть слагаемое ДНФ А, не содержащее . Тогда надо заменить слагаемое В в ДНФ А на слагаемое (т.к. ).

2) Если в ДНФ А встретится два одинаковых слагаемых , то лишнее нужно отбросить, так как .

3) Если некоторое слагаемое В в ДНФ А содержит конъюнкцию , то это слагаемое можно отбросить, так как , и следовательно, , а ложное высказывание из дизъюнкции можно выбросить (в силу равносильности .

4) Если в некоторое слагаемое В в ДНФ А переменная входит дважды, то лишнюю переменную надо отбросить так как .

3.3.2 Конъюнктивная нормальная форма и совершенная конъюнктивная нормальная форма (КНФ и СКНФ)

Определение 1. Элементарной дизъюнкцией n переменных называется дизъюнкция переменных или их отрицаний.

Определение 2. Конъюнктивной нормальной формой (КНФ) формулы А называется равносильная ей формула, представляющая собой конъюнкцию элементарных дизъюнкций.

Определение 3. Совершенной конъюнктивной нормальной форой А (СКНФ А) называется КНФ А, удовлетворяющая следующим условиям:

1. Все элементарные дизъюнкции, входящие в КНФ А, содержат все переменные.

2. Все элементарные дизъюнкции, входящие в КНФ А, различны.

3. Каждая элементарная дизъюнкция, входящая в КНФ А, содержит переменную один раз.

4. Ни одна элементарная дизъюнкция, входящая в КНФ А, не содержит переменную и ее отрицание.

СКНФ А можно получить двумя способами:

1) с помощью таблицы истинности, используя равносильность (формула двоственности);

2) с помощью равносильных преобразований.