Определение. Если P – k-местный предикатный символ языка L, а суть термы, то выражение P() называется

Определение

Если 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, которое раньше было свободным, стало связанным. Это явление называют коллизией переменных при переименовании связанных переменных. Коллизия переменных недопустима.

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

Дата добавления: 2014-01-06