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

Задача 1. Построить таблицу истинности логической формулы.

((A⟶B)⟶(A⟶C))~(A⟶(B⟶C))

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

Собака начинает радоваться только и только тогда, когда видит хозяина. Если собака радуется, то виляет хвостом. Собака не виляет хвостом. Значит, собака не видит хозяина.

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

(∃x∀yQ(x,y))⟶(∀y∃xQ(x,y))

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

Вариант 5 C=A ̅∩B ̅

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

Ответ преподавателя.

Контрольная работа 1 23.01.2022 Зачет

2022, зачёт