命題論理

命題論理は、真偽値を持つ宣言文として定義される命題を扱います。^{[ 30 ] [ 1 ]}命題の例としては、次のようなものがあります。

• ウィキペディアは、誰でも編集できる無料のオンライン百科事典です。
• ロンドンはイングランドの首都です。
• ウィキペディアの編集者は全員、少なくとも3ヶ国語を話せる。

宣言文は、「ウィキペディアとは何ですか？」のような質問や、「この記事の主張を裏付ける引用を追加してください」のような命令文とは対照的です。 ^{[ 31 ] [ 32 ]}このような非宣言文には真偽値がなく、^{[ 33 ]}エロティック論理や命令論理と呼ばれる非古典論理でのみ扱われます。

命題論理では、文は1つ以上の他の文を部分として含むことができます。^{[ 1 ]}複合文はより単純な文から形成され、構成要素となる文間の関係を表します。^{[ 34 ]}これは、論理結合子でそれらを組み合わせることによって行われます。^{[ 34 ] [ 35 ]}複合文の主な種類は、否定、接続詞、選言、含意、双条件文です。^{[ 34 ]}これらは、対応する結合子を使用して命題を接続することによって形成されます。^{[ 36 ] [ 37 ]}英語では、これらの結合子は「and」（接続詞）、「or」（選言）、「not」（否定）、「if」（実質条件）、「if and only if」（双条件）という単語で表されます。^{[ 1 ] [ 14 ]}このような複合文の例としては、次のようなものがあります。

• Wikipediaは誰でも編集できる無料のオンライン百科事典であり、すでに何百万人もの 人々が編集に参加している。（接続詞）
• ウィキペディアの編集者全員が少なくとも3ヶ国語を話せるというのは事実ではない。 （否定）
• ロンドンはイングランドの首都であるか、ロンドンはイギリスの首都であるか、あるいはその両方である。（論理和） ^{[ f ]}

論理接続詞を全く含まない文は、単純文^{[ 1 ]}または原子文[ ^{35 ]と}呼ばれ、¹つ以上の論理接続詞を含む文は、複合文[ ^{34 ]}または分子文^{[ 35 ]}と呼ばれます。

文接続詞は^、論理接続詞を含むより広いカテゴリーです。^{[ 2 ] [ 35 ]文接続詞は、}文を結合して新しい複合文を作成する言語粒子、または^単一の文を屈折させて新しい文を作成する言語粒子です。^{[2 ]論理接続詞}、または命題接続詞^は、それが作用する元の文が命題である場合（または命題を表す場合）、その適用によって生じる新しい文も命題である（または命題を表す）という特徴を持つ文接続詞の一種^です。[ 2 ]^哲学者は、命題が正確には何であるか、また自然言語のどの文接続詞を論理接続詞として数えるべきかについて意見が分かれています。^{[ 11 ] [ 2 ] [ 35 ] [ 2 ]}文結合子は文関数とも呼ばれ、^{[ 38 ]}論理結合子は真理関数とも呼ばれる。^{[ 38 ]}

以下は、命題論理の範囲内における議論の例です。

前提１：雨が降っているなら、曇っている。

前提２：雨が降っている。

結論：曇りです。

この議論の論理形式はモーダス・ポネンス[40]として知られており、古典的^に妥当な形式である[ ^{41 ] 。}したがって、古典論理では、この議論は妥当であるが、特定の状況における気象学的事実によっては、健全である場合もそうでない場合もある。この例の議論は、 §形式化の説明の際に再利用される。 

議論が妥当であるのは、その前提がすべて真である場合に結論が真となることが必然である場合に限る。 ^{[ 39 ] [ 42 ] [ 43 ]}あるいは、議論が妥当であるのは、結論が偽である間に前提がすべて真となることは不可能である場合に限る。 ^{[ 43 ] [ 39 ]}

妥当性とは健全性とは対照的である。^{[ 43 ]}議論が健全であるのは、それが妥当であり、かつその前提がすべて真である場合に限る。^{[ 39 ] [ 43 ]}そうでなければ、それは不健全である。^{[ 43 ]}

論理学は一般的に、有効な議論を正確に規定することを目指しています。^{[ 35 ]}これは、結論が前提の論理的帰結である議論を有効な議論として定義することによって行われます。 ^{[ 35 ]}これを意味論的帰結として理解すると、前提が真であるが結論が真でないというケースは存在しないことを意味します。 ^{[ 35 ]} –下記の§ 意味論を参照してください。

命題論理は、論理結合子によって分解できなくなる点を超えた命題の構造には関心がないため、^{[ 40 ] [ 1 ]}通常は、そのような原子的な（分割不可能な）命題をアルファベットの文字に置き換えて研究します。これらの文字は、命題を表す変数（命題変数）として解釈されます。^{[ 1 ]}命題変数を用いると、§ 例の議論は次のように記号化されます。

前提１：${\displaystyle P\to Q}$

前提２：${\displaystyle P}$

結論：${\displaystyle Q}$

Pを「雨が降っている」、 Qを「曇りだ」と解釈した場合、これらの記号表現は自然言語の元の表現と完全に一致します。それだけでなく、同じ論理形式を持つ他の推論とも一致します。

形式論理を表現するために形式システムを使用する場合、ステートメント文字（通常はローマ字の大文字など）のみが${\displaystyle P}$、${\displaystyle Q}$そして${\displaystyle R}$）は直接表現されます。解釈される際に生じる自然言語の命題はシステムの範囲外であり、形式システムとその解釈との関係も同様に形式システム自体の範囲外です。

モーダス・ポネンスの妥当性が公理として受け入れられていると仮定すると、同じ§ 例の議論は次のように表すこともできます。

${\displaystyle {\frac {P\to Q,P}{Q}}}$

この表示方法は、ゲンツェンの自然演繹とシーケント計算の記法である。^{[ 44 ]}前提は推論線と呼ばれる線の上に示され、^{[ 16 ]}前提の組み合わせを示すコンマで区切られる。^{[ 45 ]}結論は推論線の下に書かれる。^{[ 16 ]}推論線は構文的帰結を表し、^{[ 16 ]}時には演繹的帰結とも呼ばれ、^{[ 46 ]} ⊢ で記号化されることもある。^{[ 47 ] [ 46 ]}したがって、上記は次のように一行で書くこともできる。${\displaystyle P\to Q,P\vdash Q}$. ^{[ h ]}

構文的帰結は意味的帰結と対比され、^{[ 48 ]} ⊧ で記号化される。^{[ 47 ] [ 46 ]}この場合、自然演繹推論規則であるモーダス・ポネンスが仮定されているため、結論は構文的に導かれる。推論規則の詳細については、以下の証明システムに関するセクションを参照のこと。

原子命題変数の集合が与えられた場合${\displaystyle p_{1}}$、${\displaystyle p_{2}}$、${\displaystyle p_{3}}$、…、および命題接続詞の集合${\displaystyle c_{1}^{1}}$、${\displaystyle c_{2}^{1}}$、${\displaystyle c_{3}^{1}}$、...、${\displaystyle c_{1}^{2}}$、${\displaystyle c_{2}^{2}}$、${\displaystyle c_{3}^{2}}$、...、${\displaystyle c_{1}^{3}}$、${\displaystyle c_{2}^{3}}$、${\displaystyle c_{3}^{3}}$、...、命題論理の式は、これらの定義によって再帰的に定義されます。 ^{[ 2 ] [ 15 ] [ 51 ] [ i ]}

定義1：原子命題変数は論理式である。

定義2：もし${\displaystyle c_{n}^{m}}$は命題結合子であり、${\displaystyle \langle }$A、B、C、…${\displaystyle \rangle }$は、m 個の、原子である可能性もあるが必ずしもそうではなく、異なる可能性もあるが必ずしもそうではない式からなるシーケンスであり、その場合、適用した結果は${\displaystyle c_{n}^{m}}$に${\displaystyle \langle }$A、B、C、…${\displaystyle \rangle }$これは公式です。

