Материалы для самостоятельной работы по дисциплине «Математическая логика и теория алгоритмов» (по материалам проф. ) (стр. 3 )

удалить из табл. 5а и 5b по четыре вершины и сформировать из оставшихся строк и столбцов отношения индивидуального задания (r’1 и r’2); индексы вершин не изменять, выполнить операции (r’1∪r’2), (r’1∩r’2), (r’1\r’2), (r’1°r’2), для каждой операции написать формулы, составить  таблицы отношений-результатов, вычислить свойства отношений r’1 и r’2 и определить класс отношений (нечеткой эквивалентности, нечеткого нестрогого или нечеткого строгого порядка).

Таблица 5a        Таблица 5b

r’1	x1	x2	x3	x4	x5	x6	x7	x8	r’2	x1	x2	x3	x4	x5	x6	x7	x8
x1	0,8	0,6`	0,4	0,5	0,7	0,7	0,6	0,6	x1	0,2`	0,3	0,4	0,1	0,2	0,1`	0,4	0,2
x2	0,7	0,6	0,6	0,7	0,5	0,8	0,6`	0,7	x2	0,8	0,3`	0,3	0,2	0,2	0,4	0,2`	0,3
x3	0,4	0,7	0,5	0,8	0,5	0,7	0,6	0,8	x3	0,8	0,6`	0,1	0,2	0,2	0,3	0,3`	0,1
x4	0,6`	0,5	0,7	0,6`	0,5	0,6	0,6	0,8	x4	0,6	0,2	0,6`	0,3	0,2	0,3	0,1	0,2
x5	0,7	0,5	0,6	0,7	0,8	0,6`	0,7	0,7	x5	0,8	0,6`	0,7	0,2	0,2	0,4	0,3`	0,3
x6	0,8	0,7	0,6	0,5	0,5	0,8	0,6`	0,7	x6	0,5	0,8	0,6`	0,7	0,8	0,4`	0,2	0,1
x7	0,8	0,8	0,7	0,5	0,8	0,6`	0,7	0,5	x7	0,6`	0,7	0,6`	0,4	0,7	0,5	0,2	0,2
x8	0,5	0,8	072	0,7	0,8	0,6`	0,4	0,6	x8	0,8	0,6`	0,4	0,8	0,6`	0,4	0,7	0,1

Таблица 6

Вариант	Удалить {xi}	Вариант	Удалить {xi}	Вариант	Удалить {xi}
1	для r1: x1, x2, x4, x5, для r2: x1, x2, x4, x5.	21	для r1: x2, x3, x6, x7, для r2: x2, x3, x6, x7.	41	для r1: x4, x6, x7, x8, для r2: x4, x6, x7, x8.
2	для r1: x1, x2, x5, x6, для r2: x1, x2, x5, x6.	22	для r1: x2, x3, x4, x8, для r2: x2, x3, x4, x8.	42	для r1: x4, x5, x6, x7, для r2: x4, x5, x6, x7.
3	для r1: x1, x2, x6, x7, для r2: x1, x2, x6, x7.	23	для r1: x2, x3, x5, x7, для r2: x2, x3, x5, x7.	43	для r1: x1, x2, x4, x6, для r2: x1, x2, x4, x6.
4	для r1: x1, x2, x7, x8, для r2: x1, x2, x7, x8 .	24	для r1: x2, x3, x5, x8, для r2: x2, x3, x5, x8.	44	для r1: x1, x2, x4, x8, для r2: x1, x2, x4, x8.
5	для r1: x1, x3, x5, x6, для r2: x1, x3, x5, x6.	25	для r1: x2, x3, x4, x6, для r2: x2, x3, x4, x6.	45	для r1: x1, x2, x5, x7, для r2: x1, x2, x5, x7.
6	для r1: x1, x3, x6, x7, для r2: x1, x3, x6, x7.	26	для r1: x2, x3, x4, x5, для r2: x2, x3, x4, x5.	46	для r1: x1, x2, x5, x7, для r2: x1, x2, x5, x7.
7	для r1: x1, x3, x7, x8, для r2: x1, x3, x7, x8.	27	для r1: x3, x4, x5, x6, для r2: x3, x4, x5, x6.	47	для r1: x1, x2, x5, x8, для r2: x1, x2, x5, x8.
8	для r1: x1, x3, x4, x6, для r2: x1, x3, x4, x6 .	28	для r1: x3, x4, x5, x6, для r2: x3, x4, x5, x6.	48	для r1: x1, x3, x4, x8, для r2: x1, x3, x4, x8.
9	для r1: x1, x4, x5, x6, для r2: x1, x4, x5, x6.	29	для r1: x3, x4, x5, x7, для r2:. x3, x4, x5, x7.	49	для r1: x2, x4, x6, x8, для r2: x2, x4, x6, x8.
10	для r1: x1, x4, x5, x7, для r2: x1, x4, x5, x7.	30	для r1: x3, x4, x5, x8, для r2: x3, x4, x5, x8.	50	для r1: x2, x3, x4, x6, для r2: x2, x3, x4, x6.
11	для r1: x1, x4, x5, x8, для r2: x1, x4, x5, x8.	31	для r1: x3, x4, x6, x7, для r2: x3, x4, x6, x7.	51	для r1: x1, x4, x5, x7, для r2: x1, x4, x5, x7.
12	для r1: x1, x4, x6, x7, для r2: x1, x4, x6, x7.	32	для r1: x3, x4, x6, x8, для r2: x3, x4, x6, x8.	52	для r1: x1, x5, x6, x7, для r2: x1, x5, x6, x7.
13	для r1: x1, x4, x5, x8, для r2: x1, x4, x5, x8.	33	для r1: x3, x4, x7, x8, для r2: x3, x4, x7, x8.	53	для r1: x2, x3, x5, x6, для r2: x2, x3, x5, x6.
14	для r1: x1, x4, x6, x8, для r2: x1, x4, x6, x8.	34	для r1: x3, x5, x6, x7, для r2: x3, x5, x6, x7.	54	для r1: x2, x3, x4, x6, для r2: x2, x3, x4, x6.
15	для r1: x1, x5, x6, x7, для r2: x1, x5, x6, x7.	35	для r1: x3, x5, x6, x8, для r2: x3, x5, x6, x8.	55	для r1: x3, x4, x5, x8, для r2: x3, x4, x5, x8.
16	для r1: x1, x5, x6, x8, для r2: x1, x5, x6, x8.	36	для r1: x3, x5, x7, x8, для r2: x3, x5, x7, x8.	56	для r1: x3, x5, x6, x8, для r2: x3, x5, x6, x8.
17	для r1: x1, x5, x7, x8, для r2: x1, x5, x7, x8.	37	для r1: x3, x6, x7, x8, для r2: x3, x6, x7, x8.	57	для r1: x4, x5, x7, x8, для r2: x4, x5, x7, x8.
18	для r1: x1, x6, x7, x8, для r2: x1, x6, x7, x8.	38	для r1: x4, x5, x6, x7, для r2: x4, x5, x6, x7.	58	для r1: x1, x2, x4, x5, для r2: x1, x2, x4, x5.
19	для r1: x2, x3, x4, x5, для r2: x2, x3, x4, x5.	39	для r1: x4, x5, x6, x8, для r2: x4, x5, x6, x8.	59	для r1: x1, x4, x6, x8, для r2: x1, x4, x6, x8.
20	для r1: x2, x3, x5, x6, для r2: x2, x3, x5, x6.	40	для r1: x4, x5, x7, x8, для r2: x4, x5, x7, x8.	60	для r1: x2, x3, x5, x8, для r2: x2, x3, x5, x8.

Задание 5. Теория алгоритмов

Задача 1.

Согласно варианту (см. табл. 7):

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

                                                                                Таблица 7

Вариант	Задание	Вариант	Задание	Вариант	Задание	Вариант	Задание
qo|x #| y#|z#|s#|t#  →	qo|x#|y#|z#|s#|t#  →	qo|x#|y#|z#|s#|t#  →	qo|x#|y#|z#|s#|t#  →
1		16		31		46
2		17		32		47
3		18		33		48
4		19		34		49
5		20		35		50
6		21		36		51
7		22		37		52
8		23		38		53
9		24		39		54
10		25		40		55
11		26		41		56
12		27		42		57
13		28		43		58
14		29		44		59
15		30		45		60

Задача 2.