g) Пусть множество S вполне упорядочено отношением "ч" и пусть Р{х) - это утверждение, зависящее от элемента х из S. Покажите, что если Р{х) можно доказать, предполагая, что Р(у) верно для всех у Ч ж, то Р{х) верно для всех х из S.

[Замечания. П. (g)-это обещанное выше обобщение простой индукции. Если S - это множество положительных целых чисел, то мы получаем простой случай математической индукции, рассмотренный в тексте. Причем нас просят доказать, что Р(1) верно, если Р{у) верно для всех положительных целых у <\\ это то же самое, что просить нас просто доказать Р(1), поскольку Р{у) безусловно верно для всех таких у (таких у просто не существует). Итак, во многих случаях доказательство Р(1) не требует особой аргументации.

П. (d) в сочетании с (g) дает нам довольно сильный метод п-мерной индукции для доказательства утверждений P(mi,.. ., m„), зависящих от п целых положительных чисел mi, ..., Шп-

П. (f) можно применить к компьютерным алгоритмам следующим образом. Если каждому состоянию вычисления х поставить в соответствие элемент f{x), принадлежащий вполне упорядоченному множеству 5, таким образом, чтобы каждый шаг Вычислений переводил состояние X в состояние у так, что f{y) -< fix), то алгоритм будет конечным. Этот принцип обобщает рассуждения о строго убывающих значениях п, которые использовались при доказательстве конечности алгоритма 1.1Е.]

1.2.2. Числа, степени и логарифмы

Давайте начнем с того, что поближе познакомимся с числами, с которыми нам придется иметь дело. Целые числа - это

...,-3, -2,-1,0, 1,2,3,...

(отрицательные, положительные и нуль). Рациональное число - это отношение (частное) двух целых чисел, p/q, где q - положительное число. Действительное число - это величина х, которая имеет десятичное представление:

X = n + 0.did2d3..., (1)

где п - целое число, а каждое d;-любая цифра от О до 9, причем в конце не должно быть бесконечной последовательности из идущих подряд девяток. Представление (1) означает, что для любого положительного к

dl do dk dl do dk 1

"+То + 1оо + --- + То<"+10 + ш + -- + 15+10- 5

Вот два примера действительных чисел, которые не являются рациональными:

7Г = 3.14159265358979..., отношение длины окружности к ее диаметру;

ф = 1.61803398874989..., золотое сечение (1 + у/Е)/2 (см. раздел 1.2.8).

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

Сложные проблемы, возникающие при оперировании цеЛ»1ми числами, часто решают с помощью действительных чисел, а сложные проблемы, связанные с действительными числами, - с помощью более общего класса величин, которые называются комплексными числами. Комплексное число - это величина z, которую

можно представить в виде z х + iy, где х и у-действительные числа, а i - особая величина, удовлетворяющая уравнению = -1*. Будем называть хну действительной и мнимой часГтями z и определим модуль комплексного числа z

как

\z\ = 7x2+2/2. (3)

Под комплексным числом, сопряженным к z, понимают z = х - гу, и, таким образом, ZZ = х + у = jz2. Теория комплексных чисел во многих отношениях проще и изящнее теории действительных чисел, хотя она и считается более сложной. Поэтому в данной книге мы ограничимся действительными числами, за исключением случаев, когда использование только действительных чисел приводит к необоснованным сложностям.

Если и и V - действительные числа, для которых и < v, то замкнутым интервалом [u..v] будем называть множество действительных чисел х, таких, что и < X <v. Аналогично открытый интервал {и.. v) -это множество действительных X, для которых и < X < V. И, наконец, полуоткрытые интервалы [u:.v) или {u..v] определяются подобным образом. Мы допускаем также, что и может принимать значение -оо, а v - оо; в этом случае соответствующая сторона интервала остается открытой и мы считаем, что нижней или верхней границы у него нет. Таким образом, запись (-оо.. оо) обозначает множество всех действительных чисел, а; запись [О.. оо) - множество неотрицательных действительных чисел.

В дальнейшем в этом разделе буква b будет обозначать положительное действительное число. Если п - целое число, то 6" определяется известными правилами

fcOl, Ь" = Ь"-1Ь, если п>0, Ь = Ь+УЬ, если п < 0. (4)

По индукции легко доказать справедливость правил возведения в степень:

Ь+У = ЬЧУ, (6)" = (5)

где X п у - целые числа.

Если и - положительное действительное число, а m - положительное целое, то всегда существует единственное положительное действительное число v, такое, что 1)"* = и; оно называется корнем т-й степени из и и обозначается v = V"-

Теперь определим операцию возведения в степень Ь для рациональных чисел г - p/q следующим образом:

6Р/« = (6)

Это определение, введенное Оремом (Oresme) (ок. 1360 г.), очень удачное, так как lap/aq р/? правила возведения в степень остаются в силе, даже если х w. у - произвольные рациональные числа (см. упр. 9).

И, наконец, определим операцию возведения в степень для всех действительных чисел X. Предположим, что 6 > 1; если х определяется формулой (1), то получаем

n-l-di/lO-l-.-l-dt/lo < 5 n--di/10---l-d/b/104l/10

Итак, мы определили положительное действительное число 6 единственным образом, так как разность между правой и левой частями соотношения (7) равна

* Ее называют мнимой единицей. - Прим. перев.

n+di/io+-+dfc/ioi/io -y jj следует из упр. 13, приведенного ниже, эта разность меньше, чем Ь"+(Ь - 1)/10, и если взять достаточно большое к, то можно получить значение 6 с любой заданной точностью. Например,

100.30102999 1.9999999739..., io-3°i°°°° 2.0000000199.

поэтому для 6 = 10 и а: = 0.30102999 ... мы знаем значение 10 с большей точностью, чем до одной десятимиллионной (но при этом даже не знаем, каким будет десятичное, представление 10 -1.999... или 2.000...).

Для 6 < 1 определим операцию возведения в степень следующим образом; 6 = (1/Ь)~; если же 6 = 1, то 6 = 1. При этих определениях можно доказать, что правила возведения в степень, определяемые соотношениями (5), выполняются для всех действительных чисел хну. Эти идеи определения 6 впервые были высказаны Джоном Валлисом (John Wallis) в 1655 году и Исааком Ньютоном в 1669 году.

А теперь мы подошли к одному важному вопросу. Предположим, дано положительное действительное число у. Можно ли-найти такое действительное число х, что у Ь"? Ответ на этот вопрос утвердительный (при условии, что bl), так как можно просто использовать неравенства (7) в обратном направлении, чтобы определить п и di,d2,--- для заданного соотношения = у. Полученное в результате число X называется логарифмом у по основанию Ь и записывается как х = logj у. Согласно этому определению имеем

Например, из соотношений (8) вытекает, что

logjo 2 = 0.30102999... . (10)

Из правил возведения в степень следует, что

log(,(x2/) = logb X + log(, у, если i > О, у > D, (11)

log6(c) = у log(, с, если О 0. (12)

В равенстве (10) приведен пример так называемого десятичного логарифма, т. е. логарифма по основанию 10. Можно было бы ожидать, что в работе с компьютером более удобными окажутся двоичные логарифмы (по основанию 2), так как основу вычислений в большинстве компьютеров составляют операции с двоичными числами. Как мы вскоре увидим, двоичные логарифмы действительно очень полезны и широко используются, но дело не только в этом. Главная причина заключается в том, что ход вьшолнения компьютерного алгоритма часто разветвляется на два потока. Мы будем достаточно часто использовать двоичные логарифмы, поэтому имеет смысл ввести для них краткое обозначение. Итак, следуя предложению Эдварда М. Рейнгольда (Edward М. Reingold), будем использовать запись

lgx = log2X. (13)