Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

Структурная индукция используется для доказательства того, что некоторое предложение P ( x ) выполняется для всех x некоторой рекурсивно определенной структуры, такой как формулы , списки или деревья . В структурах определяется хорошо обоснованный частичный порядок («подформула» для формул, «подсписок» для списков и «поддерево» для деревьев). Доказательство структурной индукции - это доказательство того, что предложение верно для всех минимальных структур и что если оно верно для непосредственных подструктур некоторой структуры S , то оно должно выполняться для Sтакже. (Формально говоря, тогда это удовлетворяет посылкам аксиомы хорошо обоснованной индукции , утверждающей, что этих двух условий достаточно для выполнения предложения для всех x .)

Структурно рекурсивная функция использует ту же идею для определения рекурсивной функции: «базовые случаи» обрабатывают каждую минимальную структуру и правило рекурсии. Структурная рекурсия обычно подтверждается структурной индукцией; в особенно легких случаях индуктивный шаг часто не учитывается. Функции length и ++ в приведенном ниже примере структурно рекурсивны.

Например, если структуры представляют собой списки, один , как правило , вводит частичный порядок «<», в котором L < M , когда список L является хвост списка М . При таком порядке пустой список [] является единственным минимальным элементом. Структурное индукционное доказательство некоторого предложения P ( L ) состоит из двух частей: доказательства того, что P ([]) истинно, и доказательства того, что если P ( L ) истинно для некоторого списка L , и если L является хвостом list M , то P ( M ) также должно быть истинным.

В конце концов, может существовать более одного базового случая и / или более одного индуктивного случая, в зависимости от того, как была построена функция или структура. В таких случаях структурное индукционное доказательство некоторого предложения P ( l ) состоит из:

  1. доказательство того, что P ( BC ) истинно для каждого базового случая BC ,
  2. доказательство того, что если P ( I ) истинно для некоторого экземпляра I , а M может быть получено из I , применяя любое одно рекурсивное правило один раз, то P ( M ) также должно быть истинным.

Примеры [ править ]

Древнее древо предков, на котором изображен 31 человек в 5 поколениях

Предок дерево общеизвестной структура данных, показывая родитель, бабушка и дедушка и т.д. человека, насколько известно (см картинки для примера). Это рекурсивно определяется:

  • в простейшем случае дерево предков показывает только одного человека (если об их родителях ничего не известно);
  • в качестве альтернативы, дерево предков показывает одного человека и, соединенные ветвями, два поддеревья предков их родителей (с использованием для краткости доказательства упрощающего предположения, что если один из них известен, известны оба).

Например, свойство «Древо предков, простирающееся на g поколений, содержит не более 2 г  - 1 человека» может быть доказано структурной индукцией следующим образом:

  • В простейшем случае дерево показывает только одного человека и, следовательно, одно поколение; свойство верно для такого дерева, поскольку 1 ≤ 2 1  - 1 .
  • Как вариант, дерево показывает одного человека и деревья его родителей. Поскольку каждая из последних является подструктурой всего дерева, можно предположить, что она удовлетворяет доказываемому свойству (также известному как гипотеза индукции ). То есть можно принять p ≤ 2 g  - 1 и q ≤ 2 h  - 1 , где g и h обозначают количество поколений, на которые распространяется поддерево отца и матери, соответственно, а p и q обозначают количество людей, которых они показывать.
    • В случае g  ≤  h все дерево охватывает 1 +  h поколений и показывает p  +  q  + 1 человек, а p  +  q  + 1 ≤ (2 g  - 1) + (2 h  - 1) + 1 ≤ 2 h  + 2 h  - 1 = 2 1+ h  - 1 , т.е. все дерево удовлетворяет свойству.
    • В случае h  ≤  g все дерево распространяется на 1 +  g поколений и показывает p  +  q  + 1 ≤ 2 1 +  g  - 1 человек по аналогичным соображениям, т.е. все дерево удовлетворяет свойству и в этом случае.

