Лабораторный Практикум по Дискрмат2

= (x ÷ y) ÷ 1 = z ÷ 1.

Пример 2. Аналогично докажем, что функция s(x, y) = x + y является примитивно рекурсивной:

s(x, 0) = x + 0 = x = I11 (x), s(x, y +1) =S( s(x, y)).

Пример 3. Докажем, что операция умножения p(x, y) = x y является примитивно рекурсивной функцией:

p(x, 0) = x 0 = 0 = O(x),

p(x, y +1) = x y +x = p(x, y ) + x = s(x, p( x, y)).

Пример 4.Примером примитивно-рекурсивной функции является также функция, определяющая номер n = c(x, y) пары (x, y) в нумерации Кантора, функция r(n), определяющая правую координату и функция l(n), определяющая левую координату пары в нумерации Кантора. Номер пары (x, y) определяется следующим порядком расположения пар:

(0, 0), (0, 1), (1, 0), (0, 2), (1, 1), (2, 0), (0, 3), (1, 2), (2, 1), (3, 0), … .

Функции c(x, y), r(n), l(n) определяются следующими формулами:

		c(x, y) = n =							(x				y)2 3x y							,
												2
	x =l(n) = n ÷				1 [ 8n 1] 1 [ 8n 1] 1																				,
					2				2							2
y = r(n) =	[ 8n 1] 1				÷ ( n ÷				1			[ 8n 1] 1 [ 8n 1] 1																) ÷ 1.
	2									2		2													2

Квадратными скобками в этих формулах обозначена целая часть числа. Функции, при помощи которых выражены c(x, y), r(n), l(n) являются примитивнорекурсивными. Следовательно, примитивно-рекурсивными будут и сами функции c(x, y), r(n), l(n).

Нумерация троек, четверок и так далее, определяется при помощи нумерации пар следующим образом:

c(x, y, z) = c(c (x, y), z),

c(x, y, z, t) = c(c (x, y, z), t) = c(c ( c(x, y), z), t), … .

151

Определение координат по данному номеру тройки, четверки выполняется аналогично.

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

Тезис Черча. Числовая функция алгоритмически вычислима тогда и только тогда, когда она рекурсивна.

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

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

Теорема. Всякая частично –рекурсивная функция вычислима по Тьюрингу.

Обратное утверждение также справедливо и следует из теоремы Клини.

Порядок выполнения работы

1. При помощи оператора суперпозиции и примитивной рекурсии доказать примитивную рекурсивность данной функции.

2. Определить номер данной пары в нумерации Кантора. Для данного номера пары в нумерации Кантора определить левую и правую координату пары.

Образец выполнения заданий

а) Доказать примитивную рекурсивность функции, которая находит целую часть частного x/y.

б) Определить номер данной четверки (2, 1, 0, 3) в нумерации Клини. Для данного номера тройки c(x, y, z) = 18 в нумерации Кантора определить координаты x, y, z тройки (x, y, z).

Решение. а) Сначала докажем примитивную рекурсивность вспомогательной функции

		1, при x	0 .
sg(x) =
		0, при x	0

Применяя оператор примитивной рекурсии, получим:

152

sg(0) = 1 = S(O(0)),

sg(x 1) = 0 = O(x) = sg(0) ÷ 1.

Следовательно, функция sg(x) примитивно-рекурсивная. Докажем

теперь примитивную рекурсивность функции f(x, y ) = [x/y], то есть, целой части частного x/y. Введем обозначение n для целой части [x/y]. Тогда будут справедливы следующие неравенства

	n	x	n 1, ny x (n 1) y , ny ÷ x 0 < (n+1)y ÷ x.
		y

Из последнего двойного неравенства следует, что число n равно числу нулей в следующей конечной последовательности:

1y. ÷ x, 2y. ÷ x, 3y. ÷ x, …, ny. ÷ x, …, xy. ÷ x.

В таком случае, целую часть [x/y] будет равна следующей сумме:

		x	x
	n			sg(iy ÷ x).
		y
			i 1

Полученное выражение для целой части [x/y] представляет собой суперпозицию примитивно рекурсивных функций. Следовательно, сама эта функция также является примитивно рекурсивной.

б) Для того чтобы определить номер Кантора для четверки (2, 1, 0, 3) последовательно определим, согласно рекуррентной формуле:

c(x, y, z, t) = c(c (x, y, z), t) = c(c ( c(x, y), z), t)

и формуле номера пары, сначала номер пары c(2, 1) = 8. Затем, найдем номер пары c(8, 0) = 44. После этого, окончательно получим c(2, 1, 0, 3) = c(44, 3) = 1172. Таким образом, согласно нумерации Кантора, номером четверки (2, 1, 0, 3) является число 1172.

