"ГЕДЕЛЬ, ЭШЕР, БАХ: эта бесконечная гирлянда" - читать интересную книгу автора (Хофштадтер Даглас Р.)

ГЛАВА VII: Исчисление Высказываний

Слова и символы

ПРЕДЫДУЩИЙ ДИАЛОГ напоминает «Двухголосную инвенцию» Льюиса Кэрролла. В обоих диалогах Черепаха отказывается использовать обычные повседневные слова в их обычном повседневном значении — по крайней мере, когда ей это невыгодно. В предыдущей главе был предложен один из возможных взглядов на парадокс Кэрролла. В этой главе мы проделаем при помощи символов то, что Ахиллу не удалось проделать словами. Иными словами, мы построим такую формальную систему, один из символов которой будет действовать так, как Ахилл хотел заставить действовать Черепахино «и»; другой символ будет вести себя так, как должны были вести себя слова «если… то…». Кроме того, мы будем иметь дело со словами «или» и «не». Рассуждения, зависящие исключительно от правильного употребления этих четырех слов, называются пропозициональными рассуждениями.

Алфавит и первое правило исчисления высказываний

Я буду представлять эту новую формальную систему, называемую исчислением высказываний, в форме загадки, объясняя сначала лишь часть и предоставляя читателю догадываться о некоторых вещах самому. Начнем со списка символов:

lt; gt;

P Q R '

#923; V э ~

[ ]

(прим. символ «э» заменяет символ импликации «superset of»)


 Первое правило нашей системы таково:

ПРАВИЛО ОБЪЕДИНЕНИЯ: Если x и у — теоремы системы, то строчка lt;x #923; ygt; — тоже теорема.

Это правило соединяет две теоремы в одну. Оно должно напомнить вам о предыдущем Диалоге.

Правильно сформированные строчки

У нас будет еще несколько правил вывода; вскоре я их объясню. Однако сначала необходимо определить некое подмножество всех строчек, а именно — правильно сформированные строчки. Они будут определены рекурсивным путем, начиная с атомов. АТОМЫ: P, Q, и R называются атомами. Новые атомы получаются путем добавления штрихов справа от старых атомов, таким образом, получаются R', Q'', R''' и т. д. Это дает нам бесконечные ресурсы атомов. Все атомы правильно сформированы.

Далее, у нас имеются четыре рекурсивных правила.

ПРАВИЛА ОБРАЗОВАНИЯ: Если x и у правильно сформированы, то следующие четыре строчки также правильно сформированы.

(1) ~x

(2) lt;x #923; ygt;

(3) lt;x V ygt;

(4) lt;x э ygt;

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

P атом

~P по правилу (1)

~~P по правилу (1)

Q' атом

~Q' по правилу (1)

lt;P #923; ~Q'gt; по правилу (2)

~lt;P #923; ~Q'gt; по правилу (1)

lt;~~P э Q'gt; по правилу (4)

lt;~lt;P #923; ~Q'gt;Vlt;~~P э Q'gt;gt; по правилу (3)

Последняя строчка может показаться весьма сложной, но на самом деле, она построена всего лишь из двух компонентов — двух предыдущих строчек. Каждая из них, в свою очередь, построена из предыдущих строчек… и так далее. Происхождение любой правильно сформированной строчки может быть прослежено до ее элементарных составляющих — атомов. Для этого вы просто применяете правила в обратном порядке до тех пор, пока это возможно. Этот процесс рано или поздно должен кончиться, поскольку каждое правило вывода — удлиняющее правило; идя в обратном порядке, мы непременно дойдем до атомов.

Таким образом, метод разложения строчек служит проверкой их правильности. Это — нисходящая процедура разрешения для правильно-сформированности. Можете проверить, как вы поняли эту процедуру, найдя, какие из ниже приведенных строчек правильно сформированы:

(1) lt;Pgt;

(2) lt;~Pgt;

(3) lt;P #923; Q #923; Rgt;

(4) lt;P #923; Qgt;

(5) lt;lt;P #923; Qgt;#923;lt;Q~ #923; Pgt;gt;

(6) lt;P #923; ~Pgt;

(7) lt;lt;P Vlt;Q э Rgt;gt;#923;lt;~P V ~R'gt;gt;

(8) lt;P #923; Qgt;#923;lt;Q #923; Pgt;

(Ответ. Те строчки, номера которых являются числами Фибоначчи, сформированы неправильно; остальные — правильно.)

Еще правила вывода

Сейчас мы познакомимся с остальными правилами вывода, при помощи которых строятся теоремы системы. Во всех этих правилах символы «x» и « всегда относятся к правильно сформированным строчкам.

ПРАВИЛО РАЗДЕЛЕНИЯ: Если lt;x #923; ygt; — теорема, то и x и у — также теоремы.

