dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 9
Текст из файла (страница 9)
S(x) утверждает, что2x ≥ x2, поэтому можно заключить, что 2x+1 = 2×2x ≥ 2x2.38Стр. 38ÃËÀÂÀ 1. ÀÂÒÎÌÀÒÛ: ÌÅÒÎÄÛ È ÏÎÍßÒÈßНо нам нужно показать нечто иное, а именно: 2(x+1) ≥ (x + 1)2. Это можно сделать, доказав, например, что 2x2 ≥ (x + 1)2, а затем, использовав транзитивность отношения ≥,показать, что 2(x+1) ≥ 2x2≥ (x + 1)2. Доказывая, что2x2 ≥ (x + 1)2,(1.7)можно использовать предположение, что x ≥ 4. Для начала упростим (1.7):x2 ≥ 2x + 1.(1.8)Разделив обе части (1.8) на x, получим:x≥2+1.x(1.9)Поскольку x ≥ 4, то 1/x ≤ 1/4. Таким образом, минимальное значение выражения в левойчасти (1.9) равно 4, а максимальное значение выражения в правой — 2.25.
Итак, истинность (1.9) доказана. Следовательно, верны (1.8) и (1.7). В свою очередь, (1.7) влечет2x2≥ (x + 1)2 при x ≥ 4, что позволяет доказать утверждение S(x + 1), т.е. 2x+1 ≥ (x + 1)2. Öåëûå ÷èñëà êàê ðåêóðñèâíî îïðåäåëÿåìûå ïîíÿòèÿМы уже упоминали о том, что индуктивные доказательства особенно полезны приработе с рекурсивно определяемыми объектами. Но в первых же примерах мы столкнулись с индукцией по целым числам, которые нами, как правило, не воспринимаются как объекты, определяемые рекурсивно. Однако существует естественное рекурсивное определение неотрицательного целого числа. Это определение вполне соответствует индуктивной процедуре по целым числам: переходу от ранее определенныхобъектов к тем, что определяются позже.Базис.
0 есть целое число.Индукция. Если n — целое число, то n + 1 — тоже целое число.1.4.2. Áîëåå îáùèå ôîðìû öåëî÷èñëåííûõ èíäóêòèâíûõ äîêàçàòåëüñòâВ разделе 1.4.1 мы описали схему индуктивного доказательства по целым числам,где утверждение S доказывается вначале для некоторого базисного значения, а затемдоказывается “если S(n), то S(n + 1)”. Однако иногда индуктивное доказательствовозможно лишь при использовании более общих схем. Рассмотрим следующие дваважных обобщения.1.Можно использовать несколько базисных значений. Это значит, что мы доказываемS(i), S(i + 1), …, S(j) для некоторого j > i.2.При доказательстве S(n + 1) можно использовать истинность не только S(n), но также и всех утверждений S(i), S(i + 1), …, S(n).
Кроме того, если доказана истинность Sдля базисных значений вплоть до j, то можно предполагать не только n ≥ i, но и n ≥ j.1.4. ÈÍÄÓÊÒÈÂÍÛÅ ÄÎÊÀÇÀÒÅËÜÑÒÂÀСтр. 3939На основании доказательств такого базиса и индуктивного шага можно заключить,что S(n) истинно для всех n ≥ i.Пример 1.18.
Возможности обоих описанных выше принципов проиллюстрируем напримере следующего утверждения S(n): “если n ≥ 8, то n можно представить в виде суммы троек и пятерок”. Отметим, между прочим, что 7 нельзя представить в таком виде.Базис. В качестве базисных утверждений выберем S(8), S(9) и S(10). Доказательстваих соответственно таковы: 8 = 3 + 5, 9 = 3 + 3 + 3 и 10 = 5 + 5.Индукция.
Предположим, что n ≥ 10 и S(8), S(9), …, S(n) истинны. Используя этифакты, мы должны доказать, что истинно S(n + 1). Для этого вычтем сначала 3 из n + 1,заметим, что полученная разность должна быть представима в виде суммы троек и пятерок, а затем прибавим к этой сумме 3 и получим сумму для n + 1.Более строго вышесказанное выглядит так. Поскольку n – 2 ≥ 8, то можно сделатьпредположение об истинности S(n – 2), т.е. n – 2 = 3a + 5b для некоторых целых a и b. Нотогда n + 1 = 3 + 3a + 5b, и, значит, мы можем записать n + 1 в виде суммы a + 1 троек иb пятерок. Это позволяет нам завершить индуктивный шаг и доказывает истинность утверждения S(n + 1).
1.4.3. Ñòðóêòóðíàÿ èíäóêöèÿВ теории автоматов используется несколько рекурсивно определяемых понятий, относительно которых нам будет необходимо доказывать те или иные утверждения. Важными примерами таких понятий являются деревья и выражения. Подобно индукции, всерекурсивные определения включают базис, где определяется одна или несколько элементарных структур, и индуктивный шаг, с помощью которого более сложные структуры определяются через структуры, определенные ранее.Пример 1.19.
Рассмотрим рекурсивное определение дерева.Базис. Одиночный узел есть дерево, и этот узел является корнем дерева.Индукция. Если T1, T2, …, Tk — деревья, то можно построить новое дерево следующим образом.1.Возьмем в качестве корня новый узел N.2.Возьмем по одному экземпляру деревьев T1, T2 ,…, Tk.3.Добавим ребра, соединяющие корень N, с корнями каждого из деревьев T1, T2, …, Tk.Индуктивное построение дерева с корнем N из k меньших деревьев представлено нарис. 1.7. Пример 1.20.
Определим рекурсивно понятие выражения, использующего арифметические операции + и ∗. В качестве его операндов могут выступать как числа, так ипеременные.Базис. Всякое число или буква (т.е. переменная) есть выражение.40Стр. 40ÃËÀÂÀ 1. ÀÂÒÎÌÀÒÛ: ÌÅÒÎÄÛ È ÏÎÍßÒÈßИндукция. Пусть E и F — некоторые выражения, тогда E + F, E * F и (E) также являются выражениями.Например, 2 и x являются выражениями согласно базису.
Индуктивный шаг позволяетутверждать, что x + 2, (x + 2) и 2*(x + 2) — тоже выражения. Отметим, что каждое из нихсостоит из частей, в свою очередь являющихся выражениями. Рис. 1.7. Индуктивное построение дереваÍåôîðìàëüíîå îáîñíîâàíèå ñòðóêòóðíîé èíäóêöèèМожно неформально обосновать правомочность структурной индукции как методадоказательства.
Представим, что в процессе рекурсивного определения мы последовательно вводим некоторые структуры X1, X2, …. Первыми в этой последовательности идут базисные элементы, и структура Xi определена, если только все ее подструктуры предшествуют Xi в этой последовательности. С этой точки зрения структурнаяиндукция — ни что иное, как обычная индукция по n для утверждения S(Xn).
В частности, это может быть и обобщенная индукция, описанная в разделе 1.4.2, т.е. в неймогут использоваться базисные утверждения, а индуктивный переход может опираться на все предыдущие утверждения. Однако следует помнить, что, как и вразделе 1.4.1, данное апеллирующее к интуиции пояснение не является формальнымдоказательством. Фактически, мы должны допустить справедливость этого принципа,так же, как в том разделе допустили справедливость исходного принципа индукции.Если у нас имеется рекурсивное определение некоторого понятия, то теоремы относительно этого понятия можно доказывать с помощью следующего метода, называемого структурной индукцией.
Пусть S(X) — утверждение о структурах X, определяемых рекурсивно.1.4. ÈÍÄÓÊÒÈÂÍÛÅ ÄÎÊÀÇÀÒÅËÜÑÒÂÀСтр. 41411.В качестве базиса докажем утверждение S(X) для базисной структуры (или структур) X.2.Для индуктивного перехода возьмем структуру X, определенную рекурсивно черезY1, Y2, …, Yk. Предполагая, что верны утверждения S(Y1), S(Y2), …, S(Yk), докажем сих помощью S(X).Отсюда заключаем, что S(X) истинно для всех X.
В следующих двух примерах мы доказываем теоремы о деревьях и выражениях.Теорема 1.21. В любом дереве число узлов на единицу больше числа ребер.Доказательство. Запишем утверждение S(T), которое нам требуется доказать методом структурной индукции в формальном виде: “Если T — дерево, и T содержит n узлови e ребер, то n = e + 1”.Базис.
В качестве базисного выберем случай, когда дерево T состоит из одного узла.Тогда n = 1 и e = 0, а потому соотношение n = e + 1 выполнено.Индукция. Пусть T — дерево, построенное по индуктивному определению из корневого узла N и k меньших деревьев T1, T2, …, Tk. Предположим, что утверждение S(Ti) истинно при i = 1, 2, ..., k, т.е., если дерево Ti содержит ni узлов и ei ребер, то ni = ei + 1.Узлы дерева T — это узел N и все узлы деревьев Ti. Таким образом, T содержит1 + n1 + n2 + … + nk узлов.
Ребра T — это k ребер, которые мы добавили на индуктивномшаге определения, плюс все ребра деревьев Ti. Значит, T содержитk + e1 + e2 + ... + ek(1.10)ребер. Заменив ni на ei + 1 в выражении для числа узлов T, получим, что оно равно1 + [e1 + 1] + [e2 + 1] + ... + [ek + 1].(1.11)Поскольку в сумме (1.11) содержится k слагаемых вида “+1”, ее можно перегруппировать таким образом.k + 1 + e1 + e2 + ... + ek(1.12)Это выражение равно на единицу больше, чем значение выражения (1.10), показывающего число ребер T.
Таким образом, число узлов на единицу больше числа ребер. Теорема 1.22. Всякое выражение содержит поровну правых и левых скобок.Доказательство. Говоря формально, необходимо доказать такое утверждение S(G)относительно выражения G, определенного рекурсивно в примере 1.20: левых и правыхскобок в G поровну.Базис. Если G — базисное выражение, то это либо число, либо переменная. В этихвыражениях 0 левых и 0 правых скобок, т.е. поровну.Индукция.
По определению индуктивного шага существует три способа построениявыражения G.1.G = E + F.2.G = E * F.42Стр. 42ÃËÀÂÀ 1. ÀÂÒÎÌÀÒÛ: ÌÅÒÎÄÛ È ÏÎÍßÒÈß3.G = (E).Мы предполагаем, что утверждения S(E) и S(F) истинны, т.е. что каждое из выражений E и F содержит поровну правых и левых скобок, по n и m, соответственно. Тогда в каждом из трех случаев мы можем подсчитать число входящих в G правых и левых скобок.1.Если G = E + F, то G содержит по n + m скобок каждого сорта: по n левых и правыхскобок из выражения E, и по m — из F.2.Если G = E * F, то G также содержит по n + m скобок каждого сорта, как и в случае (1).3.Если же G = (E), то G содержит n + 1 левых скобок — одну мы видим явно, а n находятся в E.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
