15
Июл

ЛОГИКА

  Автор: admin   , категория Лекции

ной к ДНФ, — не тождественно ложной, то она является нейтральной.

Считается, что для каждой формулы логики высказываний есть экви-
валентные ей КНФ и ДНФ, т. е. формул, не сводимых и к КНФ, и к
ДНФ, нет.

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

1. Элементы исходной формулы со знаками s и ^ заменяются им
равносильными со знаками v и &.

2. Все элементы исходной формулы, имеющие вид (А —> В), заменяются на
(А v В) или (А & В) Т. е. импликация устраняется.

3. Все отрицания, стоящие над сложными элементами (т. е. состоящими

из двух и более переменных) опускаются до этих элементов (по закону де
Моргана).

• 4. Устраняются все двойные отрицания над переменными.

5. рсуществляется раскрытие всех скобок по закону дистрибутивности
дизъюнкции относительно конъюнкции — при приведении к КНФ. Или

по закону дистрибутивности конъюнкции относительно дизъюнкции —
при приведении к ДНФ.

Вообще говоря, эти операции могут производиться в разной последо-
вательности. Для их осуществления нужно знать правила взаимопревра-
щений союзов друг в друга и ряд логических законов. Мы приведем их,
хотя, конечно, их можно найти и во многих пособиях и учебниках по

символической логике (например: Войшвилло Е. К. Символическая ло-
гика. М., 1989).

155

Не нужно смотреть на все эти преобразования и приведения в тожде-
ственные формулы как на какое-то особое изобретение логиков, муд-
рость, не имеющую аналогов в жизни. Проверка (или доказательство)
истинности высказываний путем преобразования их во всегда истинные
или всегда ложные формулы, в процессе чего вскрывается внутренняя
структура этих высказываний в повседневном языке, в народной, так ска-
зать, логике имели место всегда, хотя, конечно, не в такой символичес-
кой форме, как это делается в современной логике. Вот, например, в
одной из повестей ныне забытого писателя С. А. Качиони, посвященной
жизни татарского Крыма, описывается беседа двух человек. Речь зашла о
том, что один их знакомый женится:

« — Богатую невесту взял?

— Была богатая, теперь бедная.

— Зачем же он бедную берет?

— Такая бедная богаче самой богатой, бей, — пояснил ему Чилиби
(имея в виду, что эта девушка исключительно добра и красива. — В.Т.)

— …Ты сказал совсем пустое. Скажи сам, разве худой баран может быть
жирнее самого жирного?

— Не может.

— А как же бедная невеста может быть богаче самой богатой?»

Роль всегда истинных формул в народной логике исполняют послови-
цы, положения здравого смысла, прецеденты, изречения, притчи и т. д.

3.2. Равносильность формул. Приведение к КНФ и-ДНФ выражается в
замене одних формул другими до тех пор, пока мы не достигнем искомо-
го результата. Разумеется, замена должна осуществляться без ущерба для
смысла выражения, то есть формула должна заменяться другой, но рав-
носильной ей.

Равносильны те две формулы, которые при любых одинаковых значе-
ниях (истина или ложь) переменных, входящих в их состав, принимают
одинаковые значения (например, на таблице истинности). Другими сло-
вами, равносильны те формулы, эквиваленция которых представляет со-
бою тавтологию. Например, формулы

(А->.В)и(А&В)
являются равносильными, т. е. имеющими одно и то же содержание, ут- |
верждающими одно и то же. Чтобы убедиться в этом, построим для них ^
таблицы истинности: Ц

А В А->В ABB А&В А&В

иии и и л л и

ЛИИ ЛИЛЛ И

и л л или и л

, л л и л л и л и

Поэтому (А -> В) можно менять на (А&В) и наоборот. Смысл фразы
от этого не изменится или, иными словами, изменение союзов, соединя-

законы идемпотентности.

ющих понятия, не изменит смысла фразы. Равносильные формулы сим-
метричны, т. е. если А равносильна В, то В тем самым равносильна А. Эти
формулы так же и транзитивны, т. е. если А равносильна В и С, то тем
самым В и С между собою также равносильны.

Страницы: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96

Запись оставлена Воскресенье, Июль 15th, 2012 в 8:47 пп в категории Лекции. Вы можете следить за комментариями по RSS 2.0 комментариям. Комментарии и пинги закрыты, извините.

Комментарии закрыты.