|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 構造 ： [こうぞう] 【名詞】 1. structure 2. construction ・ 的 ： [まと, てき] 【名詞】 1. mark 2. target ・ 帰納 ： [きのう] (n,vs) inductive ・ 帰納法 ： [きのうほう] 【名詞】 1. induction 2. inductive method ・ 法 ： [ほう] 1. (n,n-suf) Act (law: the X Act)
構造的帰納法()とは、数学的帰納法を一般化した証明手法の一つ。数理論理学、計算機科学、グラフ理論などの数学分野で使用される。 構造的再帰(structural recursion)は再帰の手法の一つ。通常の再帰が数学的帰納法と関係を持つのと同様に、構造的再帰は構造的帰納法と関係を持つ。 ==概要== 構造的帰納法は、（リストや木構造のように）再帰的に定義された構造のある種の ''x'' に関する全称命題 ''∀x. P(x)'' を証明する手法である。そのような構造の上には、整礎な半順序が定義できる。（リストに対する「部分リスト」、木構造に対する「部分木」など。） 構造的帰納法による証明は、構造のすべての極小元がある性質を持ち、「ある構造 ''S'' の直接の部分構造がその性質を持つなら、''S'' もその性質を持つ」ことを示すものである。（形式的にいえば、それによって整礎帰納法の原理の前提が証明されるため、整礎帰納法から結論が導かれる。このことから、前述の2つの条件が「すべての ''x'' がその性質が持つ」ことを示すのに十分だといえるのである。） 構造的に再帰した関数(structurally recursive function)は、再帰関数と同じ考え方で定義される。基礎ケース(base cases)が各極小元を処理し、帰納ステップと呼ばれる規則が再帰を処理する。構造的再帰の正しさは、通常、構造的帰納法によって証明される。特に簡単な場合には、帰納ステップはしばしば省略される。以下の ''length'' 関数と ++ 演算子は、構造的に再帰した関数の例である。 例として線型リストの構造を考える。通常は半順序 '<' を、リスト L, M に対して「L が M の尾部(tail)であるときに ''L < M''」と定める（厳密にはその推移閉包をとる）。この順序において、空のリスト ''[]'' は唯一の極小元である。リストの元 l に対する述語 ''P(l)'' の構造的帰納法による証明は、次の2つの部分証明からなる。 # ''P([])'' が真である。 # あるリスト ''L'' について ''P(L)'' が真であり、''L'' がリスト ''M'' の尾部であると仮定したとき、''P(M)'' も真である。 結局のところ、関数や構造の定義の仕方によっては、基礎ケースが2つ以上あったり、帰納ケースが2つ以上あったりする。それゆえ、それらのケースにおいて、ある性質 ''P(l)'' の構造的帰納法による証明は次の2つからなる。 # 各基礎ケース ''BC'' に対して ''P(BC)'' を証明する。 # 構造のある要素 ''I'' について ''P(I)'' が真であり、''M'' が ''I'' にいずれかの再帰ルールを適用して得られるなら、''P(M)'' もまた真である、ということを証明する。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「構造的帰納法」の詳細全文を読む スポンサード リンク
|