Вероятно, вы уже догадались, что значит символ «#923;». (Подсказка: это то самое слово, что причинило столько проблем в Диалоге.) Из следующего правила вы сможете вывести значение тильды («~»):

ПРАВИЛО ДВОЙНОЙ ТИЛЬДЫ: Строчка «~~» может быть выброшена из любой теоремы. Она также может быть вставлена в любую теорему, если при этом получается правильно сформированная строчка.

Правило фантазии

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

Чтобы использовать это правило, вы должны записать любую приглянувшуюся вам правильно сформированную строчку x, и затем спросить себя: что бы произошло, если строчка x действительно оказалась бы аксиомой или теоремой? После чего вы предлагаете системе ответить на этот вопрос; это значит, что вы начинаете вывод, используя x как первую строчку. Пусть у будет последней строчкой. От x до у включительно все является фантазиейxпосылка фантазии, а у — ее результат. Следующий шаг — выход из области фантазии; мы узнали, что

Если бы x являлось теоремой, то у также являлось бы теоремой.

Вы можете спросить: «Где же здесь настоящая теорема?» Это строчка:

lt;x э ygt;

Обратите внимание на то, как эта строчка напоминает предложение, напечатанное выше.

Чтобы отметить вход и выход в область фантазии, мы будем использовать квадратные скобки «[» и «]», соответственно. Таким образом, увидев левую квадратную скобку, вы будете знать, что вы «проталкиваетесь» в область фантазии, и следующая строчка будет посылкой. Увидев правую квадратную скобку, вы будете знать, что вы «выталкиваетесь» обратно из воображаемого мира, и что предыдущая строчка была результатом. Удобно (хотя и не необходимо) начинать те строчки вывода, что относятся к области фантазии, с нового абзаца.

Ниже приводится иллюстрация правила фантазии в действии. Строчка P служит посылкой. (На самом деле, P не является теоремой, но для нас это не важно — мы просто задаем вопрос «а что, если бы она была теоремой?») Мы воображаем следующее:

[  проталкивание в область фантазии

  P  посылка

  ~~P  результат (по правилу двойной тильды)

]  выталкивание из области фантазии

Наша фантазия показывает, что:

если бы P было теоремой, ~~P также было бы теоремой.

Теперь мы постараемся «затолкать» это высказывание русского языка (метаязык) в рамки формальной нотации (предметный язык): lt;P э ~~Pgt;. Таким образом, наша первая теорема исчисления высказываний должна подсказать вам интерпретацию символа «э».

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

[ проталкивание в область фантазии

  lt;P #923; Qgt; посылка

  P отделение

  Q отделение

  lt;Q #923; Pgt; соединение

] выталкивание из области фантазии

lt;lt;P #923; Qgt;эlt;Q #923; Pgt;gt; правило фантазии

Необходимо помнить, что только последняя строчка здесь является настоящей теоремой; все остальное — чистая фантазия.

Рекурсия и правило фантазии

Как вы могли догадаться из рекурсивной терминологии («проталкивание» и «выталкивание»), правило фантазии может быть использовано рекурсивно — так что могут существовать фантазии внутри фантазий, фантазии, вложенные друг в друга три раза, и так далее. Это означает, что для этого правила существуют различные уровни реальности, так же как и во вставленных друг в друга рассказах или фильмах. Когда вы выталкиваетесь из фильма, вставленного внутрь другого фильма, на мгновение вам кажется, что вы достигли реального мира, хотя вас все еще отделяет от него один уровень. Точно так же, когда вы выталкиваетесь из фантазии внутри фантазии, вы находитесь в «более реальном», чем предыдущий, мире, хотя он и отстоит на один уровень от настоящего.

Предупреждение «НЕ КУРИТЬ», висящее в кинотеатре, не относится к актерам, играющим в фильме: реальный мир не проникает в фантастический мир фильмов. Однако в исчислении высказываний существует не только воздействие реального мира на фантазии, но и фантазий на вложенные в них более глубокие фантазии. Это свойство отражено в следующем правиле:

ПРАВИЛО ПЕРЕНОСА: В фантазию можно внести любую теорему из «реальности» одним уровнем выше и использовать ее там.

Это похоже на то, если бы табличка «НЕ КУРИТЬ» относилась не только к зрителям, но и ко всем актерам, и далее, к актерам «фильмов в фильме», если бы таковые имелись. (Внимание: переноса в обратном направлении не существует — теоремы из фантазии не приложимы к реальному миру! Иначе мы могли бы выдумать любую первую строчку фантазии и «вынести» ее в реальный мир в качестве теоремы.)

Чтобы показать, как действует правило переноса и как правило фантазии может быть применено рекурсивно, приведу следующий вывод:

