Математическая логика и теория алгоритмов - контрольная работа (11 заданий).

Краткая выдержка из текста работы (Аннотация)

Решение Задания 1:

Функция g(x1,x2,,xn) является примитивно рекурсивной, так как получается из примитивно рекурсивных функций Ik(x1,x2,,xn) = xk (1  k  n) и f(x1,x2,,xn) с помощью операции суперпозиции (или подстановки):

g(x1,x2,,xn) = f(I2(x1,x2,,xn), I1(x1,x2,,xn), I3(x1,x2,,xn),, In(x1,x2,,xn))

Функция f(x1,x2,,xn) является примитивно рекурсивной по условию. Функции Ik(x1,x2,,xn) = xk (1  k  n) являются примитивно рекурсивными по определению.

Что и требовалось доказать.

Решение Задания 2:

Функция P(x,y) является общерекурсивной, так как получается из общерекурсивных функций o(x) = 0 и S(x,y) = x + y с помощью операции примитивной рекурсии:

P(x,0) = x0 = 0 = o(x)

P(x,y+1) = x(y+1) = xy + x = P(x,y) + x = S(P(x,y),x)

Функция S(x,y) = x + y является общерекурсивной, так как получается из общерекурсивных функций s(x) = x + 1 и I1(x) = x с помощью операции примитивной рекурсии:

S(x,0) = x + 0 = x = I1(x)

S(x,y+1) = x + (y+1) = (x + y) + 1 = S(x,y) + 1 = s(S(x,y))

Функции o(x) = 0, s(x) = x + 1 и I1(x) = x являются общерекурсивными по определению.

Что и требовалось доказать.

Содержание работы

Задание 1. Доказать, что если функция f(x1,x2,,xn) примитивно рекурсивна, то примитивно рекурсивна функция g(x1,x2,,xn) = f(x2,x1,,xn), т.е. перестановка аргументов.

Задание 2. Доказать, что следующая функция общерекурсивна. P(x,y)=xy

Задание 3. Доказать, что следующая функция общерекурсивна sgn(x), если

sgn(x)=1, если x0

sgn(x)=0, если x=0

Задание 4. Построить машину Тьюринга, которая применима ко всем словам в алфавите и {a0,a1,a2} делает следующее: любое слово x1x2xn, где xi=a1 или xi=a2 (i=1,2,,n), преобразует в слово x2x3xnx1.

Задание 5. Применяя правило подстановки, доказать, что доказуема формула

(AB)&BB

Задание 6. Применяя правило подстановки и правило заключения, доказать, что доказуема формула

AvAA

Использованная литература

1. Задание 7. Применяя производные правила вывода, показать, что доказуема формула
2. (AB)(AAvB)
3. Задание 8. Доказать, что H = {AB, BC} |- AC
4. Задание 10. Опишите машину Тьюринга, выполняющую операцию:
5. К (копирование) q101x00x0 | q001x01x0.
6. Задание 11. Опишите машину Тьюринга, выполняющую операцию:
7. Умножение: q101x+101y+10 | q0 01xy+10.
8. Задание 11. Опишите машину Тьюринга, выполняющую операцию:
9. Л (стирающая машина): q101x0 | q000x0.
10. Задание 12. По таблицам истинности найдите формулы, определяющие функции , , , . Упростите их. Постройте их КНФ, СКНФ, ДНФ, СДНФ. Для упрощенных формул постройте РКС.

Другие похожие работы

• Контрольная - Статистика финансов (контрольная)
• Контрольная - 4 блока по статистике (По полученной совокупности исходных значений анализируемого признака рассчитать следующие величины: средний уровень, дисперсию, коэф
• Реферат - Виды связи. Корреляция и корреляционные связи. Методы изучения и измерения взаимосвязей
• Курсовая - Метод случайной и механической выборки в изучении социально-экономических явлений
• Контрольная - Статистика (5 заданий)
• Контрольная - 8 задач по статистике, вариант 2, ГУУ. Распределение занятых региона по уровню средней месячной заработной платы в январе 2002 г.
• Контрольная - Статистика 2 задачи
• Контрольная - Статистическое изучение инфляции
• Контрольная - Контрольная по теории статистики, вариант 9, ОГУ. Имеются следующие данные о деятельности двух торговых фирм. Определите изменение объема товарооборота и с
• Контрольная - 3 задачи по статистике, МТУСИ. В таблице приведены данные о доходах и среднесписочной численности работников по цехам предприятия. Вычислить индексы произ