dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 8

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 8)

Мы уже упоминали о том, что, если S — некоторое утверждение, то34Стр. 34ÃËÀÂÀ 1. ÀÂÒÎÌÀÒÛ: ÌÅÒÎÄÛ È ÏÎÍßÒÈßутверждение “S — не теорема” само по себе уже не содержит параметров, а потому является наблюдением, а не теоремой.В следующих двух примерах первое утверждение, очевидно, не является теоремой, авторое лишь похоже на теорему, однако требуется некоторое дополнительное исследование, чтобы доказать, что оно — не теорема.Мнимая теорема 1.13. Все простые числа нечетны.

(Более строго: если целое числоx является простым, то x — число нечетное.)Опровержение. 2 — простое число, но 2 четно. †Обсудим теперь “теорему”, в которой используются элементы арифметической теории делимости. Но сначала дадим следующее важное определение.Если a и b — натуральные числа, то a mod b — это остаток от деления a на b, т.е.такое целое число r между 0 и b – 1, что a = qb + r, где q — некоторое целое число.

Например, 8 mod 3 = 2, а 9 mod 3 = 0. Докажем, что следующая теорема неверна.Мнимая теорема 1.14. Не существует такой пары целых чисел a и b, для которойa mod b = b mod a. †Оперируя парами объектов, как a и b в данном случае, мы зачастую можем упроститьотношения между объектами, используя симметричность. Так, мы можем подробно рассмотреть лишь случай a < b, поскольку если a > b, то a и b можно просто поменять местами.

При этом в теореме 1.14 получим то же равенство. Но необходимо быть осторожным и не забыть о третьем случае, когда a = b. Именно здесь кроется подвох в попыткедоказательства теоремы.Итак, предположим, что a < b. Тогда a mod b = a, поскольку в определении остаткаa mod b для этого случая имеем q = 0 и r = a, т.е. a = 0 × b + a, когда a < b. Ноb mod a < a, так как любой остаток от деления на a есть число между 0 и a – 1. Таким образом, если a < b, то b mod a < a mod b, так что равенство a mod b = b mod a невозможно.Используя теперь приведенные выше рассуждения о симметричности, получаем, чтоa mod b ≠ b mod a и в случае, когда b < a.Однако есть еще третий случай, когда a = b.

Поскольку для любого целого x выполнено x mod x = 0, то при a = b имеем a mod b = b mod a. Этим предполагаемая теоремаопровергнута.Опровержение мнимой теоремы 1.14. Пусть a = b = 2, тогда a mod b = b mod a = 0. †В процессе поиска контрпримера мы на самом деле нашли точные условия, при выполнении которых предполагаемая теорема верна. Ниже приведена правильная формулировка этой теоремы и ее доказательство.Теорема 1.15. a mod b = b mod a тогда и только тогда, когда a = b.Доказательство.

(Достаточность) Предположим, что a = b. Тогда, как было отмечено выше, x mod x = 0 для любого целого x. Таким образом, a mod b = b mod a = 0,если a = b.1.3. ÄÎÏÎËÍÈÒÅËÜÍÛÅ ÑÕÅÌÛ ÄÎÊÀÇÀÒÅËÜÑÒÂСтр. 3535(Необходимость) Предположим теперь, что a mod b = b mod a. Лучше всего в данномслучае применить метод “от противного”, и предположить, что заключение неверно, т.е.что a ≠ b.

Тогда, поскольку вариант a = b исключается, остается рассмотреть случаиa < b и b < a.Выше мы выяснили, что если a < b, то a mod b = a и b mod a < a. Эти утверждения совместно с гипотезой a mod b = b mod a приводят к противоречию. По свойству симметричности, если b < a, то b mod a = b и a mod b < b. Снова получаем противоречие.

Такимобразом, необходимость также доказана. Итак, теорема верна, поскольку мы доказали еев обе стороны. †1.4. Èíäóêòèâíûå äîêàçàòåëüñòâàПри оперировании с рекурсивно определенными объектами мы сталкиваемся с необходимостью использовать в доказательствах особый метод, называемый “индуктивным”.Большинство известных индуктивных доказательств оперирует с целыми числами, но втеории автоматов нам приходится индуктивно доказывать утверждения о таких рекурсивно определяемых понятиях, как деревья и разного рода выражения, например, регулярные, о которых мы уже вкратце упоминали в разделе 1.1.2. В этом разделе будут рассмотрены индуктивные доказательства сначала на примере “простых” индукций для целых чисел. Затем мы покажем, как проводить “структурную” индукцию для любыхрекурсивно определяемых понятий.1.4.1.

Èíäóêöèÿ ïî öåëûì ÷èñëàìПусть требуется доказать некое утверждение S(n), которое зависит от целого числа n.Существует общий подход к доказательствам такого рода. Доказательство разбиваетсяна следующие два этапа.1.Базис. На этом этапе мы показываем, что S(i) верно для некоторого частного целогозначения i. Обычно полагают i = 0 или i = 1, но существуют примеры, гдевыбирается большее начальное значение, например, когда для всех меньших значений i утверждение S ложно.2.Индуктивный переход.

Здесь мы предполагаем, что n ≥ i, где i — целое число из базиса индукции, и доказываем, что из истинности S(n) следует истинность S(n + 1),т.е. доказываем утверждение “если S(n), то S(n + 1)”.На уровне здравого смысла данное доказательство убеждает нас в том, что S(n) насамом деле верно для всякого целого n, большего или равного базисному i. Обосноватьэто можно следующим образом. Предположим, что S(n) ложно для одного или нескольких таких целых n. Тогда среди этих значений n существует наименьшее, скажем, j, причем j ≥ i. Значение j не может быть равным i, так как на основании базиса индукции S(i)36Стр. 36ÃËÀÂÀ 1. ÀÂÒÎÌÀÒÛ: ÌÅÒÎÄÛ È ÏÎÍßÒÈßистинно.

