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

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

Зададим сначала алфавит символов, их которых будем составлять формулы: предметные переменные: х, у, z, xi, yi,zi (i – натуральное число)$ предикатные буквы: P, Q, R, …; символы операций – отрицания, конъюнкции, дизъюнкции, импликации, эквиваленции, суммы по модулю два; кванторы общности и существования; вспомогательные символы – скобки, запятая.

Определение. Всякий нуль-местный предикатный символ – формула. Всякий n–местный предикатный символ – формула. Если F – формула, а x - предметная переменная, то "x(F) и $x(F) – формулы. Если F1 и F2 – формулы, то - формулы. Никаких других формул в логике предикатов нет.

Определение. Формулы, определенные в п. 1 и 2, называются элементарными. Формулы, не являющиеся элементарными, называют составными.

Пример 62. Р; Q(x, y, z); R(x1, x2) – элементарные формулы. "х (Р(x, y, z); "x ($y (P(x, y, z))); - составные формулы.

Формула F в формулах вида "x(F) и $x(F) называется соответственно областью действия квантора "x или $x.

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

Определение. Переменная называется свободной в формуле, если хотя бы одно ее вхождение в этой формуле свободно.

Определение. Формулы без свободных предметных переменных называются замкнутыми, а формулы, содержащие свободные переменные – открытыми.