[ проталкивание

  P посылка внешней фантазии

  [ снова проталкивание

    Q посылка внутренней фантазии

    P перенос P во внутреннюю фантазию

    lt;P #923; Qgt; объединение

  ] выталкивание из внутренней фантазии во внешнюю

  lt;Q эlt;P #923; Qgt;gt; правило фантазии

] выталкивание из внешней фантазии в реальный мир!

lt;P эlt;Q эlt;P #923; Qgt;gt;gt; правило фантазии

Обратите внимание на то, что для внешней фантазии я отступил на один абзац, в то время как для внутренней — на два; этим подчеркивается природа вставленных один в другой «уровней реальности». О правиле фантазии можно сказать, что оно вводит суждение, сделанное о системе, внутрь самой системы. Таким образом, можно сказать, что полученная нами теорема lt;x э ygt; — отображение внутри системы суждения о ней самой: «Если x — теорема, то у — также теорема». Более конкретно, lt;P э Qgt; интерпретируется как «если P, то Q» или, что одно и то же, «из P следует Q».

Перевернутое правило фантазии

В Диалоге Льюиса Кэрролла шла речь о высказываниях типа «если… то». В частности, Ахилл никак не мог убедить Черепаху принять за истинную вторую часть «если… то» высказывания, даже когда она приняла за истинные как все высказывание целиком, так и его первую часть. Следующее правило позволяет вам вывести вторую часть строчки «э», в том случае, если сама эта строчка и ее первая часть обе являются теоремами.

ПРАВИЛО ОТДЕЛЕНИЯ: Если x и lt;x э ygt; — теоремы, то у — также теорема.

Это правило часто зовется «Modus ponens», а правило фантазии — «Теоремой дедукции».

Интерпретация символов

Довольно загадок! Пора вытащить кота из мешка и открыть «значение» всех остальных символов нашей системы, если это вам еще не ясно. Итак, символ «#923;» действует в точности также, как обыкновенное «и». Символ «~» заменяет слово «не» в формальном отрицании. Уголки «lt;» и «gt;» являются группирующими скобками — их функция весьма напоминает функцию обычных скобок в алгебре. Основное различие в том, что в алгебре мы свободны вводить или не вводить скобки, согласно нашему вкусу и стилю, в то время как в формальной системе подобная анархия не допускается. Символ «V»  заменяет слово «или» (по латыни «Vel»). Имеется в виду так называемое включающее «или»; это означает, что lt;x V ygt; читается как «x или у — или оба сразу».

Единственные символы, которые мы еще не интерпретировали, это атомы. У них нет единственной интерпретации — их можно интерпретировать, как любое высказывание русского языка (если атом встречается несколько раз в одной и той же деривации, он должен быть интерпретирован всегда одинаково). Таким образом, например, правильно сформированная строчка lt;P #923; ~Pgt; может быть интерпретирована следующим образом:

Этот разум — Будда, и этот разум — не Будда.

Давайте теперь вернемся к теоремам, которые мы вывели до сих пор, и постараемся их интерпретировать. Первая теорема была lt;P э ~~Pgt;. Если интерпретировать P всегда одинаково, то мы получим следующее высказывание:

Если этот разум — Будда, то неверно, что этот разум — не Будда.

Обратите внимание, как я сформулировал двойное отрицание. В любом натуральном языке неловко повторять отрицание два раза — мы обходим это препятствие, выражая отрицание по-разному. Вторая наша теорема была lt;lt;P #923; Qgt;эlt;Q #923; Pgt;gt;. Пусть Q — высказывание «Этот огурец весит полкило»; тогда наша теорема читается как:

Если этот разум — Будда и этот огурец весит полкило, то этот огурец весит полкило и этот разум — Будда.

Третьей теоремой была lt;P эlt;Q эlt;P #923; Qgt;gt;gt;. Она разворачивается в структуру «если … то» с вложением:

Если этот разум — Будда то, если этот огурец весит полкило, то этот разум — Будда и этот огурец весит полкило.

Вы вероятно, заметили, что каждая теорема, будучи интерпретированной, выражает что-либо совершенно тривиальное и самоочевидное. (Иногда теоремы бывают настолько самоочевидными, что кажутся бессмысленными — и даже, как это ни парадоксально, ложными!) Может быть, это вас не впечатляет; но вспомните, сколько ложных высказываний, кишмя кишащих кругом, мы могли бы вывести — но не вывели. Система исчисления высказываний аккуратно ступает от истины к истины, осторожно избегая всех ложных высказываний, подобно человеку, который, переходя ручей и желая остаться сухим, осторожно ступает с камня на камень, следуя выложенной «тропинке», как бы извилиста она не была. Удивительно то, что в исчислении высказываний все делается исключительно типографским путем. «Внутри» системы нет никого, кто бы думал о значении строчек. Здесь все делается строго механически и бездумно.