Поэтому j должно быть строго больше i. Таким образом, мы знаем, что j – 1 ≥ iи S(j – 1) истинно.Но во второй части доказательства показано, что если n ≥ i, то S(n) влечет S(n + 1).Предположим, что n = j – 1. Тогда, совершая индуктивный переход, из S(j – 1) выводимS(j). Следовательно, из истинности S(j – 1) следует истинность S(j).Но мы предполагали, что справедливо отрицание доказываемого утверждения, аименно: S(j) ложно для некоторого j ≥ i. Придя к противоречию, мы тем самым доказалиметодом “от противного”, что S(n) истинно для всех n ≥ i.К сожалению, в приведенных рассуждениях присутствует трудноуловимый логический изъян.

Дело в том, что первый пункт нашего предположения о том, что мы можемвыбрать наименьшее j ≥ i, для которого S(j) ложно, зависит от того, принимаем ли мы наверу справедливость принципа индукции. Это значит, что по сути единственный способдоказать существование такого j есть индуктивное доказательство. Но с позиций здравого смысла приведенное нами “доказательство” вполне осмысленно, и соответствует нашему пониманию мира. В связи с этим мы присоединим к нашей логической системеследующий закон.• Принцип индукции: если доказано, что S(i) верно, и что при всех n ≥ i из S(n) следует S(n + 1), значит, S(n) истинно при всех n ≥ i.Покажем на следующих двух примерах, как принцип индукции используется при доказательстве теорем о целых числах.Теорема 1.16. Для всех n ≥ 0n∑ i2 =i =1n( n + 1)(2n + 1)6(1.1)Доказательство.

Доказательство будет состоять из двух частей: базиса и индуктивного шага. Докажем их по очереди.Базис. В качестве базисного значения выберем n = 0. В левой части равенства (1.1)0стоит∑,поэтому может показаться, что при n = 0 утверждение теоремы не имеетi =1смысла. Однако существует общий принцип, согласно которому, если верхний пределсуммы (в данном случае 0) меньше нижнего предела (здесь 1), то сумма не содержит0слагаемых и равна 0. Это значит, что∑ i2 = 0 .i =1Правая часть равенства (1.1) также равна нулю, поскольку 0×(0 + 1)×(2×0 + 1)/6 = 0.Таким образом, при n = 0 равенство (1.1) выполняется.Индукция.

Предположим теперь, что n ≥ 0. Мы должны совершить индуктивный переход, т.е. доказать, что, изменив в равенстве (1.1) n на n + 1, мы получим также правильное соотношение. Оно имеет следующий вид.1.4. ÈÍÄÓÊÒÈÂÍÛÅ ÄÎÊÀÇÀÒÅËÜÑÒÂÀСтр. 3737[ n +1]∑i2 =i =1[ n + 1]([n + 1] + 1)(2[ n + 1] + 1)6(1.2)Можно упростить равенства (1.1) и (1.2), раскрыв скобки в правых частях. Равенствапримут следующий вид.n∑ i 2 = (2n3 + 3n2 + n) / 6(1.3)∑ i 2 = (2n3 + 9n2 + 13n + 6) / 6(1.4)i =1n +1i =1Нам нужно доказать (1.4), используя (1.3). Эти равенства соответствуют утверждениям S(n + 1) и S(n) из принципа индукции.

“Фокус” заключается в том, чтобы разбитьсумму для n + 1 в левой части (1.4) на сумму для n плюс (n + 1)-й член. После чего мысможем убедиться, что (1.4) верно, заменив сумму первых n членов левой частью равенства (1.3). Запишем эти действия.⎛ n 2⎞⎜⎜ ∑ i ⎟⎟ + ( n + 1) 2 = ( 2n3 + 9n 2 + 13n + 6) / 6⎝ i =1 ⎠(1.5)( 2n3 + 3n 2 + n) / 6 + ( n 2 + 2n + 1) = ( 2n3 + 9n 2 + 13n + 6) / 6(1.6)Наконец, чтобы убедиться в справедливости (1.6), нужно преобразовать левую частьэтого равенства в правую с помощью несложных алгебраических действий.

†Пример 1.17. В этом примере мы докажем теорему 1.3 из пункта 1.2.1. Напомним, вэтой теореме утверждается следующее: если x ≥ 4, то 2x ≥ x2. Мы уже приводили неформальное доказательство этой теоремы, основной идеей которого являлось то, что отношение x2/2x уменьшается с ростом x, когда x > 4. Мы придадим строгость нашим рассуждениям, доказав утверждение 2x ≥ x2 по индукции, начиная с базисного значения x = 4.Отметим, кстати, что при x < 4 утверждение неверно.Базис. Если x = 4, то и 2x, и x2 равны 16. Следовательно, нестрогое неравенство 2x ≥ x2выполнено.Индукция.

Предположим, что 2x ≥ x2 для некоторого x ≥ 4. Приняв это утверждение вкачестве гипотезы, мы должны доказать, что верно и следующее утверждение2(x+1) ≥ (x + 1)2, где вместо x стоит x + 1. Эти два утверждения соответствуют S(x) иS(x + 1) в принципе индукции. Тот факт, что мы в качестве параметра используем не n, аx, не имеет значения, это всего лишь обозначение локальной переменной.Как и в теореме 1.16, мы должны переписать S(x + 1) так, чтобы можно было использовать S(x). В данном случае мы можем записать 2(x+1) как 2×2x.

Характеристики

Список файлов книги