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

Правила для правильно-сформированности.

Полезно иметь таблицу Правил Образования для правильно сформированных формул Такая таблица приведена ниже. На подготовительных этапах определяются символы чисел, переменные и термы. Эти три класса строчек являются ингредиентами правильно сформированных формул, но сами они не являются правильно сформированными. Минимальные правильно сформированные формулы — это атомы; существуют способы для соединения атомов. Многие из этих правил — рекурсивные и удлиняющие: в качестве вводных данных они берут элемент определенного класса и производят более длинный элемент того же класса. В этой таблице я использую «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 в нем свободна.

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

ОТРИЦАНИЯ.

Правильно сформированная формула перед которой стоит тильда также правильно сформирована.

Примеры: ~S0=0   ~Eb:(b+b)=S0   ~<0=0эSО=0>   ~b=S0.

Кванторный статус переменной (говорящий нам, свободна или квантифицирована эта переменная) не меняется при отрицании.

СОСТАВНЫЕ.

Если x и у — правильно сформированные формулы и при этом ни одна переменная, свободная в одной из них, не квантифицирована в другой, тогда все следующие формулы правильно сформированы: <x Λ y>, <x V y>,<x э y>

Примеры: <0=0э~0=0>    <b=bV~Ec:c=b>    <S0=0эАс:~Еь:(b+b)=c>

Кванторный статус переменной здесь не меняется.

КВАНТИФИКАЦИЯ.

Если u — переменная и x — правильно сформированная формула, в которой и свободна, то следующие строчки — также правильно сформированные формулы:Eu:x и Au:x.

Примеры: Ab:<b=bV~Ec:c=b>    Ac:~Eb:(b+b)=c    ~Ес:Sc=d.

ОТКРЫТЫЕ ФОРМУЛЫ содержат по крайней мере одну свободную переменную.

Примеры: ~c=c  b=b  <Ab:b=bΛ~c=c>

ЗАМКНУТАЯ ФОРМУЛА (суждение) не содержит свободных переменных.

Примеры: S0=0  ~Ad:d=0  Ec:<Ab:b=bΛ~c=c>

Это дает нам полную таблицу Правил Образования для правильно сформированных формул ТТЧ.