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

Наконец, в индуктивных доказательствах (обсуждаемых в разделе 1.4) мы должны доказывать базисное утверждение и индуктивную часть. Доказательство можно проводить в любом порядке. Во многих теоремах одна часть значительно проще другой. Обычно ее доказывают вначале, чтобы потом на нее не отвлекаться. В формальной логике лля обозначения утверждений типа "тогда и только тогда" встречаются операторы < — > и =-. Следовательно, запись А <-> В нлн А = — В означает то же, что и "А тогда и только тогда, когда В". Доказывая утверждения типа "тогда н только тогда", важно помнить, что следует доказывать обе его части — и необходимость, и достаточность. Иногда оказывается полезным разбить его на ряд нескольких эквивалентностей.

Таким образом, чтобы доказать, что "А тогда и только тогда, когда В", вы можете вначале доказать что "А тогда и только тогда, когда С", а затем, что "С тогда и только тогла, когда В". Еше раз подчеркнем, что, применяя этот метод, обязательно нужно доказывать и необходимость, и достаточность.

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

Доказательство. (Необходимость) В этой части мы предподагаем, что ьхз = Гх1, и попытаемся доказать, что х — целое число. Заметим, что по определению!хз<х и Гх1> х. Нам дано, что ~х1 = Гх1. Поэтому мы можем изменить в первом неравенстве ~х) на Гх1. Поскольку верны оба неравенства Гх1<х и Гх1 >х, то согласно свойствам арифметических неравенств заключаем, что Гх1= х. Поскольку число Гх1 всегда целое, х тоже целое. (г!осглаточность) Предположим теперь, что х — целое, и попытаемся доказать, что Гх~ = Гх! Эта часть доказывается легко. По определению, ~х) и Гх1 при целом х оба равны х, а следовательно, равны между собой.

С) 1.2.4. Теоремы без гипотезы Иногда встречаются теоремы, которые, на первый взгляд, не имеют гипотезы. При- мер хорошо известен из тригонометрии. Теорема 1.8. з!и'О+ соя'0= 1. П На самом деле у этой теоремы есть гипотеза, состоящая из тех утверждений, которые необходимо знать, чтобы понять смысл этого утверждения. В частности, здесь неявно предполагается, что Π— - это некоторый угол, и потому функции синус и косинус имеют обычный смысл. Исходя из определений членов этого равенства и теоремы Пифагора (в прямоугольном треугольнике квадрат гипотенузы равен сумме квадратов двух других сторон), вы можете доказать эту теорему. На самом деле, она имеет вид утверждения типа "если-то"; "если Π— угол, тойп Оесоз О= !". з з 1.3.

Дополнительные схемы доказательств В этом разделе мы рассмотрим следующие дополнительные вопросы, касающиеся методов доказательств. ! . Доказательства утверждений о множествах. 2. Доказательства методом "от противного". 3. Доказательства с помощью контрпримера. 1.3.1. Доказательства эквивалентностей, связанных с множествами В теории автоматов нам нередко приходится доказывать, что два множества, записанные разными способами, на самом деле равны. Часто эти множества состоят из цепочек символов и являются так называемыми "языками". Но в данном разделе природа множеств не будет играть роли.

Если Е и Š— выражения, представляющие некоторые множества, то утверждение Е = Е означает, что эти множества равны. Точнее, каждый элемент множества, представленного Е, принадлежит множеству, представленному Е, и наоборот. ГЛАВА 1. АВТОМАТЫ: МЕТОДЫ И ПОНЯТИЯ 30 Пример 1.9. Коммутативный закон объединения множеств утверждает, что, объединяя два множества, мы можем делать это в любом порядке, т.е. /1 0 5 = 50 К. В данном случае в качестве Е выступает выражение // 0 Е, а в качестве Š— Е 0 К.

Согласно коммутативному закону Е = Е. С3 Равенство Е = Е можно переписать, как необходимое и достаточное условие: произвольный элемент х принадлежит множеству Е тогда н только тогда, когда х принадлежит Е Следовательно, доказательство для равенств множеств имеет такую же структуру, как и для утверждений типа "тогда и только тогда". 1.

