論理学における公理系の一覧

テンプレート:More citations needed この記事は、命題論理のための代表的なヒルベルト流演繹体系の一覧を含む。

古典命題計算の体系

古典命題計算は標準的な命題論理である。その意図された意味論は二値的であり、その主要な性質は、それが強完全であること、言い換えれば、ある論理式がある前提の集合から意味論的に帰結するときにはいつでも、その前提の集合から統語論的にも帰結するということである。多くの異なる同値な完全公理系が定式化されてきた。それらは、用いられる基本的な結合子の選択によって異なっており、いずれの場合も、その結合子は（すなわち、合成によってすべての n 項の真理値表を表現できるという意味で）関数完全でなければならず、また、選ばれた結合子の基底の上でのちょうどよい完全な公理の選び方によっても異なる。

含意と否定

ここでの定式化では、基本的な結合子の関数完全な集合として含意と否定 $\{\to ,\mathrm{\neg }\}$ を用いる。あらゆる論理体系は、少なくとも1つの非0項推論規則を必要とする。古典命題計算は典型的にはモーダスポネンスの規則を用いる。

$\frac{A,A\to B}{B}.$

特に断りのない限り、以下のすべての体系にはこの規則が含まれるものとする。

フレーゲの公理系：

$A\to (B\to A)$

$(A\to (B\to C))\to ((A\to B)\to (A\to C))$

$(A\to (B\to C))\to (B\to (A\to C))$

$(A\to B)\to (\mathrm{\neg }B\to \mathrm{\neg }A)$

$\mathrm{\neg }\mathrm{\neg }A\to A$

$A\to \mathrm{\neg }\mathrm{\neg }A$

ヒルベルトの公理系：

$A\to (B\to A)$

$(A\to (B\to C))\to (B\to (A\to C))$

$(B\to C)\to ((A\to B)\to (A\to C))$

$A\to (\mathrm{\neg }A\to B)$

$(A\to B)\to ((\mathrm{\neg }A\to B)\to B)$

ウカシェヴィッチの公理系：

• 第1：

  $(A\to B)\to ((B\to C)\to (A\to C))$

  $(\mathrm{\neg }A\to A)\to A$

  $A\to (\mathrm{\neg }A\to B)$

• 第2：

  $((A\to B)\to C)\to (\mathrm{\neg }A\to C)$

  $((A\to B)\to C)\to (B\to C)$

  $(\mathrm{\neg }A\to C)\to ((B\to C)\to ((A\to B)\to C))$

• 第3：

  $A\to (B\to A)$

  $(A\to (B\to C))\to ((A\to B)\to (A\to C))$

  $(\mathrm{\neg }A\to \mathrm{\neg }B)\to (B\to A)$

新井の公理系：

$(A\to B)\to ((B\to C)\to (A\to C))$

$A\to (\mathrm{\neg }A\to B)$

$(\mathrm{\neg }A\to B)\to ((B\to A)\to A)$

ウカシェヴィッチとタルスキの公理系：

$[(A\to (B\to A))\to ([(\mathrm{\neg }C\to (D\to \mathrm{\neg }E))\to [(C\to (D\to F))\to ((E\to D)\to (E\to F))]]\to G)]\to (H\to G)$

メレディスの公理系：

$((((A\to B)\to (\mathrm{\neg }C\to \mathrm{\neg }D))\to C)\to E)\to ((E\to A)\to (D\to A))$

メンデルソンの公理系：

$A\to (B\to A)$

$(A\to (B\to C))\to ((A\to B)\to (A\to C))$

$(\mathrm{\neg }A\to \mathrm{\neg }B)\to ((\mathrm{\neg }A\to B)\to A)$

ラッセルの公理系：

$A\to (B\to A)$

$(A\to B)\to ((B\to C)\to (A\to C))$

$(A\to (B\to C))\to (B\to (A\to C))$

$\mathrm{\neg }\mathrm{\neg }A\to A$

$(A\to \mathrm{\neg }A)\to \mathrm{\neg }A$

$(A\to \mathrm{\neg }B)\to (B\to \mathrm{\neg }A)$

ソボチンスキの公理系：

• 第1：

  $\mathrm{\neg }A\to (A\to B)$

  $A\to (B\to (C\to A))$

  $(\mathrm{\neg }A\to C)\to ((B\to C)\to ((A\to B)\to C))$

• 第2：

  $(A\to B)\to (\mathrm{\neg }B\to (A\to C))$

  $A\to (B\to (C\to A))$

  $(\mathrm{\neg }A\to B)\to ((A\to B)\to B)$

含意と偽

否定の代わりに、古典論理は関数完全な結合子の集合 $\{\to ,\mathrm{\perp }\}$ を用いて定式化することもできる。

タルスキ＝ベルナイス＝テンプレート:仮リンクの公理系：

$(A\to B)\to ((B\to C)\to (A\to C))$

$A\to (B\to A)$

$((A\to B)\to A)\to A$。

$\mathrm{\perp }\to A$

チャーチの公理系：

$A\to (B\to A)$

$(A\to (B\to C))\to ((A\to B)\to (A\to C))$

$((A\to \mathrm{\perp })\to \mathrm{\perp })\to A$

メレディスの公理系：

• 第1：

  $((((A\to B)\to (C\to \mathrm{\perp }))\to D)\to E)\to ((E\to A)\to (C\to A))$

• 第2：

  $((A\to B)\to ((\mathrm{\perp }\to C)\to D))\to ((D\to A)\to (E\to (F\to A)))$

否定と選言

含意の代わりに、古典論理は関数完全な結合子の集合 $\{\mathrm{\neg },\vee \}$ を用いて定式化することもできる。これらの定式化では以下の推論規則を用いる。

$\frac{A,\mathrm{\neg }A\vee B}{B}.$

ラッセル＝ベルナイスの公理系：

$\mathrm{\neg }(\mathrm{\neg }B\vee C)\vee (\mathrm{\neg }(A\vee B)\vee (A\vee C))$

$\mathrm{\neg }(A\vee B)\vee (B\vee A)$

$\mathrm{\neg }A\vee (B\vee A)$

$\mathrm{\neg }(A\vee A)\vee A$

メレディスの公理系：

• 第1：

  $\mathrm{\neg }(\mathrm{\neg }(\mathrm{\neg }A\vee B)\vee (C\vee (D\vee E)))\vee (\mathrm{\neg }(\mathrm{\neg }D\vee A)\vee (C\vee (E\vee A)))$

• 第2：

  $\mathrm{\neg }(\mathrm{\neg }(\mathrm{\neg }A\vee B)\vee (C\vee (D\vee E)))\vee (\mathrm{\neg }(\mathrm{\neg }E\vee D)\vee (C\vee (A\vee D)))$

• 第3：

  $\mathrm{\neg }(\mathrm{\neg }(\mathrm{\neg }A\vee B)\vee (C\vee (D\vee E)))\vee (\mathrm{\neg }(\mathrm{\neg }C\vee A)\vee (E\vee (D\vee A)))$

双対的に、古典命題論理は連言と否定のみを用いて定義することもできる。

連言と否定

ロッサー・J・バークリーは、連言と否定 $\{\wedge ,\mathrm{\neg }\}$ に基づき、モーダスポネンスを推論規則とする体系を作った。彼はその著書の中で、自らの公理図式を提示するために含意を用いた。「$C\to D$」は「$\mathrm{\neg }(C\wedge \mathrm{\neg }D)$」の略記である。

• $A\to A\wedge A$
• $A\wedge B\to A$
• $(A\to B)\to (\mathrm{\neg }(B\wedge C)\to \mathrm{\neg }(C\wedge A))$

この略記を用いない場合、公理図式は次のような形になる。

• $\mathrm{\neg }(A\wedge \mathrm{\neg }(A\wedge A))$
• $\mathrm{\neg }((A\wedge B)\wedge \mathrm{\neg }A)$
• $\mathrm{\neg }(\mathrm{\neg }(A\wedge \mathrm{\neg }B)\wedge \mathrm{\neg }\mathrm{\neg }(\mathrm{\neg }(B\wedge C)\wedge \mathrm{\neg }\mathrm{\neg }(C\wedge A)))$

また、モーダスポネンスは次のようになる。

• $\frac{A,\mathrm{\neg }(A\wedge \mathrm{\neg }B)}{B}$

シェファーストローク

テンプレート:仮リンク（NAND演算子とも呼ばれる）は関数完全であるため、これを用いて命題計算全体の定式化を作ることができる。NANDによる定式化では、ジャン・ニコのモーダスポネンスと呼ばれる推論規則を用いる。

$\frac{A,A\mid (B\mid C)}{C}.$

ニコの公理系：

$(A\mid (B\mid C))\mid [(E\mid (E\mid E))\mid ((D\mid B)\mid [(A\mid D)\mid (A\mid D)])]$

ウカシェヴィッチの公理系：

• 第1：

  $(A\mid (B\mid C))\mid [(D\mid (D\mid D))\mid ((D\mid B)\mid [(A\mid D)\mid (A\mid D)])]$

• 第2：

  $(A\mid (B\mid C))\mid [(A\mid (C\mid A))\mid ((D\mid B)\mid [(A\mid D)\mid (A\mid D)])]$

ワイスバーグの公理系：

$(A\mid (B\mid C))\mid [((D\mid C)\mid [(A\mid D)\mid (A\mid D)])\mid (A\mid (A\mid B))]$

アルゴンヌの公理系：

• 第1：

$(A\mid (B\mid C))\mid [(A\mid (B\mid C))\mid ((D\mid C)\mid [(C\mid D)\mid (A\mid D)])]$

• 第2：

$(A\mid (B\mid C))\mid [([(B\mid D)\mid (A\mid D)]\mid (D\mid B))\mid ((C\mid B)\mid A)]$

アルゴンヌによるコンピュータ解析により、NAND命題計算を定式化するために用いることのできる、さらに60を超える単一公理系が明らかにされている。

含意命題計算

含意命題計算は、含意結合子のみを許容する古典命題計算の断片である。それは（偽と否定を表現する能力を欠くため）関数完全ではないが、統語論的には完全である。以下の含意計算はいずれも推論規則としてモーダスポネンスを用いる。

ベルナイス＝タルスキの公理系：

$A\to (B\to A)$

$(A\to B)\to ((B\to C)\to (A\to C))$

$((A\to B)\to A)\to A$

ウカシェヴィッチとタルスキの公理系：

• 第1：

  $[(A\to (B\to A))\to [([((C\to D)\to E)\to F]\to [(D\to F)\to (C\to F)])\to G]]\to G$

• 第2：

  $[(A\to B)\to ((C\to D)\to E)]\to ([F\to ((C\to D)\to E)]\to [(A\to F)\to (D\to E)])$

• 第3：

  $((A\to B)\to (C\to D))\to (E\to ((D\to A)\to (C\to A)))$

• 第4：

  $((A\to B)\to (C\to D))\to ((D\to A)\to (E\to (C\to A)))$

ウカシェヴィッチの公理系：

$((A\to B)\to C)\to ((C\to A)\to (D\to A))$

直観主義論理と中間論理

直観主義論理は古典論理の部分体系である。これは通常、（関数完全な）基本結合子の集合として $\{\to ,\wedge ,\vee ,\mathrm{\perp }\}$ を用いて定式化される。これは、論理を矛盾させることなく付け加えることのできる排中律 A∨¬A あるいはパースの法則 ((A→B)→A)→A を欠くため、統語論的に完全ではない。これは推論規則としてモーダスポネンスを持ち、以下の公理を持つ。

$A\to (B\to A)$

$(A\to (B\to C))\to ((A\to B)\to (A\to C))$

$(A\wedge B)\to A$

$(A\wedge B)\to B$

$A\to (B\to (A\wedge B))$

$A\to (A\vee B)$

$B\to (A\vee B)$

$(A\to C)\to ((B\to C)\to ((A\vee B)\to C))$

