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

1. Пользуясь определением формулы исчисления высказываний проверить является ли данное выражение формулой.
(A→(B→C))→((A→B)→C)

2. Записать рассуждение в логической символике и проверить правильность рассуждения методом Куайна, методом редукции и методом резолюций.
Если бы он ей не сказал, она бы не узнала. А не спроси она его, он бы и не сказал ей. Но она узнала. Значит, она его спросила.

3. Пользуясь определением формулы логики предикатов проверить, что выражение является формулой. В формуле указать свободные и связанные переменные. Привести формулу к предваренной форме
(∀x∃yQ(x,y))→((∃y∀xP(x,y))→Q(x,y))

4. Построить машину Тьюринга для перевода из начальной конфигурации в заключительную. На ленте МТ записаны нули и единицы, пустые ячейки содержат нули, x,y≥1. Проверить работу машины Тьюринга для конкретных значений x,y. Нарисовать граф, соответствующий построенной МТ.
q_1 1^x 〖01〗^y 0⇒{█(q_0 1^x,если x>y@q_0 1^y,если x≤y)

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

Вид работы: Контрольная работа
Оценка: Зачет
Проверил: Мачикина Елена Павловна
Дата оценки: Июня 2018 г.