Рекурсивное определение

редактировать

Четыре этапа создания снежинки Коха. Как и во многих других фракталах, стадии получаются с помощью рекурсивного определения.

В математике и информатике рекурсивное определение, или индуктивное определение, используется для определения элементов в наборе с точки зрения других элементов в наборе (Aczel 1977 : 740ff). Некоторые примеры рекурсивно определяемых объектов включают факториалы, натуральные числа, числа Фибоначчи и троичный набор Кантора.

A рекурсивный определение функции функция определяет значения функции для некоторых входов в терминах значений той же функции для других (обычно меньших) входов. Например, факториал функция n! определяется правилами

0! = 1.

(n + 1)! = (n + 1) · n !.

Это определение действительно для каждого натурального числа n, потому что рекурсия в конечном итоге достигает базового случая 0. Определение также может можно рассматривать как процедуру для вычисления значения функции n !, начиная с n = 0 и продолжая далее с n = 1, n = 2, n = 3 и т. д.

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

Индуктивное определение множества описывает элементы в множестве с точки зрения других элементов в множестве. Например, одно определение набора N из натуральных чисел :

1 находится в N.
Если элемент n находится в N, то n + 1 находится в N.
N- это пересечение всех наборов, удовлетворяющих (1) и (2).

Есть много наборов, которые удовлетворяют (1) и (2) - например, набор {1, 1.649, 2, 2.649, 3, 3.649,...} удовлетворяет определению. Однако условие (3) определяет набор натуральных чисел, удаляя наборы с посторонними элементами. Обратите внимание, что это определение предполагает, что N содержится в большем наборе (таком как набор действительных чисел), в котором определена операция +.

Свойства рекурсивно определенных функций и множеств часто можно доказать с помощью принципа индукции, который следует рекурсивному определению. Например, определение натуральных чисел, представленное здесь, непосредственно подразумевает принцип математической индукции для натуральных чисел: если свойство имеет место для натурального числа 0 (или 1), и свойство выполняется для n + 1, когда оно имеет значение n, тогда это свойство имеет место для всех натуральных чисел (Aczel 1977: 742).

Содержание

1 Форма рекурсивных определений
- 1.1 Принцип рекурсивного определения
2 Примеры рекурсивных определений
- 2.1 Элементарные функции
- 2.2 Простые числа
- 2.3 Неотрицательные четные числа
- 2.4 Правильно построенные формулы
3 См. Также
4 Примечания
5 Ссылки

Форма рекурсивных определений

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

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

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

То, что рекурсивные определения действительны - а это означает, что рекурсивное определение идентифицирует уникальную функцию - это теорема теории множеств, известная как теорема рекурсии, доказательство чего нетривиально. Если областью определения функции являются натуральные числа, достаточными условиями для допустимости определения являются следующие: значение $f (0) {\ displaystyle f (0)}$ $f (0)$ (т. Е. Базовый случай), а для n>0 дан алгоритм для определения $f (n) {\ displaystyle f (n)}$ $f (n)$ в терминах $n, f (0), f (1),…, f (n - 1) {\ displaystyle n, f (0), f (1), \ ldots, f (n-1)}$ ${\ displaystyle n, f (0), f (1), \ ldots, f (n-1)}$ (т.е. индуктивное предложение).

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

Принцип рекурсивного определения

Пусть $A {\ displaystyle A}$ $A$ будет набором, а $a 0 {\ displaystyle a_ {0}}$ $a_ {0}$ будет элементом $А {\ Displaystyle A}$ $A$ . Если $ρ {\ displaystyle \ rho}$ $\ rho$ - это функция, которая присваивает каждой функции $f {\ displaystyle f}$ $f$ отображение непустой части положительных целых чисел в $A {\ displaystyle A}$ $A$ , элемент $A {\ displaystyle A}$ $A$ , тогда существует уникальная функция $h: Z + → A { \ displaystyle h: \ mathbb {Z} _ {+} \ to A}$ ${ \ displaystyle h: \ mathbb {Z} _ {+} \ to A}$ так, что

h (1) = a 0 {\ displaystyle h (1) = a_ {0}}

{\ displaystyle h (1) = a_ {0}}

h (i) = ρ (h | {1, 2,…, i - 1}) для i>1. {\ displaystyle h (i) = \ rho (h | _ {\ {1,2, \ ldots, i-1 \}}) {\ text {for}} i>1.}

