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

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

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

Эта часть доказывается легко. По определению, ⎣x⎦ и ⎡x⎤ при целом x оба равныx, а следовательно, равны между собой. †1.2.4. Òåîðåìû áåç ãèïîòåçûИногда встречаются теоремы, которые, на первый взгляд, не имеют гипотезы. Пример хорошо известен из тригонометрии.Теорема 1.8. sin2 θ + cos2 θ = 1. †На самом деле у этой теоремы есть гипотеза, состоящая из тех утверждений, которыенеобходимо знать, чтобы понять смысл этого утверждения. В частности, здесь неявнопредполагается, что θ — это некоторый угол, и потому функции синус и косинус имеютобычный смысл. Исходя из определений членов этого равенства и теоремы Пифагора (впрямоугольном треугольнике квадрат гипотенузы равен сумме квадратов двух другихсторон), вы можете доказать эту теорему.

На самом деле, она имеет вид утверждения типа “если-то”: “если θ — угол, то sin2 θ + cos2 θ = 1”.1.3. Äîïîëíèòåëüíûå ñõåìû äîêàçàòåëüñòâВ этом разделе мы рассмотрим следующие дополнительные вопросы, касающиесяметодов доказательств.1.Доказательства утверждений о множествах.2.Доказательства методом “от противного”.3.Доказательства с помощью контрпримера.1.3.1. Äîêàçàòåëüñòâà ýêâèâàëåíòíîñòåé, ñâÿçàííûõ ñ ìíîæåñòâàìèВ теории автоматов нам нередко приходится доказывать, что два множества, записанные разными способами, на самом деле равны. Часто эти множества состоят из цепочексимволов и являются так называемыми “языками”.

Но в данном разделе природа множествне будет играть роли. Если E и F — выражения, представляющие некоторые множества, тоутверждение E = F означает, что эти множества равны. Точнее, каждый элемент множества, представленного E, принадлежит множеству, представленному F, и наоборот.Пример 1.9. Коммутативный закон объединения множеств утверждает, что, объединяя два множества, мы можем делать это в любом порядке, т.е. R U S = S U R. В дан30Стр. 30ÃËÀÂÀ 1. ÀÂÒÎÌÀÒÛ: ÌÅÒÎÄÛ È ÏÎÍßÒÈßном случае в качестве E выступает выражение R U S, а в качестве F — S U R. Согласнокоммутативному закону E = F.

†Равенство E = F можно переписать, как необходимое и достаточное условие: произвольный элемент x принадлежит множеству E тогда и только тогда, когда x принадлежитF. Следовательно, доказательство для равенств множеств имеет такую же структуру, каки для утверждений типа “тогда и только тогда”.1.Доказать, что если x принадлежит E, то x принадлежит и F.2.Доказать, что если x принадлежит F, то x принадлежит и E.В качестве примера рассмотрим доказательствообъединения относительно пересечения.законадистрибутивностиТеорема 1.10. R U (S I T) = (R U S) I (R U T).Доказательство.

Мы имеем дело со следующими выражениями: E = R U (S I T) иF = (R U S) I (R U T).Докажем по очереди обе части теоремы. Для доказательства необходимостипредположим, что x принадлежит E, и покажем, что тогда x принадлежит F. Эта частьдоказательства представлена на рис. 1.5. При этом мы используем определения объединения и пересечения множеств, предполагая, что читатель с ними знаком.УтверждениеОбоснование1.x принадлежит R U (S I T)Посылка2.x принадлежит R или x принадлежит S I T(1) и определение объединения3.x принадлежит R или x принадлежит как S, (1) и определение пересечениятак и T4.x принадлежит R U S(3) и определение объединения5.x принадлежит R U T(3) и определение объединения6.x принадлежит (R U S) I (R U T)(4), (5) и определение пересеченияРис.

