Математическая логика и теория алгоритмов - контрольная работа (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 являются общерекурсивными по определению.

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

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

(AB)(AAvB)

Задание 8. Доказать, что H = {AB, BC} |- AC



Задание 10. Опишите машину Тьюринга, выполняющую операцию:

К (копирование) q101x00x0 | q001x01x0.



Задание 11. Опишите машину Тьюринга, выполняющую операцию:

Умножение: q101x+101y+10 | q0 01xy+10.



Задание 11. Опишите машину Тьюринга, выполняющую операцию:

Л (стирающая машина): q101x0 | q000x0.



Задание 12. По таблицам истинности найдите формулы, определяющие функции , , , . Упростите их. Постройте их КНФ, СКНФ, ДНФ, СДНФ. Для упрощенных формул постройте РКС.