[См. John von Neuiiiaim, VoHected Works 5 (New York: Macmillan, 1963), 91-99. Cm. также ранние комментарии A. М. Тьюринга (А. М. Turing) о проверке корректности алгоритмов в Report of а Conference on High Speed Automatic Calculating Machines (Cambridge Univ., 1949), 67-68 и рисунки. Эта работа переиздана с комментариями Ф. Л. Моррис (F. L. Morris) и К. Б. Джонс (С. В. Jones) в Annals of the History of Computing 6 (1984), 139-143.]

в понимании теории программ большую помощь могут оказать один-два оператора, описывающих состояние машины в тщательно выбранные

моменты времени ... Высшая форма теоретического метода - это предоставление для утверждений неопровержимых математических доказательств.

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

Каждый из методов имеет свои недостатки.

- А. М. ТЬЮРИНГ (А, М. TURING), Ferranti Mark I Programming Manual (1950)

УПРАЖНЕНИЯ

1. [05] Объясните, как можно модифицировать идею доказательства методом математической индукции в случае, если некоторое утверждение Р(п) нужно доказать для всех неотрицательных целых чисел, т. е. для n = О, 1, 2, ... , а не для п = 1, 2, 3, ... .

2. [15] Найдите ошибку в следующем доказательстве. "Теорема. Пусть а-любое положительное число. Для всех целых положительных чисел п имеем а"~ = 1. Доказательство. Если n = 1, а"~ = а~ = а° = 1. По индукции, предполагая, что теорема верна для 1, 2, ..., п, имеем

~" ~ а("-1)-1 ~ 1 ~ следовательно, теорема верна также для п -)- 1."

3. [18] Следующее доказательство по индукции выглядит корректным, но по непонятной

3 i - 1 2 6 ~ 3-

причине для п = 6 левая часть уравнения дает f-bg-b + -b = ,а правая - - - - - -В чем же ошибка? "Теорема.

1x2 2x3 (n-l)xn 2 п

Доказательство. Используем индукцию по п. Для п = 1 доказательство очевидно: 3/2 -1/тг = 1/(1 X 2). Предполагая, что теорема верна для п, имеем;

1x2 (п- 1) X п п X (п+ 1)

3 1 1 3 1 Z1 J 3 J „

2 п n(n+l) 2 n Vn n-Ы/ 2 п+1

4. [20] Докажите, что числа Фибоначчи удовлетворяют не только соотношению (3), но и неравенству Fn > ф.

5. [21] Простое число - это целое число, большее единицы, которое делится только на 1 и на само себя. Используя данное определение и метод математической индукции, докажите, что любое целое число, большее единицы, можно записать как произведение одного или нескольких простых чисел. (Для удобства будем считать, что простое число - это "произведение" одного простого числа, т. е. его самого.)

6. [20] Докажите, что если соотношения (6) справедливы непосредственно перед выполнением шага Е4, то они верны и после его выполнения.

7. [23] Сформулируйте и докажите по индукции правило вычисления сумм 1, 2 - 1, 32 22 + 42 32 + 2 - 1 5-4 + 3-2 + 1и т. д.

► 8. [25] (а) Докажите по индукции следующую теорему Никомаха (Nicomachus) (ок. 100 г. н. э.); 1 = 1, 2 = 3-Ь5, 3 = 7-f9+ll, 4 = 13-I-15-H7-H9 и т. д.* (Ь) Воспользуйтесь этим результатом для доказательства замечательной формулы 1+2 + - Ч-п = {1+2+ -+71).

[Замечание. Интересная геометрическая интерпретация этой формулы, предложенная автору Р. В. Флойдом, показана на рис. 5. Идея этого построения связана с теоремой Никомаха и рис. 3. Другие "наглядные" доказательства можно найти в книгах Мартина Гарднера (Martin Gardner), Knotted Doughnuts (New York: Freeman, 1986), Chapter 16, a также J. H. Conway, R. K. Guy, The Book of Numbers (New York: Copernicus, 1996), Chapter 2.]

Сторона = 5 + 5-Ь5 + 5-Ь5-н5=5(5-Ь1)

Сторона = 5-Ь4--3-ь2-И 4-H-2 +3-1-4-1-5 = 2(1+2 + -.- + 5)

Площадь = 41-f4-2-244-3-344-4-444-5-5 = 4(1Ч2Ч----Ь5)

Рис. 5. Геометрическая интерпретация упр. 8, (Ь) при п = 5.

9. [20] Докажите по индукции, что если О < а < 1, то (1 - а)" > 1 - па.

10. [М22] Докажите по индукции, что если п > 10, то 2" > п.

