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

(сокращенно СКНФ)

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

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

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

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

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

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

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)