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

Пусть P(x_i,x₂,...,x_n) — n-местный предикат, определенный на М. Зафиксируем x_i=а. Определим (n-1)-местный предикат Q(x₁,x₂,...,x_{k_1}, x_k+1,x_n) следующим образом: Q(x₁,x₂,...,x_{k_i}, _xk+i,x_n)=P(x₁,x₂,...,x_k+1.,a,x_k+1, x_n). Говорят, что предикат Q(x₁,x₂,...,x_k-1, x_k+1,x_n) получен из предиката P(x₁,x₂,...,x_n) фиксацией значения i-й переменной:x_i =а.

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

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

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

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

Пусть P(x₁,x₂,...,x_n) — n-местный предикат, определенный на М. Зафиксируем в нем значения переменных x₁,x₂,...,x_k-1,x_k+1,x_n. На полученный одноместный предикат Q(x_K) навесим квантор всеобщности (существования), получим высказывание. Тем самым фиксированному набору значений переменных x₁,x₂,...,x_{k_}i,_xk+i,x_n с помощью квантора всеобщности (существования) поставлено в соответствие высказывание. Говорят, что этот (n-1)-местный предикат переменных x₁,x₂,...,x_k.₁,x_k+1,xn получен из исходного предиката P(x₁,x₂,...,х_n) навешиванием квантора всеобщности (существования) по k-й переменной. Этот предикат обозначают: x_KP(x₁,x₂,...,x_n) (х_к P(x₁,x₂,...,x_n)). Об к-й переменной (которой уже нет) говорят, что она связана квантором всеобщности (существования).

Обычно, связки и кванторы упорядочиваются по приоритету следующим образом ┐,, , &, 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

Дата добавления: 2014-01-04