Контрольная работа. Математическая логика и теория алгоритмов. Вариант №8.

1. Исчисление высказываний
Пользуясь определением формулы исчисления высказываний проверить является ли данное выражение формулой.

(A (BC))((AB)C)
2. Записать рассуждение в логической символике и проверить правильность рассуждения методом Куайна, методом редукции и методом резолюций

Если бы он ей не сказал, она бы не узнала. А не спроси она его, он бы и не сказал ей. Но она узнала. Значит, она его спросила.
3. Пользуясь определением формулы логики предикатов проверить, что выражение является формулой. в формуле указать свободные и связанные переменные. Привести формулу к предваренной форме:

(xyQ(x,y))((yxP(x,y))Q(x,y))
4. Теория алгоритмов
Построить машину Тьюринга для перевода из начальной конфигурации в заключительную. На ленте МТ записаны нули и единицы, при этом пустые ячейки содержат нули, x,y≥1. Проверить работу машины Тьюринга для конкретных значений x,y. Нарисовать граф, соответствующий построенной МТ.

q_1 1^x 〖01〗^y 0⟹{█(q_1 1^x,если x>y@q_0 1^y,если x≤y) 





5. Показать примитивную рекурсивность функции f(x,y)

f(x,y)=(x+y)mod2

Декабрь, 2015 г. Работа зачтена.