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

Каждая не тождественно истинная формула имеет одну КНФ, которая называется совершенной. СКНФ - это КНФ, обладающая следующими свойствами:

1. в ней нет двух одинаковых конъюнктов (т.е. получающихся один из другого при замене по правилу 7);

2. ни один конъюнкт (т.е. элементарная дизъюнкция) не содержит двух одинаковых дизъюнктов;

3. ни один конъюнкт не содержит переменной с отрицанием и без него;

4. в каждом конъюнкте имеются все, содержащиеся в данной формуле, переменные.

Для приведения любой формулы логики высказываний к СКНФ необходимо:

1. Сначала привести формулу к КНФ.

2. Требование а)выполняют посредством правила 15, устранением всех повторений, т.е. любой конъюнкт остается в формуле только на одном месте и вычеркивается из остальных.

3. Требование b) выполняют посредством правила 14, устранением всех повторений в каждом конъюнкте, т.е. в каждой из элементарных дизъюнкций.

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

5. Требование d) выполняется приписыванием ко всем конъюнктам, в которых отсутствует какая либо из имеющихся в формуле переменных, знака дизъюнкции и, вслед за ним тождественно ложной конъюнкции этой переменной и ее отрицания

( Х &X).

Дизъюнктивное присоединение к любой формуле ложной формулы, согласно правилу 21, не изменяет условий ее истинности. Затем применяем правило 11. Эту процедуру повторять до тех пор, пока не выполним требование d).

Пример приведения к СКНФ:

((AB)&(BC)&(CA)) + A

Сначала приводим к КНФ: _ = =

((A + B) & (B + C) & (C + A)) + A

_

(A + B + A) & ( B + C + A) & (C + A + A)

Полученную КНФ преобразуем в СКНФ:

Согласно требованию с) вычеркиваем первый конъюнкт, а в третьем, согласно требованию b) устраняем повторения. Получаем формулу (В + C + A) & (C +A)

Но во втором конъюнкте нет В. Поэтому присоединяем сюда знаком дизъюнкции (B & B).

Получаем формулу

(B + C + A) & ( C + A + (B & B))

По правилу дистрибутивности 11 получаем:

(B + C + A) & (C + A + B) & (C + A + B)

Устраняем появившиеся повторения конъюнктов и получаем СКНФ:

( B + C + A) & ( C + A + B)

Приведением формулы к СКНФ можно решать задачу отыскания всех логических следствий из данных формул. Для этого все данные формулы связываем знаком конъюнкции «&» и для возникшей таким образом формулы находим ее СКНФ. Каждый конъюнктивный член СКНФ, а также любая конъюнкция любого числа этих членов является следствием из данных формул. Затем, используя правил 28 и другие, можно получить более простую форму записи этих следствий.

Пусть даны две формулы: А и А В

Связываем их знаком конъюнкции A & (AB)

Находим СКНФ получившейся формулы

A & (AB) = A & (A + B) = ( A + (B & B)) & (A + B) = (A + B) & (A + B) &(A + B)

Полученная СКНФ позволяет увидеть все следствия данных формул в СКНФ.

Этими следствиями будут:

1. A + B

2. A + B

3. A + B

4. (A + B) & (A + B)

5. (A + B) & (A + B)

6. (A + B) & (A + B)

7. (A + B) & (A + B) & (A + B)

Применяя правило упрощения 28 к следствию 4, получаем следствие - А, которое есть одна из данных формул. В обзор всех следствий будут входить и сами данные формулы.

Из следствия 5 посредством правила 28 получаем следствие - В;

Из следствия 6 посредством правила 29 получаем следствие - A B;

Следствие 7 дает следствие - А & В.

ЗАДАНИЕ 24. Упростить данную формулу посредством приведения ее к СКНФ, или найти все следствия из предложенного набора посылок.

Варианты:

1. ((А + В)&(ВС )) + ((В  А)&(В + С))

2. ((А & В)  (В + С )) & ((В&А)  (ВС))

3. В + С; В  А ; ВС

4. ((А + В)  (A + С )) & ((В + C)  (A + В))

5. A B; ВС; С  А

6. ((А В) & (C & A) & (B C)) + A

7. (A & B) C; В; С

8. ( А  В) +(B + C)

9. А  В; A  C; A & (BC)

10. (((АВ) В) + B) + ( A & C)