Рекурсивне означення

Рекурсивне означення (також індуктивне означення) у математичній логіці та інформатиці — задання елементів множин через інші елементи цієї ж множини (Aczel 1978:740).

Чотири стадії побудови сніжинки Коха. Як і для багатьох інших фракталів, стадії задаються рекурсивним означенням.

Рекурсивне означення функції встановлює результат функції для деяких параметрів через її ж результат для інших параметрів. Наприклад, функція факторіала n! визначається наступними правилами:

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

Дане означення дійсне для всіх n, через те, що в процесі рекурсії врешті-решт досягається початковий варіант 0. Означення можна також розуміти як опис процедури, що визначає функцію n!, починаючи з n = 0 і прогресуючи далі для n = 1, n = 2, n = 3, і т.д.

Теорема рекурсії стверджує, що таке означення насправді задає функцію. Доведення ґрунтується на методі математичної індукції.

Індуктивне означення множини описує її елементи через інші елементи. Наприклад, означення множини натуральних чисел N:

  1. 1 належить N.
  2. Якщо елемент n належить N, то n+1 також належить N.
  3. 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 задає у термінах (індуктивне твердження).

Див. також

Джерела
    • Paul Halmos: Naive set theory, van Nostrand, 1960
    • P. Aczel (1977), "An introduction to inductive definitions", Handbook of Mathematical Logic, J. Barwise (ed.), ISBN 0-444-86388-5.
    • James L. Hein (2009), Discrete Structures, Logic, and Computability. ISBN 0-7637-7206-2.

    Шаблон:Види означення

    This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.