Математическая логика контрольная

Доказательство:

;

1)  g(x, y)

g(x,0)=1=S(N(x))

g(x, y+1)== ∙ x=f(g(x, y),x)

2)  x∙y ζ(x, y)

ζ(x,0)=0

ζ(x, y+1)=x(y+1)=xy+x=f(ζ(x, y)+(x))= f(ζ(x, y)+(x, y))

3)  x=y

Отношение х=у примитивно рекурсивно, так как его характеристическая функция совпадаетс функцией sg(|x-y|), которая в свою очередь примитивно рекурсивна так как:

|x-y|=(x-y)+(y-x) (подставновка) – рекурсия

sg(0)=0

sg(y+1)=1 — рекурсия

4)  x*y

Если число х = «представляет» последовательность положительных чисел, а число у= «представляет» последовательность положительных чисел, то число х*у= «представляет» последовательность , которая получается, если вторую из данных последовательностей записать непосредственно вслед за первой. Здесь мы имеем k+1=lh(x), m+1=lh(y) и bj=(y)j

Поэтому х*у=, следовательно, функция «*» является примитивно рекурсивной.

5)  Пусть R(x, y)- рекурсивное отношение. Обозначим через Q(x, z) отношение R(x, y). Тогда , где рекурсивная функция. Ограниченный квантор равносилен ограниченному квантору, который в свою очередь может быть получен с помощью подстановки из ограниченного квантора.

Функция принимает значение 1 при каждом у, для которого R(x, u) ложно при всех и принимает 0всякий раз, когда существует такое, при котором R(x, u) истинно.

Поэтому, если для данного z существуют числа у, меньшие чем z, и такие, что R(x, y) истинно, то значение функции равно числу целых неотрицательных чисел, меньших чем наименьшее из таких чисел у; в протвном случае значение функции будет рано z. но это значит, что = R(x, y). Следовательно, применение ограниченного квантора приводит к рекурсивной функции.

Список используемой литературы:

1.  Э. Мендельсон. Введение в математическую логику. М., 1971

2.  Лекции и семинары