Доказагь, что если х принадлежит Е, то х принадлежит и Г. 2. Доказать, что если х принадлежит Е, то х принадлежит и Е. В качестве примера рассмотрим доказательство закона днстрибутнвности объединения относительно пересечения. Теорема 1.10. Я 0(о П Т) =(/10Я П(//0 Т) Доказательство. Мы имеем дело со следуюшнми выражениями: Е=Н0(ЕЙТ) и Е=(КОЕ) П(К0 Т). Докажем по очереди обе части теоремы. Для доказательства необходимости предположим, что х принадлежит Е, и покажем, что тогда х принадлежит Е Эта часть доказательства представлена на рис.

1.5. При этом мы используем определения объеди- пения н пересечения множеств, предполагая, что читатель с ними знаком. Обоснование Утверждение Посылка 1. х принадлежит //0 (Я П Т) 2. х принадлежит Я илих принадлежитЯП Т (1) и определение объединения 3. х принадлежит // или х принадлежит как 9, (1) и определение пересечения так и Т Рнс. /,5. Доказательство необходимости теоремы /./О Затем нужно доказать достаточность.

Тут мы предполагаем, что х принадлежит К, и показываем, что тогда х принадлежит Е. Эта часть доказательства представлена на 31 1.3. Дополниткльнык схкмы доклзлткльств 4. х принадлежит Я 0 Е 5. х принадлежит К 0 Т 6. х принадлежит (/1 0 о) П (/1 0 Т) (3) и определение объединения (3) и определение объединения (4), (5) и определение пересечения рис. 1.6. Доказав обе части утверждения (и необходимость, и достаточность), мы тем са- мым доказали закон дистрибутивностн объединения относительно пересечения. ьз Утверждение Обоснование Посылка (1) и определение пересечения (1) и определение пересечения 4. х принадлежит )с или х принадлежит как 5, (2), (3) и рассуждения о множествах так и Т 5. т принадлежит Л или х принадлежит Я П Т (4) и определение пересечения 6.

х приналлежит 11 () (Е П Т) (5) и определение объединения Рис. Дб. Доказательство достаточности теореиы Д10 1.3.2. КонтРапоэиЦиЯ Всякое утверждение типа чесли-то" может быть записано в эквивалентной форме, что подчас облегчает его доказательство. Утверждение "если не С, то не Н" является обратным противоположному для утверждения "если Н, то С", или его контрапозицией. Утверждение и его контрапозиция либо оба истинны, либо оба ложны. Поэтому, доказав одно из них, мы доказываем и другое. Чтобы гюказать, почему именно утверждения "если Н, то С" и "если не С, то не Н" логически равносильны, рассмотрим следуюгдие четыре случая.

1, НиСобаистинны. 2, Н истинно, а Сложно. 3. С истинно, а Н ложно. 4. Н и С оба ложны. "Тогда и только тогда" для множеств Как мы уже упоминали, теоремы, которые устанавливают эквивалентность выраже- ний для множеств, являются утверждениями типа "тогда и только тогда*'. Таким об- разом, утверждение теоремы 1.10 может быть записано в виде; "элемент х принадле- жит 11 0 (Е П Т) тогда и только тогда, когда х принадлежит ()с 0 5) () ()1 0 Т)' . 22 1, х принадлежит()ГБа) П(н0 Т) 2. х принадлежит Я () 5 3, х принадлежит Д () Т ГЛАВА 1. АВТОМАТЫ: МЕТОДЫ И ПОНЯТИЯ Эквивалентность множеств можно выразить иначе с помощью оборота "все те, и только те". Например, утверждение теоремы 1.10 может быть записано в таком виде: "элементами множества й () (Я П У) являются все те, и только те элементы, которые принадлежат (Я 0 5) П (Р Ц 1)".

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

"если не С, то не Н". Для того чтобы это утверждение было ложным, его гипотеза ("не С*) должна быть истинной, а заключение ("не Н") — ложным. Но "не С"' истинно именно тогда, когда С вЂ” ложно, а "не гг" ложно именно тогда, когда Н вЂ” истинно. А это и есть случай (2). Последнее означает, что в каждом из четырех возможных случаев утверждение и его контрапозипия одновременно либо истинны, либо ложны, т.е.

онн логически эквивалентны. Обратное утверждение (конверсия) Не следует путать понятия "утверждение, обратное противоположному" (контрапозиция) и "обратное утверждение*' (конверсия). Конверсия утверждения типа "если-то" (или обратплое утверждение) есть то же угверждение, прочитанное "в обратную сторону". Следовательно, конверсией утверждения "если Н, то С" является утверждение "если С, то Н".

В отличие от контрапозипии, конверсия не является логически эквивалентной исходному утверждению. На самом деле, части утверждения типа "тогда и только тогда" всегда представляют собой некоторое утверждение и его конверсию. Пример 1.11. Вспомним теорему 1.3, в которой утверждалось: "если х>4, то 2" > х".