Предикаты, кванторы

Предикат есть функция, определенная на некотором множестве и принимающая одно из двух значений: истина (И) или ложь (Л).

Из простых предикатов с помощью логических операций можно строить и более сложные предикаты.

Пусть P (x ₁ ,…,x_k)- предикат, определенный на множестве D; é P ùозначает множество истинности предиката Р, т.е. множество всех наборов (a ₁ ,…,a_k) длины k элементов множества D, на кото­рых предикат Р принимает значение И.

Пусть Р(x ₁ ,…,x_k) и R(x ₁ ,…,x_k) - два предиката, определен­ных на множестве D. Тогда é Р ù é R ù, é P ùé R ù, D ^k \ é Р ù есть множества истинности предикатов
Р V R, Р & R, ù Р соответственно.

Пусть P(x,x ₁ ,…,x_k) есть (k+1)-местный предикат, определенный на множестве D. Запись ($ х) Р(х,х₁,...,х_k) будем понимать как "су­ществует такой элемент х из D, для которого P(x,x_l,...,x_k) истин­но"; ("x) P (x,x ₁ ,…,x_k) - "для всех х из D P(x,x_l,...,x_k) истин­но". Скажем, что предикаты

Q(x_l,...,x_k) = ($ х)Р(x,x ₁ ,…,x_k),

R (x ₁ ,…,x_k) = (" х)Р(x,x ₁ ,…,x_k)

получены из предиката P(x,x₁,...,x_k) навешиванием квантора соот­ветственно существования и общности на предикат P(x,x_l,...,x_k) по переменной х. Переменная х в выражении (Qx)P(x,x_l,...,x_k) находи­тся в области действия квантора (Qx). Навешивание квантора сущес­твования или квантора общности по некоторой переменной на (k+l)-местный предикат, содержащий эту переменную, приводит к другому предикату, местность которого на единицу меньше.

Переменная х, находящаяся в области действия квантора (Qx), называется связанной. В противном случае переменная х свободна.

Пример. D = {0,1,2,...} - множество натуральных чисел. Опре­делим на множестве D следующие предикаты:

Рr(х) - х есть простое число;

Ev(x) - число х четно;

Div(x,y) - число х делит число у;

х = у - число х равно числу у;

х £ у - число х меньше или равно числу у;

х = 2 - число х совпадает с двойкой;

Q(x,y) есть ù (х = 1) & ù (x = у) & Div(x,y);

Р(у) есть ($ x) Q (x, y).

Тогда ($ х)Рr(х) - истинное, (" х)Рr(х) - ложное, Р (2) - ложное, Р(4) - истинное высказывания.

Пусть D = {a _l ,a ₂ ,...,a_k} - конечное множество из k элементов и Р(х) - предикат, определенный на D.

Утверждение. Справедливы следующие равенства:

($ x) Р (x) = Р (a ₁) V Р(а₂) V... V P(a_k).

(" x) Р (х) = P (a ₁) & Р(а₂) &... & P(a_k).

Доказательство. Установим первое равенство. Пусть ($ х) Р(х) истинно. Тогда существует х = а_i Î D, для которого P (а _i) истинно. Отсюда P(a ₁ ) V... V P(a_k) истинно.

Пусть Р(a ₁ ) V... V P(a_k) истинно. Тогда для некоторого i, 1 £ i £ k, P (a_i) истинно; поэтому существует x = а _i Î D, для которого Р (а_i) истинно, отсюда
($ х)Р(х) истинно.

Установим второе равенство. Пусть (" х)Р(х) истинно. Тогда для всякого х из D Р(х) истинно, т.е. истинны P(a ₁ ),...,P(a_k), откуда истинно P(a ₁ ) &... & P(a_k). Пусть теперь P(a ₁ ) &... & P(a_k) истинно, т.е. истинны Р(а ₁ ),...,P(a_k). Отсюда получаем, что для всякого x из D Р(х) истинно, т.е. (" х)Р(х) истинно.

Утверждение доказано.

Аналогично доказываются следующие равенства.

($ x)P(x,x ₁ ,...,x_k) =

(" x)P(x,x ₁ ,...,x_k) =

Переменная х может стоять на любом аргументном месте предиката Р. Если кванторов несколько, то они элиминируются (устраняются) постепенно. Например,

(" x)($ y) P (x,y)=("x)(

Замечание. Пусть D есть некоторое множество и множество К Í D ⁿ. Проекция К на оси i₁,...,i_p есть множество

Проекция множества К на оси i_l,...,i_p может быть получена вычеркивани­ем (стиранием) во всех наборах (x₁,...,,...,,... ,х_n) из К всех координат, кроме

Пусть P (x ₁ ,…,x_k,x) - (k+1)-местный предикат, определенный на множес-тве D. Пусть k -местный предикат

Q (x ₁ ,…,x_k) = ($ x) P (x ₁ ,…,x_k,x).

Пусть é P ù = {(x ₁,... ,x_k,x) Î D^k+1: P(x ₁ ,...,x_k,x) истинно} и é Q ù = {(x ₁,…, x_k) Î D ^k: Q (x ₁,…, x_k) истинно} есть множества истинности предикатов Р и Q. Тогда é Q ù= é P ù.

Таков теоретико-множественный смысл квантора существования.