Определим координаты x, y, z тройки (x, y, z) с номером 284. Для этого сначала получим необходимые соотношения, связывающие номер тройки и ее координаты. Согласно рекуррентному определению номера тройки c(x, y, z) = c(c (x, y), z). Поэтому, для вычисления координаты z достаточно найти правую координату пары (c (x, y), z) с номером 284. По формуле правой координаты r(n) находим z = r(284) = 15. Далее, левая координата пары (c (x, y), z) с номером 284 равна c (x, y), то есть, l(284) = c (x, y). Откуда следует, что для нахождения координаты x достаточно применить к последнему равенству функцию l, а для нахождения

153

координаты z достаточно к правой и левой части этого равенства применить функцию r. В результате, получим формулы:

x = l(l(n)) = l (c(x, y)), y = r(l(n)) = r(c(x, y)).

По этим формулам найдем искомые координаты x = l(l(284)) = l(8) = 2, y = r(8) = 1. Таким образом, номер 284 в нумерации Кантора имеет тройка

(2, 1, 15).

Вопросы для самопроверки

1.Перечислите простые, базисные функции.

2.Определите основные операторы теории рекурсивных функций.

3.Какая связь между рекурсивными функциями и машинами Тьюринга?

Литература: [3], гл. 5, с. 82 – 106; [2], Часть 8, с. 136 – 162; [7], гл. 10, стр. 144 –201. [6], гл. 2, стр. 179 –185. [12], §8, стр. 119 –134

Задания для самостоятельной работы

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

б) Найти номера данных четверок в нумерации Кантора. Определить координаты троек с заданным номером n в нумерации Кантора.

Вариант 1.	а) f(x, y) = |x – y|;	б) c(4, 2, 3, 5), n = 326.
Вариант 2. а) f(x) = sg(x);		б) c(3, 4,	1, 8), n = 411.
Вариант 3. а) f(x, y) = 2|x – y| + y3;		б) c(2, 7,	13, 25), n =

516.

		2xy	y2
	Вариант 4. а) f(x, y) =			;
		y	5

681.

Вариант 5. а) f(x, y) = sg(x) + sg(y) + 3;

Вариант 6. а) f(x, y) = 3|x – y| + x2y3 +1;

396.

б) c(14, 21, 0, 3), n =

б) c(5, 3, 3, 7), n = 504.

б) c(2, 7, 13, 25), n =

154

	2x3	y 2
Вариант 7. а) f(x, y) =			+ x +1;
	y	x

Вариант 8. а) f(x, y) = x|x – y|+ x5 +3;

Вариант 9. а) f(x, y) = 6x3y4 + y + 2;

Вариант 10. а) f(x, y) = |x – y|+ 2sg(x);

б) c(4, 5, 4, 2), n = 731.

б) c(3, 4, 5, 3), n = 720.

б) c(8, 9, 3, 1), n = 375.

б) c(7, 9, 1, 3), n = 596.

Вариант 11. а) f(x, y) =	y2		xy	1;
	3y	x
Вариант 12. а) f(x, y) = |x sg(x) – y|+ 2				sg(y);

295.

Вариант 13. а) f(x, y) = |x – y| + xy sg(y);

Вариант 14. а) f(x, y) = sg(x) sg(y) +3;

Вариант 15. а) f(x, y) = 2|x – y| + sg(y) y3;

516.

xy2

Вариант 16. а) f(x, y) = y x3 +y+2;

881.

б) c(8, 6, 2, 3), n = 901.

б) c(3, 11, 7, 4), n =

б) c(2, 2, 3, 4), n = 677.

б) c(5, 3, 1, 0), n = 519.

б) c(2, 7, 13, 25), n =

б) c(11, 3, 6, 4), n =

Вариант 17. а) f(x, y) = |sg(x) - sg(y)| + 1;			б) c(1, 13, 2, 5), n =
504.
Вариант 18. а) f(x, y) = y|x – y| + x5y3 +x;			б) c(3, 17, 3, 15), n =
296.
Вариант 19. а) f(x, y) =	70	+ 2yx +3;	б) c(1, 3, 14, 5), n =
	y x
822.
Вариант 20. а) f(x, y) = xy+|x – y|+ sg(y)x5;			б) c(11, 2, 3, 2), n =
390.
Вариант 22. а) f(x, y) = x7y4 + 2sg(x);			б) c(5, 9, 3, 10), n = 875.
Вариант 23. а) f(x, y) = [x/y] + 2y sg(x);			б) c(3, 7, 1, 7), n = 531.

155

Вариант 24. а) f(x, y) =	y		+2sg(x);	б) c(8, 2,	1, 12), n =
	3x	4
798.
Вариант 25. а) f(x, y) = |y sg(x) – y| sg(y);				б) c(4, 9,	0, 5), n = 697.

Приложение 1. Перечисление перестановок с повторениями.

Sub Combin2()

Dim A(10, 10), B(720) For i = 1 To 6

A(i, 1) = "К": A(i, 2) = "О": A(i, 3) = "Л": A(i, 4) = "Е": A(i, 5) = "С": A(i, 6) = "О"

Next i d = 1

For i = 1 To 6

For j = 1 To 6

For k = 1 To 6

For l = 1 To 6

For m = 1 To 6

For n = 1 To 6

If i = j Then GoTo 10

