再帰的定義
(帰納的定義 から転送)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/01/15 21:00 UTC 版)
ナビゲーションに移動 検索に移動再帰的定義（Recursive Definition）は、再帰的な定義、すなわち、あるものを定義するにあたってそれ自身を定義に含むものを言う。無限後退を避けるため、定義に含まれる「それ自身」はよく定義されていなければならない。同義語として帰納的定義（Inductive Definition）がある。
概要
循環定義との違いは、再帰的定義にはその定義を使わずに定義される基本となるケースが存在することである。その他のケースの定義は、基本のケースにより近い定義によって定義されなければならない。
例として素数の定義を示す:
- 1は素数ではない。
- 1でない正整数が素数であるとは、自身より小さいどの素数でも割り切れないことである。
整数 1 がこの場合の基本ケースである。それより大きい整数 X が素数かどうかを判定するには、X と 1 の間の全ての整数について素数かどうかを知っている必要がある。そのような整数たちは X よりも基本ケースの 1 に近いので、この定義は再帰的定義として有効である。
対照的に循環定義には基本ケースがなく、単に自身で自身を定義しているにすぎない。これが悪循環を生む。従って「再帰的定義: "再帰的定義"を参照」という記述は循環定義であって再帰的定義ではない。
再帰的定義は論理学やコンピュータプログラミングでよく見受けられる。例えば論理式 (WFF; Well-founded Formula) は次のように定義される:
- 命題を表す記号 p,q, ... はWFFである - 例えば、p は「フレッドは法律家である」、q は「メリーは音楽好きである」を意味する。
- N にWFFが付属したものはWFFである - 例えば N が否定を表すとすると、Np は「フレッドは法律家である、というのは真ではない」を意味する。
- 4種類の論理演算（C, A, K, E）のいずれかに、2つのWFFが付属したものはWFFである。 - 例えば、記号 K が「両方が真である」ことを意味するとすると、Kpq は「フレッドが法律家であり、かつメリーは音楽好きである」という意味である。
- 以上により WFF と定義されるもののみが WFF である。
このような再帰的定義を使って、ある記号列が論理式であるか否かを判定することができる。
- Kpq は、WFF である p と q が K に付属したものであるため、WFF である。
- NKpq は、WFF である Kpq が N に付属したものであるため、WFF である。
- KNpNq は、K に Np と Nq が付属しており、Np および Nq は WFF であるため、WFF である。
- Npq は WFF ではない。
帰納的定義
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/11/01 02:21 UTC 版)
上記の式 (1) で与えられたテイラー展開の最初の 2 項から、最初の 2 つのルジャンドル多項式が P 0 ( x ) = 1 , P 1 ( x ) = x {\displaystyle P_{0}(x)=1,P_{1}(x)=x} となることがわかる。残りの多項式を得るのには、上記のテイラー展開を直截に計算するよりも、ボネの漸化式 ( n + 1 ) P n + 1 ( x ) = ( 2 n + 1 ) x P n ( x ) − n P n − 1 ( x ) {\displaystyle (n+1)P_{n+1}(x)=(2n+1)xP_{n}(x)-nP_{n-1}(x)} を用いるのが適当である。この漸化式は、式 (1) の両辺を t に関して微分したものを整理して得られる等式 x − t 1 − 2 x t + t 2 = ( 1 − 2 x t + t 2 ) ∑ n = 1 ∞ n P n ( x ) t n − 1 {\displaystyle {\frac {x-t}{\sqrt {1-2xt+t^{2}}}}=(1-2xt+t^{2})\sum _{n=1}^{\infty }nP_{n}(x)t^{n-1}} の分母に現れる平方根を式 (1) で置き換えて、t の冪に対する係数比較（英語版）を行えば得られる。漸化式に初期条件としてすでに得られている P0, P1 を当てはめれば、全てのルジャンドル多項式が帰納的に生成される。 漸化式を解いて陽に表せば P n ( x ) = 1 2 n ∑ k = 0 n ( n k ) 2 ( x − 1 ) n − k ( x + 1 ) k = ∑ k = 0 n ( n k ) ( − n − 1 k ) ( 1 − x 2 ) k = 2 n ⋅ ∑ k = 0 n x k ( n k ) ( n + k − 1 2 n ) {\displaystyle {\begin{aligned}P_{n}(x)&={\frac {1}{2^{n}}}\sum _{k=0}^{n}{n \choose k}^{2}(x-1)^{n-k}(x+1)^{k}\\&=\sum _{k=0}^{n}{n \choose k}{-n-1 \choose k}\left({\frac {1-x}{2}}\right)^{k}\\&=2^{n}\cdot \sum _{k=0}^{n}x^{k}{n \choose k}{{\frac {n+k-1}{2}} \choose n}\end{aligned}}} などのように書くことができる。後段はルジャンドル多項式を単に単項式として表して二項係数の乗法公式を使えば、漸化式から直ちに得られる。 具体的に最初のいくつかのルジャンドル多項式を挙げれば以下のようになる： n P n ( x ) {\displaystyle P_{n}(x)} 0 1 {\displaystyle 1} 1 x {\displaystyle x} 2 1 2 ( 3 x 2 − 1 ) {\displaystyle \textstyle {\frac {1}{2}}(3x^{2}-1)} 3 1 2 ( 5 x 3 − 3 x ) {\displaystyle \textstyle {\frac {1}{2}}(5x^{3}-3x)} 4 1 8 ( 35 x 4 − 30 x 2 + 3 ) {\displaystyle \textstyle {\frac {1}{8}}(35x^{4}-30x^{2}+3)} 5 1 8 ( 63 x 5 − 70 x 3 + 15 x ) {\displaystyle \textstyle {\frac {1}{8}}(63x^{5}-70x^{3}+15x)} 6 1 16 ( 231 x 6 − 315 x 4 + 105 x 2 − 5 ) {\displaystyle \textstyle {\frac {1}{16}}(231x^{6}-315x^{4}+105x^{2}-5)} 7 1 16 ( 429 x 7 − 693 x 5 + 315 x 3 − 35 x ) {\displaystyle \textstyle {\frac {1}{16}}(429x^{7}-693x^{5}+315x^{3}-35x)} 8 1 128 ( 6435 x 8 − 12012 x 6 + 6930 x 4 − 1260 x 2 + 35 ) {\displaystyle \textstyle {\frac {1}{128}}(6435x^{8}-12012x^{6}+6930x^{4}-1260x^{2}+35)} 9 1 128 ( 12155 x 9 − 25740 x 7 + 18018 x 5 − 4620 x 3 + 315 x ) {\displaystyle \textstyle {\frac {1}{128}}(12155x^{9}-25740x^{7}+18018x^{5}-4620x^{3}+315x)} 10 1 256 ( 46189 x 10 − 109395 x 8 + 90090 x 6 − 30030 x 4 + 3465 x 2 − 63 ) {\displaystyle \textstyle {\frac {1}{256}}(46189x^{10}-109395x^{8}+90090x^{6}-30030x^{4}+3465x^{2}-63)}
※この「帰納的定義」の解説は、「ルジャンドル多項式」の解説の一部です。
「帰納的定義」を含む「ルジャンドル多項式」の記事については、「ルジャンドル多項式」の概要を参照ください。
- 帰納的定義のページへのリンク
