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

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

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

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

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

Это определение справедливо для каждого натурального числа $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),\точки ,f(n-1)$

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

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

Пусть $A$ — множество, а $a 0$ — элемент $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{ для }}i>1.\end{aligned}}

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

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

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

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

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

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

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

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

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

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

Простые числа

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

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] Например, рекурсивное определение четного числа можно записать как логическую программу:

четный ( 0 ). четный ( s ( s ( X )))  :-  четный ( X ).

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

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

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

?-  четный ( X ). X  =  0 X  =  s ( s ( 0 )) X  =  s ( s ( s ( s ( 0 )))) X =  s  ( s ( s ( s ( s ( 0 ) ) )))) .....

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

четный ( 0 ). четный ( s ( X ))  :-  не ( четный ( X )).

Смотрите также

Примечания

^ Хенкин, Леон (1960). «О математической индукции». The American Mathematical Monthly . 67 (4): 323–338. doi :10.2307/2308975. ISSN 0002-9890. JSTOR 2308975.
^ "Все о рекурсии". www.cis.upenn.edu . Получено 24.10.2019 .
↑ Доказательство теоремы о рекурсии см. в книге Леона Хенкина «О математической индукции» (1960).
^ Манкрес, Джеймс (1975). Топология, первый курс (1-е изд.). Нью-Джерси: Prentice-Hall. стр. 68, упражнения 10 и 12. ISBN 0-13-925495-1.
^ Денекер, М., Терновска, Э.: Логика немонотонных индуктивных определений. ACM Trans. Comput. Log. 9(2), 14:1–14:52 (2008)
^ Уоррен, Д.С. и Денекер, М., 2023. Лучшая логическая семантика для пролога. В Prolog: The Next 50 Years (стр. 82-92). Cham: Springer Nature Switzerland.

Ссылки

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