Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений, страница 9

Покажем на следующих двух примерах, как принцип индукции используется при доказательстве теорем о целых числах. Теорема 1.1б. Для всех н > 0 н(в+1)(2л+ 1) 6 Доказательство. Доказательство будет состоять из двух частей: базиса и индуктивного шага.

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

ИНДУКТИВНЫЕ ДОКАЗАТЕЛЬСТВА Инлукция. Предположим теперь, что и > О. Мы должны совершить индуктивный переход, т.е. доказать, что, изменив в равенстве (1.1) и на и+ 1, мы получим также правильное соотношение. Оно имеет следующий вид. [и+ Ц([п ь Ц + Ц(2[и+ Ц+! ) 1 6 (1.2) Можно упростить равенства (1.1) и (1.2), раскрыв скобки в правых частях. Равенства примут следующий вид. 1~ = (2п3+ Зпз + и) (6 (!.3) ~ !' =(2п'+9п~+!Зп+6)/6 (! .4) (1.5) (2п'+Зпз пи)lб+(п +2и+1) =(2п'+9п +13п+6)16 (!.6) Наконец, чтобы убедиться в справедливости (!.6), нужно преобразовать левую часть этого равенства в правую с помощью несложных алгебраических действий.

СЗ Пример 1.17. В этом примере мы докажем теорему 1.3 из пункта 1.2.1. Напомним, в этой теореме утверждается следующее; если х > 4, то 2" > х . Мы уже приводили неформальное доказательство этой теоремы„основной идеей которого являлось то, что отношение х'~2" уменьшается с ростом х, когда х > 4. Мы придадим строгость нашим рассуждениям, доказав утверждение 2" >х по индукции, начиная с базисного значения х = 4. Отметим, кстати, что при х < 4 утверждение неверно. Базис.

Если х = 4, то и 2", и х' равны 16. Следовательно, нестрогое неравенство 2" > х' выполнено. Индукция. Предположим, что 2' > х' для некоторого х й 4. Приняв это утверждение в качестве гипотезы, мы должны доказать, что верно и следующее утверждение 2'~н>(ха 1)', где вместо х стоит хе 1. Эти два утверждения соответствуют б(х) и б(ха 1) в лринциле индукции. Тот факт, что мы в качестве параметра используем не и, а х, ие имеет значения, это всего лишь обозначение локальной переменной. ГЛАВА 1.

АВТОМАТЫ: МЕТОДЫ И ПОНЯТИЯ 88 Нам нужно доказать (! .4), используя (1.3). Эти равенства соответствуют утверждениям б(п ь 1) и Ю(и) из принципа индукции. "Фокус" заключается в том, чтобы разбить сумму для и+ 1 в левой части (1.4) на сумму для и плюс (и+ 1)-й член. После чего мы сможем убедиться, что (1.4) верно, заменив сумму первых и членов левой частью равенства (1.3). Запишем эти действия. Как и в теореме 1.1б, мы должны переписать Ях+ 1) так, чтобы можно было использовать 8(х). В данном случае мы можем записать 2омл как 2: 2". о1х) утверждает, что 2* З х~, позтому можно заключить, что 2~' = 2х2" > 2хз. Но нам нужно показать нечто иное, а именно: 2~1п > (х+ 1)~.

Это можно сделать, доказав, например, что 2х' > (х+ /), а затем, использовав транзитивность отношения >, показать, что 29'! > 2х~й (х + l)'. Доказывая, что 2х >(х+1), (1.7) можно использовать предположение, что х > 4. Для начала упростим (1.7): х >2хч!. (1.8) Разделив обе части (1.8) на х, получим: 1 х>2+ †, х (1.9) Целые числа как рекурсивно определяемые понятия Мы уже упоминали о том, что индуктивные доказательства особенно полезны при работе с рекурсивно определяемыми объектами. Но в первых же примерах мы столкнулись с индукцией по целым числам, которые нами, как правило, не воспринимаются как объекты, определяемые рекурсивно.

Однако существует естественное рекурсивное определение неотрицательного целого числа. Это определение вполне соответствует индуктивной процедуре по целым числам: переходу от ранее определенных обьектов к тем, что определяются позже. Базис. 0 есть целое число. Иидукция. Если л — целое число, то л + 1 — тоже целое число. 1,4.2. Более общие формы целочисленных индуктивных доказательств В разделе 1.4.1 мы описали схему индуктивного доказательства по целым числам, где утверждение Я доказывается вначале для некоторого базисного значения, а затем доказывается "если Я(п), то Я(л ч-1)".

Олнако иногда индуктивное доказательство возможно лишь при использовании более общих схем. Рассмотрим следующие два важных обобщения. 1. Можно использовать несколько базисных значений. Это значит, что мы доказываем 5(/) 5(/+ 1), ...,5(/) для некоторого/> Ь 1.4. ИНДУКТИВНЫЕ ДОКАЗАТЕЛЬСТВА Поскольку х > 4, то 1/х < 1/4. Таким образом, минимальное значение выражения в левой части (1.9) равно 4, а максимальное значение выражения в правой — 2.25. Итак, истин- ность (1.9) доказана.

Следовательно, верны (1.8) и (1.7). В свою очередь, (1.7) влечет 2х'> (х+ 1)' при х > 4, что позволяет доказать утверждение о1х+ 1), т.е. 2ьм > (х+ 1)', (Э 2. При доказательстве 5(и+ 1) можно использовать истинность не только 5(и), но также и всех утверждений 5(!), 5(! -ь 1), ..., 5(л). Кроме того, если доказана истинность 5 для базисных значений вплоть до7', то можно предполагать не только и > 0 но и л > /. На основании доказательств такого базиса и индуктивного шага можно заключить, что 5(п) истинно для всех и > ~'. Пример 1.18.

Возможности обоих описанных выше принципов проиллюстрируем на примере следующего утвержления Б(л): "если и > 8, то и можно представить в виде суммы троек и пятерок". Отметим, между прочим, что 7 нельзя представить в таком виде. Базис. В качестве базисных утверждений выберем Я(8), 5(9) и 5(!О). Доказательства их соответственно таковы: 8 = 3 + 5, 9 = 3 + 3 + 3 и 1О = 5 + 5. Индукции.

Предположим, что л > 10 и 5(8), 5(9), ..., 5(п) истинны. Используя эти факты, мы должны доказать, что истинно 5(л+ 1). Для этого вычтем сначала 3 из и+ 1, заметим, что полученная разность должна быть представима в виде суммы троек и пятерок, а затем прибавим к этой сумме 3 и получим сумму для и+ 1. Более строго вышесказанное выглядит так.

Поскольку и — 2 > 8, то можно сделать предположение об истинности 5(л -2), т е. л-2 = За+ 5Ь для некоторых целых а и Ь. Но тогда л+ 1 = 3 + За+ 5Ь, и, значит, мы можем записать л + ! в виде суммы а ь 1 троек и Ь пятерок. Это позволяет нам завершить индуктивный шаг и доказывает истинность утверждения 5(п е!). П 1.4.3. Структурная индукция В теории автоматов используется несколько рекурсивно определяемых понятий, относительно которых нам будет необходимо доказывать те или иные утверждения. Важными примерами таких понятий являются деревья и выражения.

Подобно индукции, все рекурсивные определения включают базис, где определяется одна или несколько элементарных структур, и индуктивный шаг, с помощью которого более сложные структуры определяются через структуры, определенные ранее. Пример 1.19. Рассмотрим рекурсивное определение дерева. Базис. Одиночный узел есть дерево, и этот узел является корнаи дерева. Индукции.

Если Т,, Тл ..., Ть — деревья, то можно построить новое дерево следующим образом. 1. Возьмем в качестве корня новый узел Ж. 2. Возьмем по одному экземпляру деревьев Т„Тм, Ть 3. Добавим ребра, соединяющие корень У, с корнями каждого из деревьев Тп Т,, ..., Ть Индуктивное построение дерева с корнем Ж из 7г меньших деревьев представлено на рис. 1.7. П ГЛАВА 1. АВТОМАТЫ: МЕТОДЫ И ПОНЯТИЯ 40 Пример 1.20.

Определим рекурсивно понятие выражения, использующего арифметические операции + и и. В качестве его операндов могут выступать как числа, так и переменные. Базис. Всякое число илн буква 1т.е. переменная) есть выражение. Индукция. Пусть Е и Š— некоторые выражения, тогда Е+ Е, Е и Е и (Е) также яв- ляются выражениями. Например, 2 и х являются выражениями согласно базису. Индуктивный шаг позволяет утверждать, что х ь 2, 1х+ 2) и 2игх+ 2) — тоже выражения. Отметим, что каждое из них состоит из частей, в свою очередь являющихся выражениями. Се Рис. Е 7. Индуктивное построение дереаа Неформальное обоснование структурной индукции Можно неформально обосновать правомочность структурной индукции как метода доказательства.

Представим, что в процессе рекурсивного определения мы последовательно вводим некоторые структуры Хь Хп .... Первыми в этой последовательности идут базисные элементы, и структура Х, определена, если только все ее подструктуры предшествуют Х, в этой последовательности. С этой точки зрения структурная индукция — ни что иное, как обычная индукция по н для утверждения ЯХ„). В частности, это может быть и обобщенная индукция, описанная в разделе 1.4.2, т.е. в ней могут использоваться базисные утверждения, а индуктивный переход может опираться на все предыдущие утверждения.