Классическое исчисление высказываний

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

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

Правила вывода[2]:

Правила введения связок	Правила исключения связок
Ø_в	В, ØВ ØС*	Ø_и	ØØА А
&_в	А,В А&В	&_и	А&ВА&В А В
Ú_в	А В . АÚВ АÚВ	Ú_и	АÚВ, ØААÚВ, ØВ В А
É_в	В . С*ÉВ	É_и	АÉВ, А В

* где С – последнее допущение

Данные правила представляют собой схемы разрешенных в логике высказываний преобразований. Например, правило (&_в)разрешает от утверждения двух отдельных формул А и В перейти к утверждению более сложной формулы А&В, и так далее (смысл большинства правил будет ясен любому, кто помнит табличные определения соотвествующих связок).

В комментариях нуждаются лишь два правила: введение отрицания (Ø_в) и введение импликации (É_в). Как вы поняли, формула С, фигурирующая в них, обозначает не любое высказывание, а именно последнее допущение. Дело в том, что допущения (гипотезы, версии) довольно часто применяются в построении дедуктивных рассуждений, играя в них вспомогательную роль. И как раз для того, чтобы оценить эту роль, подвести итог рассмотрению того или иного предположения, нужны правила введения отрицания и введения импликации.

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

Предположим, что Земля квадратная. (С)

Тогда тень, отбрасываемая ею, тоже должна быть квадратной. (В)

Но тень Земли на Луне во время лунного затмения – круглая. (ØВ)

Предположение неверно, т.е. Земля не является квадратной (ØС)

Рассмотрим правило введения импликации. Оно применяется в тех случаях, когда используемое допущение не приводит к явному противоречию, так что вместо двух взаимоисключающих суждений мы получаем одно, вполне ясное и непротиворечивое (В). Можем ли мы утверждать его как очевидную и незыблемую истину? Нет, ведь оно получено с использованием допущения (С), которое само по себе еще не доказано. Но мы вправе утверждать, что по крайней мере суждение В вытекает из упомянутого допущения (СÉВ), то есть В истинно при условии истинности С. Например:

Предположим, число х кратно четырем. (С)

Четыре кратно двум.

Получается, х кратно числу, которое кратно двум.

Значит, х тоже кратно двум. (В)

Итак: если число х кратно четырем, то оно кратно и двум. (СÉВ)

Выводом называется непустая конечная последовательность формул, удовлетворяющая условиям:

1.Каждая из них либо является посылкой, либо получена из предыдущих формул по одному из правил вывода;

2. Если в выводе применялись правила (É_в) или (Ø_в), то все формулы, начиная с последней посылки и вплоть до результата применения данного правила, исключаются из участия в дальнейших шагах вывода

Последнее требование означает, что эти формулы уже были использованы и возвращаться к ним более нельзя. Почему? Если использовалось правило (Ø_в), значит в выводе фигурировало заведомо ложное допущение, из которого было получено противоречие. Очевидно, что делать из него еще какие-либо умозаключения, равно как и использовать уже сделанные, абсурдно. Если же речь идет об использовании правила (É_в), то мы понимаем, что в выводе фигурировало допущение C, позволившее получить некоторую нужную нам формулу B, но само по себе еще не доказанное. Возвращаться к этому допущению (или к формулам, из него выведенным) означало бы выдавать гипотетическую истинность В (при условии С) за категорическую. Это может привести к ошибке под названием «круг в доказательстве».

Формулы, исключенные из дальнейшего хода рассуждения после применения правила (É_в) или (Ø_в), называются подвыводом. Это значит, что они были полезны лишь внутри какого-то вывода, но не обязательно являются истинными сами по себе. Стоит заметить, что в сложных рассуждениях могут встречаться не только подвыводы, но и подвыводы внутри подвыводов, и так далее. Таким образом, процедура построения вывода как бы разбивается на несколько подчиненных один другому блоков, объединенных одной общей целью. Поэтому изложенная здесь логическая теория называется системой субординатного (т.е. подчиненного) вывода.

