Задание 2.

Построить машину Тьюринга для распознавания последовательности символов на ленте. Построить машину Поста для той же задачи.

Варианты заданий.

№ п/п	Последовательность

Задание 3.

Формализовать высказывание. Получить СДНФ, СКНФ, ДНФ, КНФ. Представить высказывание в виде суперпозиции только следующих операций 1) «Штрих Шеффера», 2) «Стрелка Пирса», 3)»Импликация» и «Отрицание», 4) «Импликация» и «Константа нуля».

Вариант 1.

«Если я замолчу – возопиют камни и реки потекут вспять».

Вариант 2.

«Если возопиют камни или реки не потекут вспять, то я замолчу».

Вариант 3.

«Если мед есть, то горшок становится пустым, а Винни-Пух – сытым».

Вариант 4.

«Студент сдает зачет на 4 или на 5 тогда и только тогда, когда добросовестно решает задачи по математической логике».

Вариант 5.

«Если я сдам зачет по математической логике, то пойду в казино или в кино».

Вариант 6.

«А тогда и только тогда, когда В тогда и только тогда, когда С».

Вариант 7.

«Если зажигают звезды, то это кому-нибудь нужно; все это – тогда и только тогда, когда не хлебом единым жив человек».

Вариант 8.

«Неверно, что если число делится на 3 и 2, то оно делится на 10».

Вариант 9.

«Если студент сдает зачет по математической логике, то неверно, что его отчисляют от обучения и выдают документы».

Вариант 10.

«Студент не сдает зачет тогда и только тогда, когда он не выполнил контрольную работу и не имеет конспекта лекций».

Задание 4.

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