ГЕДЕЛЬ, ЭШЕР, БАХ: эта бесконечная гирлянда - Хофштадтер Даглас Р. - Страница 70

Итак, мы перевели высказывание «7 — сумма двух положительных кубов»; теперь нам нужно записать его отрицание. Для этого мы должны только поставить тильду слева от него. (Заметьте, что не требуется отрицать каждый квантор в отдельности, хотя нам и надо получить высказывание «Не существует чисел b и c, таких, что…») Таким образом, мы получим:

~Eb:Ec:SSSSSSS0=(((Sb*Sb)*Sb)+((Sc*Sc)*Sc))

Однако нашей первоначальной целью было выразить свойства всех чисел, а не только 7. Для этого давайте заменим символ числа SSSSSSSO строчкой ((а*а)*а), являющейся переводом «а в кубе».

~Eb:Ec:((a*a)*a)=(((Sb*Sb)*Sb)+((Sc*Sc)*Sc))

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

Aa:~Eb:Ec:((a*a)*a)=(((Sb*Sb)*Sb)+((Sc*Sc)*Sc))

Таким же правильным переводом было бы:

~Eа:Eb:Eс:((а*a)*a)=(((Sb*Sb)*Sb)+((Sc*Sc)*Sc))

В строгом ТТЧ мы могли бы использовать a' вместо b и a'' вместо c; таким образом, формула приобрела бы вид:

~Ea:Ea':Ea'':((a*a)*a)=(((Sa'*Sa')*Sa')+((Sa''*Sa'')*Sa''))

Как насчет высказывания 1: «5 — простое число»? Мы перефразировали его следующим образом: «Не существует чисел a и b больших 1, таких, что 5 равнялось бы a умноженному на b.» Теперь мы можем это немного изменить: «Не существует чисел а и b таких, что 5 равнялось бы а плюс 2 умноженному на b плюс 2.» Это еще один трюк- поскольку а и b здесь — натуральные числа, эта формулировка кажется более адекватной. Далее, «b+2» может быть переведено как (b+SS0), но есть и более короткий способ записать то же самое: SSb. Точно так же, «c плюс 2» может быть записано как SSc. Теперь наш перевод становится совсем коротким:

~Eb:Ec:SSSSS0=(SSb*SSc)

Без тильды в начале это было бы утверждением того, что существуют два натуральных числа, которые, если их увеличить на два, дают при умножении 5. Тильда в начале это отрицает; таким образом, мы получаем утверждение того, что 5 — простое число.

Если бы вместо 5 мы хотели бы сказать то же самое про d плюс e плюс 1, самым экономным способом было бы заменить символ числа 5 на строчку (d+Se):

~Eb:Ec:(d+Se)=(SSb*SSc)

Мы снова получили открытую формулу; ее интерпретация — не истина и не ложь, а лишь некое утверждение о каких-то двух числах d и e. Обратите внимание, что число, выраженное строчкой (d+Se), больше d, так как мы добавили к d хотя и неопределенную, но положительную величину. Таким образом, если мы добавим к переменной e квантор существования, мы получим формулу, утверждающую, что

Существует некое простое число, большее d.

Ee:~Eb:Ec:(d+Se)=(SSb*SSc)

Осталось только добавить, что это свойство верно всегда, вне зависимости от d. Для этого мы должны добавить квантор общности для d:

Ad:Ee:~Eb:Ec:(d+Se)=(SSb*SSc)

Перед нами — перевод высказывания 5!

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

~Ac:Eb:(SS0*b)=c

Ac:~Eb:(SS0*b)=c

Ac:Eb:~(SS0*b)=c

~Eb:Ac:(SS0*b)=c

Eb:~Ac:(SS0*b)=c

Eb:Ac:~(SS0*b)=c

(Еще одна подсказка, либо четыре из них истинны и два ложны, либо, наоборот, два истинны и четыре ложны.)

Теперь давайте на минуту остановимся и переведем дыхание — а заодно подумаем, что означало бы иметь такую формальную систему, которая могла бы отличить все истинные высказывания от ложных. Для такой системы все эти строчки были бы просто некими формальными конструкциями, лишенными содержания (в то время как мы видим в них высказывания). Эта система была бы словно решето, сквозь которое проходили бы только конструкции определенного стиля — «стиля истины». Если вы сами имели дело с шестью формулами выше и отделили истинные от ложных, размышляя об их значении, вы сможете оценить, насколько тонкой должна быть система, которая сможет проделать то же самое, но чисто типографским путем! Граница, отделяющая истинные высказывания от ложных (записанных нотацией ТТЧ) вовсе не пряма — это граница со множеством предательских извилин (вспомните рис. 18). Математики смогли установить некоторые отрезки этой границы, работая над этим сотни лет. Представьте себе, как было бы здорово иметь типографский метод, который с гарантией мог бы поставить любую формулу по правильную сторону границы!

Полезно иметь таблицу Правил Образования для правильно сформированных формул Такая таблица приведена ниже. На подготовительных этапах определяются символы чисел, переменные и термы. Эти три класса строчек являются ингредиентами правильно сформированных формул, но сами они не являются правильно сформированными. Минимальные правильно сформированные формулы — это атомы; существуют способы для соединения атомов. Многие из этих правил — рекурсивные и удлиняющие: в качестве вводных данных они берут элемент определенного класса и производят более длинный элемент того же класса. В этой таблице я использую «x» и «у» как символы для правильно сформированных формул и «s», «t» и «u» — как символы для всех остальных строчек ТТЧ. Нет нужды говорить, что никакой из этих пяти символов сам по себе не является символом ТТЧ.

СИМВОЛЫ ЧИСЕЛ

0 — это символ числа.

Символ числа, слева от которого стоит S — также символ числа.

Примеры: 0 S0 SS0 SSS0 SSSS0 SSSSS0

ПЕРЕМЕННЫЕ

a — это переменная Если забыть об аскетизме, то b, c, d, и e — тоже переменные. Переменная со штрихом справа — также переменная.

Примеры: а b' c" d''' e''''

ТЕРМЫ

Термами являются символы чисел и переменные. Терм, слева от которого стоит S — это также терм.

Если s и t — термы, то (s+t) и (s*t) — также термы.

Примеры: 0  b  SSa'  (S0*(SS0)+c))  S(Sa*(SbSc))

ТЕРМЫ могут быть подразделены на две категории:

(1) ОПРЕДЕЛЕННЫЕ термы. В них нет переменных.

Примеры: 0  (S0+S0)  SS((S0*SS0)+(S0*S0))

(2) НЕОПРЕДЕЛЕННЫЕ термы. В них есть переменные.

Примеры: b  Sa(b+S0)  (((S0+S0)+S0)+e)

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

АТОМЫ

Если s и t — термы, то s+t — атом.

Примеры: S0=0  (SS0+SS0)=SSSS0  S(b+c)=((c*d)*e)

Если атом содержит переменную u, то u в нем свободна.

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