Контрольная работа №1. Вариант №4

1. Пользуясь определением формулы исчисления высказываний проверить является ли выражение (A→(B→C))→((A→B)→(A→C)) формулой.
2. Записать рассуждение в логической символике и проверить правильность рассуждения методом Куайна, методом редукции и методом резолюций.
Если бы он хорошо знал английский язык или хотя бы она говорила помедленней, то он бы ее понял. Но он ее не понял. Значит, она как всегда говорила слишком быстро.
3. Пользуясь определением формулы логики предикатов проверить, что выражение является формулой. В формуле указать свободные и связанные переменные. Привести формулу к предваренной форме
(∃x∀yA(x,y))→(∀x∃yB(x,y))
4. Построить машину Тьюринга для перевода из начальной конфигурации в заключительную. На ленте МТ записаны нули и единицы, пустые ячейки содержат нули, x,y≥1. Проверить работу машины Тьюринга для конкретных значений x,y. Нарисовать граф, соответствующий построенной МТ.
q_1 1^x 〖01〗^y 0(⇒┬ {█(q_0 1^y,если x>2@q_0 1^x,если x≤2) )
5. Показать примитивную рекурсивность функции f(x,y).
f (x,y)={█(x,y<5,@x+1,y≥5)