Полный список правил

Мы еще не привели всех правил исчисления высказываний. Их полный список, включая три новые правила, приведен ниже.

ПРАВИЛО ОБЪЕДИНЕНИЯ: Если x и у — теоремы системы, то строчка lt;x #923; ygt; — также теорема.

ПРАВИЛО РАЗДЕЛЕНИЯ: Если lt;x #923; ygt; — теорема, то и x и у — также теоремы.

ПРАВИЛО ДВОЙНОЙ ТИЛЬДЫ: Строчка «~~» может быть выброшена из любой теоремы. Она также может быть вставлена в любую теорему, если при этом получается правильно сформированная строчка.

ПРАВИЛО ФАНТАЗИИ: Если, принимая x за теорему, можно вывести у, то lt;x э ygt; является теоремой.

ПРАВИЛО ПЕРЕНОСА: В фантазию можно внести любую теорему из «реальности» одним уровнем выше и использовать ее там.

ПРАВИЛО ОТДЕЛЕНИЯ: Если x и lt;x э ygt; — теоремы, то у — также теорема.

ПРАВИЛО КОНТРАПОЗИЦИИ: lt;x э ygt; и  lt;~y э ~xgt; взаимозаменяемы.

ПРАВИЛО ДЕ МОРГАНА: lt;~x #923; ~ygt; и ~lt;x V ygt; взаимозаменяемы.

ПРАВИЛО ЗАМЕНЫ: lt;x V ygt; и lt;~x э ygt; взаимозаменяемы.

Под «взаимозаменяемостью» здесь понимается следующее: если одно из двух выражений встречается в виде теоремы или части теоремы, оно может быть заменено на второе, и результат также будет теоремой.

Объяснение правил

Прежде чем рассматривать эти правила в действии, я хочу их коротко пояснить. Вы, вероятно, можете придумать примеры получше; поэтому я ограничусь только несколькими.

Правило контрапозиции показывает то, каким образом мы перевертываем условные предложения (обычно мы делаем это бессознательно). Например, буддистское изречение о Тропе — дороге к Мудрости:

Если вы изучаете ее, то вы далеко от Тропы,

означает то же самое, что

Если вы близко к Тропе, то вы ее не изучаете.

Правило Де Моргана может быть проиллюстрировано на примере хорошо знакомого нам высказывания «Флаг не движется и ветер не движется». Если P означает «флаг движется» и Q — «ветер движется», то комбинированное высказывание будет lt;~P #923; ~Qgt;, которое, согласно правилу Де Моргана, может быть заменено на ~lt;P V Qgt;: «Неверно, что флаг или ветер движутся». Никто не станет оспаривать, что это весьма осмысленное дзен-ключение…

Для иллюстрации правила замены возьмем высказывание «Либо туча зависла над горой, либо лунный луч проникает сквозь волны озера» — фраза, которую мог бы произнести дзен-буддистский мастер, пытаясь мысленно увидеть любимое озеро. Теперь держитесь крепче: правило замены утверждает, что это высказывание может быть заменено на мысль «Если туча не зависла над горой, то лунный луч проникает сквозь волны озера.» Это, может быть, и не Просветление, но это большее, что исчисление высказываний может нам предложить.

Игра с системой

Теперь давайте приложим эти правила к одной из предыдущих теорем и посмотрим, что у нас выйдет. Возьмем, к примеру, теорему lt;P э ~~Pgt;:

lt;P э ~~Pgt; старая теорема

lt;~~~P э ~Pgt; контрапозиция

lt;~P э ~Pgt; двойная тильда

lt;P V ~Pgt; замена

Новая теорема в интерпретации утверждает, что:

Либо этот разум Будда, либо этот разум не Будда.

Интерпретированная теорема снова оказалось истинным (хотя, может быть, и не таким уж удивительным) высказыванием.

Частичная интерпретация

Читая вслух теоремы исчисления высказываний, кажется естественным интерпретировать все, кроме атомов. Я называю это частичной интерпретацией. Например, частичной интерпретациейlt;P V ~ Pgt;  было бы:

P или не P

Хотя P здесь и не высказывание, приведенное полувысказывание все же звучит как истинное, поскольку мы можем легко вообразить на месте P любое предложение — и форма этой частичной интерпретации уверяет нас, что, независимо от нашего выбора, результатом будет истинное высказывание. Именно это — центральная идея исчисления высказываний: оно производит теоремы, которые, будучи частично интерпретированными, производят «универсально истинные полувысказывания». Независимо от того, как мы дополним интерпретацию, у нас получатся истинные суждения.

Топор Ганто

Теперь мы можем проделать более сложное упражнение, основанное на дзен-буддистстком коане под названием «Топор Ганто». Вот его начало:

