Непейвода. Прикладная логика

§ 6.1. О РАЗНЫХ ВИДАХ ИНДУКЦИИ

применяемым

Все вы знакомы с методом математической индукции,

к утверждениям, содержащим свободную переменную по натуральным

числам. Приведем пример доказательства по индукции.

Пример 6.1.1. Докажем, что сумма трех последовательных кубов нату-

ральных чисел делится на 9.

Базис. 13

+ 23 + 33 = 36 и делится на 9.

Шаг. Чтобы произвести шаг, нужно предположить доказываемое

утверждение для n и затем

доказать его для n + 1. Пусть n3

+ (n +

1)3 + (n + 2)3 делится на 9.

Тогда

(n + 1)3 + (n + 2)3 + (n + 3)3 =

(n + 1)3 + (n + 2)3 + n3 + 9n2 + 27n + 27 =

(n3 + (n + 1)3 + (n + 2)3) + (9n2 + 27n + 27).

Но все слагаемые в последней скобке делятся на 9, а первая скобка де-

лится на 9 по предположению, значит, и исходная сумма делится на 9.

Таким образом, мы установили, что делимость суммы, начинающейся с

n, влечет делимость суммы,

начинающейся с n + 1.

Следовательно, утверждение доказано для всех n.

утверждение,

Итак, в математической индукции имеются базис —

что свойство выполнено для самого маленького из рассматриваемых чи-

сел, и шаг —

обоснование перехода от числа n к числу n + 1.

На язы-

ке логики метод математической индукции представляется следующей

формулой:

A(0) & n (A(n) A(n + 1)) n A(n).

(6.1)

Пример 6.1.3. Пусть на плоскости имеется точечный прожектор, осве-

щающий сектор внутри угла α < 180◦. Пусть заданы n непересекаю-

щихся отрезков (которые могут смыкаться концами). Докажем, что то-

гда выполнено одно и только одно из трех:

1.

Прожектор не освещает ни одной точки ни одного отрезка.

2.

Прожектор освещает конец хотя бы одного из отрезков

3.

Имеется отрезок ai (часть которого, пересекающаяся с сектором,

полностью освещена), полностью затеняющий все остальные, пе-

ресекающиеся с сектором освещения.

6.1. ОБ ИНДУКЦИЯХ

143

Точка A затенена отрезком ai, если внутри отрезка OA встре-

чается точка из ai.

Базис индукции. Если у нас всего один отрезок AB, то он либо пе-

ресекается, либо не пересекается с освещенным сектором. Если он не

пересекается, то выполнена первая возможность. Если же он пересека-

ется,

то либо хотя бы один из его концов лежит в освещенном секторе,

либо же оба они лежат вне его.

В первом случае соответствующий ко-

нец A освещен (либо же, если отрезок тянется вдоль луча OA и B лежит

на этом луче до A, то освещен

B). Во втором возьмем на отрезке про-

извольную точку C, лежащую внутри освещенного сектора. Отрезок не

может лежать вдоль OC, так как его концы не освещены, значит, точка

C освещена.

Шаг индукции. Пусть для любой системы из n отрезков имеет место

один из рассмотренных случаев. Рассмотрим систему из n + 1 отрезка.

Удалим из нее последний отрезок. Рассмотрим три возможных случая

для получившейся системы.

, . . . , an не освещен, то ни один из них

Если ни один из отрезков a1

не пересекается с сектором освещения, и все рассматривается точно так

же, как в базисе индукции, в соответствии с положением последнего

отрезка.

Если некоторые из концов отрезков были освещены, то рассмотрим,

затеняет ли их отрезок an+1. Если все освещенные концы им затеняют-

ся, то остается рассмотреть два подслучая:

1.

Хотя бы один из концов an+1 лежит в секторе освещения. Тогда

хотя бы один из его концов будет освещен, и выполнен второй слу-

чай.

2.

Оба конца этого отрезка лежат вне сектора освещения. Тогда он

затеняет все остальные отрезки, а его пересекающаяся с сектором

освещения часть полностью освещена.

В программировании математическая индукция соответствует ци-

клам типа пересчета (for i:=0 to k do языка Паскаль).

Применение математической индукции, конечно же, содержит мно-

го тонкостей. Приведем несколько софизмов, доказываемых при помо-

щи неправильного применения индукции.

Пример 6.1.4. Докажем, что все лошади одного цвета. Действуем по

индукции. Параметр индукции —

число n лошадей в их множестве.

Базис. n = 1. Одна лошадь, естественно, одного цвета. Точнее, все

лошади, принадлежащие одноэлементному множеству лошадей, одного

цвета.

