Операции навешивания кванторов

   
На этом шаге мы рассмотрим операции навешивания кванторов.

   
В логике предикатов кроме операций отрицания, дизъюнкции, конъюнкции, импликации и эквивалентности, рассматриваются и операция навешивания квантора всеобщности и квантора существования.

   
Пусть на множестве М ≠ ∅ задан одноместный предикат 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)

   
На следующем шаге мы рассмотрим примитивно рекурсивный предикат.



Вы можете оставить комментарий, или Трекбэк с вашего сайта.

Оставить комментарий