Рассмотрим пример рассуждения, производимого с помощью системы субординатного вывода. (В дальнейшем тот факт, что некоторые формулы в выводе являются исключенными, будем обозначать вертикальной чертой, а допущения, используемые в ходе вывода – знаком «+».)

Наташа долго думала, кого пригласить на свой день рожденья: «Если пригласить Тараса, то не придет Эрика – она с ним в ссоре. Если на дне рожденья будет Элла, то надо приглашать и Тараса, потому что они брат и сестра. А если не придет Элла, то не придет и Таня». Докажите, что если пригласить Таню, то не придет Эрика.

Примем обозначения:

d – придет Тарас

j – придет Эрика

r – придет Таня

m – придет Элла

Запишем условия задачи в качестве посылок:

+1. d É Øj

+2. m É d по условию

+3. Øm É Ør

Посмотрим, что будет, если пригласить Таню:

+4. r [цель: Øj]

Придет ли тогда Элла?

+5.Øm Допустим, она не придет. [цель: прот.]

6. Ør (3, 5 É_и) Тогда не придет и Таня.

Мы получили противоречие (6 противоречит 4). Придется отрицать последнее допущение. Закрываем этот подвывод.

7. ØØm (4, 6 Ø_в)

8. m (7 Ø_и) Элла все-таки придет

9. d (2, 8 É_и) Значит, придет и Тарас

10. Øj (1,9 É_и) Следовательно, не придет Эрика.

Итак, из предположения, что придет Таня, мы с необходимостью получаем, что не явится Эрика. Это и требовалось доказать. Вводим импликацию и снова закрываем подвывод.

11.r É Øj (10 É_в)

Конечно, данный вывод можно было строить и другими способами. Все зависит от того, какие допущения и в каком порядке мы выбираем. Но лучше делать это не наобум, а руководствуясь определенными эвристиками. (Эвристика – тактический прием, упрощающий процедуру поиска решения.)

Эвристики, основанные на анализе цели:

№	Цель	Допущение	Новая цель
	А	ØА	противоречие
	ØА	А	противоречие
	А É В	А	В
	А & B		А, потом В (или наоборот)
	А Ú B	ØА,	противоречие
потом ØВ	противоречие

Так, в приведенном выше рассуждении про Таню и Эрику были использованы эвристики №3 и №1 (см. указания о введении новых целей на шагах 4 и 5).

Конечно, в процессе построения вывода необходимо держать в уме не только поставленные цели, но и достигнутые на каждом шаге результаты.

Эвристики, основанные на анализе вывода:

№	В выводе есть формула	Поставленная цель	Допущение	Новая цель
	А Ú В	В	А	противоречие, чтобы затем получить ØА, а из него – В
	Ø(А Ú В)	противоречие	А (либо В)	А Ú В, чтобы возникло протворечие
	А É В	В	ØА	противоречие, чтобы затем получить А, а из него – В

Упражнение. При помощи системы субординатного вывода обоснуйте следующие рассуждения. Укажите, какие эвристики вы при этом использовали.

а) Если Динамо не выиграет следующий свой матч, то в случае, если Спартак выиграет свой матч, он станет чемпионом. Если же и Спартак и Динамо победят в своих следующих встречах, Торпедо уже не может рассчитывать на второе место. Следовательно, если Торпедо все-таки займет второе место, а Спартак не станет чемпионом, то только потому, что он проиграл свой матч.

б) Если в мире существует зло, то Бог, если он всеведущий, должен знать об этом. Если Бог знает о существовании зла, но не может его исправить, то он не всемогущий. Если же он может его исправить, но не исправляет, то он не всеблагой. Но Бог по определению является всеведущим, всеблагим и всемогущим. Следовательно, если зло существует, то оно будет им исправлено.

Обратите внимание, что в рассуждении про Таню и Эрику мы опирались на некоторые изначально данные условия (шаги 1 - 3). Полученное заключение справедливо лишь для этих условий, но не является логическим законом (теоремой) само по себе. Теперь необходимо ввести еще два определения:

Доказательством называется вывод из пустого множества не исключенных посылок.

Теоремой (логическим законом) называется последняя формула в доказательстве.

Другими словами, доказать теорему – значит вывести ее из пустого множества не исключенных посылок.