定義3：それ以外は公式ではない。

適用結果を記述する${\displaystyle c_{n}^{m}}$に${\displaystyle \langle }$A、B、C、...${\displaystyle \rangle }$関数表記では、${\displaystyle c_{n}^{m}}$(A、B、C、…)の場合、整形式の式の例として以下が挙げられます。

• ${\displaystyle p_{5}}$
• ${\displaystyle c_{3}^{2}(p_{2},p_{9})}$
• ${\displaystyle c_{3}^{2}(p_{1},c_{2}^{1}(p_{3}))}$
• ${\displaystyle c_{1}^{3}(p_{4},p_{6},c_{2}^{2}(p_{1},p_{2}))}$
• ${\displaystyle c_{4}^{2}(c_{1}^{1}(p_{7}),c_{3}^{1}(p_{8}))}$
• ${\displaystyle c_{2}^{3}(c_{1}^{2}(p_{3},p_{4}),c_{2}^{1}(p_{5}),c_{3}^{2}(p_{6},p_{7}))}$
• ${\displaystyle c_{3}^{1}(c_{1}^{3}(p_{2},p_{3},c_{2}^{2}(p_{4},p_{5})))}$

上記定義2で示された、式の構成を担うものは、コリン・ハウソンによって構成原理と呼ばれている。^{[ 40 ] [ j ]}言語の構文の定義におけるこの再帰性 こそが、命題変数を指すのに「原子的」という言葉を使うことを正当化する。なぜなら、その言語のすべての式は、${\displaystyle {\mathcal {L}}}$原子を究極の構成要素として構築される。^{[ 2 ]}複合式（原子以外のすべての式）は分子[ ^{50 ]}または分子文^{[ 35 ]}と呼ばれる。 （これは化学との不完全な類推である。なぜなら、化学分子は単原子ガスのように、原子^が1つしかない場合もあるからである。）^{[ 50 ]}

上記で定義3として示されている「それ以外は式ではない」という定義は、構文内の他の定義によって特に要求されていない式を言語から除外します。^{[ 38 ]}特に、無限に長い式は整形式ではないとされています。^{[ 38 ]}これは、閉鎖節と呼ばれることもあります。^{[ 54 ]}

数学者は、命題定数、命題変数、およびスキーマを区別することがあります。命題定数は特定の命題を表しますが、 ^{[ 58 ]}命題変数はすべての原子命題の集合を範囲とします。^{[ 58 ]}しかし、スキーマ、またはスキーマ文字は、すべての式を範囲とします。^{[ 38 ] [ 1 ]} (スキーマ文字はメタ変数とも呼ばれます。) ^{[ 39 ]}命題定数はA、B、Cで、命題変数はP、Q、Rで表され、スキーマ文字はギリシャ文字、最もよく使われるのはφ、ψ、χであることが多いです。^{[ 38 ] [ 1 ]}

しかし、一部の著者は、形式体系において「命題定数」を2つしか認めていない。${\displaystyle \top }$常にTrueと評価される「真理」と呼ばれるもの、および特別な記号${\displaystyle \bot }$これは「偽」と呼ばれ、常にFalseと評価されます。^{[ 59 ] [ 60 ] [ 61 ]}他の著者もこれらの記号を同じ意味で含めていますが、それらを「ゼロ位の真理関数」^{[ 38 ]}または同等に「ヌル項結合子」^{[ 51 ]と考えています。}

