Пусть 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