14. Исчисление высказываний. Приложения

Обратимся теперь к обыденным приложениям теории вывода, рассмотренной в предыдущих параграфах. Обычно в число условий, сопутствующих изложению какого-либо доказательства, входит наличие слушателя, имеющего право принимать или отвергать утверждение, что некоторое высказывание В представляет собой логическое следствие высказываний А1, А2,....., АM. В этом случае самостоятельно рассуждающий человек захочет доказать либо, что B — логическое следствие из всех А, либо, что рассуждение не логично, т. е. что можно приписать рассматриваемым простым компонентам такие истинностные значения, что одновременно все А получат значения Т, а В — значение F. Самый подходящий способ решения всего вопроса состоит в следующем: принять, что истинностное значение высказывания В есть F, а каждого из А — Т, и проанализировать, что получается из необходимого приписывания истинностных значений для простых компонентов. Такой анализ приводит либо к противоречию, доказывающему, что В есть логическое следствие из всех А, либо к приписыванию для каждого из простых компонентов такого истинностного значения, что все допущения будут удовлетворяться: последнее подтверждает, что это рассуждение не логично.

Изложенный здесь метод доказательства того, что некоторая формула есть логическое следствие других, обесценивает метод, выдвинутый в предшествующем разделе, поскольку второй метод так быстро приводит к результату. Однако первый метод имеет свои достоинства (во всяком случае, с педагогической точки зрения). Например, он ведет к ознакомлению с тавтологиями теоремы 2.4. Случаи использования тавтологий весьма обычны в математических доказательствах, и читателю следует приобрести навык в распознавании тавтологий, как таковых. Например, тавтология 20 оправдывает призывное заключение, что если контрапозиция высказывания есть логическое следствие из А, то и — тоже логическое следствие из А.

Примеры А

I. Рассмотрим следующее рассуждение.

Если я пойду завтра на первое занятие, то должен буду встать рано, а если я пойду вечером на танцы, то лягу спать поздно. Если я лягу спать поздно, а встану рано, то я буду вынужден довольствоваться пятью часами сна. Я просто не в состоянии обойтись пятью часами сна. Следовательно, я должен или пропустить завтра первое занятие, или не ходить на танцы.

Чтобы исследовать, справедливо ли это рассуждение, символизуем его, заменяя простые высказывания буквами. Пусть С означает «Я иду (пойду) завтра на первое занятие»; G — «Я должен встать рано»; D — «Я иду (пойду) вечером на танцы»; S — «Я лягу спать поздно», а Е — «Я могу обойтись пятью часами сна». Тогда посылки можно записать символически в следующем виде:

А искомое заключение будет

Следуя описанному выше методу анализа, примем, что имеет значение F, а каждая из посылок имеет значение Т. Тогда и С, и D должны иметь значение Т. Далее, как следует из первой посылки, и G, и S имеют значение Т. Это и вторая посылка влекут за собой, что Е имеет значение Т. Но это противоречит допущению, что третья посылка имеет значение Т.

Таким образом, доказано, что есть логическое следствие имеющихся посылок.

2. Предположим, что дано следующее утверждение:

|=

Примем, что имеет значение F, а каждая из посылок —Т. Первое допущение удовлетворяется, если приписать В значение Т, а D — значение F. В таком случае С имеет значение F и А — значение Т. При таких истинностных значениях каждая из посылок получает значение Т, а принимает значение F. Следовательно, рассуждение не логично.

С изложенным выше связан, но отличается от него вопрос о непротиворечивости множества высказываний, которое предлагается рассматривать как систему посылок для вывода. Множество {А1, А2,....., АM} высказываний непротиворечиво (в исчислении высказываний), если существует по меньшей мере одно такое распределение истинностных значений простым компонентам, что все А одновременно получают значение Т. Противоречивость множества высказываний есть отрицание его непротиворечивости. Так, {А1, А2,....., АM} есть противоречивое множество, если при всяком распределении истинностных значений простым компонентам по меньшей мере одно из А получает значение F. Короче говоря, {А1, А2,....., АM} непротиворечиво если Имеет значение Т по меньшей мере для одной комбинации приписываемых простым компонентам истинностных значений, и {А1, А2,....., АM} противоречиво, если имеет значение F для всех комбинаций истинностных значений, приписываемых простым компонентам.

Противоречивость множества высказываний можно установить, пользуясь системой методов, описанных в предыдущем параграфе, как только мы введем следующее определение. Противоречие есть формула, которая всегда принимает истинностное значение F (например,).

Теорема 2.8. Множество высказываний {А1, А2,....., АM} противоречиво, если из него в качестве логического следствия можно вывести противоречие.

