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

° Если множества Я и Т являются подмножествами некоторого множества (/, то говорят, что Т есть дополнение Я (относительно множества ~l), если о!! Т= У и Я П Т= Я. Таким образом, всякий элемент У содержится в одном, и только в од- ном, из множеств Я или Т. Другими словами, в Т содержатся те, и только те, элементы К которые не содержатся в 5.

Теорема 1.5. Пусть 5 — конечное подмножество бесконечного множества (/, и пусть Т вЂ” дополнение 5 относительно с/. Тогда Т вЂ” бесконечное множество. 1.2. ВВЕДЕНИЕ В ТЕОРИЮ ФОРМАЛЬНЫХ ДОКАЗАТЕЛЬСТВ 25 Доказательство. Интуитивно утверждение теоремы гласит, что, если имеется бесконечный запас чего-либо ((л), и из него изымается конечное количество (5), то оставшееся содержимое по-прежнему бесконечно. Для начала перепишем положения теоремы так, как показано на рис.

1.4. Исходное утверждение Новое утверждение 5 конечно Убесконечно Т является дополнением 5 Существует целое п и Я = п Не существует целогор, при котоРом ~~Ч =Р 50 Т= У и 5()Т= О Рис. П4. Переформулировио положений теоремы /.5 Чтобы сдвинуться с места в нашем доказательстве, мы должны применить общий метод, называемый "доказательством от противного". Применяя этот метод, который обсуждается в разделе 1.3.3, мы предполагаем, что заключение теоремы ложно. Затем, ос- сделать вывод, что заключение истинно, если истинна гипотеза, т.е. что теорема верна.

В теореме 1.5 отрицанием заключения является "Т вЂ” конечное множество". Предположим, что Т вЂ” конечно, вместе с утверждением гипотезы о конечности 5, т.е. й511 = л при некотором целом и. Наше предположение можно переформулировать в виде 1Щ = т дяя некоторого целого числа т'*. Одна из посылок утверждает, что 5 0 Т= У и 5() Т= О, т.е. каждый элемент У при- надлежит в точности одному из множеств 5 или Т. Но тогда в (' должно содержаться и + т элементов. Поскольку и + т — целое число, и, как показано, ~~ Ц1 = п + т, то У— конечное множество. Точнее, мы показали, что число элементов У есть целое число, что соответствует определению конечного множества. Но утверждение, что У вЂ” конечно, противоречит условию теоремы, согласно которому У вЂ” бесконечное множество. Таким образом, предположив противное заключению теоремы, мы получили противоречие одному нз данных утверждений ее гипотезы.

Согласно принципу "доказательства от противного" приходим к выводу, что теорема верна. П Доказательства не обязательно должны быть столь подробными. Зная идею доказа- тельства, мы можем теперь записать его в несколько строк. Доказательство (теоремы 1.5). Известно, что 5 Ц Т= У и множества 5 и Т не пере- секаются, а потому ~Д + ~~7)~ = 1ПЦ). Поскольку 5 — конечное множество, то ~Д~ = л для некоторого целого числа и, а из того, что У вЂ” бесконечное множество, следует, что не ГЛАВА 1.

АВТОМАТЫ: МЕТОДЫ И ПОНЯТИЯ 26 новываясь на этом предположении и отдельных утверждениях гипотезы теоремы, доказываем утверждение, являющееся отрицанием какого-либо из утверждений гипотезы. Этим мы показываем, что невозможно, чтобы одновременно все части гипотезы были истинными, а заключение — ложным. Остается единственная возможность— существует такого целого числа р, для которого !1Ц = р. Допустим, что множество Т— конечное, т.е. (Щ = т для некоторого целого т.

Тогда !)Щ = ((Я) + 1Щ) = т е и, что противоречит посылке — утверждению, что не существует целого числа, равного )~Ц. П 1.2.3. Другие формы теорем Во многих разделах математики наиболее распространены теоремы вида "если-то". Однако приходится доказывать в виде теорем и другие типы утверждений. В этом разделе мы изучим основные схемы таких утверждений и способы их доказательств.

Разновидности утверждений типа „если-то" Существует множество видов теорем, утверждения которых, на первый взгляд, отличаются от простого "если Н, то С", но на самом деле означают то же самое, а именно; если гипотеза Н верна при данном значении параметра (параметров), то при этом значении верно и заключение С. Вот несколько возможных способов записи утверждений типа "если Н, то С'*. 1.

