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

Сокращенная конъюнктивная форма позволяет найти все простые следствия из конъюнкции данных формул. Следствие называют простым если оно есть не содержащая повторений и не тождественно истинная элементарная дизъюнкция, которая, будучи логическим следствием из конъюнкции данных формул, не поглощается никаким более сильным следствием такого же вида, т.е. после отбрасывания какого-нибудь из ее членов перестает быть следствием из данных формул. Иногда более сильное следствие поглощает слабые. Так, при тождественной истинности формул вида AB, считают, что А сильнее чем В.

Сокращенная КНФ некоторой формулы есть конъюнкция всех ее простых следствий.

Она обладает следующими свойствами:

1. ни в одном конъюнкте ни одна переменная не повторяется;

2. нет таких пар конъюнктивных членов, что всякий дизъюнкт из одного имеется в другом;

3. для всяких двух конъюнктивных членов, из которых один содержит некоторую переменную, а другой ее отрицание (при условии, что другой переменной, для которой это же имеет место, в данной паре конъюнктов нет), имеется в этой же КНФ конъюнктивный член, равный дизъюнкции остальных дизъюнктов этих двух конъюнктивных членов.

Для получения обзора всех простых следствий из данных посылок необходимо:

1. Привести конъюнкцию посылок к КНФ.

2. Из всех одинаковых конъюнктов оставить только один и в элементарных дизъюнкциях устранить все повторения.

3. На основании правил 20 и 22 устранить все конъюнкты, которые содержат хотя бы одну переменную одновременно с отрицанием и без него.

4. Если из двух конъюнктов один содержит некую переменную, а другой - ее отрицание, то согласно правилу 30 добавить к формуле новый конъюнкт, равный дизъюнкции остальных дизъюнктов этих двух конъюнктивных членов. Например, если два конъюнкта имеют вид:

A + C и B + C, то добавляется новый конъюнкт A + В.

Ана основании правила 31 - (A + C) & C = (A + C) & C & A и правила 32 - C& (B + C)=C & (B + C) & B, которые являются частными случаями правила 30, при наличии конъюнктов вида С и В + C или же вида А + С и С мы в первом случае приписываем новый конъюнкт В, а во втором - А.

5. Если имеется возможность, применяем правило 9, т.е. если есть конъюнкты вида А и A + В, то дизъюнкция A + В вычеркивается.

6. Если необходимо, то применяем правило 15, устраняя повторения конъюнктов.

Врезультате применения пунктов 1-6 получим сокращенную КНФ (силлогиcтический многочлен), содержащую все простые следствия из данных посылок.

Пример. Даны посылки A B, A + C, B & C.

Найти все простые следствия из этих посылок:

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

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

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

(A + C) & B.

Это значит, что при данных посылках формула А + С истинна, а В - ложна.

ЗАДАНИЕ 25. Найти все простые следствия из данного набора посылок путем приведения к сокращенной КНФ конъюнкции этих посылок.

Вариант:

1. (A & B) C, (A + C) (B + D)

2. (A + B)(D + C), D(C & B)

3. A(B & C), (A & D) B, (A&C) E

4. A+ B, B + C, A & C

5. AB, AC, B + C

6. AC, CB, AC

7. (A + B) & C, A C, B C

8. AB, C + D, A (D & C)

9. AB, D + E, B  C, C D, E(A&D)

10. C(A & B), A(B & C), (B & C) A

ЗАДАНИЕ 26. Методом приведения к совершенной КНФ решить следующую задачу.

Рабочий должен снимать с конвейера бракованные детали. Мастер сказал, что бракованными следует считать те детали, которые удовлетворяют одновременно ряду условий, а именно они:

1. искривлены, заржавлены или не окрашены;

2. или нестандартны, или заржавлены, или то и другое вместе;

3. или искривлены, или не заржавлены, или то и другое вместе;

4. или нестандартны, или не заржавлены, или то и другое вместе;

5. искривлены, заржавлены или окрашены.

Предложенный мастером набор условий упростить до двух характеристик отбираемых деталей.

Это задание общее для всех вариантов.