Однажды Токусан сказал своему ученику Ганто «В нашем монастыре есть два монаха, которые прожили здесь много лет. Иди и проверь их». Ганто взял топор и пошел в хижину, где монахи занимались медитацией. Он поднял топор со словами. «Если вы скажете хоть одно слово, я отрублю вам головы; и если вы не скажете ни слова, я все равно отрублю вам головы».[13]

Если вы скажете хоть одно слово, я прерву этот коан; и если вы не скажете ни слова, я все равно прерву этот коан — поскольку хочу перевести его в нашу нотацию. Пусть «вы скажете слово» будет P, а «я отрублю вам головы» — Q. Тогда угроза Ганто записывается как lt;lt;P э Qgt;#923;lt;~P э Qgt;gt;. Что, если бы эта угроза являлась бы аксиомой? Ответом на этот вопрос служит следующая фантазия:

  (1) [ проталкивание

  (2)   lt;lt;P э Qgt;#923;lt;~P э Qgt;gt; аксиома Ганто

  (3)   lt;P э Qgt; разделение

  (4)   lt;~Q э ~Pgt; контрапозиция

  (5)   lt;~P э ~Qgt; разделение

  (6)   lt;~Q э ~~Pgt; контрапозиция

  (7)   [ снова проталкивание

  (8)     ~Q посылка

  (9)     lt;~Q э ~Pgt; перенос строки 4

(10)     ~P отделение

(11)     lt;~Q э ~~Pgt; перенос строки 6

(12)     ~~P отделение (строки 8 и 11)

(13)     lt;~P #923; ~~Pgt; объединение

(14)     ~lt;P V ~Pgt; Де Морган

(15)   ] выталкивание

(16)   lt;~Q э ~lt;P V~Pgt;gt; правило фантазии

(17)   lt;lt;P V ~Pgt; э Qgt; контрапозиция

(18)   [ проталкивание

(19)     ~P посылка (и результат!)

(20)   ] выталкивание

(21)   lt;~Р э ~Рgt; правило фантазии

(22)   lt;P V ~Pgt; правило замены

(23)   Q отделение (строки 22 и 17)

(24) ] выталкивание


Этот пример показывает, насколько мощно исчисление высказываний. Всего лишь за 24 шага мы логически вывели, что Q — иными словами, головы будут отрублены! (Зловещая примета: последнее использованное нами правило было правилом «отделения»…) Теперь, скажете вы, нет смысла продолжать коан, так как исход уже известен. Однако я передумал и не буду его прерывать — в конце концов, это настоящий дзен-коан! Итак, вот конец этого рассказа:

Оба монаха продолжали медитировать как ни в чем не бывало, словно они ничего не слышали. Тогда Ганто опустил топор и воскликнул: «Вы — настоящие дзен-буддисты!» Затем он вернулся к Токусану и рассказал о случившемся. «Я понимаю вашу идею», — сказал тот, — «но скажите мне, какова их идея?» «Тозан мог бы принять их в ученики, — ответил Ганто, — но они не должны быть приняты в ученики Токусаном».[14]

Понимаете ли вы мою идею? А как насчет идеи дзена?

Имеется ли разрешающий алгоритм для теорем?

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

Весьма важным здесь является вопрос о разрешающей процедуре — а именно, существует ли некий механический метод отличения теорем от не-нетеорем? Если да, то это будет означать, что теоремы исчисления высказываний не только рекурсивно перечислимы, но и рекурсивны. Оказывается, что алгоритм разрешения существует, и довольно интересный — таблицы истинности. Изложение этого метода увело бы нас слишком далеко в сторону; вы можете найти его почти в любой книге по логике. А как насчет дзен-буддистских коанов? Может ли существовать такая механическая процедура разрешения, которая отличала бы настоящий дзен-коан от всех остальных вещей?

Откуда мы знаем, что система непротиворечива?

