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

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

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

Пусть S — конечное подмножество бесконечного множества U, и пустьT — дополнение S относительно U. Тогда T — бесконечное множество.Доказательство. Интуитивно утверждение теоремы гласит, что, если имеется бесконечный запас чего-либо (U), и из него изымается конечное количество (S), то оставшееся1.2. ÂÂÅÄÅÍÈÅ Â ÒÅÎÐÈÞ ÔÎÐÌÀËÜÍÛÕ ÄÎÊÀÇÀÒÅËÜÑÒÂСтр. 2525содержимое по-прежнему бесконечно. Для начала перепишем положения теоремы так,как показано на рис. 1.4.Исходное утверждениеНовое утверждениеS конечноСуществует целое n и ||S|| = nU бесконечноНе существует целого p, при котором ||U|| = pT является дополнением SSUT=UиSIT=∅Рис. 1.4.

Переформулировка положений теоремы 1.5Чтобы сдвинуться с места в нашем доказательстве, мы должны применить общий метод, называемый “доказательством от противного”. Применяя этот метод, который обсуждается в разделе 1.3.3, мы предполагаем, что заключение теоремы ложно. Затем, основываясь на этом предположении и отдельных утверждениях гипотезы теоремы,доказываем утверждение, являющееся отрицанием какого-либо из утверждений гипотезы. Этим мы показываем, что невозможно, чтобы одновременно все части гипотезыбыли истинными, а заключение — ложным.

Остается единственная возможность —сделать вывод, что заключение истинно, если истинна гипотеза, т.е. что теорема верна.В теореме 1.5 отрицанием заключения является “T — конечное множество”. Предположим, что Т — конечно, вместе с утверждением гипотезы о конечности S, т.е. ||S|| = nпри некотором целом n. Наше предположение можно переформулировать в виде “||T|| = mдля некоторого целого числа m”.Одна из посылок утверждает, что S U T = U и S I T = ∅, т.е. каждый элемент U принадлежит в точности одному из множеств S или T. Но тогда в U должно содержатьсяn + m элементов. Поскольку n + m — целое число, и, как показано, ||U|| = n + m, то U —конечное множество.

Точнее, мы показали, что число элементов U есть целое число, чтосоответствует определению конечного множества. Но утверждение, что U — конечно,противоречит условию теоремы, согласно которому U — бесконечное множество. Такимобразом, предположив противное заключению теоремы, мы получили противоречие одному из данных утверждений ее гипотезы. Согласно принципу “доказательства от противного” приходим к выводу, что теорема верна. †Доказательства не обязательно должны быть столь подробными. Зная идею доказательства, мы можем теперь записать его в несколько строк.Доказательство (теоремы 1.5). Известно, что S U T = U и множества S и T не пересекаются, а потому ||S|| + ||T|| = ||U||. Поскольку S — конечное множество, то ||S|| = n длянекоторого целого числа n, а из того, что U — бесконечное множество, следует, что несуществует такого целого числа p, для которого ||U|| = p.

Допустим, что множество T —конечное, т.е. ||T|| = m для некоторого целого m. Тогда ||U|| = ||S|| + ||T|| = m + n, что противоречит посылке — утверждению, что не существует целого числа, равного ||U||. †26Стр. 26ÃËÀÂÀ 1. ÀÂÒÎÌÀÒÛ: ÌÅÒÎÄÛ È ÏÎÍßÒÈß1.2.3. Äðóãèå ôîðìû òåîðåìВо многих разделах математики наиболее распространены теоремы вида “если-то”.Однако приходится доказывать в виде теорем и другие типы утверждений. В этом разделе мы изучим основные схемы таких утверждений и способы их доказательств.Ðàçíîâèäíîñòè óòâåðæäåíèé òèïà “åñëè-òî”Существует множество видов теорем, утверждения которых, на первый взгляд, отличаются от простого “если H, то С”, но на самом деле означают то же самое, а именно: если гипотеза H верна при данном значении параметра (параметров), то при этом значении верно и заключение С.

