15
Июл

ЛОГИКА

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

Обозначим: А — дерево познают по плодам;

В — плоды познают по дереву;

С — этот Фальстаф, по-моему, в высшей степени добродетельный че-
ловек. .

И в целом вся фраза: ((А & В) -> С).

3. «Только два из высказываний А, В, С ложны».
На языке логики высказываний это будет:

(А & В & С) v (А & В & С) v(A & В & С))

4. «Самое большее два из высказываний А, В, С истинны».

‘Серрюс Ш. Опыт исследования значения логики. М., 1948, с. 12. Вступительная
статья В.Ф. Асмуса.

153

В переводе на язык логики высказываний это будет:

((A v В) & С) v ((A v С) & В) v ((В v С) & А)).
Формулы (т. е. то, что мы получили в результате перевода обычных фраз

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

1. Тождественно истинные (общезначимые), т. е. истинные всегда, ка-
кие бы значения мы не подставляли в них вместо букв.

2. Тождественно ложные, т. е. ложные при каких угодно значениях своих

переменных.

3. Нейтральные, т. е. при одних значениях переменных ложные, а при

других истинные.

Тождественно истинные и нейтральные формулы называются выпол-
нимыми.

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

1. Табличный метод, т. е. построение для каждой формулы соответству-
ющей ей таблицы истинности. Например, для формулы

((А & В) ->. (А v В))

таблица будет такова:

А В,. А В (А&В) (А&В) (AvB) (A&B)->(AvB)

и и л л л

и л л и и

л и и л л

л л и и л

и

Отсюда видно, что данная формула тождественно истинна, т. е. выража-
ет собою логический закон.

2. Применение таблиц удобно, лишь если число переменных в формуле
невелико. Если формула имеет п переменных, то число строк в таблице
равно 2″, т. е. при двух переменных — 4, а при шести — 64 и т.д. Поэтому
целесообразнее в случае большого числа переменных другая процедура —

приведение в нормальные формы.

Таких форм две — конъюнктивная нормальная форма (КНФ) и дизъ-
юнктивная нормальная форма (ДНФ). ;

КНФ — это конъюнкция дизъюнкций переменных или их отрицаний. Т.

е. выражение, выглядящее так:

((А v В v С) & (В v С) & (А v С)).

Это выражение показывает нам, является ли соответствующая форму-
ла (та, которая была приведена к КНФ) общезначимой или нет. Крите-

‘Зегет В. Элементарная логика. М., 1985, с. 70.

154

рий здесь такой — если в каждой дизъюнкции, складывающей это выраже-
ние, любая переменная один раз встречается с отрицанием, а другой раз
без отрицания, то формула эта тождественно истинна. Если же этого нет
хотя бы в одной дизъюнкции, то выражение не является тождественно
истинным, а будет либо тождественно ложным, либо нейтральным (каким
именно, пока неизвестно). Так, вышеприведенная формула не является
общезначимой, поскольку ни в одной из ее дизъюнкций нет переменной
одновременно с ее отрицанием. А вот формула

((А v А v В) & (А v В v В))
общезначима.

ДНФ — это ряд элементов, соединенных дизъюнкцией. Каждый эле-

мену — конъюнкция каких-либо переменных или их отрицаний. Напри-
мер, выражение

((А & В & С) v (В & С) v (A & С))
есть ДНФ.

По ДНФ мы можем судить, является ли формула тождественно ложной
‘ или нет. Критерий здесь следующий — если в каждой конъюнкции, со-
ставляющей ДНФ, некоторая переменная входит один раз с отрицанием,
а другой раз без него, то это выражение тождественно ложное. Если же
этого нет хотя бы в одном случае, то выражение не тождественно ложное,
т. е. общезначимое или нейтральное. Так,_выражение _

((В & А & В) v (В & А & А) v (В & С & С)
является тождественно ложным. Очевидно, что если формула, будучи при-
веденной к КНФ, оказывается не тождественно истинной, а приведен-

Страницы: 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 комментариям. Комментарии и пинги закрыты, извините.

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