$\mathrm{\perp }\to A$

別法として、直観主義論理は、基本結合子の集合として $\{\to ,\wedge ,\vee ,\mathrm{\neg }\}$ を用いて公理化することもでき、その場合は最後の公理を次のもので置き換える。

$(A\to \mathrm{\neg }A)\to \mathrm{\neg }A$

$\mathrm{\neg }A\to (A\to B)$

中間論理は直観主義論理と古典論理の中間に位置する。以下にいくつかの中間論理を挙げる。

• ヤンコフ論理（KC）は直観主義論理の拡張であり、直観主義の公理系に次の公理を加えることで公理化できる。

$\mathrm{\neg }A\vee \mathrm{\neg }\mathrm{\neg }A.$

• ゲーデル＝ダメット論理（LC）は、直観主義論理に次の公理を加えることで公理化できる。

$(A\to B)\vee (B\to A).$

正の含意計算

正の含意計算は、直観主義論理の含意断片である。以下の計算はいずれも推論規則としてモーダスポネンスを用いる。

ウカシェヴィッチの公理系：

$A\to (B\to A)$

$(A\to (B\to C))\to ((A\to B)\to (A\to C))$

メレディスの公理系：

• 第1：

  $E\to ((A\to B)\to (((D\to A)\to (B\to C))\to (A\to C)))$

• 第2：

  $A\to (B\to A)$

  $(A\to B)\to ((A\to (B\to C))\to (A\to C))$

• 第3：

  $((A\to B)\to C)\to (D\to ((B\to (C\to E))\to (B\to E)))$

ヒルベルトの公理系：

• 第1：

  $(A\to (A\to B))\to (A\to B)$

  $(B\to C)\to ((A\to B)\to (A\to C))$

  $(A\to (B\to C))\to (B\to (A\to C))$

  $A\to (B\to A)$

• 第2：

  $(A\to (A\to B))\to (A\to B)$

  $(A\to B)\to ((B\to C)\to (A\to C))$

  $A\to (B\to A)$

• 第3：

  $A\to A$

  $(A\to B)\to ((B\to C)\to (A\to C))$

  $(B\to C)\to ((A\to B)\to (A\to C))$

  $(A\to (A\to B))\to (A\to B)$

正命題計算

正命題計算は、直観主義論理のうち、（関数完全ではない）結合子 $\{\to ,\wedge ,\vee \}$ のみを用いる断片である。これは、上述の正の含意計算のための公理系のいずれかに、次の公理を合わせることで公理化できる。

$(A\wedge B)\to A$

$(A\wedge B)\to B$

$A\to (B\to (A\wedge B))$

$A\to (A\vee B)$

$B\to (A\vee B)$

$(A\to C)\to ((B\to C)\to ((A\vee B)\to C))$

任意で、結合子 $\leftrightarrow$ と次の公理を含めることもできる。

$(A\leftrightarrow B)\to (A\to B)$

$(A\leftrightarrow B)\to (B\to A)$

$(A\to B)\to ((B\to A)\to (A\leftrightarrow B))$

テンプレート:仮リンクのテンプレート:仮リンクは、正命題計算のための公理系のいずれかを用いて、その言語に0項結合子 $\mathrm{\perp }$ を追加することにより、追加の公理図式なしに公理化できる。別法として、これは言語 $\{\to ,\wedge ,\vee ,\mathrm{\neg }\}$ において、正命題計算に次の公理を追加することによっても公理化できる。

$(A\to \mathrm{\neg }B)\to (B\to \mathrm{\neg }A)$

あるいは次の公理の組によっても公理化できる。

$(A\to B)\to (\mathrm{\neg }B\to \mathrm{\neg }A)$

$A\to \mathrm{\neg }\mathrm{\neg }A$

否定を伴う言語における直観主義論理は、正計算の上に次の公理の組を加えることで公理化できる。

$(A\to \mathrm{\neg }B)\to (B\to \mathrm{\neg }A)$

$\mathrm{\neg }A\to (A\to B)$

あるいは次の公理の組によっても公理化できる。

$(A\to \mathrm{\neg }A)\to \mathrm{\neg }A$

$\mathrm{\neg }A\to (A\to B)$

言語 $\{\to ,\wedge ,\vee ,\mathrm{\neg }\}$ における古典論理は、正命題計算に次の公理を加えることで得られる。

$(\mathrm{\neg }A\to \mathrm{\neg }B)\to (B\to A)$

あるいは次の公理の組によっても得られる。

$(A\to \mathrm{\neg }B)\to (B\to \mathrm{\neg }A)$

$\mathrm{\neg }\mathrm{\neg }A\to A$

フィッチ計算は、正命題計算のための公理系のいずれかを取り、次の公理を加えたものである。

$\mathrm{\neg }A\to (A\to B)$

$A\leftrightarrow \mathrm{\neg }\mathrm{\neg }A$

$\mathrm{\neg }(A\vee B)\leftrightarrow (\mathrm{\neg }A\wedge \mathrm{\neg }B)$

$\mathrm{\neg }(A\wedge B)\leftrightarrow (\mathrm{\neg }A\vee \mathrm{\neg }B)$

第1と第3の公理は直観主義論理においても成り立つことに注意されたい。

同値計算

同値計算は、古典命題計算の部分体系であり、（関数的に不完全な）同値結合子のみを許容する。ここではこの結合子を $\equiv$ と表す。これらの体系で用いられる推論規則は次の通りである。

$\frac{A,A\equiv B}{B}.$

伊関の公理系：

$((A\equiv C)\equiv (B\equiv A))\equiv (C\equiv B)$

$(A\equiv (B\equiv C))\equiv ((A\equiv B)\equiv C)$

伊関＝新井の公理系：

$A\equiv A$

$(A\equiv B)\equiv (B\equiv A)$

$(A\equiv B)\equiv ((B\equiv C)\equiv (A\equiv C))$

新井の公理系：

• 第1：

  $(A\equiv (B\equiv C))\equiv ((A\equiv B)\equiv C)$

  $((A\equiv C)\equiv (B\equiv A))\equiv (C\equiv B)$

• 第2：

  $(A\equiv B)\equiv (B\equiv A)$

  $((A\equiv C)\equiv (B\equiv A))\equiv (C\equiv B)$

ウカシェヴィッチの公理系：

• 第1：

  $(A\equiv B)\equiv ((C\equiv B)\equiv (A\equiv C))$

• 第2：

  $(A\equiv B)\equiv ((A\equiv C)\equiv (C\equiv B))$

• 第3：

  $(A\equiv B)\equiv ((C\equiv A)\equiv (B\equiv C))$

メレディスの公理系：

• 第1：

  $((A\equiv B)\equiv C)\equiv (B\equiv (C\equiv A))$

• 第2：

  $A\equiv ((B\equiv (A\equiv C))\equiv (C\equiv B))$

• 第3：

  $(A\equiv (B\equiv C))\equiv (C\equiv (A\equiv B))$

• 第4：

  $(A\equiv B)\equiv (C\equiv ((B\equiv C)\equiv A))$

• 第5：

  $(A\equiv B)\equiv (C\equiv ((C\equiv B)\equiv A))$

• 第6：

  $((A\equiv (B\equiv C))\equiv C)\equiv (B\equiv A)$

• 第7：

  $((A\equiv (B\equiv C))\equiv B)\equiv (C\equiv A)$

テンプレート:仮リンクの公理系：

$A\equiv ((B\equiv (C\equiv A))\equiv (C\equiv B))$

テンプレート:仮リンクの公理系：

• 第1：

  $A\equiv ((B\equiv C)\equiv ((A\equiv C)\equiv B))$

• 第2：

  $A\equiv ((B\equiv C)\equiv ((C\equiv A)\equiv B))$

XCB公理系：

$A\equiv (((A\equiv B)\equiv (C\equiv B))\equiv C)$

関連項目

• 矛盾許容論理 — ヒルベルト流の矛盾許容論理のための公理図式の一覧