Задание состоит в следующем

ЗАДАНИЕ СОСТОИТ В СЛЕДУЮЩЕМ:

Выполнить первую задачу
Исправить вторую и третью в соответствии с замечаниями (выделены красным)

ВАРИАНТ 6

Задание 1 (выполнить)

Проверить выводимость в исчислении высказываний методом Куайна, методом редукции и методом резолюций:

Решение:

Задание 2 (исправить формулу)

Пусть  - множество людей. На множестве  заданы следующие предикаты:

Е(х,у)=И х и у – один и тот же человек;

Р(х,у)=И х родитель у;

С(х,у)=И х и у – супруги;

М(х)=И х – мужчина;

W(х)=И х – женщина.

С использованием этих предикатов записать формулу, выражающую утверждение: Х – деверь.

Решение:

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

каждый человек, являющийся мужчиной;
при этом существует человек, являющийся его родителем;
при этом человек из п.2 является родителем другого мужчины;
при этом мужчина из п. 3 женат на женщине:

Поскольку фраза «х – деверь» зависит от переменной х, то и формула также должна зависеть от этой переменной. Исправьте.

Задание 3 (исправить в соответствии с замечанием)

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

Решение:

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

преобразует в последовательность вида

. Составим программу машины Тьюринга и оформим ее в виде таблицы, обозначая символом

пустые ячейки, соответствующие нулям: Не совсем понятно. Символ

записывается в пустые ячейки? А 0 в какие ячейки записывается? или достаточно одного пустого символа?

	q₁	q₂	q₃	q₄	q₅	q₆	q₇	q₈
1	1Пq₂	1Пq₂	Пq₃	Пq₅	1Лq₇	Сq₀	Пq₈	1Сq₄
	-	Пq₃	Пq₄	-	Лq₆	Лq₆	Лq₇	Пq₈

состояние q₁ является начальным состоянием;
машина находится в состоянии q₂ до тех пор, пока происходит движение вправо вдоль последовательности , при этом единицы в ячейках остаются без изменений. Как только появляется пустая ячейка, соответствующая нулю, машина переходит в состояние q₃;
в состоянии q₃ машина осуществляет движение вправо вдоль последовательности до тех пор, пока не встретится пустая ячейка, при этом стирает в ячейках единицы. Как только появляется пустая ячейка, машина переходит в состояние q₄;
в следующей после нуля ячейке должна содержаться единица (первая единица последовательности ), в состоянии q₄ машина ее стирает, смещается вправо на одну ячейку и переходит в состояние q₅;
в состоянии q₅ машина происходит проверка, была ли единица в предыдущей ячейке последней в последовательности , то есть если текущая ячейка оказалось пустой, то машина смещается влево и переходит в состояние q₆, иначе – в состояние q₇;
в состоянии q₆ машина движется влево, пока не встретит последнюю справа единицу последовательности , тогда она ее стирает и работа машины заканчивается;
в состоянии q₇ машина также движется влево, пока не встретит последнюю справа единицу последовательности , и также стирает ее, а после этого возвращается вправо до тех пор, пока не встретит следующую единицу последовательности . После этого она переходит в состояние q₄, чтобы опять проверить, последняя ли эта единица последовательности или нет, и т.д.

Проверим работу машины на последовательности 11101011:

Значение ячейки	Новое значение ячейки	Действие	Новое состояние
1	1	вправо	q2
1	1	вправо	q2
1	1	вправо	q2
0	0	вправо	q3
1	0	вправо	q3
0	0	вправо	q4
1	0	вправо	q5
1	1	влево	q7
0	0	влево	q7
0	0	влево	q7
0	0	влево	q7
0	0	влево	q7
1	0	вправо	q8
0	0	вправо	q8
0	0	вправо	q8
0	0	вправо	q8
0	0	вправо	q8
1	1	стоять	q4
1	0	вправо	q5
0	0	влево	q6
0	0	влево	q6
0	0	влево	q6
0	0	влево	q6
0	0	влево	q6
0	0	влево	q6
1	0	стоять	q0

Таким образом, произошло преобразование:

11101011

11000000