Математическая логика и теория алгоритмов. Контрольная работа. Вариант №1. 2-й семестр. 2-й курс

Контрольная работа по дисциплине Математическая логика и теория алгоритмов. Вариант 1.
Исчисление высказываний

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


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

Вариант 1: Если подозреваемый совершил кражу, то либо кража была тщательно подготовлена, либо имелся соучастник. Если бы кража была тщательно подготовлена, то был бы соучастник. Значит, подозреваемый не виновен в краже.

Решение:

Исчисление предикатов

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

Теория алгоритмов

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

q1*1^x*01^y*0=>q0*1^y*01^x*0

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

f(x,y)=x^y+2+y.

Зачтена в январе 2018 года без замечаний.