§ 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) является тождественно ложным.