Определение
Если P – k-местный предикатный символ языка L, а суть термы, то выражение P( ) называется атомарной (или элементарной) формулой.
В частности, если P – пропозициональная буква (0-местный предикатный символ), то P сама по себе является атомарной формулой.
Определение
i) Каждая атомарная формула есть формула;
ii)
,
т.е. если уже построена формула A,
то разрешается построить новую формулу
;
подобным образом следует трактовать и
следующий пункт:
iii)
,
где
– любая логическая связка;
iv)
,
т.е. если уже построена формула A,
и x
– произвольная переменная языка L,
то разрешается построить новую формулу
;
так же следует трактовать и следующий
пункт:
v)
.
В
формулах вида
,
выражение
или
называют кванторной
приставкой,
x
– переменной
кванторной приставки,
а формулу A
– областью
действия кванторной приставки.
Как уже отмечалось, вхождение переменной x в формулу A может быть связанным (если оно попадает в область действия квантора по x или в саму кванторную приставку с переменной x) или свободным.
Заметим, что одна и та же переменная может иметь и свободные, и связанные вхождения в одну и ту же формулу. Переменная x называется свободной переменной формулы A, или параметром A, если x входит (хотя бы один раз) свободно в A. Формула, не содержащая параметров, называется замкнутой (она является высказыванием).
Свободные и связанные переменные играют различные роли в формуле. Во-первых, вместо связанной переменной нельзя подставить конкретное значение – получится бессмысленное выражение. Во-вторых, связанная переменная не имеет самостоятельного значения, ее можно заменить на другую переменную, и смысл формулы от этого не изменится.
Все
формулы:
,
,
- выражают
один и тот же предикат, одну и ту же
функцию от x,
z.
Такая операция называется переименованием
связанной переменной.
При переименовании связанной переменной смысл формулы не меняется, если при этом никакая свободная переменная в любой подформуле данной формулы не может после переименования оказаться связанной.
Например,
если в формуле
мы решим заменить переменную y
на переменную x,
то получится формула
,
которая имеет совершенно иной смысл,
чем исходная формула. Формула
зависит уже лишь от одного параметра
z,
а не от двух. Причина состоит в том, что
после неудачного переименования
связанной переменной y
первое вхождение переменной x,
которое раньше было свободным, стало
связанным. Это явление называют коллизией
переменных
при переименовании связанных переменных.
Коллизия переменных недопустима.
Главным рабочим инструментом в логике предикатов, как и в логике высказываний, служит понятие равносильности формул.
Определение
Формулы
Ф
и Y
равносильны
(Ф
Y),
если:
множества их свободных переменных совпадают;
при любом замещении входящих в формулы Ф и Y предикатных символов конкретными предикатами эти формулы переходят либо в один и тот же предикат, либо в высказывания, имеющие одно и то же истинностное значение (последнее – в случае, когда Ф и Y замкнуты, т.е. множества их свободных переменных пусты).
Разумеется, все вхождения одного и того же предикатного символа как в Ф, так и в Y должны замещаться одним и тем же предикатом.