Шаг. Пусть доказано для n. Докажем для n + 1. Возьмем произвольное

множество Л из n + 1 лошади. Удалим из него некоторую лошадь л0.

По предположению индукции, Л0 = Л \ {л0} состоит из лошадей од-

ного цвета. Теперь удалим из

Л0 некоторую лошадь л1 и добавим туда

л0. Полученное множество Л1

также состоит из лошадей одного цвета,

значит, л0 того же цвета, что и остальные лошади из Л1, а они являются

элементами Л0

и того же цвета, что и л1. Что и требовалось доказать.

Пример 6.1.5.

Докажем, что все ученые —

лысые.

Документально засвидетельствовано,

что у некоторых академиков

на голове не осталось ни одного волоса. Тогда они, естественно, лысые.

Но если лысому человеку добавить один волос, то он останется лы-

сым. Значит, по индукции получаем, что ученые с любым количеством

волос на голове лысые.

Ошибки найдите сами.

Принцип математической индукции допускает несколько перефор-

мулировок, которые в традиционной математике эквивалентны исход-

ному принципу.

возвратная индукция. Здесь переход происходит

Первая из них —

не от одного значения к следующему, а от всех предыдущих значений

к последующему, шаг индукции переводит не от A(n) к A(n + 1), а от

x < n A(x) к

A(n). Как ни парадоксально, при таком переходе не тре-

6.1. ОБ ИНДУКЦИЯХ

145

B

B

·

A

C

A·

·C

E1·

D

·E2

D

E1

E2

Для треугольника это доказывается в элементарной математике, а

многоугольников с числом углов меньше 3

нет. Таким образом, утвер-

ждение индукции доказано для всех n 6 31.

Пусть имеется многоугольник с числом сторон n > 3, и для всех

k < n утверждение индукции уже доказано.

Возьмем в многоугольнике

любые три смежные вершины A, B, C. Из вершины B либо виден один

из других углов D2, либо не виден ни один,

и тогда все лучи, лежащие

в угле ABC, первой пересекают одну и ту же сторону многоугольника.

В последнем из случаев могу быть еще два подслучая, симметрич-

ных друг другу. Либо на продолжении одной из сторон BA, BC первой

встречается некоторая вершина D, либо никакой вершины не встреча-

ется.

Тогда могут быть два случая (см. рис. 6.1).

1.

Луч первой пересекает одну из сторон многоугольника. Тогда мно-

гоугольник разбивается лучом на два многоугольника. В каждом

из них появляется одна новая вершина D, но пары вершин {A, E1},

{B, E2} лежат в разных многоугольниках, так что каждый из них

содержит меньшее число вершин, чем исходный. Пусть один из

них содержит m1 вершин, а второй —

m2. Тогда m1 + m2 = n + 2

(поскольку вершина B теперь принадлежит обоим многоугольни-

кам, а D вообще новая и также принадлежит им обоим). Соответ-

1 Хотя мы только что обращали внимание на то, что формально возвратная индукция

базиса не требует, фактически подобие базиса появляется практически в каждом таком

доказательстве, поскольку случаи для наименьших возможных n обычно приходится

рассматривать отдельно.

2 Виден —

означает, что отрезок BD целиком лежит внутри открытого многоуголь-

ника

146

ГЛАВА 6. ИНДУКЦИЯ И ОПРЕДЕЛЕНИЯ

2. Луч прежде всего входит в вершину многоугольника. Опять-таки

многоугольник разбивается на два многоугольника. В каждом из

них присутствуют две вершины исходного многоугольника B и

D, а все остальные вершины распределены между ними. Каждый

из получившихся многоугольников содержит меньше вершин, чем

исходные,

поскольку в нем не присутствует хотя бы одна из вер-

шин A, C.

Еще одна переформулировка метода математической индукции бы-

ла известна еще древним грекам, хотя явно сформулировали ее лишь в

XVII веке. Это —

метод бесконечного спуска.

Если для

каждого натурального числа, удовлетворяющего

свойству A(n), найдется меньшее, удовлетворяющее этому

же свойству, то чисел n, для которых выполнено A(n), во-

обще нет.

Или формально:

n (A(n) m(m < n & A(m))) n ¬A(n).

(6.2)

Метод бесконечного спуска получается просто контрапозицией шага из

возвратной индукции по ¬A(n), а попробуйте Вы усмотреть это из их

содержательных формулировок!

Рассмотрим пример применения метода бесконечного спуска.

Пример 6.1.7. Докажем, что абсурдно предположение, что у каждого

человека мать являлась человеком. В самом деле, за все время суще-

ствования Земли на ней жило конечное число людей. Пусть у каждого