До сих пор, мы только предполагали, что все теоремы, интерпретированные должным образом, производят истинные высказывания. Но знаем ли мы это наверняка? Можем ли мы это доказать? Иными словами, заслуживают ли наши интерпретации («и» для «#923;» и так далее) того, чтобы именоваться «пассивными значениями» символов? На это существуют два различных взгляда, которые можно назвать «осторожным» и «неосторожным». Я представлю это взгляды так, как я их понимаю; пусть их выразителей зовут, соответствено, «Осторожность» и «Неосторожность».

Осторожность: Мы будем знать наверняка, что при нашей интерпретации все теоремы получаются истинными, только тогда, когда сможем это доказать. Это вдумчивый и осторожный способ действия.

Неосторожность: Напротив, ОЧЕВИДНО, что все теоремы получаются истинными. Если вы в этом сомневаетесь, взгляните еще раз на правила системы. Вы увидите, что каждое правило заставляет символ действовать точно также, как должно действовать слово, им представляемое. Например, правило объединения заставляет символ «#923;» действовать как «и»; правило отделения заставляет «э» действовать также, как слова «если … то», и так далее. Если только вы не похожи в этом отношении на Черепаху, то легко узнаете в каждом правиле кодификацию схем, которыми пользуетесь в собственных мыслях. Поэтому, если вы доверяете собственным мыслям, вы ОБЯЗАНЫ верить в то, что все теоремы в интерпретации выходят истинными. Таково мое мнение. Я не нуждаюсь в дальнейших доказательствах. Если вы считаете, что какая-нибудь теорема может получиться ложной, значит вы думаете, что какое-то из правил неверно. В таком случае, покажите мне, какое именно?

Осторожность: Не могу, поскольку я не знаю точно, что там есть неверные правила — поэтому я не могу указать вам на одно из них Все же я могу вообразить себе следующую сцену. Следуя правилам, вы выводите теорему — скажем, x. Между тем, я, также следуя правилам, вывожу другую теорему — и предположим, у меня вышло ~x. Можете ли вы представить себе такое?

Неосторожность: Хорошо — представим себе, что такое произошло. Чем это вам помешает? Скажем, мы обе играем с системой MIU; у меня получилась теорема x, а у вас — xU. Можете вы представить такое?

Осторожность: Разумеется: и MI, и MIU — теоремы.

Неосторожность: И вас это не смущает?

Осторожность: Конечно, нет. Ваш пример просто смешон, поскольку теоремы MI и MIU не ПРОТИВОРЕЧАТ одна другой, в то время как строчки x и ~x в исчислении высказываний противоречивы.

Неосторожность: Хорошо — если только вы решили интерпретировать «~» как «не». Но что заставляет вас думать, что «~» должно быть интерпретировано именно так?

Осторожность: Сами правила. Их них видно, что единственной возможной интерпретацией для «~» является «не», единственной возможной интерпретацией для «#923;» — «и» и так далее.

Неосторожность: Иными словами, вы считаете, что правила описывают значения слов?

Осторожность: Именно так.

Неосторожность: И, несмотря на это, вы все еще цепляетесь за мысль, что обе x и ~x могут быть теоремами? Почему бы вам заодно не предположить, что ежи — это жабы, или что 1 равняется 2, или что луна сделана из зеленого сыра? Я, со своей стороны, не хочу даже и думать, что основные ингредиенты моего мыслительного процесса могут быть ошибочными — иначе мне пришлось бы усомниться в собственном анализе всего этого вопроса, и я бы совершенно запуталась.

Осторожность: Ваши аргументы притянуты за уши. Все же мне хотелось бы увидеть ДОКАЗАТЕЛЬСТВО того, что все теоремы истинны, или того, что x и ~x не могут быть теоремами одновременно.

Неосторожность: Желаете доказательства? По-моему, вы более хотите убедиться в непротиворечивости исчисления высказываний, чем в вашем собственном душевном здоровье. Любое мыслимое доказательство включало бы более сложные операции, чем те, что возможны в самом исчислении высказываний. И что бы это доказало? С вашим желанием доказать непротиворечивость исчисления высказываний вы напоминаете мне человека, который захотел выучить русский и потребовал для этого словарь, определяющий все простые слова через более сложные…

Снова Кэрролловский Диалог

Этот небольшой спор показывает, как трудно использовать логику и рассуждеения для защиты самой логики. В какой-то момент вы упираетесь в стенку, и вам ничего не остается, кроме как выкрикивать: «Я знаю, что я прав!» Мы снова столкнулись с вопросом, который Льюис Кэрролл так ярко проиллюстрировал в своем Диалоге: продолжать защищать схему собственного мышления до бесконечности невозможно. Рано или поздно наступает момент, когда приходится в нее просто поверить.

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

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

Ахилл: Если у вас имеется lt;lt;A #923; Bgt;э Zgt; и lt;A #923; Bgt;, то у вас наверняка есть Z.

Черепаха: Вы имеете в виду, что lt;lt;lt;lt;A #923; Bgt; эZgt;#923;lt;A #923; Bgt;gt; эZgt;, не так ли?

(Подсказка: то, что Ахилл считает правилом вывода, Черепаха туг же превращает в простую строчку системы. Используя только буквы А, В и Z, вы получите непрерывно удлиняющуюся рекурсивную структуру.)

Кратчайший путь и выведенные правила

Выводя теоремы исчисления высказываний, мы обычно вскоре изобретаем различные сокращения пути, строго говоря, не являющиеся частью системы. Например, если бы в какой-то момент нам понадобилась бы строчка lt;Q V ~ Qgt;, и при этом у нас уже имелась бы ранее выведенная строчка lt;P V ~ Pgt;, многие из нас действовали бы так, словно строчка lt;Q V ~ Qgt; уже выведена, так как мы знаем, что ее вывод в точности соответствует выводу lt;P V ~ Pgt;. Выведенная теорема используется здесь как «схема теорем» — форма для их отливки. Этот прием вполне допустим, поскольку он помогает нам выводить новые теоремы — но сам по себе он не является правилом исчисления высказываний. Скорее это вторичное, выведенное правило, часть нашего знания о системе. Конечно, то, что это правило всегда оставляет нас в области теорем, еще надо доказать — но тем не менее, это правило отличается от дериваций внутри системы. Оно является доказательством в ординарном, интуитивном значении этого слова — цепочка рассуждений, проведенная по способу I. Теория об исчислении высказываний является «мета-теорией», и ее результаты можно назвать «мета-теоремами» — Теоремами о теоремах. (Обратите внимание на заглавную букву в выражении «Теоремы о теоремах». Это — следствие нашего соглашения: мета-теоремы являются Теоремами (доказанными результатами), касающимися теорем (выводимые строчки).)

В исчислении высказываний можно найти множество других мета-теорем, или вторичных правил вывода. Вот, например, вторичное правило Де Моргана:

lt;~ V ~ ygt; и ~lt;x #923; уgt; взаимозаменяемы.

Если бы это было правилом системы, это значительно ускорило бы многие деривации. А что, если мы докажем, что оно верно — достаточно ли этого, чтобы использовать его в качестве еще одного правила вывода?

У нас нет причин сомневаться в истинности этого выведенного правила. Однако как только вы начинаете использовать выведенные правила в процедуре исчисления высказываний, формальность системы теряется, поскольку эти правила выведены неформально — вне системы. Формальные системы были предложены, как способ проследить за каждым шагом доказательства внутри единой строгой системы, чтобы каждый математик мог механически проверить работу своих коллег. Однако если вы готовы при малейшей возможности выскочить за рамки системы, то зачем ее вообще было создавать? Как видите, у подобных правил есть и отрицательная сторона.

Формализация высших уровней

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

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

Ошибки получаются, когда нам не удается четко разграничить работу внутри системы (способ M) и размышления о системе (способ I). Например, может показаться вполне разумным предположить, что, поскольку lt;P V ~ Pgt; (частично интерпретируемое как P или не P) — теорема, то одна из двух — либо P, либо не P, должна также являться теоремой. Но это совершенно неверно; не один из членов этой пары не является теоремой. Опасно считать, что символы можно свободно передвигать между разными уровнями — как, например, язык формальной системы и ее метаязык (русский).

Размышления о сильных и слабых сторонах системы

Мы только что познакомились с системой, предназначенной отразить часть архитектуры логического мышления. Эта система имеет дело с небольшим количеством простых и точных понятий. Именно простота и точность исчисления высказываний делает его таким привлекательным для математиков. Для этого есть две причины. (1) Его свойства можно изучать сами по себе (так геометрия изучает простые и неподвижные формы). Исчисление высказываний можно варьировать путем изменения различных символов, правил вывода, аксиом или схем аксиом и так далее. (Кстати, представленный здесь вариант исчисления высказываний был изобретен Г. Гентценом в начале 1930-х годов. Существуют другие версии, в которых используется единственное правило вывода — обычно, отделение — ив которых есть несколько аксиом или схем аксиом.) Изучение методов логического мышления при помощи элегантных формальных систем — это весьма привлекательная ветвь чистой математики. (2) Исчисление высказываний может быть легко расширено до включения других фундаментальных аспектов мышления. Это будет частично показано в следующей главе, где исчисление высказываний целиком будет включено в намного большую и глубокую систему, способную на сложные рассуждения в области теории чисел.

Доказательства и деривации

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

Обычно формальная деривация бывает крайне длинна по сравнению с соответствующей «естественной» мыслью. Это, конечно, плохо — но это та цена, которую приходится платить за упрощение каждого шага. Часто бывает, что деривация и доказательство «просты» в дополнении друг к другу. Доказательство просто в том смысле, что каждый шаг «кажется правильным», даже если мы и не знаем точно, почему; деривация проста, потому что каждый из мириада ее шагов так прост, что к нему невозможно придраться и, поскольку вся деривация состоит из таких шагов, мы предполагаем, что она безошибочна. Каждый тип простоты, однако, привносит свой тип сложности. В случае доказательств, это сложность системы, на которую они опираются — а именно, человеческого языка; в случае дериваций, это их астрономическая длина, делающая их почти невозможными для понимания.

Таким образом, мы считаем исчисление высказываний частью общего метода для составления искусственных структур, подобных доказательствам. Однако оно лишено гибкости или всеобщности, поскольку предназначено только для работы с математическими понятиями, которые, в свою очередь, жестко определенны. В качестве довольно интересного примера давайте рассмотрим деривацию, в которой посылкой фантазии является необычная строчка: lt;Р #923; ~ Рgt;. По крайней мере, ее частичная интерпретация звучит странно. Исчисление высказываний, однако, не задумывается над интерпретациями — вместо этого, оно просто манипулирует типографскими символами, а в типографском смысле в этой строчке нет ничего необычного.

Вот фантазия с данной строчкой в качестве посылки.

  (1) [ проталкивание

  (2)   lt;Р #923; ~Рgt; посылка

  (3)   Р разделение

  (4)   ~Р разделение

  (5)   [ проталкивание

  (6)     ~Q посылка

  (7)     Р переход, строка 3

  (8)     ~~Р двойная тильда

  (9)   ] выталкивание

(10)   lt;~Q э ~~Рgt; фантазия

(11)   lt;~P э Qgt; контрапозиция

(12)   Q отделение (строчки 4, 11)

(13) ] выталкивание

(14) lt;lt;P #923; ~Pgt; э Qgt; фантазия


Эта теорема имеет очень странную частичную интерпретацию:

Из P и не P вместе взятых следует Q.

Поскольку Q можно интерпретировать любым предложением, мы можем считать, что эта теорема утверждает, что «из противоречия следует что угодно»! Поэтому системы, основанные на исчислении высказываний, не могут содержать противоречий — противоречия мгновенно заражают всю систему, подобно глобальному раку.

Подход к разрешению противоречий

Это не похоже на человеческую мысль. Если вы обнаружите в своих рассуждениях противоречие; вряд ли это разрушит все здание вашего мышления. Вместо этого вы, скорее всего, попытаетесь найти те идеи или методы рассуждения, которые явились причиной противоречия. Иными словами, вы попытаетесь, насколько это возможно, выйти из ваших внутренних систем, приведших к противоречию, и попробуете их исправить. Маловероятно, что вы поднимете руки вверх и воскликнете: «Это показывает, что теперь я верю во все, что угодно!» — разве что в шутку.

В действительности, противоречия — это важный источник прогресса во всех областях жизни, и математика не является исключением. В прошлом, когда в математике обнаруживалось противоречие, математики тут же пытались найти виновную в этом систему, выйти из таковой, проанализировать ее и, если возможно, залатать прореху. Вместо того, чтобы делать математику слабее, нахождение и «починка» противоречивых систем только усиливали ее. Этот путь был долог и усеян ошибками, но в конце концов, он приносил плоды. Например, в средневековье предметом горячих споров была бесконечная последовательность

1-1 + 1-1 + 1-…

Существовали «доказательства», что эта серия равняется 0, 1, 1/2 — а может быть, и другим числам. Из подобных противоречивых результатов выросла более полная и глубокая теория бесконечных рядов. Более актуальный пример — противоречие, с которым мы сталкиваемся в данный момент; это противоречие между тем, как мы действительно думаем, и тем, как исчисление высказываний имитирует наше мышление. Это продолжает быть источником дискомфорта для многих логиков; множество творческих усилий было приложено к тому, чтобы улучшить исчисление высказываний, чтобы оно не было таким жестким. Одна из попыток, изложенная в книге А. Р. Андерсона и Н. Белнапа «Следствие» (A.R. Anderson amp; N.Belnap, «Entailment»),[15] включает «уместный подтекст», с тем, чтобы придать символу «если — то» действительную причинность или, по крайней мере, некоторую связь со смыслом. Взгляните на следующие теоремы исчисления высказываний:

lt;P э lt;Q э Pgt;gt;

lt;P эlt;Q V ~Qgt;gt;

lt;lt;Р #923; ~Рgt; э Qgt;

lt;lt;P э Qgt;Vlt;Q э Pgt;gt;


Эти и другие подобные теоремы показывают, что первая и вторая части суждений типа «если… то» вовсе не должны иметь никакой связи для того, чтобы быть доказанными в исчислении высказываний. С другой стороны, «уместный подтекст» ставит некоторые ограничения на контекст, в котором может действовать правило вывода. Опираясь на интуицию, он говорит нам, что «что-то может быть выведено из чего-то только в том случае, если эти части как-то соотносятся между собой». Например, строка 10 в деривации выше была бы невозможна в данной системе — и это, в свою очередь, заблокировало бы вывод строчки lt;lt;P #923; ~Pgt;эQgt;.

Более радикальные попытки полностью отказываются от поисков непротиворечивости и полноты, пытаясь взамен симулировать человеческое мышление со всеми его противоречиями. Подобные исследования уже не ставят своей целью дать математике прочный фундамент; они занимаются изучением процесса человеческой мысли.

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


Рис. 42. М. К. Эшер «Крабий канон» (1965)