1.5. Доказательство необходимости теоремы 1.10Затем нужно доказать достаточность. Тут мы предполагаем, что x принадлежит F, ипоказываем, что тогда x принадлежит E. Эта часть доказательства представлена нарис. 1.6. Доказав обе части утверждения (и необходимость, и достаточность), мы тем самым доказали закон дистрибутивности объединения относительно пересечения.

†1.3. ÄÎÏÎËÍÈÒÅËÜÍÛÅ ÑÕÅÌÛ ÄÎÊÀÇÀÒÅËÜÑÒÂСтр. 3131УтверждениеОбоснование1.x принадлежит (R U S) I (R U T)Посылка2.x принадлежит R U S(1) и определение пересечения3.x принадлежит R U T(1) и определение пересечения4.x принадлежит R или x принадлежит как S, (2), (3) и рассуждения о множествахтак и T5.x принадлежит R или x принадлежит S I T(4) и определение пересечения6.x принадлежит R U (S I T)(5) и определение объединенияРис.

1.6. Доказательство достаточности теоремы 1.101.3.2. ÊîíòðàïîçèöèÿВсякое утверждение типа “если-то” может быть записано в эквивалентной форме, чтоподчас облегчает его доказательство. Утверждение “если не C, то не H” является обратным противоположному для утверждения “если H, то C”, или его контрапозицией. Утверждение и его контрапозиция либо оба истинны, либо оба ложны. Поэтому, доказаводно из них, мы доказываем и другое.Чтобы показать, почему именно утверждения “если H, то C” и “если не C, то не H”логически равносильны, рассмотрим следующие четыре случая.1.H и C оба истинны.2.H истинно, а C ложно.3.C истинно, а H ложно.4.H и C оба ложны.“Òîãäà è òîëüêî òîãäà” äëÿ ìíîæåñòâКак мы уже упоминали, теоремы, которые устанавливают эквивалентность выражений для множеств, являются утверждениями типа “тогда и только тогда”.

Таким образом, утверждение теоремы 1.10 может быть записано в виде: “элемент x принадлежит R U (S I T) тогда и только тогда, когда x принадлежит (R U S) I (R U T)”.Эквивалентность множеств можно выразить иначе с помощью оборота “все те, итолько те”. Например, утверждение теоремы 1.10 может быть записано в таком виде:“элементами множества R U (S I T) являются все те, и только те элементы, которыепринадлежат (R U S) I (R U T)”.32Стр. 32ÃËÀÂÀ 1. ÀÂÒÎÌÀÒÛ: ÌÅÒÎÄÛ È ÏÎÍßÒÈßУтверждение типа “если-то” может быть ложным лишь в одном случае — когда гипотеза истинна, а заключение ложно, что соответствует случаю (2). В остальных трехслучаях, включая и случай (4), в котором заключение ложно, данное утверждение типа“если-то” остается истинным.Теперь рассмотрим, когда ложно утверждение, обратное противоположному, т.е.“если не C, то не H”. Для того чтобы это утверждение было ложным, его гипотеза (“не C”)должна быть истинной, а заключение (“не H”) — ложным. Но “не C” истинно именно тогда, когда C — ложно, а “не H” ложно именно тогда, когда H — истинно.

А это и естьслучай (2). Последнее означает, что в каждом из четырех возможных случаев утверждение и его контрапозиция одновременно либо истинны, либо ложны, т.е. они логическиэквивалентны.Îáðàòíîå óòâåðæäåíèå (êîíâåðñèÿ)Не следует путать понятия “утверждение, обратное противоположному” (контрапозиция) и “обратное утверждение” (конверсия).

Конверсия утверждения типа “если-то”(или обратное утверждение) есть то же утверждение, прочитанное “в обратную сторону”. Следовательно, конверсией утверждения “если H, то C” является утверждение“если C, то H”. В отличие от контрапозиции, конверсия не является логически эквивалентной исходному утверждению. На самом деле, части утверждения типа “тогда итолько тогда” всегда представляют собой некоторое утверждение и его конверсию.Пример 1.11. Вспомним теорему 1.3, в которой утверждалось: “если x ≥ 4, то2 ≥ x2”.