特定の言語の場合${\displaystyle {\mathcal {L}}}$解釈、^{[ 66 ]}評価、^{[ 52 ]}ブール評価、^{[ 67 ]}またはケース、^{[ 35 ] [ k ]}は、各式に意味値を割り当てることである。${\displaystyle {\mathcal {L}}}$[ ^{35 ]}古典論理の形式言語では、ケースは、の各式への割り当てとして定義される^。${\displaystyle {\mathcal {L}}}$、真理値のうち一方のみ、つまり真理（T、または1）と偽（F、または0）のいずれか一方のみ。^{[ 68 ] [ 69 ]}古典論理の規則に従う解釈は、ブール値と呼ばれることもある。^{[ 52 ] [ 70 ]}古典論理の形式言語の解釈は、真理値表で表現されることが多い。^{[ 71 ] [ 1 ]}各式には単一の真理値しか割り当てられないため、解釈は定義域がである関数と見なすことができる。${\displaystyle {\mathcal {L}}}$、そしてその範囲は意味値の集合である。${\displaystyle {\mathcal {V}}=\{{\mathsf {T}},{\mathsf {F}}\}}$[ ^{2 ]}または^​${\displaystyle {\mathcal {V}}=\{1,0\}}$[ ^{35 ]​}

のために${\displaystyle n}$異なる命題記号が存在する${\displaystyle 2^{n}}$異なる解釈の可能性。特定の記号について${\displaystyle a}$例えば、${\displaystyle 2^{1}=2}$考えられる解釈：${\displaystyle a}$Tが割り当てられる、または${\displaystyle a}$Fが割り当てられます。そして、ペアについては${\displaystyle a}$、${\displaystyle b}$がある${\displaystyle 2^{2}=4}$考えられる解釈: 両方にTが割り当てられるか、両方にFが割り当てられるか、${\displaystyle a}$Tが割り当てられ、${\displaystyle b}$Fが割り当てられます。${\displaystyle a}$Fが割り当てられ、${\displaystyle b}$Tが割り当てられる。^{[ 71 ]}${\displaystyle {\mathcal {L}}}$もっている${\displaystyle \aleph _{0}}$つまり、可算個の命題記号があり、${\displaystyle 2^{\aleph _{0}}={\mathfrak {c}}}$したがって、数えきれないほど多くの異なる解釈が可能${\displaystyle {\mathcal {L}}}$全体として。^{[ 71 ]}

どこ${\displaystyle {\mathcal {I}}}$解釈であり、${\displaystyle \varphi }$そして${\displaystyle \psi }$式を表す場合、 §引数で定義される引数の定義は、ペアとして表すことができます。 ${\displaystyle \langle \{\varphi _{1},\varphi _{2},\varphi _{3},...,\varphi _{n}\},\psi \rangle }$、 どこ${\displaystyle \{\varphi _{1},\varphi _{2},\varphi _{3},...,\varphi _{n}\}}$は、前提と${\displaystyle \psi }$結論は、議論の妥当性の定義、つまりその性質は${\displaystyle \{\varphi _{1},\varphi _{2},\varphi _{3},...,\varphi _{n}\}\models \psi }$は、反例がないものとして表現でき、反例はケースとして定義される。${\displaystyle {\mathcal {I}}}$議論の前提${\displaystyle \{\varphi _{1},\varphi _{2},\varphi _{3},...,\varphi _{n}\}}$すべて真実だが結論は${\displaystyle \psi }$これは真実ではない。^{[ 35 ] [ 40 ]} § 意味論的真理、妥当性、帰結でわかるように、これは結論が前提の意味論的帰結であると言うことと同じである。

解釈では、原子式に直接意味値が割り当てられます。^{[ 66 ] [ 35 ]}分子式には、使用される接続子に応じて、構成原子の値の関数が割り当てられます。 ^{[ 66 ] [ 35 ]}接続子は、接続子を持つ原子から形成される文の真偽値が、それらが適用される原子の真偽値のみに依存するように定義されます。 [ ^{66 ] [ 35 ]この}仮定は、コリン・ハウソンによって接続子の真偽関数性の仮定と呼ばれています。^{[ 40 ]}

与えられた${\displaystyle \varphi }$そして${\displaystyle \psi }$言語の公式（または文）として${\displaystyle {\mathcal {L}}}$、 そして${\displaystyle {\mathcal {I}}}$解釈（または事例）として^{[ n ]}${\displaystyle {\mathcal {L}}}$すると、次の定義が適用されます。^{[ 71 ] [ 69 ]}

