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

Для данного утверждения обратное противоположному есть: "если не 2" > х', то не х ~ 4". Говоря обычным языком и приняв во внимание, что "не а > Ь" означает а < Ь, можно записать эту контрапозицию таким образом: "если 2" < х', то х < 4". П Использование контрапозиции при доказательстве теорем типа "тогда и только тогда*' дает нам несколько дополнительных возможностей. Представьте, например, что необходимо доказать эквивалентность множеств Е = Е. Тогда в утверждении "х принадлежит Е тогда и только тогда, когда х принадлежит Р" мы можем одну нз частей заменить ее контрапозипией. Одна из возможных форм такова. ° Если х принадлежит Е, то х принадлежит Е, а если х не принадлежит Е, то х не принадлежит Е.

В последнем утверждении Е и Р можно также поменять местами. 1.3. ДОПОЛНИТЕЛЬНЫЕ СХЕМЫ ДОКАЗАТЕЛЬСТВ 33 1.3.3. Доказательство методом „от противного" Еше один способ доказать утверждение типа "если-то" состоит в том, чтобы доказать утверждение ° "Н и не С влечет ложь". Следовательно, следует вначале предположить, что верны гипотеза Н и отрицание заключения С. Затем нужно доказать, что из Н и "не С" следует некоторое заведомо ложное утверждение.

Эта схема доказательства называется доказательством "от противного". Пример !.!2. Вспомним теорему 1.5, в которой было доказано утверждение типа "если-то'*с гипотезой Н = "У в бесконечноемножество,о — конечное подмножество К Т вЂ” дополнение о относительно ~/" и заключением С ="Т вЂ” бесконечное множество". Мы доказывали зту теорему методом "от противного": предполагая "не С", т.е., что Т— конечное множество. пытались вывести некоторое ложное утверждение. Мы показали, что если б и Т вЂ” оба конечны, то и У должно быть конечным. Но, поскольку согласно гипотезе Н У в бесконечное множество, и быть одновременно конечным и бесконечным множество не может, то полученное утверждение ложно.

Выражаясь терминами логики, мы имеем некоторое утверждение р (У вЂ” конечно) и его отрицание "не р" (У— бесконечно). Затем используем тот факт, что утверждение "р и не р" всегда ложно. П Обоснуем теперь корректность метода доказательства "от противного" с точки зрения логики. Вспомним раздел !.3.2, где мы показали, что из четырех возможных комбинаций значений истинности Н и С только во втором случае утверждение "если Н, то С ' ложно, Из ложности Н и не С следует, что случай 2 невозможен. Таким образом, возможны лишь оставшиеся три комбинации, и для каждой из них утверждение "если Н, то С' истинно. 1.3.4.

Контрпримеры В обыденной жизни нам не приходится доказывать теорем. Однако довольно часто мы сталкиваемся с чем-то, что кажется нам верным — например, со стратегией реализации программы, и мы вынуждены задумывается над истинностью такого рода "теоремы". Чтобы решить эту проблему, можно попытаться сначала доказать ее истинность, а если это ие удастся, то обосновать ее ложность.

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

ГЛАВА 1. АВТОМАТЫ: МЕТОДЫ И ПОНЯТИЯ 34 Схожая ситуация имеет место и с программами, поскольку мы обычно считаем, что программа содержит ошибку, если она неверно обрабатывает хотя бы один набор входных данных, с которым оиа должна работать. Часто бывает легче доказать, что утверждение не является теоремой, чем доказать, что оио — теорема. Мы уже упоминали о том, что, если 5 — некоторое утверждение, то утверждение "5 — не теорема" само по себе уже не содержит параметров, а потому является наблюдением, а не теоремой. В следующих двух примерах первое утверждение, очевидно, не является теоремой, а второе лишь похоже на теорему, однако требуется некоторое дополнительное исследование, чтобы доказать, что оно — ие теорема. Мнимая теорема 1.13. Все простые числа нечетны. (Более строго: если целое число х является простым, то х — число нечетное.) Опровержение.

2 — простое число, но 2 четно. Е3 Обсудим теперь "теорему", в которой используются элементы арифметической теории делимости. Но сначала дадим следующее важное определение. Если а и Ь вЂ” натуральные числа, то а вод Ь вЂ” это остаток от деления а на Ь, т.е. такое целое число г между О и Ь вЂ” 1, что а = дЬ+ г, где д — некоторое целое число.

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

Итак, предположим, что а < Ь. Тогда а вод Ь = а, поскольку в определении остатка а воб Ь для этого случая имеем д = О и г = а, т.е, а = О х Ь + а, когда а < Ь. Но Ь вод а < а, так как любой остаток от деления на а есть число между О и а — 1. Таким образом, если а < Ь, то Ь вод а < а вод Ь, так что равенство а вод Ь = Ь вод а невозможно. Используя теперь приведенные выше рассуждения о симметричности, получаем, что а вод Ь в Ь вод а и в случае, когда Ь < а. Однако есть еше третий случай, когда а = Ь. Поскольку для любого целого х выполнено хвоях = О, то при а = Ь имеем а вод Ь=Ь вод а.

Этим предполагаемая теорема опровергнута. Опровержение мнимой теоремы 1.14. Пусть а = Ь = 2, тогда а вод Ь = Ь вод а = О. Е3 В процессе поиска контрпримера мы на самом деле нашли точные условия, при выполнении которых предполагаемая теорема верна. Ниже приведена правильная формулировка этой теоремы и ее доказательство.

1.3. ДОПОЛНИТЕЛЬНЫЕ СХЕМЫ ДОКАЗАТЕЛЬСТВ Теорема 1.15. и пюд Ь = Ь шод а тогда и только тогда, когда а = Ь. Доказательство. (Досгпагпочносгпь) Предположим, что а = Ь. Тогда, как было отмечено выше, хтобх= О для любого целого х. Таким образом, ашод 6= 6 шод а=О, если а = Ь. (Необходимость) Предположим теперь, что а под Ь = Ь тод а. Лучше всего в данном случае применить метод 'от противного", и предположить, что заключение неверно, т.е.

что а е Ь. Тогда, поскольку вариант а = Ь исключается, остается рассмотреть случаи а<ЬиЬ<л, Выше мы выяснили, что если а < Ь, то а шоб Ь = а и Ь щод а < а. Эти утверждения совместно с гипотезой а пюд Ь = Ь щод а приводят к противоречию. По свойству симметричности, если Ь < а, то Ь щод а = Ь и а пюд Ь < Ь. Снова получаем противоречие. Таким образом, необходимость также доказана. Итак, теорема верна, поскольку мы доказали ее в обе стороны. 1:З 1.4.

Индуктивные доказательства При оперировании с рекурсивно определенными объектами мы сталкиваемся с необходимостью использовать в доказательствах особый метод, называемый "индуктивным". Большинство известных индуктивных доказательств оперирует с целыми числами, но в теории автоматов нам приходится индуктивно доказывать утверждения о таких рекурсивно определяемых понятиях, как деревья и разного рода выражения, например, регулярные, о которых мы уже вкратце упоминали в разделе 1.1.2. В этом разделе булут рассмотрены индуктивные доказательства сначала на примере "простых" индукций для целых чисел. Затем мы покажем, как проводить "структурную" индукцию для любых рекурсивио определяемых понятий. 1.4.1.

Индукции по целым числам Пусть требуется доказать некое утверждение Б(п), которое зависит от целого числа п. Существует общий подход к доказательствам такого рода. Доказательство разбивается на следующие два этапа. 1. Базис. На этом этапе мы показываем, что Б(~) верно для некоторого частного целого значения й Обычно полагают 1=0 или 1=1, но существуют примеры, где выбирается большее начальное значение, например, когда для всех меньших значений ! утверждение Б ложно.

2. Индуктивный переход, Здесь мы предполагаем, что п > Ь где ! — целое число из базиса индукции, и доказываем, что из истинности Б(п) слелует истинность Б(п+!), т.е. доказываем утверждение "если 5(п), то Б(п е !)". На уровне злравого смысла данное доказательство убеждает нас в том, что Б(п) на самом леле верно для всякого целого п, большего или равного базисному Ь Обосновать ГЛАВА 1. АВТОМАТЫ: МЕТОДЫ И ПОНЯТИЯ 36 это можно следующим образом. Предположим, что Я(н) ложно для одного или нескольких таких целых н. Тогда среди этих значений н существует наименьшее, скажем, г', причем) > 1. Значение г' ие может быть равным г', так как на основании базиса индукции 5(!) истинно.

Поэтому г' должно быть строго больше 1. Таким образом, мы знаем, что ) — 1 > 1 н Я(1- 1) истинно. Но во второй части доказательства показано, что если и > О то о(п) влечет 5(н е 1). Предположим, что и =у — 1. Тогда, совершая индуктивный переход, из 5(г'- 1) выводим Я()). Следовательно, из истинности ЯЦ вЂ” 1) следует истинность 5(у). Но мы предполагали, что справедливо отрицание доказываемого утверждения, а именно: ЯЦ) ложно для некоторого ) > й Придя к противоречию, мы тем самым доказали методом "от противного*', что Я(н) истинно для всех и > 1 К сожалению, в приведенных рассуждениях присутствует трудноуловимый логический изъян.

Дело в том, что первый пункт нашею предположения о том, что мы можем выбрать наименьшее ! > О для которого Я(г) ложно, зависит от того, принимаем ли мы на веру справедливость принципа индукции. Это значит, что по сути единственный способ доказать существование такого ! есть индуктивное доказательство. Но с позиций здравого смысла приведенное нами "доказательство" вполне осмысленно, и соответствует нашему пониманию мира. В связи с этим мы присоединим к нашей логической системе следующий закон. ° Првнцин индукции: если доказано, что 5(1) верно, и что при всех н > ! нз 5(л) следуете5(п -> 1), значит, Я(н) истинно при всех л >!.