Схемы доказательств, основанные на аксиоме индукции

Особую методологическую и практическую значимость для рекурсивных вычислений имеет специальный вид дедуктивный умозаключений - метод полной математической индукции. Его дуальность по отношению к рекурсии проявляется в том, что, во-первых, метод доказательства с помощью индукции есть не что иное, как типичный образец рекурсивных вычислений, а во вторых, метод математической индукции является основным инструментом доказательства правильности рекурсивных алгоритмов. Для более обстоятельного разговора на этот счет предварительно уточним используемую терминологию и приведем основные схемы доказательств с помощью метода полной математической индукции.

Индукция – логическое умозаключение, ведущее от частных фактов и положений к утверждениям более общего характера. Дедукция – вывод по правилам логики; цепь умозаключений, звенья которой связаны отношением логического следования.

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

Пусть требуется доказать справедливость некоторого утверждения P(n) для любого натурального n. Доказательство (" n)P(n) методом математической индукции состоит из двух частей:

Справедливость обоих утверждений доказывается дедуктивно. А из истинности базиса и индукционного шага по аксиоме математической индукции (5-я аксиома Пеано в аксиоматике арифметики) и делается вывод о справедливости P(n) для любого натурального n. Таким образом, математическая индукция есть специальный вид дедуктивных рассуждений в математике. К методу математической индукции относят и другие схемы доказательств, основанные на использовании аксиомы индукции. Некоторые из них собраны в таблице 1.

Вторая схема возвратной индукции обобщается в так называемую трансфинитную индукцию, в основе которой лежит использование вполне упорядоченных множеств и аксиомы выбора. Имеются и другие разновидности дедуктивных рассуждений, аналогичных математической индукции.

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

Мультипликативная индукция. Под ней понимается следующая разновидность индуктивных доказательств.

Пусть требуется доказать справедливость некоторого утверждения Â для всех натуральных n>1. Сделать это можно так.

Отсюда по теореме об однозначности разложения натуральных чисел, больших единицы, на простые сомножители вытекает, что утверждение Â выполнено для всех n>1.

Веерная индукция. Под ней понимается следующая разновидность индуктивных доказательств.

Пусть требуется доказать справедливость некоторого утверждения Â для всех натуральных n³k (k - натуральное). Сделать это можно так.

Отсюда вытекает, что утверждение Â выполнено для всех n>k. Этот факт доказывается уже методом простой индукции. И сделать это можно, например, так. Проведем индукцию по s, устанавливая справедливость Â для натуральных чисел n вида: k^s-1£ n<k^s- 1 (s=2,3,…). При s=2 это так, что вытекает из базиса внешней индукции. Пусть при некотором натуральном p³ s утверждение Â выполнено для значений n из диапазона: k^p-1£ n<k^p- 1. Тогда из индуктивного шага внешней индукции следует справедливость Â для всех n× k+r (0£ r<k- 1), то есть для всех n таких, что: k^p£ n<k^p+1- 1. Следовательно, Â выполнено для любых n вида: k^s-1£ n<k^s- 1 при всех s=2,3,… . Это и означает справедливость Â для всех n³ k.

Теперь несколько слов о рекурсивной сути дедуктивного метода полной математической индукции, а точнее его опоры - 5-ой аксиомы Пеано. Остановимся сначала на первом варианте простой индукции (см. табл. 1).

Простая индукция (первый вариант). Пусть утверждение P(n) требуется доказать для каждого натурального n и, тем или иным способом, удалось установить справедливость утверждений: P(1) (базис индукции) и (" n)[P(n)® P(n+1)] (индукционный шаг). Дальше на основании 5-ой аксиомы Пеано в аксиоматике арифметики делаем вывод о справедливости P(n) для любого натурального n. В чем же суть этой аксиомы и где здесь рекурсия? Дело все в том, что если базис индукции P(1) считать базой рекурсии, то индукционный шаг “вычерчивает” однозначную траекторию переходов (утверждений о справедливости) от P(1) до всякого P(n) при фиксированном значении n: P(1)® P(2)® … ® P(n). Но такая жесткая траектория переходов однозначно определяет последовательность обратных ссылок от P(n) при фиксированном n до P(1): P(n) Þ P(n- 1) Þ … Þ P(1). А на это соотношение мы можем смотреть как на последовательное сведение задачи вычисления (доказательства справедливости) P(k) к вычислению P(k- 1) для значений k: k=n, n- 1,…,2, то есть пока не попадем в базу рекурсии P(1), одновременно являющуюся и базисом индукции. А далее на исходную последовательность переходов P(1)® P(2)® … ® P(n) можно смотреть как на проведение серии отложенных вычислений вплоть до получения P(n), то есть решения исходной задачи для любого фиксированного n.

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

Индукция спуска. Пусть утверждение P(n) требуется доказать для каждого натурального n удовлетворяющего условиям: k£ n£ m (k и m - натуральные) и, тем или иным способом, удалось установить справедливость утверждений: P(m) (базис индукции) и (" n: k<n£ m)[P(n)® P(n- 1)] (индукционный шаг). Будем считать базис индукции P(m) считать базой рекурсии. Индукционный шаг “вычерчивает” однозначную траекторию переходов (утверждений о справедливости) от P(m) до всякого P(1): P(m) ® P(m- 1) ® … ® P(1). Но такая жесткая траектория переходов однозначно определяет последовательность обратных ссылок от P(1) до P(m): P(1) Þ P(2) Þ … Þ P(m). А на это соотношение мы можем смотреть как на последовательное сведение задачи вычисления (доказательства справедливости) P(k- 1) к вычислению P(k) для значений k: k=2, 3,…, m, то есть пока не попадем в базу рекурсии P(m). А далее на исходную последовательность переходов P(m) ® P(m- 1) ® … ® P(1) можно смотреть как на проведение серии отложенных вычислений вплоть до получения P(1), то есть решения исходной задачи.

Какие же можно сделать выводы из проведенных рассуждений? Они таковы. Во-первых, каждый тип индукции определяет некоторый рекурсивный процесс, то есть, фактически задает конкретную стандартную форму рекурсивных вычислений. Во-вторых, основания арифметики, а значит и всей математики, базируются на рекурсии. Следовательно, рекурсия может служить методологической основой и информатики и, в частности, обучения алгоритмизации.

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

В заключение этого раздела заметим, что применение индукции в рекурсии часто опирается на понятие частично упорядоченного множества.