• 真実の事例：^{[ 35 ]}文${\displaystyle \varphi }$の${\displaystyle {\mathcal {L}}}$ある解釈の下では真である${\displaystyle {\mathcal {I}}}$もし${\displaystyle {\mathcal {I}}}$真理値Tを割り当てる${\displaystyle \varphi }$[ ^{69 ] [ 71 ]}もし^​${\displaystyle \varphi }$真である${\displaystyle {\mathcal {I}}}$、 それから${\displaystyle {\mathcal {I}}}$はモデルと呼ばれます${\displaystyle \varphi }$[ ^{71 ]​}
• 虚偽事例: ^{[ 35 ]}${\displaystyle \varphi }$ある解釈の下では偽である${\displaystyle {\mathcal {I}}}$もし、そしてその場合に限り、${\displaystyle \neg \varphi }$真である${\displaystyle {\mathcal {I}}}$[ ^{71 ] [ 81 ] [ 35 ]}これは、ある場合における偽の「否定の真理」の定義である。^{[ 35 ]}ある場合における偽は、「補集合」の定義によっても定義できる^。${\displaystyle \varphi }$ある解釈の下では偽である${\displaystyle {\mathcal {I}}}$もし、そしてその場合に限り、${\displaystyle \varphi }$は真実ではない${\displaystyle {\mathcal {I}}}$[ ^{69 ] [ 71 ]}古典論理ではこれらの定義は同等ですが、非古典論理ではそうで^はありません。^{[ 35 ]}
• 意味的帰結：文${\displaystyle \psi }$の${\displaystyle {\mathcal {L}}}$意味論的帰結（${\displaystyle \varphi \models \psi }$文の）${\displaystyle \varphi }$解釈がない場合${\displaystyle \varphi }$真実であり、${\displaystyle \psi }$真実ではない。^{[ 69 ] [ 71 ] [ 35 ]}
• 有効な式（同義反復）：文${\displaystyle \varphi }$の${\displaystyle {\mathcal {L}}}$論理的に妥当である（${\displaystyle \models \varphi }$)、^{[ o ]}または同義反復、^{[ 82 ] [ 83 ] [ 80 ] [ 52 ]}すべての解釈の下で真である場合、^{[ 69 ] [ 71 ]}またはすべての場合に真である場合。^{[ 35 ]}
• 一貫性のある文:文${\displaystyle {\mathcal {L}}}$少なくとも一つの解釈の下で真であれば、それは整合的である。整合していなければ、それは不整合である。^{[ 69 ] [ 71 ]}不整合な式は自己矛盾とも呼ばれ、^{[ 1 ]}自己矛盾[ ^{1 ]}、あるいは単に矛盾[ ^{84 ] [ 85 ] [ 86 ]}とも呼ばれるが、後者の名称は^、特定の形式の命題にのみ用いられることがある^。${\displaystyle (p\land \neg p)}$[ ^{1 ]​}

解釈（事例）について${\displaystyle {\mathcal {I}}}$の${\displaystyle {\mathcal {L}}}$次のような定義が時折提示される。

• 完全なケース:ケース${\displaystyle {\mathcal {I}}}$は、以下のいずれかに該当する場合に限り完了します。${\displaystyle \varphi }$真実である${\displaystyle {\mathcal {I}}}$または${\displaystyle \neg \varphi }$真実である${\displaystyle {\mathcal {I}}}$どのような場合でも${\displaystyle \varphi }$で${\displaystyle {\mathcal {L}}}$[ ^{35 ] [ 87 ]​}
• 一貫性のあるケース：ケース${\displaystyle {\mathcal {I}}}$は、以下の条件が満たされる場合に限り、一貫性がある。${\displaystyle \varphi }$で${\displaystyle {\mathcal {L}}}$両方とも${\displaystyle \varphi }$そして${\displaystyle \neg \varphi }$真実である${\displaystyle {\mathcal {I}}}$[ ^{35 ] [ 88 ]​}

すべてのケースが完全かつ無矛盾であると仮定する古典論理では、^{[ 35 ]}次の定理が適用されます。

