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

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

(A→B)→((C→A)→(C→B))

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

Незнание правил дорожного движения не освобождает от ответственности в случае их несоблюдения. Для того чтобы нести ответственность нужно нарушать правила. Следовательно, знать правила нужно.

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

(∀yA(x,y)) ∨ (∃x∀yB(x,y))

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

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

Год сдачи: 2015
Оценка:Зачет