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

1<2 = Я, Ъ<2 = Л, 1<2\/2<3 = Я.

Символ равенства = будет рассматриваться также как символ двуместного предиката, определенного на любом множестве.

Алфавит А рассматриваемого исчисления предикатов состоит из символов &, V, П, 3, V, (,), , =, Р, F, а, Р, у. Слова вида [Frx.. . .ар. . . 5) = («"И и (Ра"Р") будем обозначать через

Fn 1 Рп и называть соответственно т-местными функциональным и предикатным символами. Слова Xi = (v+i) [i = О, 1, . . .) будут называться предметными символами.

Задать «значение» какого-нибудь предметного символа Xi в некотором множестве Ж - значит поставить этому символу в соответствие какой-либо элемент из М. Задать значение какого-нибудь функционального символа Fn на множестве М - значит поставить ему в соответствие некоторую т-местную операцию, определенную на-М". Аналогично, задать «значение» предикатного символа Рп - значит поставить ему в соответствие какой-либо т-местный предикат на Ж.

Слова в алфавите А, имеюп1;ие определенный ниже специальный вид, называются термами и формулами. Понятие терма уже было введено в § 1: термами называются предметные символы а также выражения вида(uj, ... . . ., dm), где uj, . . ., - термы меньшей длины. Например, термами являются слова

Pi [Р\ {ч), Xl), Fl (xi, Хг, Xl),

тогда как.слово Р\ (xq) термом не является.

Пусть й - некоторый терм, и пусть значения всех входяш;их в запись й функциональных п предметных символов заданы на некотором хшожестве М. Тогда, выполняя над значениями предметных переменных последовательно операции, указанные в записи терма, получим в результате некоторый элемент из Л/, который и называется значением тердга й при заданных значениях предметных и функциональных переменных. Наиртгер, рассмотртг терм

F\ (хо, Fl (хо, Xl)).

Пусть значениями символов Хо, Xi, F\ Fl будут соответственно числа 3, 2 и операции -Ь, X, определенные на множестве натуральных чисел. Тогда значением терма будет

3 -Ь (3 X 2) = 9.

Если в каком-нибудь терме л значения всех функциональных и некоторых предметных символов фиксированы, то значение этого терма будет функцией от значений остальных предметных символов, участвуюп1;их в записи терма. Функции такого рода называются термальными или представляющимися термами.

Перейдем к определению понятия формулы.

а) Если Й1, . . ., йт - термы, то слова вида

Рп{&1, • • ., Йто), Йг==Йгз

называются первичными формулами. Пусть на некотором множестве М заданы значения предикатного символа и значения всех предметных и функциональных символов, встречающихся в записи термов Й1, . . ., й„. Тогда значения термов ui будут вполне определенными элементами «то из М и выражение Рп (fli, . . -i/am) [Р - значение символа Р) будет равно И или Л. Это и будет значением рассматриваемой первичной формуйы.

Предметный символ Xj называется связанным в слове Ь, если слово Ь содержит подслово (ЭхЛ или подслово (Vx;). Если предметный символ х;, встречающийся в слове Ь, не связан в этом слове, то он называЬтся свободным. В частности, в первичных формулах все предметные символы свободны. Определяемые ниже «значения» формул пе зависят от значений связанных неременных, а зависят лишь от значений свободных предметных символов и значений функциональных и предикатных символов.

б) Если S8 - формулы, причем ни один из связанных предметных символов любой из этих формул не встречается в другой, то формулами являются и слова

(3tS8), П-

Чтобы найти значение какой-либо из этих более сложных формул, надо найти значения формул 51, S и затем над эттш значениями (равными .0пли Л) произвести соответствующую операцию &, V, П-