11. [МЗО] Найдите и докажите простую формулу для следующей суммы;

1 3 5 (-1)"(2п+1)

14+4 34+4+ 54+4 "" (2п+1)0+4 •

12. [М25] Покажите, как можно обобщить алгоритм Е, чтобы, как было указано в тексте, для него допускались входные значения вида u + ii\/2, где и и ь - целые числа, и вычисления по-прежнему выполнялись элементарным образом (т. е. не выражая иррациональное число \/2 бесконечной десятичной дробью). Докажите, что при m = 1 и тг = \/2 выполнение алгоритма никогда не закончится.

► 13. [М23] Обобщите алгоритм Е, введя новую переменную Т и доб№,ив в начале каждого шага операцию Т <- Т+1. (Таким образом, переменная Т - счетчик выполненных шагов.)

* Требуется доказать формулу (п2 - п + 1) + (п - п + 3) + • • + (п2 -)- п - 1) = п. - Прим. перса.

Предположим, что первоначальное значение Т равно нулю, поэтому утверждение AJ па рис. 4 примет вид m > О, п > О, = 0. Аналогично к А2 следует добавить дополнительное условие Т = 1. Покажите, как добавить к утверждениям дополнительные условия таким образом, чтобы из любого утверждения А1, А2, ..., А6 следовало, что Т < Зп, и чтобы можно было провести доказательство по индукции. (Следовательно, вычисления должны закончиться максимум через Зп шагов.)

14. [50] (Р. В. Флойд.) Составьте компьютерную программу, на вХод Которой полаются программы, написанные на некотором языке программирования, вместе с необязательными утверждениями и которая пытается сформулировать остальные утверждения, необходимые для доказательства корректности входной компьютерной программы. Например, постарайтесь составить программу, с помощью которой можно доказать корректность алгоритма Е, если даны только утверждения А1, А4 и А6. Более подробную информацию об этом можно найти в статьях Р. В. Флойда и Дж. К. Кинга (J. С. King) (IFIP Congress proceedings, 1971).

► 15. [НМ28] (Обобщенная индукция.) В тексте показано, как доказывать по индукции утверждения Р{п), зависящие от единственного целого числа п, но ничего не говорится о том, как доказывать утверждения Р(т,п), зависящие от двух целых чисел. В подобных случаях обычно используют что-то вроде "двойной индукции", и поэтому доказательство часто выглядит довольно запутанным. Но на самом деле существует важный принцип доказательства, который является более общим, чем простая индукция, и при.меняется не только в подобных случаях, но и тогда, когда утверждения нужно доказывать для несчетных множеств, например если нужно доказать Р{х) для всех действительных х. Этот общий принцип называется вполне упорядоченностью.

Пусть "-<" -отношение на множестве 5, удовлетворяющее следующим свойствам.

i) Для любых X, у и z из S, если х -< у и у -< z, то х -< z.

ii) Для любых ж и у из S выполняется ровно одна из следующих трех возможностей; X у, X = у либо у < X.

Ш) Если А - любое непустое подмножество 5, то существует элемент х из Л, такой, что X < у {г. е. X -< у или X = у) для всех у из А.

Говорят, что это отношение вполне упорядочивает множество S. Например, очевидно, что множество положительных целых чисел вполне упорядочено обычным отношением "меньше чем" ("<").

a) Покажите, что множество есеа; целых чисел не является вполне упорядоченны.м отношением "<".

b) Определите на множестве всех целых чисел отношение вполне упорядоченности,

c) Является ли множество всех неотрицательных действительных чисел вполне упорядоченным отношением "<"?

d) {Лексикографический порядок.) Пусть множество S вполне упорядочено отношением "-<" и пусть Тп, п > О, - множество всех наборов {xi,X2, ,Хп) элементов xj из S. Определим отношение (xi,X2, . ,Хп) -< (уь Уг,..., Уп), если существует некоторое к, 1 < к < п, такое, что Xj = yj для 1 < j < к, а Xk -< ук в S. Будет ли отношение "-<" вполне упорядочивать Гп?

e) Продолжая п, (d), положим Г = Un>i-"; определим отношение {xi,X2, ,Хт) -< (у1,У2,... ,уп), если Xj = yj для \ <]<кпхк<Ук для некоторого к < min(ni,n) или если т < nwxj = yj для 1 < j < m. Будет ли отношение "-<" вполне упорядочивать Т?

f) Покажите, что отношение "-<" вполне упорядочивает множество S тогда и только тогда, когда оно удовлетворяет приведенным выше условиям (i) и (ii) и не существует бесконечной последовательности xi, Х2, хз, ..., такой, что Xj+i -< Xj для всех j > 1.