Типовой расчет по мат. логике и теории алгоритмов.

Задание 1.

1.Представить в ПНФ и ССФ предикаты и .

№

Задание 2.

Используя метод резолюций для предикатных выражений для заданного множества гипотез и утверждения , доказать справедливость выражения .

№

Задание 3.

Представить утверждения, сформулированные на естественном языке в виде множества предикатных выражений. Доказать их справедливость, используя метод резолюций.

№
	Все мексиканцы носят сомбреро. Ни одна обезьяна не носит сомбреро. Следовательно, ни одна обезьяна не является мексиканцем.
	Каждый член демократической партии голосует за президента и не любит коммунистов. Некоторые демократы являются предпринимателями. Следовательно, существуют предприниматели, которые не любят коммунистов.
	Все отцы – мужчины. Если у детей один отец, то они единокровны. Брат – это единокровный мужчина. Джон – отец Боба. Джон – отец Сида. Сид – отец Лизы. Следовательно, Сид и Боб братья.
	Ни один человек не является четвероногим. Все женщины – люди. Следовательно, ни одна женщина не является четвероногой.
	Некоторые республиканцы любят всех демократов. Ни один республиканец не любит ни одного социалиста. Следовательно, ни один демократ не является социалистом.
	Ни один торговец наркотиками не является наркоманом. Некоторые наркоманы привлекаются к ответственности. Следовательно, не все привлекающиеся к ответственности являются торговцами наркотиками.
	Все рациональные числа являются действительными числами. Некоторые рациональные числа – целые числа. Следовательно, некоторые действительные числа – целые.
	Все первокурсники общаются со всеми второкурсниками. Ни один первокурсник не общается ни с одним студентом последнего курса. Следовательно, ни один второкурсник не является студентом последнего курса.
	Некоторым нравится группа «Queen». Некоторые не любят никого, кому нравится группа «Queen». Следовательно, некоторые любят не всех.
	Каждый родитель имеет ребенка. Если родитель – женщина, то это – мать. Лиз ‑ женщина. Анна – родитель Лиз. Следовательно, Анна – мать.
	Если родитель – мужчина, то это отец. Если ребенок – мужчина, то это сын. Иван – мужчина. Сидор – мужчина. Иван – отец Сидора. Следовательно, Иван – отец и Сидор – сын.
	Если два человека являются родственниками третьего, то первый ‑ родственник второго. Каждый ‑ чей-нибудь родственник. Значит, если Иван ‑ родственник Петра, а Петр ‑ родственник Сидора, то Иван – родственник Сидора.
	Таможенники возвращают всех, кто въехал в страну без паспорта. Люди на машинах въехали в страну и были возвращены только другими людьми на машинах. Ни один человек на машине не имел паспорта. Следовательно, некоторые таможенники были на машинах.
	Преподаватели принимали зачеты у всех студентов, не являющихся отличниками. Некоторые аспиранты и студенты сдавали зачеты только аспирантам. Ни один из аспирантов не был отличником. Следовательно, некоторые преподаватели были аспирантами.
	Существуют студенты, которые любят всех преподавателей. Ни один из студентов не любит невежд. Следовательно, ни один преподаватель не является невеждой.

Задание 4.

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

2. Проверить работу машины Тьюринга над некоторыми словами.

№

Задание 5.

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

2. Проверить работу построенной машины над некоторым набором значений переменных.

№

Задание 6.

1. Написать формулу числовой функции , вычислимой машиной Тьюринга с множеством внутренних состояний , где 0 – заключительное, а 1 – начальное состояния, если машина задана своей программой.

2. Проверить работу машины Тьюринга с некоторым набором значений аргументов.

№	n
		λ	2R1	3R1	4Rλ	5Lλ	5Lλ	0Sλ
	1Rλ	2R1	3R1	4Rλ	6Lλ	0Lλ

№	n
		λ	‑	5R1	4Rλ	0Sλ	‑	0Sλ
	2R1	3Rλ	3Rλ	4Rλ	6R1	6Rλ

№	n
		λ	2Rλ	3Rλ	4Lλ	0S1	6L1	4L1
	1Rλ	2Rλ	3R1	5Rλ	5R1	6L1

№	n
		λ	4R1	3Lλ	0Sλ	5L1	6R1	0S1
	2R1	1R1	3Lλ	4R1	5L1	6R1

№	n
		λ	‑	3R1	4Rλ	5Lλ	5Lλ	0S1
	2Rλ	2Rλ	3R1	6Lλ	6L1	6L1

№	n
		λ	2Rλ	3R1	4Rλ	5Lλ	5Lλ	‑
	1Rλ	2R1	3R1	4Rλ	6Lλ	0Sλ

№	n
		λ	4Rλ	3R1	1R1	5Lλ	5Lλ	0Sλ
	2Lλ	2L1	3R1	4Rλ	6Lλ	6L1

№	n
		λ	2R1	3R1	4R1	5Lλ	6Lλ	6Lλ
	1R1	2Rλ	3R1	‑	5Lλ	0S1

№	n
		λ	2R1	3R1	4Lλ	4Lλ	6L1	0L1
	1Rλ	2R1	3Rλ	5Lλ	5L1	‑

№	n
		λ	2Rλ	3Rλ	4Rλ	5Lλ	5Lλ	0S1
	1Rλ	2Rλ	3R1	4Rλ	6Lλ	6L1

№	n
		λ	2Rλ	0S1	5R1	0S1	6L1	0S1
	1Rλ	3R1	4R1	4R1	5L1	6L1

№	n
		λ	2Rλ	3R1	4L1	5R1	6L1	0S1
	1Rλ	2Rλ	3R1	4L1	5R1	6L1

№	n
		λ	4R1	3R1	1R1	5R1	6R1	0Sλ
	2Lλ	2L1	3R1	4R1	‑	0S1

№	n
		λ	0Sλ	3Rλ	4R1	5R1	‑	1L1
	2S1	2Rλ	3Rλ	4R1	6L1	6L1

№	n
		λ	2R1	3Lλ	6R1	5L1	3L1	0S1
	1R1	2R1	4Rλ	4R1	5L1	6R1