в) Если 3( - формула, содерлчащая свободный предметный символ Xi, то формулами являются и слова

(VxOSf, {3xi)%.

Пусть задано множество М и на этом множестве заданы значения всех предикатных, функциональных и свободных предметных символов, входящих в форлгулу 3f. Тогда в формуле % будет не задано значение лишь одного свободного предметного символа Xj. Для каждого значения Xi ъ М я фиксированных значений остальных символов значение формулы 2( будет равно И или Л. Если Ш для любых значений Xi в 31 имеет значение И, то говорят, что формула (Vxj) 5( имеет значение И при фиксированных значениях входящих в нее свободных символов. Если же формула 51 хотя бы,при одном значении xt из 31 имеет значение Л, то формула (Vxt) Ч также имеет значение Л.

Аналогично, если при фиксированных значениях функциональных, предикатных и свободных предметных символов формулы {3xi) % формула 5( ложна для любых значений предметного символа Xi в множестве 3£, то говорят, что формула {3xi) % имеет значение Л для фиксированных значений символов. В противном случае говорят, что {3xi) 3f имеет значение И на 3£.

Слово % называется формулой, если оно является формулой в силу предписаний а), б), в).

При практическом использовании формул удобно употреблять сокращенную запись формул. Например, формулу П = Ь) обычно записывают в виде лфЪ. Внешние скобки обычно опускают; если Т - двуместный предикатный или функциональный символ, то вместо Т {х, у) пишут хТу и т. д. Часто вместо самих символов Xi, Рп, Fn пишут их обозначения. Говорят, например, «Пусть Р - двуместный предикатный символ, / - двуместный функциональный символ, х, у - предметные переменные. Рассмотри.м форму.лу

Р {х, f {у, х)) & Р {х, х)».

На самом деле при этом имеют в виду формулу, которая получится из (1) после замены символов P,f, у, х соответ-ствзгюшдми словалш в алфавите А.

Пусть Pi, . . ., Ps, Fy, . . ., Ft - обозначения предикатных и функциональных символов, имеющих задан-

ные числа мест, ш у, . . ., Уи - обозначения предметных символов. Задать модель сигнатуры о = (Ру, . . ., Ps, , Ft, Уу, . , Уи) - значит задать некоторое непустое множество 3£ (основное множество элементов модели) и задать на 3f значения всех указанных сигнатурных символов. Полученная модель обозначается через <Ж; Ру,. .. . . .,Ps, Fy, . . ., Ft,yy, . . ., Уи>- Например, <.Y; +>, где -j- есть символ бинарной операции, имеющий в качестве значения операцию сложения натуральных чисел, аЖ - совокупность всех натуральных чисел, есть аддитивная полугруппа натуральных чисел. В этой полугруппе формулы (Vxy) (х + у = у + х), {Уху) (3z) (х -Ь Z = г/ V \/ у + Z = х) истинны, а формула

(32) {X + Z = y)

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

Формула % называется формулой сигнатуры а, если все ее предикатные, функциональные и свободные предметные символы (за исключением знака =) содержатся в 0. Поэтому, если задана какая-то модель сигнатуры о, то каждая формула сигнатуры а будет на этой модели истинной или ложной. Классом моделей сигнатуры о называется произвольная система моделей заданной сигнатуры. В частности, класс может состоять из одной конкретной модели, а может состоять и из «всех» моделей данной сигнатуры.

Формула 5( сигнатуры о называется истинной на некотором классе моделей сигнатуры а, если она истинна на каждой модели этого класса.

Согласно Тарскому, Мостовскому и Р.Робинсону [1] совокупность Т {Щ всех формул сигнатуры о, истинных на классе называется элементарной теорией класса .

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

Рассмотрим произвольную систему S каких-то форьгул заданной сигнатуры о. Совокупность К (S) всех дюделей сигнатуры 0J на которых истинна каждая формула спсте-

S, если Y имеет вид 9(-1Б, 5( в остальных случаях.

Затем показывается, что все тождественно истпнные формулы получаются с помощью операций вывода из аксц-

ом, т. е. что совокупность всех тождественно истинных формул порождается лшожеством аксиом с помощью операций вывода. Так как множество аксиом рекурсивно, а операции вывода являются рекурсивными функциями, то согласно теореме о порожденных множествах из п. 4,3 совокупность £ всех тождественно истинных формул рекурсивно перечислима..

Чтобы доказать теорему 1 в общем виде, обозначим через %fj, %i, . . . рекурсивную последовательность всех формул из 2. Известно, что формула % принадлежит Т [К (2)) тогда и только тогда, когда для некоторого п формула

..&п--Ч (3)

является тождественно истиниой. Поэтому мы составляем множество Ш всех формул вида (3), заставляя п пробегать натуральный ряд, а ( пробегать совокупность всех формул сигнатуры о. Множество рекурсивно перечислимо. Поэтому рекурсивно перечислимо и его пересечение с множеством всех тождественно истинных формул. Пусть So, 1, ... - формулы этого пересечения, имеет форму g-o & 5i • • < Snj потому Т {К (S)) будет состоять из членов рекурсивно перечислимой последовательности 50,, • п, • •, лто итребовалось.

Теорема 2 (Чёрч [2]). Совокупность £ всех тождественно истинных формул исчисления предикатов является креативным (и потому нерекурсивным) множеством.

Для краткости обозначим точкой бинарный функциональный символ Fl и рассмотрпм класс ф всех полугрупп, определяемый аксиомой (2). Согласно теореме Поста - Маркова (п. 13.1) существует полугрзшповое исчисление с порождающими элементами . . ., х„и определяющими соотношениями

Й1 = bi, йо = tV2, . . ., в,, = Ь.5

такое, что дгножество U всех слов, эквивалентных некоторому подходящему слову а, является креативным. Каждое слово XiXi, . . . Xi этого полугруппового исчисления мы блдем рассматривать как терм {[xi-xi-Xi. . . -xi.

Из определения эквивалентности слов в ф следует, что слово й эквивалентно слову г тогда и только тогда, когда

мы S, называется классом моделей, определенным системой аксиом 2. Система 2 называется выполнимой, если класс К [Ъ) ш пуст. В противном случае система 2 называется невыполнимой.

Например, пусть • служит обозначением некоторой бинарной операции. Тогда аксиома

(Уххгз) {{ххХо)-х = Хх-{хг-х)) (2)

выражает ассоциативность операции • и класс моделей, определяемый указанной аксиомой, есть класс нолзгрупп с операцией •.

Каждая аксиома системы 2 и каждая формула теории Т {К (2)) являются словами в конечном алфавите А. Поэтому имеет смысл ставить вопрос об алгоритмической природе совокупностей 2, Т [К (2)): будут ли они рекурсивными, креативными и т. п.. Нижеследуюш;ие две фундаментальные теоремы дают ответ на этот вопрос в основных случаях.

Теорема 1 (Гильберт - Гёдель). Если 2 - рекурсивно перечислимая система формул заданной сигнатуры а, то элементарная теория Т [К (2)) также рекурсивно перечислима.

Для доказательства сначала рассматривается cobokjti-ность £ вообще всех тождественно истинных формул (любой сигнатуры). В курсах математической логики (см., например, Гильберт и Бернайс [1]) показывается, что формулы £ могут быть получены следующим способом. Выделяется некоторый класс тождественно истинных формул, называемых аксиомами исчисления. В разных курсах этот класс выбирается по-разнолгу. Однако всегда оказывается вполне очевидным, что аксиомы образуют рекурсивное множество. Затем указывается конечное число особых «правил вывода». Одно из них (правило силлогизма) имеет вид: если даны формулы 3( и 5( S8, то образуем формулу Ъ. По существу эти правила являются irpoCTO словарными функциялш, притом рекурсивными в алфавите А. Например, правилу силлогизма соответствует такая функция: