「再帰」の版間の差分

履歴の双方向閲覧

← 古い編集新しい編集 →

削除された内容追加された内容

ビジュアルウィキテキスト

インライン

2022年9月11日 (日) 03:34時点における版

再帰（さいき　英:Recursion,Recursive）は、ある物事について記述する際に、記述しているもの自体への参照が^{[注釈 1]}、その記述中にあらわれることをいう。

再帰は、言語学から論理学に至る様々な分野で使用されている。最も一般的な適用は数学と計算機科学で、定義されている関数がそれ自身の定義の中で参照利用されている場合を言う。

定義

平行な合わせ鏡の間に物体を置くと、その像が鏡の中に無限に映し出される。このように、あるものが部分的にそれ自身で構成されていたり、それ自身によって定義されている時に、それを「再帰的(Recursive)」だとニクラウス・ヴィルトが呼ぶようになった^[1]^[2]。論理的思考の重要な特質のひとつであり、数学では漸化式や数学的帰納法が再帰的構造を持っている^[1]。計算機科学だと、オブジェクト (プログラミング)やメソッド (計算機科学)のクラス (コンピュータ)が、以下2つの項目で定義できる場合に再帰的構造だと言える。

単純な基底段階(base case) - 答えを出すのに再帰を使わない、論理展開の終着点。基底は複数あっても構わない。
再帰段階(recursive step) - 後続のあらゆる事例を基底段階に帰着させる一連の法則。

例えば、これは人間の祖先の再帰的定義である。ある人物の祖先は次のいずれかになる。

その人物の親（基底段階）、または
その人物の親の祖先（再帰段階）。

フィボナッチ数列は、再帰を用いた古典的な数式例である。

基底1として $Fib(0)=0$ ,
基底2として $Fib(1)=1$ ,
$n>1$ のあらゆる整数について $Fib(n)=Fib(n-1)+Fib(n-2)$ .

多くの数学的公理は、再帰を用いた法則に基づいている。例えば、ペアノ公理による自然数の正式な定義は「ゼロは自然数であり、各自然数には後続数があり、これも自然数である」と記述されうる^[3]。この基底段階および再帰を用いた法則によって、全ての自然数の集合を生成できる。

他にも再帰を用いて定義されている数学的対象としては、関数の漸化式、集合のカントール集合、フラクタル分野、プログラミング言語における階乗、などがある。

言語

言語学者ノーム・チョムスキーらは、言語において適格文の数に上限がなく、適格文の長さにも上限がないことは、自然言語での再帰の結果として説明可能だと論じている^[4]^[5]。

これは、文章など統語範疇での再帰的定義という観点から理解可能である。文章では、動詞の補語などが別の文章という構造を持つことができる。「ドロシーは魔女が危険だと考えている」には「魔女は危険だ」の一文がより大きな文章に含まれている。それゆえ文章とは、名詞句と動詞に別の文章を含みうる構造を持つものだと、再帰的に（非常に大まかだが）定義することができる。

これは、文章が任意の長さになり得ることも意味する。例えば、英語だと関係代名詞の"that"を使うことによって、

"Dorothy thinks that Toto suspects that Tin Man said that..."

と再帰的に文を継ぎ足すことが可能である。再帰的に定義できうる文章の他にも多くの構造があり、別の品詞に文章を組み込む方法も沢山ある（例えば修飾語を文章形式にする）。長い歳月を経て、言語には一般的にこの種の分析で順応性があることが証明されている^[6]。

しかし近年、再帰が人類の言語の本来的な性質であるという一般的に受け入れられている思想は、ダニエル・L・エヴェレットによって彼のピダハン語研究に基づく反論が行われている。アンドリュー・ネヴィンズ、デイヴィッド・ペセツキー、シリーン・ロドリゲスがこれに反対する識者達である^[7]。いずれの場合でも、文学的な自己言及は数学的・論理的な再帰とは種類が異なると論じられている^[8]。

再帰は、構文だけでなく自然言語の意味論においても重要な役割を果たしている。例えば接続詞"and"は、文意に沿った新しい文章を付加できる機能だと解釈することが可能で、名詞句や動詞句などに適用できる。これは、文を繋げる単純な場合について定義したもので、他の接続詞は同様の観点から再帰的に定義することができる^[9]。

再帰を使った洒落

たまに再帰は、計算機科学・プログラミング等の書物で、ジョークとして掲載される場合がある。そうした本では概して循環定義や自己参照が付されており、次のような馬鹿らしい項目が用語集として載っていることも珍しくない。

