Предикатные формулы.

Предикатные формулы (формулы логики предикатов) вводятся следующим образом:

всякая элементарная формула есть предикатная формула:

если А и В — предикатные формулы, то суть предикатные формулы. Если А — предикатная формула и — предметная переменная, то суть предикатные формулы;

выражение есть предикатная формула в том случае, если оно есть элементарная формула или построено из элементарных формул последовательным применением правил а) и b).

Предикатные формулы, не являющиеся элементарными формулами, называются составными предикатными формулами.

Для обозначения формул логики предикатов будем употреблять большие буквы латинского алфавита, напечатанные жирным шрифтом: А, В, С, Р, Q и т. д.

В формулах формула А называется областью действия кванторов соответственно.

Обычно принимают соглашения об опускании скобок. Кроме того, считают, что кванторы связывают сильнее остальных операций. Поэтому формулу можно записать так: .

ОПРЕДЕЛЕНИЕ. Предикатная формула называется общезначимой, если после замены входящих в нее элементарных формул любыми предикатами получается тождественно истинный предикат.

ОПРЕДЕЛЕНИЕ. Предикатные формулы называются равносильными, если после замены входящих в них элементарных формул любыми предикатами получаются равносильные предикаты. Записывать равносильность формул А и В будем так: .

Легко доказать, что предикатная формула общезначима тогда и только тогда, когда А и В — равносильные предикатные формулы.

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

соответствуют равносильности логики предикатов

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

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

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