If i = k Then GoTo 10

If i = l Then GoTo 10

If i = m Then GoTo 10

If i = n Then GoTo 10

If j = k Then GoTo 10

If j = l Then GoTo 10

If j = m Then GoTo 10

If j = n Then GoTo 10

If k = l Then GoTo 10

If k = m Then GoTo 10

If k = n Then GoTo 10

If l = m Then GoTo 10

If l = n Then GoTo 10

If m = n Then GoTo 10

'Cells(d, 1) = A(i, j) + A(j, k) + A(k, l) + A(l, m) + A(m, n) + A(n, i) B(d) = A(i, j) + A(j, k) + A(k, l) + A(l, m) + A(m, n) + A(n, i)

d = d + 1 10 '***

Next n, m, l, k, j, i

156

d = 1

For j = 1 To 720

For i = j To 719

If B(j) = B(i + 1) Then GoTo 20 GoTo 30

20 Cells(d, 2) = B(j) d = d + 1

30 '*** Next i, j End Sub

Приложение 2. Решение задачи коммивояжера.

Sub commiw() Dim a(8, 8), b(8, 8)

a(1, 1) = 120: a(1, 2) = 322: a(1, 3) = 116: a(1, 4) = 643: a(1, 5) = 671 a(2, 1) = 337: a(2, 2) = 122: a(2, 3) = 345: a(2, 4) = 321: a(2, 5) = 533 a(3, 1) = 351: a(3, 2) = 246: a(3, 3) = 754: a(3, 4) = 212: a(3, 5) = 245 a(4, 1) = 357: a(4, 2) = 678: a(4, 3) = 553: a(4, 4) = 754: a(4, 5) = 785 a(5, 1) = 223: a(5, 2) = 334: a(5, 3) = 553: a(5, 4) = 335: a(5, 5) = 769 m = 1

For i = 2 To 5

For j = 2 To 5

For k = 2 To 5

For l = 2 To 5

If i = j Then GoTo 10

If i = k Then GoTo 10

If i = l Then GoTo 10

If j = k Then GoTo 10

If j = l Then GoTo 10

If k = l Then GoTo 10

s1 = a(1, i) + a(i, j) + a(j, k) + a(k, l) + a(l, 1) s2 = 10000 + 1000 * i + 100 * j + 10 * k + l Cells(m, 1) = s1

Cells(m, 2) = s2 m = m + 1

10 ' stb Next l, k, j, i End Sub

157

Библиографический список

1. Алеев Г.Г., Абрамов О.М., Ситников Д.Э. Дискретная математика. Учебное пособие. - М.: Феникс. 2003, - 144с.

2.Галушкина Ю.И., Марьямов А.Н. Конспект лекций по дискретной математике. М.: Изд. АЙРИС Пресс, 2007, 176с.

3.Гринченков Д.В., Потоцкий С.И. Математическая логика и теория алгоритмов для программистов. Учебное пособие. - М.: «КноРус», 2010, - 206.

4.Иванов В.И. Дискретная математика. Алгоритмы и программы. - М.: Физматлит, 2007, - 408с.

5.В.И. Игошин. Математическая логика и теория алгоритмов. М.: Наука, 2005

6.Колдаев В.Д. Основы алгоритмизации и программирования. – М.: «ФОРУМ», 2009, - 413с.

7.Кузнецов О.П., Адельсон-Вельский Г. М. Дискретная математика для инженеров. М.: Наука, 2008, 408с.

8.Поздняков С.Н. Дискретная математика. - М.: Академия, 2008, -

448с.

9.Шапорев С.Д. Дискретная математика. – С.-Пб.: Петербург,2007, -

400с.

10.Яблонский С.В. Введение в дискретную математику. Учебное пособие. - М.: Наука, 2006, 384с.

11.Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной математики. - М.: Физматлит,2004, - 416с.

12.Игошин В.И. Задачник-практикум по математической логике. М.: Изд. АЙРИС Пресс, 2007.

158

	СОДЕРЖАНИЕ
Лабораторная работа 1.	…………………………………. 3
Лабораторная работа 2.	…………………………………. 13
Лабораторная работа 3.	…………………………………. 23
Лабораторная работа 4.	…………………………………. 30
Лабораторная работа 5.	…………………………………. 36
Лабораторная работа 6.	…………………………………. 44
Лабораторная работа 7.	…………………………………. 55
Лабораторная работа 8.	…………………………………. 63
Лабораторная работа 9.	…………………………………. 70
Практическое занятие 1.	…………………………………. 78

Практическое занятие 2. …………………………………. 85 Практическое занятие 3. …………………………………. 91 Практическое занятие 4. …………………………………. 101 Практическое занятие 5. …………………………………. 108 Практическое занятие 6. …………………………………. 116 Практическое занятие 7. …………………………………. 125 Практическое занятие 8. …………………………………. 132 Практическое занятие 9. …………………………………. 138

Приложение 1. …………………………………. 145 Приложение 2. …………………………………. 146

Библиографический список ………………………….… 147

159