再帰については「再帰」を参照のこと^[10]。

これは想定した再帰段階が基底段階へと帰着することなく、無限後退を引き起こすという（プログラミング失敗例の）洒落である。この手の最初のジョークは1975-76年に出版されたプログラム言語の教本『Let's talk Lisp 』と『in Software Tools』に見られる。これは関数型プログラミングを伝授する一環としての洒落で、上の書籍が出版される前に（米国の）プログラミング関連コミュニティで既に広まっていた。

もう一つの冗談が「再帰を理解するには、再帰を理解する必要がある」^[10]というものである。英語版Googleウェブ検索エンジンで"recursion"を検索すると、同サイトでは一番上に"Did you mean: recursion（再帰って意味だったかな）"と赤く表示される^[11]^{[注釈 2]}。

再帰的頭字語は、再帰を含んだ洒落の例である。例えば、PHP (プログラミング言語)は"PHP Hypertext Preprocessor"の略で、WINEは"WINE Is Not an Emulator"、GNUは"GNU's not Unix"を表す。

数学

日本国内の数学では、"Recursion"や"Recursive"に対して再帰の代わりに「帰納」の訳語をあてた数学用語も幾つか存在する（帰納的可算集合、帰納言語、帰納的関数など）。これは下にある「自然数の再帰的定義の例」でも分かるように、数学における再帰には数学的帰納法と原理的な共通性があるためである。

再帰的定義

詳細は「再帰的定義」を参照

例: 自然数

「閉包」も参照

再帰的に定義された集合の標準例が、自然数である。

0 は

\mathbb {N}

に含まれる。

仮にnが

\mathbb {N}

に含まれるなら、n+1は

\mathbb {N}

に含まれる。

自然数の集合

\mathbb {N}

とは、上記2つの性質を満たす最小の集合である^{[注釈 3]}。

数理論理学において、ペアノの公理とはドイツの数学者リヒャルト・デーデキントとイタリアの数学者ジュゼッペ・ペアノによって19世紀に提示された自然数の公理である。ペアノ公理は、再帰的な後者関数と再帰関数としての加算・乗算を参照して自然数を定義している。

例: 証明手続き

もう1つの例は、以下のように帰納または再帰を用いて定義される証明手続き (Proof procedure) の観点から定義される公理体系内のあらゆる「証明可能な」命題の集合である。

ある命題が公理であるならば、それは証明可能な命題である。
ある命題が推論規則によって真に到達可能な命題から導出できるなら、それは証明可能な命題である。
証明可能な命題の集合は、これらの条件を満たす命題の最小の集合である。

有限分割規則

詳細は「:en:Finite subdivision rule」を参照

有限分割規則は再帰の幾何学的形式で、これはフラクタル模様を作図するのに使用される。分割規則は、有限に多くのラベルでラベル付けされた多角形の集まりを起点として、各多角形は最初の多角形ラベルにのみ依存する方法で、より小さなラベル付き多角形に分割される。この工程は繰り返し行うことができる。カントール集合を作るための標準的な「3等分の中央部を除去する」技法が、分割規則の例である。

関数での再帰

詳細は「漸化式」を参照

関数は自身を再帰的に定義する場合がある。とりわけ漸化式が数列を再帰的に定める数式であり、その身近な例が $F(n)=F(n-1)+F(n-2)$ というフィボナッチ数列である。こうした漸化式による定義が成立する場合、その数式は再帰を用いずに定義された基底値（フィボナッチの場合 $F(0)=0$ と $F(1)=1$ ）に帰着できる必要がある。また、漸化式の再帰関係を解いた場合は非再帰的な定義（一般項）を得ることが可能である^{[注釈 4]}。

有名な再帰関数にアッカーマン関数があるが、これは原始再帰関数よりも早く増大して巨大数を生み出すため、再帰を使わずに一般項を簡単な式で表すことが出来ない^[13]点がフィボナッチ数列とは異なる。

再帰的定義を含む証明

前節のような、再帰的定義がされた集合や関数に対して複数場合分けによる証明の標準的な手法を適用すると、構造的帰納法が得られる。これは数理論理学とコンピュータサイエンスで証明を導出するのに広く使用されている数学的帰納法の強力な一般化である。

再帰を使った最適化

動的計画法は、多周期ないし多段階の最適化問題を再帰形式で再記述する数理最適化へのアプローチ手法である。動的計画法の主な成果がベルマン方程式で、これは最適化問題の直近時（直近段階）での値を、その次回時刻（次段階）における値の観点から記述するものである。