Вот несколько возможных способов записи утверждений типа “если H, то С”.1.H влечет C.2.H только тогда, когда C.3.C, если H.4.Из H следует C.Форма 4 имеет множество разновидностей, например: “если H, следовательно, C” или“если верно H, то C также верно”.Пример 1.6. Утверждение теоремы 1.3 может быть записано в следующих четырехформах.1.x ≥ 4 влечет 2x ≥ x2.2.x ≥ 4 только тогда, когда 2x ≥ x2.3.2x ≥ x2, если x ≥ 4.4.Из x ≥ 4 следует 2x ≥ x2.†Óòâåðæäåíèÿ ñ êâàíòîðàìèВо многих теоремах присутствуют утверждения с кванторами “для всех” и“существует” или их вариациями, например, “для каждого” вместо “для всех”. От того, в каком порядке кванторы входят в утверждение, зависит его смысл.

Часто оказывается полезным представлять утверждения с кванторами как “игру”, в которой участвуют два игрока — “Для всех” и “Существует”. Они по очереди определяют значения параметров теоремы. Игрок “Для всех” должен рассматривать все существующиевозможности, поэтому параметры, на которые он действует, всегда остаются переменными. Игроку “Существует”, напротив, достаточно выбрать лишь одно значение,которое может зависеть от значений параметров, выбранных игроками ранее. Правопервого хода определяется порядком вхождения кванторов в данное утверждение.Утверждение верно, если игрок, делающий ход последним, всегда может выбратьподходящее значение параметра.1.2. ÂÂÅÄÅÍÈÅ Â ÒÅÎÐÈÞ ÔÎÐÌÀËÜÍÛÕ ÄÎÊÀÇÀÒÅËÜÑÒÂСтр.

2727В качестве примера рассмотрим альтернативное определение “бесконечного множества”: множество S бесконечно тогда и только тогда, когда для каждого целого числаn существует подмножество T множества S, содержащее ровно n элементов. Здесь“Для каждого” предшествует “Существует”, поэтому мы должны рассматривать произвольное целое n. Затем “Существует”, используя информацию об n, выбирает подмножество T. Так, если S — множество всех целых чисел, то “Существует” можетвыбрать подмножество T = {1, 2, …, n}, удовлетворив таким образом требование независимо от n. Тем самым доказано, что множество целых чисел бесконечно.Следующее утверждение, похожее на определение бесконечного множества, некорректно, поскольку кванторы в него входят в обратном порядке: “существует подмножество T множества S, при котором для всякого n множество T содержит ровно nэлементов”.

Теперь нам дано множество S, например множество целых чисел, и игрок“Существует” может выбрать произвольное его подмножество T, например {1, 2, 5}.Относительно данного множества “Для всех” должен доказать, что при любом n оносодержит n элементов. Но это невозможно, поскольку при n = 4, и вообще, для любого n ≠ 3 это утверждение ложно.В дополнение скажем, что в формальной логике вместо оборота “если-то” часто используется оператор →. Таким образом, вместо выражения “если H, то C” в математической литературе встречается запись H → C. Далее в книге этот оператор используется для других целей.Óòâåðæäåíèÿ òèïà “òîãäà è òîëüêî òîãäà”Иногда мы встречаемся с выражениями вида “A тогда и только тогда, когда B”. Разновидностями этого утверждения являются “A эквивалентно B”, “A равносильно B” или“A в точности тогда, когда B”1.

На самом деле такое утверждение содержит два утверждения типа “если-то”: “если A, то B” и “если B, то A”. Чтобы доказать, что “A тогда итолько тогда, когда B”, необходимо доказать оба эти утверждения.1.Достаточность (B для A), или “если”-часть: “если B, то A”, т.е. “A тогда, когда B”.2.Необходимость (B для A), или “только-если”-часть: “если A, то B”, т.е. “A только тогда, когда B”.Êàêèìè äîëæíû áûòü ôîðìàëüíûå äîêàçàòåëüñòâà?Ответить на этот вопрос не так просто.

