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

Конечно, неплохо уметь чувствовать истинность необходимого вам утверждения, однако плохо то, что в школе теперь не изучают весьма важные методики доказательств. А между тем, всякий, кто занимается информатикой, должен уметь понимать доказательства. Некоторые специалисты в области информатики придерживаются крайней точки зрения, полагая, что формальное доказательство корректности программы должно идти рука об руку с ее написанием. Продуктивность такого подхода вызывает сомнение.

С другой стороны, есть и такие, ко- торые считают, что в программировании как дисциплине нет места доказательствам. Среди них популярен девиз; "Если ты не уверен в правильности своей программы— запусти ее и убедись". Мы занимаем промежуточную позицию по отношению к этим полярным подходам. Тестирование программ, безусловно, важно.

Однако тестирование проходит до поры до времени, поскольку вы не в состоянии проверить работу вашей программы для всех возможных входных данных. Важнее, что, если ваша программа достаточно сложна (скажем, какая-нибудь хитрая рекурсия или итерация), то, не зная точно, что происходит при входе в цикл нли рекурсивном вызове некоторой функции, вы вряд ли сумеете верно записать код. Получив сообщение об ошибке, вам все равно придется искать правильное решение. Чтобы правильно выполнить рекурсию или итерацию, необходимо предварительно построить некую индуктивную гипотезу, причем полезно обосновать формально или неформально, что эта гипотеза остается истинной при рекурсии или итерации.

В сущности, процедура уяснения механизма работы правильно написанной программы— это то же самое, что процедура доказательства по индукции теоремы. Поэтому наряду с моделями, полезными для различных видов программного обеспечения, в курсе теории автоматов традиционно изучают и методы формальных доказательств. Теория автоматов, пожалуй, в большей степени, чем все остальные предметы, лежащие в основе информатики, прибегает к естественным и содержательным доказательствам, как дедуктивным (состоящим из последовательности обоснованных шагов), так и индуктивным. Последние представляют собой рекурсивные доказательства параметризованных утверждений, в которых используется само утверждение с "меньшими'* значениями параметра. 1.2.1. Дедуктивные доказательства Как указывалось выше, дедуктивное доказательство состоит из последовательности утверждений, истинность которых следует из некоторого исходного утверждения, называемого гипотезой, или данным утверждением ~данными утверждениями), или посылкой.

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

В таких случаях каждое из этих утверждений считается гипотезой или данным утверждением. Теорема„которую мы доказываем, переходя от гипотезы Н к заключению С, является утверждением вида "если Н, то С"'. Мы говорим, что С логически (дедуктивно) следует из Н. Следующая теорема служит иллюстрацией утверждения данного типа. Теорема 1.3. Еслнх>4,то2" >х'. П Формальное доказательство теоремы 1.3, основанное на индукции, мы рассмотрим в примере 1.17.

Неформальное же доказательство этой теоремы особых усилий не требует. Для начала отметим, что гипотезой Н является угверждение "х > 4". Эта гипотеза зависит от параметра х, а потому не является ни истинной, ни ложной. Истинность Н зависит от значения параметра х: так, например, при х = 6 она верна, а при х = 2 — ложна. Точно так же заключение С вЂ” это утверждение "2" > хэ". Данное утверждение также зависит от параметра х и является истинным при одних значениях параметра и ложным — при других. Например, С ложно при х = 3, поскольку 2 = 8 не превышает 3' = 9.

з С другой стороны, С истинно при х= 4, так как 2 = 4 = 16. Для х = 5 утверждение также истинно, поскольку 2' = 32 не меньше, чем 5' = 25. Интуиция наверняка вам подсказывает, что утверждение 2' > х' истинно при х > 4. В его истинности при х = 4 мы уже убедились. Если х > 4 н х возрастает, то 2* удваивается всякий раз, когда значение х увеличивается на 1. При этом выражение х', стоящее в правой части, увеличивается в ((х т 1)/х)' раз. Если х>4, то 11х е 1)/х) не превышает 1.25„ следовательно, 1(х + 1)/х)' не превышает 1.5625.

Поскольку 1.5625 < 2, то при х >4 с ростом х левая часть 2" растет быстрее, чем правая х'. Таким образом, если, начиная со значения х, при котором неравенство 2" > х' выполняется, например для х = 4, мы увеличиваем х, то неравенство остается верным. Мы завершили неформальное, но вполне аккуратное доказательство теоремы 1.3. К более строгому доказательству этой теоремы мы еще вернемся в примере 1.17, после то- го как познакомимся с "индуктивными" доказательствами.

Как и все содержательные теоремы, теорема 1.3 охватывает бесконечное число связанных между собой фактов. В данном случае для всех целых х имеем "если х > 4„то 2' > х~". На самом деле, необязательно предполагать, что х — целое. Но, поскольку в доказательстве теоремы говорится лишь об х, возрастаюших на единицу, начиная с х = 4, то в действительности теорема доказана только для целых х.

Из теоремы 1.3 можно вывести ряд других теорем, В следующем примере мы рассмотрим полное дедуктивное доказательство простой теоремы, использующее теорему 1.3. Ь2. ВВЕДЕНИЕ В ТЕОРИЮ ФОРМАЛЬНЫХ ДОКАЗАТЕЛЬСТВ 23 Теорема 1.4. Если х является суммой квадратов четырех положительных целых чисел, то 2' > х . Доказательство. На интуитивном уровне идея доказательства состоит в том, что если Обоснование утверждение ! „= 2 ььг.ьсз+Ы2 2. а>1;Ь>1;с>1;В>1 3, а» > 1; о' > 1; с > 1; ~Р > 1 4. х>4 5. 2'>т Посылка Посылка (2) и свойства арифметики (1), (3) и свойства арифметики (4) и теорема 1.3 Рив.

1В, Форлавьлов Докозательслтво льеоречм 1.4 На шаге 2 записана еще одна часть предположения теоремы: каждое из чисел, возводимых в квадрат, не меньше 1. Технически, это утверждение содержит в себе четыре отдельных утверждения для каждого из данных четырех целых чисел. Затем, на шаге 3, за- ГЛАВА 1. АВТОМАТЫ: МЕТОДЫ И ПОНЯТИЯ прелположение данной теоремы верно лля некоторого х, то, поскольку х — сумма квадратов четырех положительных целых чисел. значение х по крайней мере не меньше 4. Но тогда выполнено условие теоремы 1.3, а поскольку мы считаем, что она верна, то мы можем утверждать, что и заключение этой теоремы справедливо лля х. рассуждения можно представить в виде последовательности шагов, каждый из которых является либо гипотезой доказываемой теоремы, либо ее частью, либо утверждением, которое следует из олного или нескольких предыдуших утвержлений.

Под словом "следует" мы подразумеваем, что, если предыдугцим утверждением является гипотеза какой-либо теоремы, то заключение этой теоремы верно и может быть записано, как утверждение в нашем доказательстве. Это логическое правило часто называют правилом тог4из ропепв. Оно гласит, что, если известно, что утверждение Н истинно и утверждение "если Н, то С."' истинно, то можно заключить, что С также истинно. Кроме того, при выводе утверждений из одного или нескольких предыдущих утверждений допустимы и другие логические шаги. Так, например, если А и  — два предыдущих утвержления, то мы можем вывести и записать утверждение "А и В". На рис.

1.3 приведена вся последовательность утверждений, необходимых для доказательства теоремы 1,4, Отметим, что мы не собираемся доказывать теоремы в такой стилизованной форме, хотя она помогает представить доказательство в виде явного перечня строго обоснованных утверждений. На шаге (1) мы повторяем одну из посылок теоремы: х есть сумма квадратов четырех целых чисел. В доказательствах часто оказывается полезным как-то обозначать величины. Здесь четыре целых числа обозначены как а, Ь, с и А.

мечаем, что квадрат числа, не меньшего 1, также не меньше 1. В качестве обоснования используется истинность утверждения 2 и "свойства арифметики", т.е. мы предполагаем, что читатель знает или может самостоятельно вывести простые утверждения с неравенствами, такие как; "если у > 1„то у > 1". г На шаге 4 используются утверждения 1 и 3. В первом из них говорится, что х есть сумма четырех квадратов, а во втором — что каждый из квадратов не меньше 1. Воспользовавшись известными свойствами арифметики, заключаем, что минимальное значениехравно 1 + !ч-!ч-!, т.е,4. На последнем шаге 5 используем утверждение 4, которое является гипотезой теоремы 1.3. Теорема же сама по себе есть основание, благодаря которому мы можем выписать ее заключение, поскольку предыдущее утверждение является ее предположением.

Так как утверждение 5, т.е. заключение теоремы 1.3, является также заключением теоремы 1.4, то теорема!.4 доказана. Таким образом, исходя из предположения теоремы, нам удалось вывести ее заключение. С3 1.2.2. Сведение к определениям В двух предыдущих теоремах использовались такие хорошо известные понятия, как целые числа, сложение и умножение. Во многих других теоремах, в том числе во многих теоремах теории автоматов, понятия, используемые в утверждениях, могут быть не столь очевидными. Для многих доказательств оказывается полезным следующее правило. ° Если вы не знаете, с чего начать доказательство, то замени~с все понятия, входящие в гипотезу, их определениями. Приведем пример теоремы, которую легко доказать, переписав ее утверждение в элементарных терминах.

В ней используются следующие определения. 1. Множество Б называется конечным, если существует целое число п, и Ь' содержит ровно п элементов. Мы пишем ~Д =- п, где )Д~ обозначает число элементов во множестве 5. Если множество 5 не является конечным, то его называют бесконечным. Интуитивно бесконечное множество можно представлять как множество, число элементов которого больше любого целого числа.