• 任意の解釈に対して、与えられた式は、その解釈の下では真か偽かのどちらかである。^{[ 71 ] [ 81 ]}
• 同じ解釈の下では、いかなる公式も真であり偽であることはない。^{[ 71 ] [ 81 ]}
• ${\displaystyle \varphi }$真である${\displaystyle {\mathcal {I}}}$もし、そしてその場合に限り、${\displaystyle \neg \varphi }$偽である${\displaystyle {\mathcal {I}}}$; ^{[ 71 ] [ 81 ]}${\displaystyle \neg \varphi }$真である${\displaystyle {\mathcal {I}}}$もし、そしてその場合に限り、${\displaystyle \varphi }$は真実ではない${\displaystyle {\mathcal {I}}}$[ ^{71 ]​}
• もし${\displaystyle \varphi }$そして${\displaystyle (\varphi \to \psi )}$両方とも真である${\displaystyle {\mathcal {I}}}$、 それから${\displaystyle \psi }$真である${\displaystyle {\mathcal {I}}}$[ ^{71 ] [ 81 ]​}
• もし${\displaystyle \models \varphi }$そして${\displaystyle \models (\varphi \to \psi )}$、 それから${\displaystyle \models \psi }$[ ^{71 ]​}
• ${\displaystyle (\varphi \to \psi )}$真である${\displaystyle {\mathcal {I}}}$次のいずれかの場合に限り${\displaystyle \varphi }$は真実ではない${\displaystyle {\mathcal {I}}}$、 または${\displaystyle \psi }$真である${\displaystyle {\mathcal {I}}}$[ ^{71 ]​}
• ${\displaystyle \varphi \models \psi }$もし、そしてその場合に限り、${\displaystyle (\varphi \to \psi )}$論理的に妥当である、つまり、${\displaystyle \varphi \models \psi }$もし、そしてその場合に限り、${\displaystyle \models (\varphi \to \psi )}$[ ^{71 ] [ 81 ]​}

${\displaystyle {\begin{array}{|c|c|c|c|}x_{0}&x_{1}&{\bar {x_{1}}}&x_{0}\&{\bar {x_{1}}}\\\hline 0&0&1&0\\0&1&0&0\\1&0&1&1\\1&1&0&0\end{array}}}$

真理値表の例

意味論的証明システムは、意味論的帰結の概念に基づいており、次のように象徴されます。${\displaystyle \varphi \models \psi }$これは、もし${\displaystyle \varphi }$そうだとすれば${\displaystyle \psi }$あらゆる解釈において真でなければならない。^{[ 94 ]}

一方、構文証明システムは、特定の規則に従って記号を形式的に操作することに焦点を当てています。構文的帰結の概念は、${\displaystyle \varphi \vdash \psi }$は、${\displaystyle \psi }$から導き出すことができる${\displaystyle \varphi }$形式体系の規則を使用する。^{[ 94 ]}

推論規則の提示方法には著者によって多少の違いがあり、その点は指摘しておく。しかし、証明の見た目や雰囲気に最も影響を与えるのは、記法のスタイルの違いである。 §ゲンツェン 記法は、以前に簡単に説明したが、実際には積み重ねて大きな木のような自然演繹証明を作成することができる^{[ 44 ] [ 16 ]} ―分析タブローの別名である「真理の木」と混同しないように。^{[ 72 ]}また、スタニスワフ・ヤシュコフスキによるスタイルもあり、証明中の式はさまざまな入れ子になったボックスの中に書かれている^{[ 44 ]。}さらに、フレドリック・フィッチによるヤシュコフスキのスタイルの簡略化（フィッチ記法）もあり、ボックスは仮定の導入の下の単純な水平線と、仮定の下にある線の左側の垂直線に簡略化されている。^{[ 44 ]}最後に、この記事で実際に使用される唯一の記法スタイルは、パトリック・サップス[ ^{44 ]}によるものですが、 EJ レモンとベンソン・メイツ^{[ 112 ]}によって広く普及しました。この方法は、グラフィカルに作成および表示するのに最も手間がかからないという利点があり、他の方法で証明を作成するために必要な複雑な LaTeX コマンドを理解していなかったこの記事のこの部分を書いた編集者にとって^自然な選択でした。