h(i)=\rho (h|_{\{1,2,\ldots,i-1\}}){\text{ for }}i>1.

Примеры рекурсивных определений

Элементарные функции

Сложение определяется рекурсивно на основе подсчета как

0 + a = a, {\ displaystyle 0 + a = a,}

{\ displaystyle 0 + a = a,}

(1 + n) + a = 1 + (n + a). {\ displaystyle (1 + n) + a = 1 + (n + a).}

{\ displaystyle (1 + n) + a = 1 + (n + a).}

Умножение рекурсивно определяется как

0 a = 0, { \ displaystyle 0a = 0,}

{\ displaystyle 0a = 0,}

(1 + n) a = a + na. {\ displaystyle (1 + n) a = a + na.}

{\ displaystyle (1 + n) a = a + na.}

Возведение в степень рекурсивно определяется как

a 0 = 1, {\ displaystyle a ^ {0} = 1,}

{\ displaystyle a ^ {0} = 1, }

a 1 + n = aan. {\ displaystyle a ^ {1 + n} = aa ^ {n}.}

{\ displaystyle a ^ {1 + n} = aa ^ {n}.}

Биномиальные коэффициенты можно определить рекурсивно как

(a 0) = 1, {\ displaystyle {\ binom {a} {0}} = 1,}

{\ displaystyle {\ binom {a} {0}} = 1,}

(1 + a 1 + n) = (1 + а) (ан) 1 + п. {\ displaystyle {\ binom {1 + a} {1 + n}} = {\ frac {(1 + a) {\ binom {a} {n}}} {1+ n}}.}

{\ displaystyle {\ binom {1 + a} {1 + n}} = {\ frac {(1 + a) {\ binom {a} {n}}} {1 + n}}.}

Прим e числа

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

1 не является простым числом,
любое другое положительное целое число является простое число тогда и только тогда, когда оно не делится на любое простое число, меньшее его самого.

Простота целого числа 1 является базовым случаем; проверка простоты любого большего целого числа X по этому определению требует знания простоты каждого целого числа от 1 до X, что хорошо определяется этим определением. Последнее утверждение может быть доказано индукцией по X, для которой важно, чтобы во втором предложении говорилось «тогда и только тогда»; если бы было сказано просто «если», примитивность, например, 4 не была бы ясна, и дальнейшее применение второго предложения было бы невозможным.

Неотрицательные четные числа

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

0 находится в наборе E неотрицательных событий (базовое предложение),
Для любого элемента x в множестве E, x + 2 находится в E (индуктивное предложение),
В E нет ничего, если оно не получено из базисного и индуктивного предложений (экстремальное предложение

Правильно построенные формулы

Рекурсивные определения чаще всего встречаются в логике или компьютерном программировании. Например, правильно построенная формула (wff) может быть определена как:

символ, который обозначает предложение - например, p означает «Коннор - юрист ".
Знак отрицания, за которым следует wff - как Np, означает:« Неправда, что Коннор - адвокат ».
Любой из четыре двоичных связки (C, A, K или E), за которыми следуют две wffs. Символ K означает «оба верны», поэтому Kpq может означать «Коннор - юрист, а Мэри любит музыку».

Ценность такого рекурсивного определения заключается в том, что его можно использовать для определения того, является ли какая-либо конкретная строка символов «правильно сформированной».

Kpq сформирован правильно, потому что это K, за которым следует атомарный wffs p, а q.
NKpq сформирован правильно, потому что он N, за которым следует Kpq, который, в свою очередь, является wff.
KNpNq - это K, за которым следуют Np и Nq ; и Np - wff и т. д.

См. также

Примечания

Ссылки

Пол Халмос (1960). Наивная теория множеств. ван Ностранд. OCLC 802530334.
Aczel, Peter (1977). «Введение в индуктивные определения». В Барвайз, Дж. (Ред.). Справочник по математической логике. Исследования по логике и основам математики. 90. Северная Голландия. С. 739–782. DOI : 10.1016 / S0049-237X (08) 71120-0. ISBN 0-444-86388-5.
Хайн, Джеймс Л. (2010). Дискретные структуры, логика и вычислимость. Джонс и Бартлетт. ISBN 978-0-7637-7206-2. OCLC 636352297.