Предикаты, кванторы, их область действия. Свободные и связанные переменные

Предикат – это логическая функция предметных переменных. Предикат от n аргументов называют n – местным предикатом. Например: на множестве натуральных чисел N имеется два трёхместных предиката: S (x, y, z) = 1 x + y = z (предикат суммы), P (x, y, z) = 1 x y = z (предикат произведения)

Кроме операций логики высказываний в логике предикатов применяется ещё и операция связывания квантором.

Квантор общности: . ( x) Q (x) = 1, если Q (x) = 1 для каждого x из множества, на котором определён предикат Q(x). Читается этот предикат так: «для каждого x Q (x)». Это высказывание уже не зависит от x. Например, ( x) R (x,x) – истинное высказывание, а ( x) R (x,x) – ложное.

Квантор существования: . ( x) Q (x) = 1, если существует x такое, что Q (x) = 1. Читается этот предикат так: «существует x такое, что Q (x)». Это высказывание уже не зависит от x. Например, ( x) (C (x) & H (x)) – истинное высказывание, а ( x)( R (x,x)) – ложное.

Слово в алфавите логики предикатов называется формулой, если оно символ предиката. Такая формула называется атомарной. Все переменные атомарных формул свободные, связанных переменных нет.

Если A – формула, то A тоже формула. Свободные и связанные переменные формулы ( A) - это соответственно свободные и связанные переменные формулы A.

Если A и B – формулы и нет таких предметных переменных, которые были бы свободны в одной формуле и связаны в другой, тогда (A B), (A B), (A & B), (A ~ B) есть формулы, в которых свободные переменные формул A и B остаются свободными, а связанные – связанными.

Если A – формула, содержащая свободную переменную x, тогда ( x)A и ( x)A тоже формулы. Переменная x в них связана. Остальные переменные, которые в формуле A свободны, остаются свободными и в формулах ( x)A и ( x)A. Переменные, которые в формуле A связаны, остаются связанными и в этих двух формулах. Формула A в этих двух формулах называется областью действия кванторов. По определению формулы никакая переменная не может быть одновременно свободной и связанной.