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

 

Задание 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