человека мать —

человек. Упорядочим людей по моментам рождения.

Список всех бывших людей в порядке времени рождения назовем Кни-

гой Судеб3. Мать рождается раньше своих детей, и поэтому в Книге Су-

деб она стоит раньше. Таким образом, для каждого человека найдется

стоящий раньше него в Книге Судеб. По принципу бесконечного спуска,

получаем, что людей вообще нет и не было, что абсурдно4. Полученное

противоречие доказывает утверждение.

Еще одно следствие из возвратной индукции, эквивалентное ей5:

принцип наименьшего числа.

3

Книга Судеб — легендарная книга, в которую Аллах записал еще до сотворения

Земли судьбу каждого человека.

4

Правда, Диоген искал хотя бы одного человека в Афинах днем с огнем. . .

5

Но только в классической математике!

6.1. ОБ ИНДУКЦИЯХ

147

§ 6.2.

ОБ ИНДУКТИВНЫХ ОПРЕДЕЛЕНИЯХ

Индуктивное определение имеет следующую общую форму:

(Базис индукции) Выражения вида A есть B.

(Шаг индукции) Если мы имеем выражения A1, . . . , An типа B, то

C, построенное из них, также есть выражение типа B.

С каждым индуктивным определением связан принцип индукции по

построению объекта типа B.

(Базис индукции) Каждый объект вида A обладает свойством θ.

им

(Шаг индукции) Если A1, . . . , An обладают свойством θ, то и C

обладает.

(Заключение индукции) Тогда любой объект типа B обладает свой-

ством

θ.

6.2. ОБ ИНДУКТИВНЫХ ОПРЕДЕЛЕНИЯХ

149

современной теории часто приходится рассматривать определения, ко-

торые включают шаги, опирающиеся на бесконечное множество ранее

построенных объектов. Тут индукция остается единственным коррект-

ным и инвариантным способом выражения минимальности7.

Стоит отметить, что логическая индукция по построению вовсе не

требует однозначности представления объекта в форме, соответствую-

щей одному из пунктов его определения. Но для задания функций ин-

дукцией по построению такая однозначность необходима.

Теперь рассмотрим другие возможности, связанные с индуктивны-

ми определениями. Часто несколько понятий вводятся совместным ин-

дуктивным определением, в котором в каждом шаге могут участвовать

уже построенные понятия разных типов. Для того чтобы превратить

раздельные определения формулы и терма в совместное, достаточно вве-

сти пункт типа: если A(x) —

формула, то εx A(x) —

терм8. В совмест-

ных определениях индукцию и рекурсию по построению приходится ве-

сти одновременно для всех понятий. Далее, в математических теориях

широко применяются определения, в шагах которых могут быть ссыл-

ки на бесконечное множество ранее построенных понятий. Они также

допустимы, но, конечно, уже не могут быть прямо перенесены на пред-

ставление данных в программах.

Часто отмечается возможность представления логических формул в

виде дерева. На самом деле в такой же структуре представляются любые

индуктивно определенные понятия. Но называть структуру данных, со-

ответствующую индуктивным определениям, просто деревом несколь-

ко неточно. Как известно, дерево —

это ориентированный граф, в кото-

ром имеется корень и в любую другую вершину ведет ровно один путь

из корня. Таким образом, по определению графа, ребра, выходящие из

любой вершины дерева, равноправны. Структура же, соответствующая

индуктивному понятию, является нагруженным деревом, вершинам ко-

торого сопоставлены слова, а ребра помечены согласно роли их назна-

чения в структуре понятия.

Например, на рис. 6.2 даны формула и соот-

7 В теории множеств часто определяют множество объектов типа B при помощи сле-

дующей процедуры: возьмем пересечение всех множеств объектов, включающих базис

определения и замкнутых относительно его шага. Но такое определение, с одной сторо-

ны, включает в себя скрытый порочный круг (B определяется в том числе и через само

B); с другой стороны, оно не сохраняется при переходе к неклассической логике.

8 Эти термы были введены Д. Гильбертом. Их семантика —

выбрать такое x, что A(x),

150

ГЛАВА 6. ИНДУКЦИЯ И ОПРЕДЕЛЕНИЯ

x

x

y ϕ

B

D

x

&

A

y

ветствующее нагруженное дерево.

Рассмотрение деревьев, соответствующих построению индуктивных

объектов, позволяет вывести мощную и не очень зависящую от измене-

ний взгляда на математику характеризацию минимальности класса объ-

ектов, задаваемых индуктивным определением. Дерево с конечными пу-

тями —

такое, в котором нет ни одного бесконечного пути, и значит,