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

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

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

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

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

Работа сдана в 2017г.
Зачтесна с первого раза без замечаний.

2017