На этом шаге мы рассмотрим операции навешивания кванторов.
В логике предикатов кроме операций отрицания, дизъюнкции, конъюнкции, импликации и эквивалентности, рассматриваются и операция навешивания квантора всеобщности и квантора существования.
Пусть на множестве М ≠ ∅ задан одноместный предикат p(x).
Определение. Будем говорить, что выражение вида ∀x p(x) на множестве M представляет собой истинное высказывание, тогда и только тогда, когда p(x) истинно для любого элемента x∈M.
Из определения следует, что если p(x) истинно на множестве M, то высказывание ∀xp(x) тоже истинно на этом множестве; и в случае, когда p(x) ложно на множестве M, то высказывание ∀xp(x) - тоже является ложным на данном множестве.
Определение. Будем говорить, что выражение ∃xp(x) на множестве M представляет собой истинное высказывание, тогда и только тогда, когда p(x) - истинно хотя бы для одного элемента из этого множества.
Очевидно, если p(x)= 0, то ∃xp(x) = 0; и если p(x)<>0, то ∃xp(x) = 1.
Пусть на множестве М ≠ ∅ задан двуместный предикат p(x,y).
Определение. Выражение ∀xp(x,y) при y0∈M представляет собой высказывание ∀xp(x,y0) = 1 (истинное высказывание) тогда и только тогда, когда p(x,y0) - истинно для любого элемента x∈M.
Определение. Выражение ∃xp(x,y) при заданном y0∈M представляет высказывание ∃xp(x,y0) = 1 (истинное высказывание), тогда и только тогда, когда p(x,y0) истинно хотя бы для одного элемента из множества M.
Таким образом, операции навешивания кванторов (всеобщности и существования) к двуместным предикатам приводит к одноместному предикату, т.е.:
p(y) = ∀xp(x,y0) (13)
p(y) = ∃xp(x,y0) (14)
Пример. Пусть задан двуместный предикат p(x,y) = ∃x (x<y), где x,y∈R.
Для проверки на истинность предиката, поступим следующим образом. Берем произвольный элемент y0 из множества M, подставляя в данный предикат, получим одноместный предикат: p(x) = (x<y0).
Тогда выражение ∃х (x<y0) является истинным высказыванием, так как во множестве действительных чисел всегда для произвольного элемента из этого же множества, найдется элемент меньше его.
Если взять предикат вида p(x,y) = ∀xp(x<y), где x,y∈R, то он является ложным во множестве R.
Если множество М, на котором рассматривается предикат р(х) является конечным множеством, т.е. M = {x1, ..., xn}, то высказывание вида ∀xp(x) тождественно равно высказыванию p(x1)∧, ..., , ∧p(xn) т.е. имеет место следующее равенство:
∀xp(x) = p(x1)∧, ..., , ∧p(xn) (15)
Аналогично, если множество М, на котором рассматривается предикат р(х) является конечным множеством, т.е. M = {x1, ..., xn}, то высказывание вида ∃xp(x) тождественно равно высказыванию p(x1)V, ..., , Vp(xn), т.е. имеет место следующее равенство:
∃xp(x) = p(x1)V, ..., , Vp(xn) (16)
На следующем шаге мы рассмотрим примитивно рекурсивный предикат.
