Упражнение. 1. АÚВÚВ=АÚВ.

Дана КНФ: .

Построить СКНФ.

1. АÚ ВÚ В=АÚ В.

2. (АÚ В)(АÚ В)=АÚ В.

3. , следовательно, .

4. .

Следовательно, ,

Из определений и теорем 3, 4 следует, что тождественно истинная формула не имеет СКНФ, а тождественно ложная - СДНФ.

Каждая не тождественно истинная и не тождественно ложная формула имеет единственную СКНФ и СДНФ.

Совершенные нормальные формы могут быть применены для установления равносильности двух заданных формул алгебры высказываний. Для этого нужно обе формулы привести к СКНФ или СДНФ и убедить в их совпадении. Например, формулы

и равносильны:

.

Полной элементарной конъюнкцией называется конъюнкция, удовлетворяющая свойствам 2, 3, 4 определения 5. Аналогично, полной элементарной суммой называется элементарная дизъюнкция, удовлетворяющая свойствам 2, 3, 4 определения 6.

Поэтому совершенные нормальные формы можно определить так:

Определение 7. Совершенной дизъюнктивной нормальной формой некоторой формулы алгебры высказываний называется формула, равносильная данной формуле алгебры высказываний и являющаяся дизъюнкцией различных полных элементарных конъюнкций.

Определение 8. Совершенной конъюнктивной нормальной формой некоторой формулы алгебры высказываний называется формула, равносильная данной формуле алгебры высказываний и являющаяся конъюнкцией различных полных элементарных дизъюнкций.

Каждая полная элементарная конъюнкция на одном наборе значений переменных высказываний, ее составляющих, обращается в 1: переменное высказывание, входящее без знака отрицания, принимает значение 1, а со знаком отрицания - 0. Этот набор значений элементарных составляющих называется единицей данной полной элементарной конъюнкции. Так единицей полной элементарной конъюнкции является (1, 0, 1).

Аналогично. Каждая полная элементарная дизъюнкция на одном наборе значений переменных высказываний, ее составляющих, обращается в 0: переменное высказывание, входящее без знака отрицания, принимает значение 0, а со знаком отрицания - 1. Этот набор значений элементарных составляющих называется нулем данной полной элементарной дизъюнкции. Так нулем полной элементарной дизъюнкции является (1, 1, 0).