51.Закон пронесения квантора общности и существования через импликацию.

Следующие формулы алгебры логики предикатов равносильны :

1) = ;

2) = ;

3) = ;

4) = ;

Доказательство. Пусть А(х) – произвольный конкретный одноместный предикат, определённый на множестве М, а Р – произвольное конкретное высказывание.

1) Пусть = 1. Тогда согласно определению 11 ≡1. Отсюда нетрудно показать, что либо А(х) ≡ 0, либо Р = 1. А это значит, что либо = 0, либо Р = 1. В любом из этих случаев = 1.

Пусть теперь = 0. Тогда согласно определению 11 1. А это значит, что А(х) 1 и Р = 0. Тогда = 1 и Р = 0. Отсюда = 0.

2) Пусть =1. Тогда согласно определению 11 0. Тогда либо Р = 1, либо А(х) 1. В любом случае =1.

Пусть теперь = 0. Тогда согласно определению 12 ≡0. А это значит, что А(х) ≡ 1 и Р = 0. Отсюда = 1 и Р = 0. А это значит, что = 0.

3) Пусть =1. Тогда согласно определению 11 ≡1. Отсюда либо Р = 0, либо А(х) 1. Следовательно, либо

Р = 0, либо = 1. В любом случае = 1.

Пусть теперь = 0. Тогда согласно определению 11 1. Тогда Р = 1 и А(х) 1. Отсюда Р = 1 и = 0. Следовательно = 0.

4) Пусть = 1. Тогда согласно определению 12 0. Отсюда либо Р = 0, либо А(х) 0. Следовательно, либо

Р = 0, либо =1. А это значит, что существует = 1.

Пусть теперь = 0. Тогда согласно определению 12 ≡ 0. Отсюда Р = 1 и А(х) ≡ 0. Следовательно Р = 1 и = 0. А это значит, что = 0. Теорема доказана.

52.Закон удаления квантора общности и введение квантора существования.

Теорема (законы коммутативности для кванторов):Следующие формулы алгебры логики предикатов равносильны:

1) = ;

2) .

Доказать, что формула является тавтологией.

Известно, что

Тогда

53. Детерминированные функции и графическое изображение (примеры).

Функция y = из называется детерминированной, если каково бы ни было число t и каковы бы ни были последовательности а и b такие, что a(1)=b(1), a(2)=b(2), … a(t)=b(t) значения функций α, β, где α= , β= представляют собой последовательности, у которых тоже совпадают первые t членов, т. е. α(1) = β(1), α(2) = β(2), …, α(t) = = β(t).

Множество всех детерминированных функций обозначим через .

- дерево.

Построена она следующим образом. Возьмём произвольную вершину , которую назовём корнем дерева. Из неё проведём N рёбер, которые образуют первый ярус. Из концов каждого из рёбер также проведём N рёбер, которые образуют второй ярус и т. д. Рёбра каждого пучка нумеруются слева направо числами 0, 1,…, N-1 или их значениями в k-ичной системе счисления.

Далее, каждому ребру в построенном дереве произвольным образом припишем одно из чисел множества {0, 1,…, k-1}. В результате получим так называемое нагруженное дерево.

Теорема 1 Функция из будет детерминированной тогда и только тогда, когда она может быть задана с помощью нагруженного дерева.

Пример . Ясно, что и число ребер, выходящих из вершин равно .