Доказательство. Примем, что для некоторой формулы В А1, А2,....., АM |= . Тогда |= и искомое заключение следует из истинностной таблицы для импликации.

Противоречия играют также важную роль в методе косвенного доказательства (называемого также доказательством от противного, или доказательством reductio ad absurdum). Основой такого вида доказательства служит следующий результат:

Теорема 2.9. А1, А2,....., АM |= В, если в качестве логического следствия из А1, А2,....., АM и можно вывести противоречие.

Доказательство. Примем, что для некоторой формулы С А1, А2,....., АM , |= . Тогда А1, А2,....., АM |= . Рассмотрим теперь такое распределение истинностных значений, приписываемых данным простые компонентам, что каждая А принимает значение Т. Тогда имеет значение Т. Это и то, что получает значение F, влечет за собой для значение F, и, следовательно, В имеет значение Т.

Упражнения

Применить рассмотренный в этом параграфе метод для доказательства логичности или нелогичности рассуждений, приведенных в упр. 1 – 12. если рассуждение логично, построить для него доказательство. Пользуйтесь везде предложенными в тексте буквами для символической записи рассуждения.

1. Я пойду домой (H) или останусь здесь и выпью стаканчик (S). Я не пойду домой. Следовательно, я останусь и выпью.

2. Если Джон ляжет сегодня поздно (S), он будет утром в отупении (D). Если он ляжет не поздно, то ему будет казаться, что не стоит жить (L). Следовательно, или Джон будет завтра в отупении, или ему будет казаться, что не стоит жить.

3. Заработная плата возрастет (W) только, если будет инфляция (J). Если будет инфляция, то увеличится стоимость жизни (С). Заработная плата возрастет. Следовательно, увеличится стоимость жизни.

4. Если 2 — простое число (Р), то это наименьшее простое число (L). Если 2 — наименьшее простое число, то 1 не есть простое число (N). Число 1 не есть простое число. Следовательно, 2 — простое число.

5. Джон или переутомился (E), или болен (S). Если он переутомился, то он раздражается (С). Он не раздражается. Следовательно, он болен.

6. Если завтра будет холодно (С), я надену теплое пальто (H), если рукав будет починен (S). Завтра будет холодно, а рукав не будет починен. Следовательно, я не надену теплое пальто.

7. Если исход скачек будет предрешен сговором (R) или в игорных домах будут орудовать шулеры (H), то доходы от туризма упадут (D), И город пострадает (S). Если доходы от туризма упадут, полиция будет довольна (Р). Полиция никогда не бывает довольна. Следовательно, исход скачек не предрешен сговором.

8. Если Доджеры выиграют (D), то Лос-Анджелес будет торжествовать (L), а если выиграет Уайт-Сокс (W), то торжествовать будет Чикаго (С). Выиграют или Доджеры, или Уайт-Сокс. Однако если выиграют Доджеры, то Чикаго не будет торжествовать, а если выиграет Уайт-Сокс, то не будет торжествовать Лос-Анджелес. Итак, Чикаго будет торжествовать тогда и только тогда, когда не будет торжествовать Лос-Анджелес.

9. Или Сэлли и Боб одного возраста (S), или Сэлли старше Боба (О). Если Сэлли и Боб одного возраста, то Нэнси и Боб не одного возраста (N). Если Сэлли старше Боба, то Боб старше Уолтера (W). Следовательно или Нэнси и Боб не одного возраста, или Боб старше Уолтера.

10. Если 6 — составное число (S), то 12 — составное число (W). Если 12 — составное число, то существует простое число, большее чем 12 (Р). Если существует простое число больше 12, то существует составное число больше 12 (С). Если 6 делится на 2 (D), то 6 — составное число. Число 12 составное. Следовательно, 6 — составное число.

11. Если я поеду автобусом (В), а автобус опоздает (L), то я пропущу назначенное свидание (М). Если я пропущу назначенное свидание и начну огорчаться (D), то мне не следует ехать домой (Н). Если я не получу эту работу (I), то я начну огорчаться и мне следует поехать домой. Следовательно, если я поеду автобусом и автобус опоздает, то я получу эту работу.

12. Если Смит победит на выборах (N), он будет доволен (Н), а если он будет доволен, то он плохой борец в предвыборной кампании (С). Но если он провалится на выборах, то потеряет доверие партии (Р). Он плохой борец в предвыборной кампании, если он потеряет доверие партии. Если он плохой борец в предвыборной кампании, ему следует выйти из партии (R). Смит или победит на выборах, или провалится. Следовательно, ему нужно выйти из партии.

< Предыдущая		Следующая >