Все доказательства имеют одну цель —убедить кого-либо, будь то человек, проверяющий вашу работу, или вы сами, в кор-1В англоязычной математической литературе вместо выражения “if and only if” часто используется его краткое обозначение — “iff”. Это утверждение еще называют эквивалентностью. —Прим. ред.28Стр. 28ÃËÀÂÀ 1. ÀÂÒÎÌÀÒÛ: ÌÅÒÎÄÛ È ÏÎÍßÒÈßректности выбранной вами стратегии. Если доказательство убедительно, то этоговполне достаточно. Если же оно вызывает сомнения у “потребителя”, значит оно недостаточно подробно.Неопределенность в степени подробности доказательств обусловлена различнымиуровнями знаний у его возможного потребителя. Так, при доказательстве теоремы 1.4мы предполагали, что читатель знает арифметику, и что такое утверждение, как “еслиy ≥ 1, то y2 ≥ 1”, не вызовет у него сомнений. Если бы он не был знаком с арифметикой, то нам бы пришлось доказывать это утверждение и, соответственно, добавлять внаше дедуктивное доказательство несколько дополнительных пунктов.Существуют, однако, определенные требования к доказательству, которыми никакнельзя пренебрегать, иначе оно будет некорректным.

Например, нельзя считать корректным дедуктивное доказательство, если оно содержит утверждение, не доказанноеисходя из предыдущих или данных утверждений. Затем при доказательстве утверждений типа “тогда и только тогда” мы, конечно же, должны проводить их и в одну, ив другую сторону. Наконец, в индуктивных доказательствах (обсуждаемых вразделе 1.4) мы должны доказывать базисное утверждение и индуктивную часть.Доказательство можно проводить в любом порядке. Во многих теоремах одна часть значительно проще другой. Обычно ее доказывают вначале, чтобы потом на нее не отвлекаться.В формальной логике для обозначения утверждений типа “тогда и только тогда”встречаются операторы ↔ и ≡.

Следовательно, запись A ↔ B или A ≡ B означает то же,что и “А тогда и только тогда, когда B”.Доказывая утверждения типа “тогда и только тогда”, важно помнить, что следует доказывать обе его части — и необходимость, и достаточность. Иногда оказывается полезным разбить его на ряд нескольких эквивалентностей. Таким образом, чтобы доказать,что “A тогда и только тогда, когда B”, вы можете вначале доказать что “A тогда и толькотогда, когда C”, а затем, что “C тогда и только тогда, когда B”. Еще раз подчеркнем, что,применяя этот метод, обязательно нужно доказывать и необходимость, и достаточность.Доказав подобное утверждение лишь в одну сторону, мы тем самым оставляем доказательство незавершенным.Приведем простой пример доказательства теоремы типа “тогда и только тогда”. Введем следующие обозначения.1.⎣x⎦ обозначает наибольшее целое число, меньшее или равное вещественному числу x.2.⎡x⎤ обозначает наименьшее целое число, которое больше или равно вещественномучислу x.Теорема 1.7.

Пусть x — вещественное число. ⎣x⎦ = ⎡x⎤ тогда и только тогда, когдаx — целое.1.2. ÂÂÅÄÅÍÈÅ Â ÒÅÎÐÈÞ ÔÎÐÌÀËÜÍÛÕ ÄÎÊÀÇÀÒÅËÜÑÒÂСтр. 2929Доказательство. (Необходимость) В этой части мы предполагаем, что ⎣x⎦ = ⎡x⎤, ипопытаемся доказать, что x — целое число. Заметим, что по определению ⎣x⎦ ≤ x и⎡x⎤ ≥ x. Нам дано, что ⎣x⎦ = ⎡x⎤. Поэтому мы можем изменить в первом неравенстве ⎣x⎦ на⎡x⎤. Поскольку верны оба неравенства ⎡x⎤ ≤ x и ⎡x⎤ ≥ x, то согласно свойствам арифметических неравенств заключаем, что ⎡x⎤ = x. Поскольку число ⎡x⎤ всегда целое, x тоже целое.(Достаточность) Предположим теперь, что x — целое, и попытаемся доказать, что⎣x⎦ = ⎡x⎤.

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

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