Для данного утверждения обратное противоположному есть: “если не 2x ≥ x2, тоне x ≥ 4”. Говоря обычным языком и приняв во внимание, что “не a ≥ b” означает a < b,можно записать эту контрапозицию таким образом: “если 2x < x2, то x < 4”. †Использование контрапозиции при доказательстве теорем типа “тогда и только тогда”дает нам несколько дополнительных возможностей. Представьте, например, что необходимо доказать эквивалентность множеств E = F.

Тогда в утверждении “x принадлежит Eтогда и только тогда, когда x принадлежит F” мы можем одну из частей заменить ее контрапозицией. Одна из возможных форм такова.x• Если x принадлежит E, то x принадлежит F, а если x не принадлежит E, то x непринадлежит F.В последнем утверждении E и F можно также поменять местами.1.3.3. Äîêàçàòåëüñòâî ìåòîäîì “îò ïðîòèâíîãî”Еще один способ доказать утверждение типа “если-то” состоит в том, чтобы доказатьутверждение• “H и не C влечет ложь”.1.3. ÄÎÏÎËÍÈÒÅËÜÍÛÅ ÑÕÅÌÛ ÄÎÊÀÇÀÒÅËÜÑÒÂСтр. 3333Следовательно, следует вначале предположить, что верны гипотеза H и отрицаниезаключения C. Затем нужно доказать, что из H и “не C” следует некоторое заведомоложное утверждение.

Эта схема доказательства называется доказательством “отпротивного”.Пример 1.12. Вспомним теорему 1.5, в которой было доказано утверждение типа“если-то” с гипотезой H = “U — бесконечное множество, S — конечное подмножество U,T — дополнение S относительно U” и заключением C = “T — бесконечное множество”.Мы доказывали эту теорему методом “от противного”: предполагая “не C”, т.е., что T —конечное множество, пытались вывести некоторое ложное утверждение.

Мы показали,что если S и T — оба конечны, то и U должно быть конечным. Но, поскольку согласногипотезе H U — бесконечное множество, и быть одновременно конечным и бесконечным множество не может, то полученное утверждение ложно. Выражаясь терминами логики, мы имеем некоторое утверждение p (U — конечно) и его отрицание “не p” (U —бесконечно). Затем используем тот факт, что утверждение “p и не p” всегда ложно. †Обоснуем теперь корректность метода доказательства “от противного” с точки зрения логики.

Вспомним раздел 1.3.2, где мы показали, что из четырех возможных комбинаций значений истинности H и C только во втором случае утверждение “если H, тоC” ложно. Из ложности H и не C следует, что случай 2 невозможен. Таким образом,возможны лишь оставшиеся три комбинации, и для каждой из них утверждение “еслиH, то C” истинно.1.3.4. ÊîíòðïðèìåðûВ обыденной жизни нам не приходится доказывать теорем. Однако довольно частомы сталкиваемся с чем-то, что кажется нам верным — например, со стратегией реализации программы, и мы вынуждены задумывается над истинностью такого рода“теоремы”.

Чтобы решить эту проблему, можно попытаться сначала доказать ее истинность, а если это не удастся, то обосновать ее ложность.Теоремы, вообще говоря, являются утверждениями, включающими бесконечное число случаев, соответствующих множеству значений входящих в них параметров. В математике существует строгое соглашение о том, что утверждение можно назвать“теоремой” лишь тогда, когда оно описывает бесконечное число случаев. Те же утверждения, в которые параметры либо вовсе не входят, либо они могут принимать лишь конечное число значений, называют наблюдениями. Для того чтобы доказать, что предполагаемая теорема неверна, достаточно показать, что она ложна хотя бы в одном случае.Схожая ситуация имеет место и с программами, поскольку мы обычно считаем, чтопрограмма содержит ошибку, если она неверно обрабатывает хотя бы один набор входных данных, с которым она должна работать.Часто бывает легче доказать, что утверждение не является теоремой, чем доказать,что оно — теорема.

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

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