再帰定理

集合論において、これは再帰的定義がなされた関数が存在することを保証する定理である。集合 $X$ と、 $X$ の要素 $a$ と、関数 $f : X \to X$ が与えられた場合に、任意の自然数 $n$ について

F(0)=a

F(n+1)=f(F(n))

となるような一意な関数 $F:\mathbb {N} \to X$ (where $\mathbb {N}$ が存在する、と同定理は述べている（ここでの $\mathbb {N}$ は、ゼロを含む自然数の集合を示す）。

一意性の証明

2つの関数 $F:\mathbb {N} \to X$ と $G:\mathbb {N} \to X$ を採ると:

F(0)=a

G(0)=a

F(n+1)=f(F(n))

G(n+1)=f(G(n))

ここで $a$ は $X$ の要素である。

すべての自然数 $n$ について $F (n) = G (n)$ であることは数学的帰納法によって証明できる。

基底段階:

F (0) = a = G (0)

だから

n = 0

に対して等式が成り立つ。

帰納段階: ある

k\in \mathbb {N}

.について

F (k) = G (k)

と仮定すると、

F (k + 1) = f (F (k)) = f (G (k)) = G (k + 1)

である。

したがって

F (k) = G (k)

は

F (k + 1) = G (k + 1)

を含んでいる。

帰納法により、全ての $n\in \mathbb {N}$ について $F (n) = G (n)$ である。

計算機科学

単純化の一般的な方法は、問題を同じ種類の小問に分割することである。コンピュータプログラミングの技法としてこれは分割統治法と呼ばれ、多くの重要なアルゴリズム設計の鍵となる。分割統治法は、問題解決へのトップダウン型アプローチとして機能し、そこでは問題がより小さなインスタンスを解決することにより解決される。反対のアプローチ手法は動的計画法である。こちらはボトムアップ型アプローチとして機能し、目的の規模に達するまでより大きなインスタンスを解決することによって問題が解決される。

プログラミングの観点では、nを表現するのにn-1という参照を持ち出してくるものを「再帰」という。再帰の古典的な例としては、C言語で与えられた階乗関数の定義がある。

/* 階乗 n! の計算 */
int fact(int n) {
  if (n == 0) return 1; /* 基底段階。(n = 0) の場合: 1*/
  else return fact(n - 1) * n; /* 再帰的な構造。(n > 0) の場合: n * (n - 1)!。再帰呼出し */
}

この関数では、掛け算のため入力自身より小さな(n-1)という参照を再帰的に呼び出し、再帰呼び出しの結果にnを掛ける処理を、階乗の数学的定義と同じく基底段階の値に達するまで実行する。

アルゴリズムにおける再帰の使用には、長所も短所もある。主な長所は、一般に命令の単純さである。主な短所は、自身を呼び出す手法なので引数が再帰終了条件を満たさない状況を避けるよう値の変化に注意する必要があること。また、再帰アルゴリズムのメモリ使用量が著しく激増して負荷ががかかるため^[1]、大規模なインスタンスを扱うには非実用的な点である。

再帰呼出し

手続きや関数といった概念をもつプログラミング言語では、ある手続き中で再びその手続き自身を呼び出すことを認める場合が多い。これを再帰呼出しといい、階乗計算やフィボナッチ数列のように、本来再帰的な構造をもつアルゴリズム（再帰的アルゴリズム）を記述するのに適している。

複数の手続き／関数が互いに相手を呼ぶ場合も、広い意味での再帰呼出し（相互再帰）である。C言語での例：

void a() {
    b();
}
void b() {
    a();
}

処理を中断・終了する基底条件が必ず1つは必要で、その部分が誤っていると、無限に関数を呼び出し続けることがある（暴走）。無限再帰に陥ると、スタックオーバーフローによりプログラムが異常終了したり、システムが停止したりする原因となる。

再帰的データ構造

「再帰データ型」も参照

連結リストや木構造は、要素（ノード）の型の中にその要素型自身への参照（自己参照）が存在するようなデータ型を用いて実現される。これは再帰的データ構造（再帰データ型）である。再帰的データ構造の探索には、再帰呼び出しを使うことが多い。

下記は Java での例。Tree のクラス定義の中で Tree を使用している。

class Tree {
    Tree[] children;
}

生物学

ある大きな部位が複数の小さな自己相似に分岐する構造（フラクタル）など、再帰的な過程によって生じたと思われる形状が、植物や動物で時々見られる。野菜のロマネスコがその一例である^[14]

芸術

「ドロステ効果」も参照

ロシアで生まれたマトリョーシカ人形は、再帰という概念の物理的造形例で^[15]、日本ではこうした形式を「入れ子細工」とも呼んでいる。

再帰は、1320年に作られたジョットの三連祭壇画 (Stefaneschi Triptych) 以来、絵画で使用されている。この中央パネルにはステファネスキ枢機卿のひざまずく姿があり、三連祭壇画自体を供物として掲げている^[16]^[17]。この手法は一般的にドロステ効果と通称されており、紋中紋技法の一例である。

マウリッツ・エッシャーによる1956年の作品 (Print Gallery (M. C. Escher)) は、再帰的な絵を飾った画廊を含む歪んだ都市を描いた版画で、無限に堂々巡りする構図となっている^[18]。

日本の文芸作品では、夢野久作の『ドグラ・マグラ』が再帰的である。本作の序盤に、記憶喪失の青年は『ドグラ・マグラ』なる小説（記憶喪失の精神患者が書いたもの）を見つけることになり、この作中作に綴られている展開や結末をなぞるかのように本作も展開していき混迷の結末へ、という入れ子構造が見られる^[19]。

類似する概念

ここではプログラミング手続きの観点から、再帰との主な違いを述べる。

回帰 - 元々あったオブジェクト（元の位置や状態）に戻ってくる事を指す。

対して「再帰」は元々のオブジェクトではなく、その参照 (計算機科学)にあたる小さいオブジェクトを呼び出す。

帰納 - 証明手続きの方向性として「基底段階の小さなものから段々と大きい（普遍的な）もの」へと進んでいく。特に数学的帰納法の帰納段階では、任意の自然数 $k$ に対して $P(k)\to P(k+1)$ が成り立つ事を示す。

対して「再帰」のプログラムは「大きなものから、段々と小さいもの」に進んでいく^[20]。

P(k)

を計算するために

k-1

の参照オブジェクトを呼び出し、この

k

が基底段階に達するまで処理を繰り返し行う。

脚注

注釈

^ 記述している対象と同義な性質・情報を有する（幾何学でいう相似関係の）主に小さい事象を参照と呼ぶ。記述している対象と完全に同一なもの（幾何学でいう合同図形）は、参照に含めない。
^ 顛末まで解説すると、"recursion"の文字列には青のページリンクが張られており、このリンク先が"recursion"を再検索（自己参照）した結果ページという洒落。日本語版Google検索でも、「再帰」を検索すると同様の仕組みが「もしかして：再帰」で見られる。
^ なお、自然数に0を含めるか否かは扱う数学分野によって異なることがある（例えば数論や解析学では一般に0を含めない）。詳細は自然数を参照。
^ フィボナッチ数列の非再帰的な一般項は、次の通り^[12]: $F_{n}={\frac {1}{\sqrt {5}}}\left\{\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}\right\}$

出典

^ ^a ^b ^c 林創「再帰呼び出しを含む手続き処理の難しさ」日本認知科学会『認知科学』6巻 (1999) 4号、389-405頁
^ Wirth,N.(1986)Algorithms & Data Structures（浦昭二・国府方久史　訳『アルゴリズムとデータ構造』東京近代科学社、1990年）
^ “Peano axioms | mathematics” (英語). Encyclopedia Britannica. 2019年10月24日閲覧。
^ Pinker, Steven (1994). The Language Instinct. William Morrow
^ Pinker, Steven; Jackendoff, Ray (2005). “The faculty of language: What's so special about it?”. Cognition 95 (2): 201?236. doi:10.1016/j.cognition.2004.08.004. PMID 15694646.
^ Nordquist, Richard. “What Is Recursion in English Grammar?” (英語). ThoughtCo. 2019年10月24日閲覧。
^ Nevins, Andrew; Pesetsky, David; Rodrigues, Cilene (2009). “Evidence and argumentation: A reply to Everett (2009)”. Language 85 (3): 671?681. doi:10.1353/lan.0.0140. オリジナルの2012-01-06時点におけるアーカイブ。.
^ Drucker, Thomas (4 January 2008). Perspectives on the History of Mathematical Logic. Springer Science & Business Media. p. 110. ISBN 978-0-8176-4768-1
^ Barbara Partee and Mats Rooth. 1983. In Rainer Bäuerle et al., Meaning, Use, and Interpretation of Language. Reprinted in Paul Portner and Barbara Partee, eds. 2002. Formal Semantics: The Essential Readings. Blackwell.
^ ^a ^b Hunter, David (2011). Essentials of Discrete Mathematics. Jones and Bartlett. pp. 494. ISBN 9781449604424
^ “recursion - Google Search”. www.google.com. 2019年10月24日閲覧。
^ 奥村晴彦『C言語による最新アルゴリズム事典』技術評論社、1991年、305頁。ISBN 4-87408-414-1。
^ 百物語改め「九一三・六物語」「アッカーマン関数の漸化式による説明、数列・カリー化」2015年1月27日
^ “Picture of the Day: Fractal Cauliflower” (2012年12月28日). 2020年4月19日閲覧。
^ “Recursion”. 2015年9月24日閲覧。 “More examples of recursion: Russian Matryoshka dolls. Each doll is made of solid wood or is hollow and contains another Matryoshka doll inside it.”
^ “Giotto di Bondone and assistants: Stefaneschi triptych”. The Vatican. 2015年9月16日閲覧。
^ Svozil, Karl (2018). Physical (A)Causality: Determinism, Randomness and Uncaused Events. Springer. pp. 12
^ “Art and Mathematics” (2007年9月5日). 2020年7月5日閲覧。
^ ホンシェルジュ「5分でわかる『ドグラ・マグラ』読んだら気が狂う？【あらすじと解説】」2022年3月24日
^ タクマ「【再帰的プログラム】再帰・帰納の違いを解説【階乗0!が1の理由】」2020年5月21日

外部リンク

「再帰処理」を使って幾何学模様を描いてみよう - マイナビ、関数プログラムを含めた解説
Recursion - tutorial by Alan Gauld
Zip Files All The Way Down

[1] 記述している対象と同義な性質・情報を有する（幾何学でいう相似関係の）主に小さい事象を参照と呼ぶ。記述している対象と完全に同一なもの（幾何学でいう合同図形）は、参照に含めない。

[13] 顛末まで解説すると、"recursion"の文字列には青のページリンクが張られており、このリンク先が"recursion"を再検索（自己参照）した結果ページという洒落。日本語版Google検索でも、「再帰」を検索すると同様の仕組みが「もしかして：再帰」で見られる。

[14] なお、自然数に0を含めるか否かは扱う数学分野によって異なることがある（例えば数論や解析学では一般に0を含めない）。詳細は自然数を参照。

[16] フィボナッチ数列の非再帰的な一般項は、次の通り^[12]: $F_{n}={\frac {1}{\sqrt {5}}}\left\{\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}\right\}$ 　

[HH-2] 林創「再帰呼び出しを含む手続き処理の難しさ」日本認知科学会『認知科学』6巻 (1999) 4号、389-405頁

[3] Wirth,N.(1986)Algorithms & Data Structures（浦昭二・国府方久史　訳『アルゴリズムとデータ構造』東京近代科学社、1990年）

[4] “Peano axioms | mathematics” (英語). Encyclopedia Britannica. 2019年10月24日閲覧。

[5] Pinker, Steven (1994). The Language Instinct. William Morrow

[6] Pinker, Steven; Jackendoff, Ray (2005). “The faculty of language: What's so special about it?”. Cognition 95 (2): 201?236. doi:10.1016/j.cognition.2004.08.004. PMID 15694646.

[7] Nordquist, Richard. “What Is Recursion in English Grammar?” (英語). ThoughtCo. 2019年10月24日閲覧。

[8] Nevins, Andrew; Pesetsky, David; Rodrigues, Cilene (2009). “Evidence and argumentation: A reply to Everett (2009)”. Language 85 (3): 671?681. doi:10.1353/lan.0.0140. オリジナルの2012-01-06時点におけるアーカイブ。.

[Drucker2008-9] Drucker, Thomas (4 January 2008). Perspectives on the History of Mathematical Logic. Springer Science & Business Media. p. 110. ISBN 978-0-8176-4768-1

[10] Barbara Partee and Mats Rooth. 1983. In Rainer Bäuerle et al., Meaning, Use, and Interpretation of Language. Reprinted in Paul Portner and Barbara Partee, eds. 2002. Formal Semantics: The Essential Readings. Blackwell.

[Hunter-11] Hunter, David (2011). Essentials of Discrete Mathematics. Jones and Bartlett. pp. 494. ISBN 9781449604424

