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

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

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

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

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

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

Задача 5. Дана машина Тьюринга с алфавитом и программой
, , , .
Определить конфигурацию, в которую переходит машина Тьюринга после выполнения не более чем 5 команд, если начальная конфигурация была .