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

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

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

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

{\begin{aligned}&0!=1.\\&(n+1)!=(n+1)\cdot n!.\end{aligned}}

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

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

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

1 находится в $\mathbb {N} .$
Если элемент n находится в $\mathbb {N}$ тогда $n + 1$ находится в $\mathbb {N} .$
$\mathbb {N}$ — наименьшее множество, удовлетворяющее (1) и (2).

Существует множество наборов, удовлетворяющих (1) и (2) — например, набор ${1, 1,649, 2, 2,649, 3, 3,649,\dots}$ удовлетворяет определению. Однако условие (3) уточняет набор натуральных чисел, удаляя наборы с посторонними членами.

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

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

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

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

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

То, что рекурсивные определения действительны – это означает, что рекурсивное определение идентифицирует уникальную функцию – это теорема теории множеств, известная как теорема о рекурсии , доказательство которой нетривиально. ^[3] значение $f (0)$ Если областью определения функции являются натуральные числа, достаточные условия для того, чтобы определение было действительным, состоят в том, что задано $(т. е. базовый случай) и что для n > 0$ дан алгоритм определения $f (n)$ через $n$ , $f(0),f(1),\dots ,f(n-1)$ (т.е. индуктивное предложение).

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

Принцип рекурсивного определения [ править ]

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

{\begin{aligned}h(1)&=a_{0}\\h(i)&=\rho \left(h|_{\{1,2,\ldots ,i-1\}}\right){\text{ for }}i>1.\end{aligned}}

Примеры рекурсивных определений [ править ]

Элементарные функции [ править ]

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

{\begin{aligned}&0+a=a,\\&(1+n)+a=1+(n+a).\end{aligned}}

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

{\begin{aligned}&0\cdot a=0,\\&(1+n)\cdot a=a+n\cdot a.\end{aligned}}

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

{\begin{aligned}&a^{0}=1,\\&a^{1+n}=a\cdot a^{n}.\end{aligned}}

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

{\begin{aligned}&{\binom {a}{0}}=1,\\&{\binom {1+a}{1+n}}={\frac {(1+a){\binom {a}{n}}}{1+n}}.\end{aligned}}

Простые числа [ править ]

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

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

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

Неотрицательные четные числа [ править ]

Четные числа можно определить как состоящие из

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

Хорошо составленная формула [ править ]

Понятие правильно сформированной формулы (wff) в логике высказываний определяется рекурсивно как наименьшее множество, удовлетворяющее трем правилам:

$p$ — это wff, если $p$ — пропозициональная переменная.
$\neg p$ — это wff, если $p$ — это wff.
$(p • q)$ является wff, если $p$ и $q$ являются wff и • является одной из логических связок ∨, ∧, → или ↔.

Определение можно использовать, чтобы определить, является ли какая-либо конкретная строка символов wff:

$(p \land q)$ является wff, потому что пропозициональные переменные $p$ и $q$ являются wff, а $\land$ является логической связкой.

$\neg (p \land q)$ — это wff, потому что $(p \land q)$ — это wff.

$(\neg p \land \neg q)$ — это wff, потому что $\neg p$ и $\neg q$ — это wff, а $\land$ — логическая связка.

определения как логические Рекурсивные программы

Логические программы можно понимать как наборы рекурсивных определений . ^[5]^[6] Например, рекурсивное определение четного числа можно записать в виде логической программы:

even(0).
even(s(s(X))) :- even(X).

Здесь :- представляет собой , если и s(X) представляет собой преемника X, а именно X+1, как в арифметике Пеано .

Язык логического программирования Пролог использует обратные рассуждения для решения задач и ответов на запросы. Например, учитывая запрос ?- even(s(s(0))) это дает ответ true. Учитывая запрос ?- even(s(0)) это дает ответ false.

Программу можно использовать не только для проверки истинности запроса, но и для генерации верных ответов. Например:

?- even(X).
X = 0
X = s(s(0))
X = s(s(s(s(0))))
X = s(s(s(s(s(s(0))))))
.....

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

even(0).
even(s(X)) :- not(even(X)).

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

Примечания [ править ]

^ Хенкин, Леон (1960). «О математической индукции». Американский математический ежемесячник . 67 (4): 323–338. дои : 10.2307/2308975 . ISSN 0002-9890 . JSTOR 2308975 .
^ «Все о рекурсии» . www.cis.upenn.edu . Проверено 24 октября 2019 г.
^ Доказательство теоремы о рекурсии см. в книге Леона Хенкина «О математической индукции » (1960) .
^ Манкрес, Джеймс (1975). Топология, первый курс (1-е изд.). Нью-Джерси: Прентис-Холл. п. 68, упражнения 10 и 12 . ISBN 0-13-925495-1 .
^ Денекер, М., Терновска, Э.: Логика немонотонных индуктивных определений. АКМ Пер. Вычислить. Бревно. 9(2), 14:1–14:52 (2008)
^ Уоррен, Д.С. и Денекер, М., 2023. Лучшая логическая семантика для пролога. В Прологе: Следующие 50 лет (стр. 82–92). Чам: Springer Nature, Швейцария.

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

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

[1] Хенкин, Леон (1960). «О математической индукции». Американский математический ежемесячник . 67 (4): 323–338. дои : 10.2307/2308975 . ISSN 0002-9890 . JSTOR 2308975 .

[2] «Все о рекурсии» . www.cis.upenn.edu . Проверено 24 октября 2019 г.

[3] Доказательство теоремы о рекурсии см. в книге Леона Хенкина «О математической индукции » (1960) .

[Munkres-4] Манкрес, Джеймс (1975). Топология, первый курс (1-е изд.). Нью-Джерси: Прентис-Холл. п. 68, упражнения 10 и 12 . ISBN 0-13-925495-1 .

[5] Денекер, М., Терновска, Э.: Логика немонотонных индуктивных определений. АКМ Пер. Вычислить. Бревно. 9(2), 14:1–14:52 (2008)

[6] Уоррен, Д.С. и Денекер, М., 2023. Лучшая логическая семантика для пролога. В Прологе: Следующие 50 лет (стр. 82–92). Чам: Springer Nature, Швейцария.

[1]

[2]

[3]

[4]

[5]

[6]