§ 3. Связанные и свободные переменные. Свойства операций навешивания кванторов.

Операции навешивания кванторов можно применять не только к одноместным предикатам, но и к n-местным, причем не одну, а обе и не один раз, а k=n раз, в результате чего будем получать n-k местные предикаты.

Например. Если на переменную х двухместного предиката Р(х,y) навесить квантор общности, то получим одноместный предикат (х) Р(х, y). Если на переменные х и y двухместного предиката Р(х, y) навесить оба квантора, то получим выражение (х)(  y) (Р(х, y), которое будет нуль-местным предикатом или высказыванием.

Определение. Пусть дан n-2 местный предикат (х₁) (х₂) (Р(х₁, х₂,...,х_n), на две переменные которого навешаны кванторы.

Переменные, на которые навешаны кванторы, называются связанными, а переменные без кванторов называются свободными.

Понятия связанных и свободных переменных употребляются не только в математической логике, но и в других разделах математики, например в выражении a_n переменная n является связанной, а k- свободной.

Основные свойства операций навешивания кванторов.

Теорема 1. Пусть на конечном множестве М = {a₁, a₂, ...,a_k} задан n-местный предикат Р(х₁, х₂, ...,х_n), тогда n-1 местный предикат (х₁) (Р(х₁, х₂,...,х_n)  Р(а₁, х₂, ..., х_n)  P(a₂, x₂, ..., x_n)  ...  P(a_k, x₂, ..., x_n).

Теорема 2. Пусть на конечном множестве M = {a₁, а₂, ..., а_l} задан n-местный предикат Р(х₁, х₂,...,х_n), тогда n-1 местный предикат (х₁)Р(х₁, х₂,...,х_n)  Р(а₁, х₂, ..., х_n)  P(a₂, x₂, ..., x_n) ... P(a_k, x₂, ..., x_n).

Очевидно, что эти два свойства позволяют выражать операции навешивания кванторов через операции “” и ““ для случая n-местных предикатов.

Пример. Пусть двухместный предикат P(x,y) задан на конечном множестве M = {a₁, а₂, а₃}. Выразить операции навешивания кванторов через операции “” и ““. т.1

Рассмотрим высказывание (х) (y)P(x,y)  (х) ((y)P(x,y))  (y)Р(а₁,y) (y)Р(а₂,у) (y)Р(а₃,y)  (P(a₁,a₁) P(a₁,a₂) P(a₁,a₃))  (P(a₂,a₁) (P(a₂,a₂) (P(a₂,a₃)) (P(a₃,a₁) (P(a₃,a₂) (P(a₃,a₃)).

Теорема 3. n-1 местный предикат (х₁)Р(х₁, х₂,...,х_n) тождественно истинен тогда и только тогда, когда n местный предикат Р(х₁, х₂,...,х_n) является тождественно истинным.

Теорема 4. n-1 местный предикат (х₁)Р(х₁, х₂,...,х_n) тождественно ложен тогда и только тогда, когда n местный предикат Р(х₁, х₂,...,х_n) является тождественно ложным.

§ 4. Формулы алгебры предикатов и их основные виды.

Определение 1. Формулой алгебры предикатов называется выражение, состоящее из n-местных предикатов, n-k местных предикатов со связанными и свободными переменными, соединенными семью логическими операциями или частью из них.

Пример. (х) F(x,y); F(x)  H(x); F(x,y) (x)H(x,y).

Определение 2, 3. Формула алгебры предикатов, заданная на множестве М, называется выполнимой (опровержимой), если при некоторой подстановке вместо предикатных переменных конкретных предикатов, заданных на множестве М, она обращается в выполнимый (опровержимый) предикат.

Определение 4,5. Формула алгебры предикатов, заданная на множестве М, называется ТИ (ТЛ), если при всякой подстановке вместо предикатных переменных любых конкретных предикатов, заданных на множестве М, она обращается в ТИ (ТЛ) предикат.