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

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

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

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

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

3) Если в некоторую элементарную дизъюнкцию В переменная входит дважды, то лишнюю переменную нужно отбросить, так как .

4) Если в элементарную дизъюнкцию входит пара , то ее можно отбросить так как , а истинное высказывание из конъюнкции можно выбросить (в силу равносильности ).