dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 5
Текст из файла (страница 5)
Äåäóêòèâíûå äîêàçàòåëüñòâàКак указывалось выше, дедуктивное доказательство состоит из последовательностиутверждений, истинность которых следует из некоторого исходного утверждения, называемого гипотезой, или данным утверждением (данными утверждениями), или посылкой. Конечное утверждение этой цепочки называется заключением.
Каждый шаг дедуктивного доказательства делается в соответствии с некоторыми допустимыми логически22Стр. 22ÃËÀÂÀ 1. ÀÂÒÎÌÀÒÛ: ÌÅÒÎÄÛ È ÏÎÍßÒÈßми принципами на основании либо известных фактов, либо предыдущих утверждений,либо комбинации тех и других.Исходная гипотеза может быть истинной или ложной. Обычно это зависит от значений входящих в нее параметров.
Часто гипотеза содержит несколько независимых утверждений, связанных логическим союзом “И”. В таких случаях каждое из этих утверждений считается гипотезой или данным утверждением.Теорема, которую мы доказываем, переходя от гипотезы H к заключению C, являетсяутверждением вида “если H, то C”. Мы говорим, что C логически (дедуктивно) следуетиз H.
Следующая теорема служит иллюстрацией утверждения данного типа.Теорема 1.3. Если x ≥ 4, то 2x ≥ x2. Формальное доказательство теоремы 1.3, основанное на индукции, мы рассмотрим впримере 1.17. Неформальное же доказательство этой теоремы особых усилий не требует.Для начала отметим, что гипотезой Н является утверждение “x ≥ 4”. Эта гипотеза зависитот параметра x, а потому не является ни истинной, ни ложной.
Истинность H зависит отзначения параметра х: так, например, при x = 6 она верна, а при х = 2 — ложна.Точно так же заключение C — это утверждение “2x ≥ x2”. Данное утверждение такжезависит от параметра x и является истинным при одних значениях параметра и ложным — при других. Например, C ложно при x = 3, поскольку 23 = 8 не превышает 32 = 9.С другой стороны, C истинно при x = 4, так как 24 = 42 = 16. Для x = 5 утверждение такжеистинно, поскольку 25 = 32 не меньше, чем 52 = 25.Интуиция наверняка вам подсказывает, что утверждение 2x ≥ x2 истинно при x ≥ 4.
Вего истинности при x = 4 мы уже убедились. Если x > 4 и x возрастает, то 2x удваиваетсявсякий раз, когда значение x увеличивается на 1. При этом выражение x2, стоящее в правой части, увеличивается в ((x + 1)/x)2 раз. Если x ≥ 4, то ((x + 1)/x) не превышает 1.25,следовательно, ((x + 1)/x)2 не превышает 1.5625. Поскольку 1.5625 < 2, то при x >4 с ростом x левая часть 2x растет быстрее, чем правая x2.
Таким образом, если, начиная со значения x, при котором неравенство 2x ≥ x2 выполняется, например для x = 4, мы увеличиваем x, то неравенство остается верным.Мы завершили неформальное, но вполне аккуратное доказательство теоремы 1.3. Кболее строгому доказательству этой теоремы мы еще вернемся в примере 1.17, после того как познакомимся с “индуктивными” доказательствами.Как и все содержательные теоремы, теорема 1.3 охватывает бесконечное число связанных между собой фактов.
В данном случае для всех целых x имеем “если x ≥ 4, то2x ≥ x2”. На самом деле, необязательно предполагать, что x — целое. Но, поскольку в доказательстве теоремы говорится лишь об x, возрастающих на единицу, начиная с x = 4, тов действительности теорема доказана только для целых x.Из теоремы 1.3 можно вывести ряд других теорем. В следующем примере мырассмотрим полное дедуктивное доказательство простой теоремы, использующеетеорему 1.3.1.2. ÂÂÅÄÅÍÈÅ Â ÒÅÎÐÈÞ ÔÎÐÌÀËÜÍÛÕ ÄÎÊÀÇÀÒÅËÜÑÒÂСтр. 2323Теорема 1.4.
Если x является суммой квадратов четырех положительных целых чисел, то 2x ≥ x2.Доказательство. На интуитивном уровне идея доказательства состоит в том, что еслипредположение данной теоремы верно для некоторого x, то, поскольку x — сумма квадратов четырех положительных целых чисел, значение x по крайней мере не меньше 4. Но тогда выполнено условие теоремы 1.3, а поскольку мы считаем, что она верна, то мы можем утверждать, что и заключение этой теоремы справедливо для x. Рассуждения можнопредставить в виде последовательности шагов, каждый из которых является либо гипотезой доказываемой теоремы, либо ее частью, либо утверждением, которое следует изодного или нескольких предыдущих утверждений.Под словом “следует” мы подразумеваем, что, если предыдущим утверждением является гипотеза какой-либо теоремы, то заключение этой теоремы верно и может быть записано, как утверждение в нашем доказательстве.
Это логическое правило часто называют правилом modus ponens. Оно гласит, что, если известно, что утверждение H истинно и утверждение “если H, то C” истинно, то можно заключить, что C также истинно.Кроме того, при выводе утверждений из одного или нескольких предыдущих утверждений допустимы и другие логические шаги. Так, например, если A и B — два предыдущихутверждения, то мы можем вывести и записать утверждение “A и B”.На рис. 1.3 приведена вся последовательность утверждений, необходимых для доказательства теоремы 1.4. Отметим, что мы не собираемся доказывать теоремы в такойстилизованной форме, хотя она помогает представить доказательство в виде явного перечня строго обоснованных утверждений.
На шаге (1) мы повторяем одну из посылоктеоремы: x есть сумма квадратов четырех целых чисел. В доказательствах часто оказывается полезным как-то обозначать величины. Здесь четыре целых числа обозначены как a, b, c и d.Утверждение22Обоснование22Посылка1.x=a +b +c +d2.a ≥ 1; b ≥ 1; c ≥ 1; d ≥ 1Посылка3.a2 ≥ 1; b2 ≥ 1; c2 ≥ 1; d2 ≥ 1(2) и свойства арифметики4.x≥4(1), (3) и свойства арифметики5.2 x ≥ x2(4) и теорема 1.3Рис. 1.3.
Формальное доказательство теоремы 1.4На шаге 2 записана еще одна часть предположения теоремы: каждое из чисел, возводимых в квадрат, не меньше 1. Технически, это утверждение содержит в себе четыре отдельных утверждения для каждого из данных четырех целых чисел. Затем, на шаге 3, за24Стр. 24ÃËÀÂÀ 1. ÀÂÒÎÌÀÒÛ: ÌÅÒÎÄÛ È ÏÎÍßÒÈßмечаем, что квадрат числа, не меньшего 1, также не меньше 1. В качестве обоснованияиспользуется истинность утверждения 2 и “свойства арифметики”, т.е. мы предполагаем,что читатель знает или может самостоятельно вывести простые утверждения с неравенствами, такие как: “если y ≥ 1, то y2 ≥ 1”.На шаге 4 используются утверждения 1 и 3.
В первом из них говорится, что x естьсумма четырех квадратов, а во втором — что каждый из квадратов не меньше 1. Воспользовавшись известными свойствами арифметики, заключаем, что минимальное значение x равно 1 + 1 + 1 + 1, т.е. 4.На последнем шаге 5 используем утверждение 4, которое является гипотезойтеоремы 1.3. Теорема же сама по себе есть основание, благодаря которому мы можемвыписать ее заключение, поскольку предыдущее утверждение является ее предположением. Так как утверждение 5, т.е. заключение теоремы 1.3, является также заключениемтеоремы 1.4, то теорема 1.4 доказана. Таким образом, исходя из предположения теоремы, нам удалось вывести ее заключение. 1.2.2.
Ñâåäåíèå ê îïðåäåëåíèÿìВ двух предыдущих теоремах использовались такие хорошо известные понятия, какцелые числа, сложение и умножение. Во многих других теоремах, в том числе во многихтеоремах теории автоматов, понятия, используемые в утверждениях, могут быть не стольочевидными. Для многих доказательств оказывается полезным следующее правило.• Если вы не знаете, с чего начать доказательство, то замените все понятия, входящие в гипотезу, их определениями.Приведем пример теоремы, которую легко доказать, переписав ее утверждение в элементарных терминах.
В ней используются следующие определения.1.Множество S называется конечным, если существует целое число n, и S содержитровно n элементов. Мы пишем ||S|| = n, где ||S|| обозначает число элементов во множестве S. Если множество S не является конечным, то его называют бесконечным.Интуитивно бесконечное множество можно представлять как множество, число элементов которого больше любого целого числа.• Если множества S и T являются подмножествами некоторого множества U, то говорят, что T есть дополнение S (относительно множества U), если S U T = U иS I T = ∅. Таким образом, всякий элемент U содержится в одном, и только в одном, из множеств S или T. Другими словами, в T содержатся те, и только те, элементы U, которые не содержатся в S.Теорема 1.5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
