0 / 0 / 0
Регистрация: 15.02.2017
Сообщений: 42
1

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

26.05.2019, 14:16. Показов 3477. Ответов 3
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Доказать, что предикат ¬¬B⊃B является (или не является) (примитивно) рекурсивным:
«х есть геделев номер частного случая схемы логических аксиом (10)»
Не пойму с чего подходить к доказательству. Буду рад любой помощи!
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
26.05.2019, 14:16
Ответы с готовыми решениями:

Доказать, что предикат является (или не является) (примитивно) рекурсивным
Нужна курсовая по теме. Если у кого то есть хоть какая то информация - буду очень признателен. ...

Доказать, что предикат является примитивно рекурсивным
Доказать что предикат P(e,x,t) является примитивно рекурсивным: P(e,x,t) - машина Тьюринга с...

Доказать, что множество является рекурсивным
Доказать, что множество А={ n принадлежит множеству натуральных чисел, такое что в двоичной записи...

Докажите, что функция является примитивно-рекурсивной
Докажите, что функция является примитивно-рекурсивной f(x)=2^x

3
Эксперт по математике/физике
5004 / 3616 / 1162
Регистрация: 01.09.2014
Сообщений: 9,769
26.05.2019, 17:13 2
Цитата Сообщение от kolyanchi1 Посмотреть сообщение
Доказать, что предикат ¬¬B⊃B является (или не является) (примитивно) рекурсивным:
«х есть геделев номер частного случая схемы логических аксиом (10)»
Во-первых, задание должно формулироваться так: "Доказать, что следующий предикат является (или не является) (примитивно) рекурсивным: «х есть геделев номер частного случая схемы логической аксиомы (10) ¬¬B⊃B»".

Что вы знаете про примитивную рекурсивность предикатов вида "x есть геделев номер..." и про примитивно рекурсивные функции вообще?
0
0 / 0 / 0
Регистрация: 15.02.2017
Сообщений: 42
26.05.2019, 18:31  [ТС] 3
3D Homer, Я пробовал читать мендельсона по этим темам, но не уверен, что все понял. Еще отсюда читал инфу http://it.kgsu.ru/TI_6/rec_011.html
0
Эксперт по математике/физике
5004 / 3616 / 1162
Регистрация: 01.09.2014
Сообщений: 9,769
26.05.2019, 20:45 4
Лучший ответ Сообщение было отмечено kolyanchi1 как решение

Решение

С примитивно рекурсивными функциями (ПРФ), как и с машинами Тьюринга, есть довольно длинная последовательность рассмотрения все более сложных функций. Ее цель состоит в том, чтобы убедить читателя, что все это можно выразить ПРФ. Так, сначала показывается, что все знакомы арифметические функции — ПРФ, затем описывается, как представлять числами последовательности, показывается, что основные функции на последовательностях — ПРФ, затем рассматривается арифметизация логического синтаксиса, то есть представление формул числами, и доказывается, что все основные функции для анализа формул — ПРФ. Это действительно должно описываться в Мендельсоне, а также в следующих книгах:

Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. 4-е изд. М.: МЦНМО, 2012.

Булос Дж., Джеффри Р. Вычислимость и логика. — М.: Мир, 1994. Особенно глава "Арифметизация синтаксиса" или что-то в этом роде.

Результат состоит в том, что почти все нормальные функции являются ПРФ. Всюду определенные не-ПРФ нужно специально строить. Правда, все ПРФ всюду определенные. Интуитивно, операция примитивной рекурсии соответствует циклу for, но не while. Все, что можно вычислить в современном языке программирования с помощью for, можно выразить и через ПРФ. В частности, распознавание того, формула имеет вид той или иной схемы.
1
26.05.2019, 20:45
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
26.05.2019, 20:45
Помогаю со студенческими работами здесь

Доказать, что переменная xi является существенной хотя бы у одной из функций f(x^n) или g(x^n)
Пусть n ≥ 1 и функции f(x^n) и g(x^n) таковы, что сумма f(x^n) ⊕ g(x^n) обращается в 1 на нечетном...

Привести пример булевых функций или доказать, что такой не существует, которая одновременно является линейной
2)Привести пример булевых функций или доказать, что такой не существует, которая одновременно...

Доказать , что формула является противоречием
¬q∧p∧(p→ q)

Доказать, что множество является решёткой.
Рассмотрим множество L=N*B, где N – множество натуральных чисел, а В={0,1}. Положим (n,i)<=(m,j)...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru