AOP_Tom1 (1021736), страница 12
Текст из файла (страница 12)
Причем нас просят даказатеь что Р(1) верно, если Р(у) верно для всех положительных целых у < 1; это то же самое, что просить нас просто доказать Р(Ц, поскольку Р(у) безусловно верна для всех таких у (таких у просто не существует). Итак, во многих случаях доказательство Р(1) не требует особой аргументации. П. (4) в сочетании с (й) дает нам довольно сильный метод п-мерной индукции для доказательства утверждений Р(гпп..., т„), зависящих от и целых положительных чисел тп..., та. П. (1) можно применить к компьютерным алгоритмам следующим образом.
Если каждому состоянию вычисления х поставить в соответствие элемент у(х), принадлежащий вполне упорядоченному множеству Я, таким образом, чтобы каждый шэг вычислений переводил состояние х в состояние у так, что т'(у) -с 1(х), то алгоритм будет конечным. этот принцип обобщает рассуждения о строго убывающих значениях п, которые использовались при доказательстве конечности алгоритма 1.1Е.] 1.2.2. Числа, степени и логарифмы Давайте начнем с того, что поближе познакомимся с числами, с которыми нам придется иметь дело.
Целые числа †э — 3, — 2, — 1, О, 1, 2, 3, (отрицательные, положительные и нуль). Рациональное число — это'отношение (частное) двух целых чисел, р/а, где д — положительное число. Действительное числа — это величина х, которая имеет десятичное представление: х = и+ ОАдздз ", где и — целое число, а каждое д, — любая цифра от 0 до 9, причем в конце не должно быть бесконечной последовательности из идущих подряд девяток. Представление (1) означает, что для любого положительного )с 4 д дь 1 п+ — +=+ + — <х<п+ — +=+ + — + —.
10 100 10ь 10 100 10ь 10ь Р) Вот два примера действительных чисел, которые не являются рациональными: х = 3.14159265358979..., отношение длины окружности к ее диаметру; ф = 1.61803398874989..., золотое сечение (1+ ~/5)/2 (см, раздел 1.2.8). Таблица важнейших числовых постоянных с точностью до сорокового десятичного знака приведена в приложении А. Думаю, нет необходимости обсуждать хороша известные всем свойства сложения, вычитания, умножения, деления и сравнения действительных чисел. Сложные проблемы, возникающие при оперировании цеЛыми числами, часто решают с помощью действительных чисел, а сложные проблемы, связанные с действительными числами,— с помогцью более общего класса величин, которые называются комплексными числами.
Комплексное число — это величина х, которую можно представить в виде х ~ х + гу, где х и у — действительные числа, а г— особая величина, удовлетворяющая уравнению в' = -1*. Будем называть х и у действительной и мнимой часвтями х и определим модуль комплексного числа х как (х( = /хз + уэ. (3) Под комплексным числом, сопряженным к х, понимают й = х — 1у, и, таким образом, хй = х~ + у~ = ~э~э. Теория комплексных чисел во многих отношениях проще и изящнее теории действительных чисел, хотя она и считается более сложной. Поэтому в данной книге мы ограничимся действительвыми числами, за исключением случаев, когда использование только действительных чисел приводит к необоснованным сложностям.
Если и и и — действительные числа, для которых и < и, то замкнутым интервалом [и..и) будем называть множество действительных чисел х, таких, что и < х < и. Аналогично открытый интервал (и., и) — это множество действительных х, для которых и < х < и. И, наконец, полуоткрытые интервалы (и..и) или (и..и] определяются подобным образом. Мы допускаем также, что и может принимать значение — со, а и — оо; в этом случае соответствующая сторона интервала остается открытой и мы считаем, что нижней нли верхней границы у него нет. Таким образом, запись ( — оо .. оо) обозначает множество всех действительных чисел, а запись (О ..
оо) — множество неотрицательных действительных чисел. В дальнейшем в этом разделе буква Ь будет обозначать положительное действительное число. Если и — целое число, то Ь" определяется известными правилами Ь" = Ь" 'Ь, если и > О, Ь" = Ь"е'/Ь, если и < О. (4) По индукции легко доказать справедливость правил возведения в степень: Ье~к = Ь*Ь", (Ь*)" = Ь*", (5) где х и у — целые числа.
Если и — положительное действительное число, а т — положительное целое, то всегда существует единственное положительное действительное число и, такое, что и = и; оно называется корнем т-й степени из и и обозначается и = ~/иш Теперь определим операцию возведения в степень Ь" для рациональных чисел г = р/9 следующим образом: Ь >= Фьр. (6) Это определение, введенное Оремом (Огеэше) (ок.
1360 г.), очень удачное, так как Ь'Р!'е = Ье~е и правила возведения в степень остаются в силе, даже если х и у— произвольные рациональные числа (см. упр. 9). И, наконец, определим операцию возведения в степень Ь* для всех действительнеях чисел х. Предположим, что Ь > 1; если х определяется формулой (1), то получаем Ьпеш/$а+" +ае/но' < Ьв < Ьв+нсна.~...еы,/~о'+1/~о" (7) Итак, мы определили положительное действительное число Ь* единственным образом, так как разность между правой и левой частями соотношения (7) равна ' Ке иввывака мивмой единицей.
— Лрцм. верее. 6" с"опоз"'"ьг'l'о (Ь' с'о — 1). Как следует из упр. 13, приведенного ниже, эта разность меньше, чем Ь"в'(6 — 1)/!Оь, и если взять достаточно большое 6, то можно получить значение 6* с любой заданной точностью. Например, 1Оо.зосоззгэ 1 9999999739 10о.зосозооо 2 0000000199 поэтому для 6 = 10 и х = 0.30102999... мы знаем значение 10* с большей точностью, чем до одной десятимиллионной (но при этом даже не знаем, каким будет десятичное представление 10* — 1.999 ...
нли 2.000...). Для Ь < 1 определим операцию возведении в степень следующим образом: 6* = (1/6) *; если же Ь = 1, то Ь' = 1. При этих определениях можно доказать, что правила возведения в степень, определяемые соотношениями (5), выполняются для всех дейсслвитглъннх чисел х н у. Эти идеи определения 6* впервые были высказаны Джоном Валлнсом (Зо!зп с1а!1!з) в 1655 году и Исааком Ньютоном в 1669 году. А теперь мы подошли к одному важному вопросу. Предположим, дано положительное действительное число у. Можно лн.найти такое действительное число х, что у = 6*? Ответ на этот вопрос утвердительный (при условии, что 6 ф- 1), так как можно просто использовать неравенства (7) в обранином направлении, чтобы определить и и дс, дз..... для заданного соотношс пня Ь* =- у. Полученное в результате число х называется логарифмом у яо основанию Ь и записывается как х = !обо у, Согласно этому определению имеем Ьмг~ ~ !о8 (6*) (9) Например, из соотношений (8) вьстекает, что (10) 1обсо 2 = 0 30102999 .
Из правил возведения в степень следует, что !обз(хУ) = !обзх+!обо У, если х > О, У >,О, !обз(сг) = У!обз с, если с > О. (12) В равенстве (10) приведен пример так называемого десятичного логарифма, т. е. логарифма по основанию 10, Можно было бы ожидать, что в работе с компьютером более удобными окажутся двоичные логарифмы (по основанию 2), так как основу вычислений в большинстве компьютеров составляют операции с двоичными числами.
Как мы вскоре увидим, двоичные логарифмы действительно очень полезны и широко используются, но дело не только в этом. Главная причина заключается в том, что ход вьспатнвння компьютерного алгоритма часто разветвляется на два потока. Мы будем достаточно часто использовать двоичные логарифмы, поэтому имеет смысл ввести для них краткое обозначение. Итак, следуя предложению Эдварда М. Рейнгольда (Ес!згагс! М. Ве!пбо!д), будем использовать запись !8 х = 1ойз х, (13) А теперь возникает воп!юсг существует ли некая связь между 1бх и 1ойю х. К счастью. она действительно существует. Из (9) и (12) следует, что !о84ох = 1ой,о(2'в*) = (18х)(!о84о2).
Таким образом, !8х = 1ойщх/!ой,о 2. В общем виде эта формула выглядит следующим образом: 1о84 х (14) !084 с Соотношения (11), (12) и (14) — это фундаментальные правила выполнения операций с логарифмами. Оказывается, в большинстве случаев ни 10, ни 2 не являются идеальным основанием логарифма. Но если взять в качестве основания действительное число е = 2.718281828459045..., то логарифмы приобретают более простые свойства.
Логарифмы с основанием е принято называть натуральными логарпфмами; при этом используется следующая запись: (15) !и х = !ой х. Это нестрогое определение (в сущности, мы даже не определили число е) вряд ли позволит читателю почувствовать особую "натуральность" (т. е, естественность) такого логарифма; ио по мере работы с натуральными логарифмами !пх они будут казаться нам все более естественными. Фактически натуральные логарифмы были введены Джоном Непером (3о)1п г)ар!ег) (в несколько видоизмененном виде и вне связи со степенями) еще до 1590 года, за много лет до (1, 1) того, как стали известны другие виды логарифмов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
