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

Задача 1. Построить таблицу истинности логической формулы.
3. F=(A⟶B)⟶((C⟶A)⟶(C~B))


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

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

Задача 4. На координатной плоскости даны множества A и B (A ограничено красным цветом, B – синим, границы включены в множества). Описать предикат P_C (z), определенный на координатной плоскости, который принимает значение «истина», если точка z=(x,y) принадлежит множеству C, и значение «ложь», если точка z не принадлежит множеству C. Для записи предиката можно использовать любые логические операции и сравнение ≤.

Задача 5.
3. Дана машина Тьюринга с алфавитом A={0,1} и программой:
q_1 1⟶1Lq_1; q_1 0⟶1Lq_2; q_2 0⟶0Rq_0; q_2 1⟶1Rq_2
Определить конфигурацию, в которую переходит машина Тьюринга после выполнения не более чем 5 команд, если начальная конфигурация была:
00q_1 11110110

Вариант 3
сдавалась 2020.
оценка Зачет.