Н влечет С. 2. Н только тогда, когда С. 3. С, если Н, 4. Из Н следует С. Форма 4 имеет множество разновидностей, например: "если Н, следовательно, С"' или "если верно Н, то С также верно". Пример 1.6. Утверждение теоремы 1.3 может быть записано в следующих четырех формах. 1. х> 4 влечет2" >х~. 2. х > 4 только тогда, когда 2" > х~. 3. 2" > х', если х > 4. 4. Изх>4следует2" >х', Ъ'тверждения с кванторами Во многих теоремах присутствуют утверждения с кванторачи "для всех" и "существует" или их вариациями, например, "для каждого'* вместо "для всех". От того, в каком порядке кванторы входят в утверждение, зависит его смысл.

Часто оказывается полезным представлять утверждения с кванторами как "игру", в которой участвуют два игрока — "Для всех" и "Существует". Они по очереди определяют значения параметров теоремы. Игрок "Для всех" должен рассматривать все существующие возможности, поэтому параметры, на которые он действует, всегда остаются переменными. Игроку "Существует", напротив, достаточно выбрать лишь одно значение, 1.2. ВВЕДЕНИЕ В ТЕОРИЮ ФОРМАЛЬНЫХ ДОКАЗАТЕЛЬСТВ ко~орое может зависеть от значений параметров„выбранных игроками ранее. Право первого хода определяется порядком вхождения кванторов в данное утверждение.

Утверждение верно, если игрок, делающий ход последним, всегда может выбрать подходящее значение параметра. В качестве примера рассмотрим альтернативное определение "бесконечного множества":множество 5 бесконечно тогда и только тогда, когда для каждого целого числа и существует подмножество Т множества В, содержащее ровно л элементов. Здесь "Для каждого" предшествует "Существует", поэтому мы должны рассматривать произвольное целое н. Затем "Существует", используя информацию об л, выбирает подмножество Т. Так, если 5 — множество всех целых чисел, то "Существует" может выбрать подмножество Т= 11, 2, ..., п), удовлетворив таким образом требование независимо от и. Тем самым доказано, что множество целых чисел бесконечно. Следующее утверждение, похожее на определение бесконечного множества, некорректно, поскольку кванторы в него входят в обратном порядке: "существует подмножество Т множества В, при котором для всякого и множество Т содержит ровно в элементов".

Теперь нам дано множество В, например множество целых чисел, и и~рок "Существует" может выбрать произвольное его подмножество Т, например 11, 2, 5). Относительно данного множества "Для всех" должен доказать, что при любом и оно содержит л элементов. Но это невозможно, поскольку при п = 4, и вообще, для любого л в 3 это утверждение ложно. В дополнение скажем, что в формальной логике вместо оборота "если-то" часто используется оператор — э.

Таким образом, вместо выражения "если Н, то С"' в математической литературе встречается запись Н -э С. Далее в книге этот оператор используется лля других целей. Утверждения типа „тогда и только тогда" Иногда мы встречаемся с выражениями вида "А тогда и только тогда, когда В". Разновидностями этого утверждения являются "А эквивалентно В'*, "А равносильно В" или "А в точности тогда, когда В"'. На самом деле такое утверждение содержит два утверждения типа "если-то"; "если А, то В" и "если В, то А". Чтобы доказать, что "А тогда и только то~да, когда В", необходимо доказать оба эти утверждения. 1.

Достиэлочлость (В лля А), нли "если"-часть: "если В, то А*', т.е. "А тогда, когда В". 2. Необходимость (В для А), или "только-если"-часть: "если А, то В", т.е. "А только тогда, когда В". 'В англоязычной математической литературе вместо выражения "11 ало ол1у ~Г часто используется его краткое обозначение — "1й". Это утверждение еше называют эквиволентвостыю.— Врив ред ГЛАВА 1.

АВТОМАТЫ: МЕТОДЫ И ПОНЯТИЯ 28 Какими должны быть формальные доказательства? Ответить на этот вопрос не так просто. Все доказательства имеют одну цель— убедить кого-либо, будь то человек, проверяюший вашу работу, или вы сами, в корректности выбранной вами стратегии. Если доказательство убедительно, то этого вполне достаточно, Если же оно вызывает сомнения у "потребителя", значит оно недостаточно подробно.

Неопределенность в степени подробности доказательств обусловлена различными уровнями знаний у его возможного потребителя, Так, при доказательстве теоремы 1.4 мы предполагали, что читатель знает арифметику, н что такое утверждение, как "если у > 1, то у' >!", не вызовет у него сомнений. Если бы он не был знаком с арифметикой, то нам бы пришлось доказывать это утверждение и, соответственно, добавлять в наше дедуктивное доказательство несколько дополнительных пунктов. Сушествуют, однако, определенные требования к доказательству, которыми никак нельзя пренебрегать, иначе оно будет некорректным.

Например, нельзя считать корректным дедуктивное доказательство, если оно содержит утверждение, не доказанное исходя из предыдуших нлн данных утверждений. Затем при доказательстве утверждений типа "тогда и только тогда" мы, конечно же, должны проводить нх и в одну, и в другую сторону.