Следовательно, по структурной индукции каждое дерево предков удовлетворяет этому свойству.

В качестве другого, более формального примера рассмотрим следующее свойство списков:

 длина (L ++ M) = длина L + длина M [EQ]

Здесь ++ обозначает операцию конкатенации списков, а L и M - списки.

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

 длина [] = 0 [LEN1] длина (h: t) = 1 + длина t [LEN2]
 [] ++ list = список [APP1] (h: t) ++ list = h: (t ++ list) [APP2]

Наше предложение P ( l ) состоит в том, что EQ верно для всех списков M, когда L равно l . Мы хотим показать, что P ( l ) истинно для всех списков l . Мы докажем это с помощью структурной индукции по спискам.

Сначала докажем, что P ([]) истинно; то есть EQ истинно для всех списков M, когда L оказывается пустым списком []. Рассмотрим эквалайзер:

 длина (L ++ M) = длина ([] ++ M) = длина M (по APP1) = 0 + длина M = длина [] + длина M (по LEN1) = длина L + длина M

Итак, эта часть теоремы доказана; EQ верно для всех M , когда L равно [], потому что левая и правая части равны.

Далее рассмотрим любой непустой список I . Поскольку I непусто, у него есть заголовок x и хвостовой список xs, поэтому мы можем выразить его как (x: xs). Гипотеза индукции состоит в том, что EQ верно для всех значений M, когда L равно xs :

 длина (xs ++ M) = длина xs + длина M (гипотеза)

Мы хотели бы показать, что если это так, то EQ также верно для всех значений M, когда L = I = (x: xs). Действуем как раньше:

 длина L + длина M = длина (x: xs) + длина M = 1 + длина xs + длина M (по LEN2) = 1 + длина (xs ++ M) (по предположению) = длина (x: (xs ++ M)) (по LEN2) = длина ((x: xs) ++ M) (по APP2) = длина (L ++ M)

Таким образом, из структурной индукции получаем, что P (L) истинно для всех списков L.

Хороший порядок [ править ]

Так же, как стандартная математическая индукция эквивалентна принципу хорошего порядка , структурная индукция также эквивалентна принципу хорошего порядка. Если множество всех структур определенного вида допускает хорошо обоснованный частичный порядок, то каждое непустое подмножество должно иметь минимальный элемент. (Это определение « хорошо обоснованного ».) Значение леммы в этом контексте состоит в том, что она позволяет нам сделать вывод, что если есть какие-либо контрпримеры к теореме, которую мы хотим доказать, то должен быть минимальный контрпример. Если мы можем показать, что из существования минимального контрпримера следует еще меньший контрпример, мы получаем противоречие (поскольку минимальный контрпример не минимальный), и поэтому набор контрпримеров должен быть пустым.

В качестве примера этого типа аргумента рассмотрим набор всех двоичных деревьев . Мы покажем, что количество листьев в полном двоичном дереве на единицу больше, чем количество внутренних узлов. Предположим, есть контрпример; тогда должен существовать такой с минимально возможным количеством внутренних узлов. Этот контрпример, C , имеет n внутренних узлов и l листьев, где n  + 1 ≠  l . Более того, C должно быть нетривиальным, потому что тривиальное дерево имеет n  = 0 и l  = 1 и, следовательно, не является контрпримером. Cпоэтому имеет по крайней мере один лист, родительский узел которого является внутренним узлом. Удалите этот лист и его родителя из дерева, переместив родственный узел листа на позицию, ранее занимаемую его родителем. Это уменьшает как n, так и l на 1, так что новое дерево также имеет n  + 1 ≠  l и, следовательно, является меньшим контрпримером. Но по гипотезе C уже был наименьшим контрпримером; следовательно, предположение о существовании каких-либо контрпримеров с самого начала должно было быть ложным. Частичное упорядочение подразумевается «меньше» здесь есть один , который говорит , что S < T , когда S имеет меньше узлов , чем Т .

См. Также [ править ]

Ссылки [ править ]

Ранние публикации о структурной индукции включают: