4. Формулы логики предикатов

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

Определение 6.2. Множество Ф называется множеством формул логики предикатов, если удовлетворяет условиям:

1. O и I (эти две формулы называются тривиальными), ;

(2) , (такие формулы называются атомарными), есть множество всех предметных переменных, входящих в термы ;

3. если , то и , ;

4. если , то и , ;

5. если , , то , ;

6. если множество W удовлетворяет свойствам (1) – (5), то .

Замечания. (1) Определение множества формул снова индуктивное.

(2) Множество формул существует и единственно, доказательство этого факта снова аналогично многому, приведённому ранее.

(3) Символы отношений во многом аналогичны функциональным символам. Символ заменяет собой привычное ; на нём не написана арность отношения, так что в отсутствие коллизий всегда считается, что арность как раз соответствует количеству термов, стоящих следом за знаком отношения; формулой не является выражение .

(4) «Победив» «противоестественные кванторы», мы теперь можем (при желании) их восстановить, заменив в пункте (5) определения формулу на более общую .

(5) В формуле иксы, стоящие до и после буквы Е – различные! При этом оба вида иксов – связанные. Вообще, появление квантора слева «закрывает» (связывает!) переменную так же, как появление символа заканчивает использование x в качестве переменной интегрирования.

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

(7) В действительности почти никогда не требуется разрешать использовать в формулах все возможные символы функций и отношений. Как правило, рассматривается множество тех функций и отношений, которые предполагается использовать, у всех функциональных символов (явно или неявно) указывается количество аргументов, а у всех символов отношений – арность. Такой набор называется сигнатурой, и можно говорить о множествах формул данной сигнатуры.

(8) Равным образом, приведённый набор логических связок, использованных при построении формул (и даже кванторов, трудно представить, да? ) не является единственно возможным.

(9) Очень похожее на формулу выражение , и даже более определённое формулой не является, потому что неизвестно, сколько в ней переменных (как это – неизвестно? Их n штук ).

(10) Дав определения в терминах языка, полезно вернуться к скобочной записи функций и отношений, равно как и к обычным обозначениям логических связок: так понятнее .

Лемма 6.1. Для любой формулы множество её параметров определено однозначно.

Доказательство проводится индукцией по множеству формул. Пусть U – множество тех формул, для которых утверждение верно. Тогда и удовлетворяет условиям (1) – (5) из определения множества Ф: если для предыдущей формулы множество параметров было определено однозначно, то оно однозначно определено и для следующей, чуть более сложной (в определении прямо написано, чему оно равно ). Тогда, в силу условия (6), .

QED

Пример. Формула является таковой только при условии, что f – символ функции двух переменных, G – символ двухместного отношения, S – символ трёхместного отношения. При этом . Она является формулой потому, что формулами являются выражения , , , и . Последние две формулы являются атомарными. Они, в свою очередь, являются формулами потому что выражения , , x, y, z являются термами. Далее, .