Кванторы, их свойства.

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

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

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

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

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

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

Обычно, связки и кванторы упорядочиваются по приоритету следующим образом ┐,, , &, V,

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

Теорема 2.3. (основные равносильности, содержащие кванторы) Имеют место следующие равносильности:

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

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

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

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

x(P(x) V Q(y)) = xP(x) VxQ(y) , x(P(x)&Q(y) = xP(x) & xQ(y)

Для любого двухместного предиката уxP(x, у) xyP(x, у) = 1