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

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

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

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

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

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

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

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

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

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. Методом приведения к совершенной КНФ решить следующую задачу.

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

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

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

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

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

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

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

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

Заключение

В предложенной работе сделана попытка представить кратко основные разделы традиционной формальной логики и элементы символической логики высказываний. Можно предположить, что знакомство с теорией и решение практических задач позволит студенту, если он не остановится на первом шаге, подготовиться к дальнейшему, более глубокому изучению логики. Получив в свое распоряжение «технику» обличения, правильных умозаключений об ошибочных. Тот, кто неплохо разберется с представленным материалом, найдет, что изученное имеет многочисленные сферы применения, и не только в повседневной жизни. Он обнаружит, что систематическое рассмотрение обыкновенных рассуждений делает и его собственное мышление яснее и логичней. А рассмотренные здесь логические средства, несмотря на их элементарность, могут быть использованы для решения ряда логических задач.

ЛИТЕРАТУРА

1. Аристотель «ОРГАНОН» соч. В 4-х т. т.2 М., 1976

2. Берков В.Ф., Яскович Я.С., Бартон В.И. Логика. Логические основы общения (учебные пособия для ВУЗов) М., 1994

3. Бочаров В.А., Маркин В.И. Основы логики. Учебник. М., 1994

4. Брюшинкин В.Н. Практический курс логики для гуманитариев. М., 1994

5. Войшвилло Е.К., Дегтярев М.Г. Логика как часть теории познания и научной методологии (фундаментальный курс). Учебное пособие для студентов философских факультетов и преподавателей логики. М., 1994

6. Гетманова А.Д. Учебник по логике. М. 1994

7. Гильберт Д., Аккерман В. Основы теоретической логики. М., 1947

8. Горский Д.П. Логика. М., 1963

9. Ивлев Ю.В. Логика. М., 1994

10.Кириллов В.И. Упражнения по логике. М., 1993

11.Кириллов В.И., Старченко А.А. Логика. М., 1987

12.Клини С.К. Математическая логика. М., 1973

13.Кобзарь В.И. Основы логических знаний. С-П., 1994

14.Кондаков Н.И. Логический словарь-справочник. М., 1976

15.Краткий словарь по логике. М., 1991

16.Кэролл Л. Логическая игра. М., 1991

17.Логика и клиническая диагностика. Теоретические основы. М., 1994

18.Мельников А.Н. Сборник задач по логике. Киев, 1990

19.Мендельсон Э. Введение в математическую логику. М., 1973

20.Ненашев М.И. Введение в логику. Киров, 1995

21.Новиков П.С. Элементы математической логики. М., 1973

22.Упражнения по логике. М., 1990

23.Формальная логика. Л., 1977

24.Челпанов Г.И. Учебник логики. М., 1994

25.Черч А. Введение в математическую логику. Т.1 М., 1960