[12] “recursion - Google Search”. www.google.com. 2019年10月24日閲覧。

[algo-15] 奥村晴彦『C言語による最新アルゴリズム事典』技術評論社、1991年、305頁。ISBN 4-87408-414-1。

[17] 百物語改め「九一三・六物語」「アッカーマン関数の漸化式による説明、数列・カリー化」2015年1月27日

[18] “Picture of the Day: Fractal Cauliflower” (2012年12月28日). 2020年4月19日閲覧。

[19] “Recursion”. 2015年9月24日閲覧。 “More examples of recursion: Russian Matryoshka dolls. Each doll is made of solid wood or is hollow and contains another Matryoshka doll inside it.”

[20] “Giotto di Bondone and assistants: Stefaneschi triptych”. The Vatican. 2015年9月16日閲覧。

[21] Svozil, Karl (2018). Physical (A)Causality: Determinism, Randomness and Uncaused Events. Springer. pp. 12

[22] “Art and Mathematics” (2007年9月5日). 2020年7月5日閲覧。

[23] ホンシェルジュ「5分でわかる『ドグラ・マグラ』読んだら気が狂う？【あらすじと解説】」2022年3月24日

[24] タクマ「【再帰的プログラム】再帰・帰納の違いを解説【階乗0!が1の理由】」2020年5月21日

[注釈 1]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[注釈 2]

[注釈 3]

[注釈 4]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[12]

表話編歴フラクタル
特徴	フラクタル次元 Assouad（英語版） Box-counting（英語版） Correlation（英語版）ハウスドルフ Packing（英語版）位相再帰（英語版）自己相似自己相似過程スケール不変性
反復関数系	バーンズリーのシダカントール集合ドラゴン曲線レヴィC曲線コッホ雪片メンガーのスポンジシェルピンスキーのカーペットシェルピンスキーの三角形空間充填曲線 T-square（英語版）
ストレンジアトラクター	多重フラクタル系（英語版）
L-system	空間充填曲線
Escape-time fractals	バーニングシップ・フラクタルジュリア集合充填リアプノフ・フラクタルマンデルブロ集合ニュートン・フラクタル（英語版）
確率的フラクタル	ブラウン運動非整数ブラウン運動ブラウンの木（英語版）拡散律速凝集フラクタル地形 Lévy flight（英語版）パーコレーション理論（英語版） Self-avoiding walk（英語版）
人物	ゲオルク・カントールフェリックス・ハウスドルフガストン・ジュリアヘルゲ・フォン・コッホポール・レヴィアレクサンドル・リャプノフブノワ・マンデルブロルイス・フライ・リチャードソンヴァツワフ・シェルピニスキ
その他	"How Long Is the Coast of Britain?（英語版）" 海岸線のパラドックス List of fractals by Hausdorff dimension（英語版） The Beauty of Fractals（英語版） (1986 book)
カテゴリ

表話編歴数理論理学
一般	形式言語構成規則形式体系演繹システム（英語版）形式的証明形式意味論論理式集合元クラス古典論理公理自然演繹推論規則関係定理論理的帰結公理系型理論記号（英語版）統語論（英語版）理論（英語版）
Traditional logic（英語版）	命題推論論証妥当性 Cogency 三段論法 Square of opposition（英語版）ベン図
命題論理・ブール論理	ブール関数命題論理命題論理式（英語版）論理演算真理値表多値論理
述語論理	一階量化子述語（英語版）二階 Monadic predicate calculus（英語版）
素朴集合論	集合空集合元数え上げ外延有限集合無限集合部分集合冪集合可算集合非可算集合帰納的集合定義域終域像写像関数関係順序対
集合論	数学基礎論ツェルメロ＝フレンケル集合論選択公理一般集合論（英語版） Kripke–Platek 集合論（英語版）フォン・ノイマン＝ベルナイス＝ゲーデル集合論（英語版）モース-ケリー集合論タルスキ＝グロタンディーク集合論（英語版）
モデル理論	モデル（英語版）解釈（英語版）超準モデル（英語版）有限モデル理論真理値妥当性
証明論	形式的証明演繹システム（英語版）形式体系定理論理的帰結推論規則統語論（英語版）シークエント計算
計算理論再帰理論	計算可能性計算複雑性複雑性クラス P≠NP予想再帰帰納的集合帰納的可算集合決定問題停止性問題チャーチ＝チューリングのテーゼ計算可能関数原始再帰関数 μ再帰関数チューリングマシンラムダ計算