Шаг 10.
Понятие рекурсии.
Операции навешивания кванторов

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

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

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

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




Предыдущий шаг Содержание Следующий шаг