Решение задач по математике | Математическая логика контрольная | Matematiku5
Вузы по математике Готовые работы по математике Как писать работы по математике Примеры решения задач по математике Решить задачу по математике online

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


Задание:

Доказать, что следующий предикат является (или не является) (примитивно) рекурсивным:

«х есть геделев номер частного случая схемы логических аксиом (10)»

 

Теоретическая часть:

Каждому символу u произвольной теории первого порядка K следующим образом поставим в соответствие положительное число g(u), называемое гёделевым номером символа u.

Предложение3.17. Отношения, которые можно получить из примитивно рекурсивных (или рекурсивных) с помощью пропозицио­нальных связок и ограниченных кванторову также примитивно ре — курсивны (соответственно рекурсивны); применение ограниченных [х-операторов или к примитивно рекурсивным (рекур­сивным) отношениям приводит к примитивно рекурсивным (рекурсив­ным) функциям.

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

;

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.  Лекции и семинары

Наташа

Автор

Наташа — контент-маркетолог и блогер, но все это не мешает ей оставаться адекватным человеком. Верит во все цвета радуги и не верит в теорию всемирного заговора. Увлекается «нефрохиромантией» и тайно мечтает воссоздать дома Александрийскую библиотеку.

Распродажа дипломных

 Скидка 30% по промокоду Diplom2020

А ты боишься COVID-19?

 Пройди опрос и получи промокод