Упражнение. 1. Первое и последние слагаемые одинаковы

.

Задана ДНФ. Приведем ее к СДНФ.

1. Первое и последние слагаемые одинаковы. На основании свойства операции дизъюнкции АÚ А=А одно из одинаковых слагаемых можно отбросить.

2. АСС=АС.

3. .

Получим .

Теперь выполнили условия 1 - 3. Чтобы выполнить условие 4, поступим следующим образом:

;

.

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

Теперь условие 4 выполнено, но появились одинаковые слагаемые. Исключив их получим:

.

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

1. Она не содержит двух одинаковых сомножителей.

2. Ни один из сомножителей не содержит одновременно двух одинаковых слагаемых.

3. Ни один из сомножителей не содержит одновременно некоторого высказывания и его отрицания.

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

Определение СКНФ также является конструктивным.