Рекурсивне означення (також індуктивне означення) у математичній логіці та інформатиці — задання елементів множин через інші елементи цієї ж множини (Aczel 1978:740).
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpOWtMMlE1TDB0dlkyaEdiR0ZyWlM1emRtY3ZNakl3Y0hndFMyOWphRVpzWVd0bExuTjJaeTV3Ym1jPS5wbmc=.png)
Рекурсивне означення функції встановлює результат функції для деяких параметрів через її ж результат для інших параметрів. Наприклад, функція факторіала 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) визначає множину натуральних чисел, видаляючи всі підмножини, що містять ненатуральні числа.
Властивості рекурсивно-означених функцій і множин часто можна вивести з принципу математичної індукції (який слідує рекурсивному означенню). Наприклад, означення натуральних чисел наведене вище напряму містить принцип індукції для натуральних чисел: якщо властивість чинна для натурального числа 0, і властивість чинна для n+1 кожного разу, коли вона чинна для n, тоді властивість чинна для всіх натуральних чисел (Aczel 1978:742).
Види рекурсивних означень
Більшість рекурсивних означень у своїй основі мають два елементи: початкове значення (базис, англ. basis) і індуктивне твердження. Наявність базису — основна відмінність рекурсивного означення від : базис (або кілька базисів) дає означення функції без звернення до самої функції (тобто, без рекурсії). На противагу, кругове (або циркулярне, англ. circular) означення часто не має базису, і задає значення функції через те саме значення (замість інших значень) цієї функції. Дана ситуація приводить до (нескінченної регресії).
Чинність рекурсивного означення (іншими словами, твердження, що рекурсивне означення задає унікальну функцію) є теоремою у теорії множин, доказ якої нетривіальний. Коли областю визначення функції є натуральні числа, достатніми умовами для чинності означення є наявність значення (базис), і наявність алгоритму, що для всіх n>0 задає
у термінах
(індуктивне твердження).
Цей розділ потребує доповнення. (лютий 2018) |
Див. також
Джерела
- Paul Halmos: Naive set theory, van Nostrand, 1960
- P. Aczel (1977), "An introduction to inductive definitions", Handbook of Mathematical Logic, J. Barwise (ed.), .
- James L. Hein (2009), Discrete Structures, Logic, and Computability. .
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет