Кванторы

Пусть P(x1,x2…xn) — n-местный предикат, определенный на M. Зафиксируем xi=a. Определим (n-1)-местный предикат Q(x1,x2…xk-1,xk+1,xn) следующим образом: Q(x1,x2…xk-1,xk+1,xn)=P(x1,x2…xk-1,xk+1,a,xn). Говорят, что предикат Q(x1,x2…xk-1,xk+1,xn) получен из предиката P(x1,x2…xn) фиксацией значения i-й переменной: xi=a.

Определение 1. Пусть Р(х) — одноместный предикат. Поставим ему в соответствие высказывание, обозначаемое ∀xP(x) (читается «для любого х Р(х)»), которое истинно тогда и только тогда, когда Р(х) — тождественно истинный предикат. О высказывании ∀xP(x) говорят, что оно получено из предиката Р навешиванием квантора всеобщности по переменной х.

Определение 2. Пусть Р(х) — одноместный предикат. Поставим ему в соответствие высказывание, обозначаемое ∃xP(x) (читается «существует х Р(х)»), которое ложно тогда и только тогда, когда Р(х) — тождественно ложный предикат. О высказывании ∃xP(x) говорят, что оно получено из предиката Р навешиванием квантора существования по переменной х.

Замечание 1. Обозначения ∀ и ∃ для кванторов — это перевернутые латинские буквы А и Е соответственно, которые являются первыми буквами в английских словах All — все, Exist — существовать.

Замечание 2. Высказывания можно считать предикатами, не содержащими переменных, т. е. 0-местными предикатами (или предикатами любой местности).

Пусть P(x11,x2…xn) — n-местный предикат, определенный на M. Зафиксируем в нем значения переменных x1,x2…xk-1,xk+1,xn. На полученный одноместный предикат Q(xk) навесим квантор всеобщности (существования), получим высказывание. Тем самым фиксированному набору значений переменных x1,x2…xk-1,xk+1,xn с помощью квантора всеобщности (существования) поставлено в соответствие высказывание. Говорят, что этот (n-1)-местный предикат переменных x1,x2…xk-1,xk+1,xn получен из исходного предиката P(x11,x2…xn) навешиванием квантора всеобщности (существования) по k-й переменной. Этот предикат обозначают: ∀xkP(x1,x2…xn) (∃xkP(x1,x2…xn)). Об k-й переменной (которой уже нет) говорят, что она связана квантором всеобщности (существования).

Пример 1. Пусть D(x1,x2) = «Натуральное число х1 делится (без остатка) на натуральное число х2.» — двухместный предикат. Навесим последовательно на его переменные кванторы. Ясно, что:

1) ∀x1∀x2D(x1,x2)=0

2) ∀x2∀x1D(x1,x2)=0

3) ∃x1∃x2D(x1,x2)=1

4) ∃x2∃x1D(x1,x2)=1

5) ∀x1∃x2D(x1,x2)=1

6) ∃x2∀x1D(x1,x2)=1

7) ∃x1∀x2D(x1,x2)=0

8) ∀x1∃x2D(x1,x2)=1

Таким образом (сравнением 7 и 8 в последнем примере) мы доказали теорему.

Обычно, связки и кванторы упорядочиваются по приоритету следующим образом ¬, ∀, ∃, &, v, →, ∼.

Теорема 1. Разноименные кванторы, вообще говоря, не коммутируют.

Теорема 2. (основные равносильности, содержащие кванторы).

Имеют место следующие равносильности:

1. Законы де Моргана

¬(∀xP(x))=∃x¬(P(x))

¬(∃xP(x))=∀x¬(P(x))

2. Коммутативность

∀x∀yP(x,y)=∀y∀xP(x,y)

∃x∃yP(x,y)=∃y∃xP(x,y)

3. Дистрибутивность

∀x(P(x)&Q(x))=∀xP(x)&∀xQ(x)

∃x(P(x)&Q(x))=∃xP(x)&∃xQ(x)

4. Ограничение действия кванторов

∀x(P(x)vQ(y))=∀xP(x)vQ(y)

∃x(P(x)&Q(y))=∃xP(x)&Q(y)

5. Для любого двухместного предиката

∃y∀xP(x,y)→∀x∃yP(x,y)=1