ГОТОВЫЕ ДИПЛОМНЫЕ РАБОТЫ, КУРСОВЫЕ РАБОТЫ, ДИССЕРТАЦИИ И РЕФЕРАТЫ
Математическая логика и теория алгоритмов - контрольная работа (11 заданий). | |
| Автор | Ольга |
| Вуз (город) | Москва |
| Количество страниц | 10 |
| Год сдачи | 2007 |
| Стоимость (руб.) | 650 |
| Содержание | Задание 1. Доказать, что если функция f(x1,x2,…,xn) примитивно рекурсивна, то примитивно рекурсивна функция g(x1,x2,…,xn) = f(x2,x1,…,xn), т.е. перестановка аргументов.
Задание 2. Доказать, что следующая функция общерекурсивна. P(x,y)=xy Задание 3. Доказать, что следующая функция общерекурсивна sgn(x), если sgn(x)=1, если x0 sgn(x)=0, если x=0 Задание 4. Построить машину Тьюринга, которая применима ко всем словам в алфавите и {a0,a1,a2} делает следующее: любое слово x1x2…xn, где xi=a1 или xi=a2 (i=1,2,…,n), преобразует в слово x2x3…xnx1. Задание 5. Применяя правило подстановки, доказать, что доказуема формула (AB)&BB Задание 6. Применяя правило подстановки и правило заключения, доказать, что доказуема формула AvAA |
| Список литературы | Задание 7. Применяя производные правила вывода, показать, что доказуема формула
(AB)(AAvB) Задание 8. Доказать, что H = {AB, BC} |- AC Задание 10. Опишите машину Тьюринга, выполняющую операцию: К (копирование) q101x00x0 | q001x01x0. Задание 11. Опишите машину Тьюринга, выполняющую операцию: Умножение: q101x+101y+10 | q0 01xy+10. Задание 11. Опишите машину Тьюринга, выполняющую операцию: Л (стирающая машина): q101x0 | q000x0. Задание 12. По таблицам истинности найдите формулы, определяющие функции , , , . Упростите их. Постройте их КНФ, СКНФ, ДНФ, СДНФ. Для упрощенных формул постройте РКС. |
| Выдержка из работы | Решение Задания 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) = x0 = 0 = o(x) P(x,y+1) = x(y+1) = xy + 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 являются общерекурсивными по определению. Что и требовалось доказать. |