Suppes–Lemmon記法[ ^{44 ]に従って}記述された証明は、文を含む行のシーケンスであり^{[ 39 ]} 、各文は仮定であるか、シーケンス内の前の文に証明規則を適用した結果のいずれかである。^{[ 39 ]}証明の各行は、証明文、注釈、仮定セット、および現在の行番号で構成される。^{[ 39 ]}仮定セットは、与えられた証明文が依存する仮定をリストし、行番号によって参照される。[ ^{39 ]注釈}は、現在の文を生成するためにどの証明規則がどの前の行に適用されたかを指定する。^{[ 39 ]} §自然演繹証明の例を参照。 

ゲンツェンに由来する自然演繹推論規則は、以下に示すとおりである。^{[ 111 ]}証明には10個の基本規則があり、それは仮定規則、二項結合子の導入規則と除去規則の4組、および背理法規則である。^{[ 39 ]}選言三段論法は、適切な∨除去のより簡単な代替手段として使用できる^{[ 39 ]} 。また、MTTとDNは基本規則ではないが、一般的に与えられた規則である^{[ 111 ] 。 [ 39 ]}

以下の証明^{[ 39 ]}は、${\displaystyle -P}$から${\displaystyle P\to Q}$そして${\displaystyle -Q}$MPPとRAAのみを使用すると、MTTは原始的なルールではないことがわかります。なぜなら、MTTは他の2つのルールから導き出すことができるからです。

公理的証明は、有名な古代ギリシャの教科書であるユークリッドの『幾何学原論』以来使用されてきましたが、命題論理では、ゴットロープ・フレーゲの1879年の『概念書』に遡ります。^{[ 38 ] [ 114 ]}フレーゲの体系は、結合子として含意と否定のみを使用しました。^{[ 2 ]} 6つの公理がありました。^{[ 114 ] [ 115 ] [ 116 ]}

• 提案1：${\displaystyle a\to (b\to a)}$
• 提案2：${\displaystyle (c\to (b\to a))\to ((c\to b)\to (c\to a))}$
• 提案8：${\displaystyle (d\to (b\to a))\to (b\to (d\to a))}$
• 提案28：${\displaystyle (b\to a)\to (\neg a\to \neg b)}$
• 提案31：${\displaystyle \neg \neg a\to a}$
• 提案41：${\displaystyle a\to \neg \neg a}$

これらはフレーゲによってモーダス・ポネンスと置換規則（使用されたが、正確には明示されなかった）とともに使用され、古典的な真理関数命題論理の完全かつ一貫した公理化をもたらした。^{[ 115 ]}

ヤン・ウカシェヴィチは、フレーゲの体系において、「第3の公理は先行する2つの公理から導き出せるため冗長であり、最後の3つの公理は単一の文に置き換えることができる」ことを示した。${\displaystyle CCNpNqCqp}$「. ^{[ 116 ]}ルカシェヴィチのポーランド記法から現代の記法に移すと、${\displaystyle (\neg p\rightarrow \neg q)\rightarrow (q\rightarrow p)}$したがって、ルカシェヴィチはこの３つの公理体系を考案したとされている^{[ 114 ] 。}

• ${\displaystyle p\to (q\to p)}$
• ${\displaystyle (p\to (q\to r))\to ((p\to q)\to (p\to r))}$
• ${\displaystyle (\neg p\to \neg q)\to (q\to p)}$

フレーゲのシステムと同様に、このシステムも代入規則を使用し、推論規則としてモーダス・ポネンスを使用します。^{[ 114 ]}まったく同じシステムが（明示的な代入規則とともに）アロンゾ・チャーチによって提示され、^{[ 117 ]}彼はそれをシステム P2 [117][118] と呼び_、^{普及に貢献しました}。^{[ 118 ]}

• 一階述語論理
• 二階命題論理
• 二階述語論理
• 高階論理