自然演繹

Kind of proof calculus

論理学と証明論において、自然演繹は一種の証明計算であり、論理的推論は「自然な」推論方法に密接に関連した推論規則によって表現されます。 ^{[1]これは、}演繹的推論の論理法則を表現するために可能な限り公理を使用するヒルベルトスタイルのシステムとは対照的です。

歴史

自然演繹は、ヒルベルト、フレーゲ、ラッセルの体系に共通する演繹的推論の公理化への不満という文脈から生まれた（例えば、ヒルベルト体系を参照）。こうした公理化は、ラッセルとホワイトヘッドが数学論文『プリンキピア・マテマティカ』で最もよく使われている。1926年にポーランドで行われた、より自然な論理の扱いを主張するウカシェヴィチの一連のセミナーに刺激を受けて、ヤシュコフスキはより自然な演繹を定義する最も初期の試みを行い、最初は1929年に図式的記法を使用し、後に1934年と1935年の一連の論文で彼の提案を更新した。^{[2]彼の提案は、}フィッチ記法やサッペス法などのさまざまな記法につながり、レモンは現在サッペス・レモン記法として知られる変種を与えた。

現代的な形の自然演繹は、1933年にドイツの数学者ゲルハルト・ゲンツェンによってゲッティンゲン大学数理科学部に提出された博士論文の中で独自に提唱されました。^[3]自然演繹（あるいはドイツ語の同義語natürliches Schließen ）という用語は、この論文の中で造られました。

私は修道女を知り、形式主義をアウフステレンに導き、自分自身を理解することができます。したがって、ergab sich ein "Kalkül des natürlichen Schließens" です。^[4]

翻訳：

まず私は、実際の推論に可能な限り近い形式主義を構築したいと考えました。こうして「自然演繹の計算」が生まれました。

ゲンツェンは数論の無矛盾性を確立したいという願望に突き動かされていた。無矛盾性の結果に必要な主要な結果であるカット消去定理（ハウプトザッツ）を自然演繹に対して直接証明することはできなかった。このため彼は代替体系であるシーケント計算を導入し、これによって古典論理と直観主義論理の両方に対してハウプトザッツを証明した。1961年と1962年に行われた一連のセミナーで、プラヴィッツは自然演繹計算の包括的な概要を示し、ゲンツェンのシーケント計算に関する研究の多くを自然演繹の枠組みに持ち込んだ。1965年の彼のモノグラフ「自然演繹：証明理論的研究」^[5]は自然演繹の参考図書となり、様相論理と第二階述語論理への応用を含んでいた。

自然演繹では、推論規則を繰り返し適用することで、前提の集合から命題が演繹されます。本稿で提示するシステムは、ゲンツェンやプラウィッツの定式化を若干改変したもので、マルティン＝レーフによる論理的判断と接続詞の記述により忠実に従っています。^[6]

記法スタイルの歴史

自然演繹には多種多様な記法スタイル^[7]があり、それらに慣れていないと証明を理解するのが難しくなることがあります。こうした状況に対処するため、この記事では「§ 記法」のセクションで、実際に使用されるすべての記法の読み方を解説しています。このセクションでは、記法スタイルの歴史的進化についてのみ説明しています。これらの記法スタイルのほとんどは、パブリック著作権ライセンスの下で利用できる図がないため、ここでは図示できません。図については、SEPとIEPを参照してください。

• ゲンツェンは、ツリー型の証明を使用した自然演繹を発明しました。詳細については、§ ゲンツェンのツリー表記法を参照してください。
• ヤシュコフスキはこれを様々なネストされたボックスを使った表記法に変更した。^[7]
• フィッチはヤシュコフスキのボックス描画法を変更し、フィッチ記法を作成した。^[7]
• 1940年:クワイン^[8]は教科書の中で、先行依存関係を角括弧で囲んだ行番号で示し、1957年のサッペスの行番号表記法を予期した。
• 1950年：クワイン（1982年、241～255ページ）は教科書の中で、証明の各行の左側に1つ以上のアスタリスクを用いて依存関係を示す手法を示した。これはクリーネの縦棒に相当する。（クワインのアスタリスク表記が1950年の初版に登場していたのか、それとも後の版で追加されたのかは完全には明らかではない。）
• 1957年：サッペス著の教科書『実用論理学の定理証明入門』（1999年、25～150ページ）に掲載。この教科書では、各行の左側に行番号を付して依存関係（つまり、先行命題）を示していた。
• 1963年：ストール（1979、pp. 183–190、215–219）は、行番号のセットを使用して、自然演繹推論規則に基づく連続した論理議論の行の先行依存関係を示します。
• 1965年: Lemmon (1978) による教科書全体は、現在Suppes–Lemmon 記法として知られているSuppesの方法に基づいた論理証明の入門書です。
• 1967年：クリーネ（2002、pp.50-58、128-130）は教科書の中で、2種類の実際的論理証明を簡単に示した。1つは各行の左側に先行命題を明示的に引用するシステムであり、もう1つは依存関係を示すために左側に縦線を使用するシステムである。^[9]

表記

以下は、論理接続詞の最も一般的な表記法のバリエーションを示す表です。

接続詞の表記法のバリエーション^{[10] [11]}

接続詞	シンボル
そして	${\displaystyle A\land B}$、、、、、​​​ ${\displaystyle A\cdot B}$ ${\displaystyle AB}$ ${\displaystyle A\&B}$ ${\displaystyle A\&\&B}$
同等	${\displaystyle A\equiv B}$、、​ ${\displaystyle A\Leftrightarrow B}$ ${\displaystyle A\leftrightharpoons B}$
暗示する	${\displaystyle A\Rightarrow B}$、、​ ${\displaystyle A\supset B}$ ${\displaystyle A\rightarrow B}$
ナンド	${\displaystyle A{\overline {\land }}B}$、、​ ${\displaystyle A\mid B}$ ${\displaystyle {\overline {A\cdot B}}}$
同等ではない	${\displaystyle A\not \equiv B}$、、​ ${\displaystyle A\not \Leftrightarrow B}$ ${\displaystyle A\nleftrightarrow B}$
または	${\displaystyle A{\overline {\lor }}B}$、、​ ${\displaystyle A\downarrow B}$ ${\displaystyle {\overline {A+B}}}$
ない	${\displaystyle \neg A}$、、、、​​ ${\displaystyle -A}$ ${\displaystyle {\overline {A}}}$ ${\displaystyle \sim A}$
または	${\displaystyle A\lor B}$、、、、​​ ${\displaystyle A+B}$ ${\displaystyle A\mid B}$ ${\displaystyle A\parallel B}$
XNOR	${\displaystyle A}$XNOR ${\displaystyle B}$
排他的論理和	${\displaystyle A{\underline {\lor }}B}$、 ${\displaystyle A\oplus B}$

ゲンツェンのツリー記法

自然演繹を発明したゲンツェンは、議論のための独自の記法を持っていました。これは、以下の簡単な議論で例証されます。命題論理における簡単な議論の例、「もし雨が降っているなら曇りである。雨が降っている。ゆえに曇りである」としましょう。（これは前置詞法です。）これを、一般的に命題のリストとして表すと、次のようになります。

${\displaystyle 1)~P\to Q}$

${\displaystyle 2)~P}$

${\displaystyle \therefore ~Q}$

ゲンツェンの記法^[7]では、これは次のように書かれる。

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

前提は推論線と呼ばれる線の上に示され、[ ^{12] [13]}前提の組み合わせを示すコンマで区切られます。 ^[14]結論は推論線の下に書かれます。^[12]推論線は統語的帰結を表し、^[12]演繹的帰結と呼ばれることもあり、^{[15] [16]} ⊢で表すこともできます。^[16]そのため、上記は と1行で書くこともできます。 （統語的帰結を表す回転式記号は、前提の組み合わせを表すコンマよりも優先順位が低く、コンマは物質的含意を表す矢印よりも優先順位が低いため、この式を解釈するのに括弧は必要ありません。）^[14] ${\displaystyle P\to Q,P\vdash Q}$

統語的帰結は意味的帰結^[17]と対比され、意味的帰結は⊧で表されます。^{[18] [16]}この場合、自然演繹は推論規則をプリミティブとして想定する統語的証明システムであるため、結論は統語的に成り立ちます。

本稿の大部分では、ゲンツェンのスタイルが用いられます。仮説的判断を内在化するためにゲンツェンが用いた解読注釈は、証明をA（が真）という判断の木ではなく、 Γ⊢Aのシークエント の木として表現することで回避できます。

サッペス・レモン記法

多くの教科書ではSuppes–Lemmon 記法[ ^7]が使用されているため、この記事でもその表記法を扱います。ただし、現時点では命題論理についてのみ取り上げており、残りの説明は Gentzen スタイルでのみ行います。Suppes–Lemmon 記法スタイルに従って記述された証明 は文を含む行のシーケンスであり、^[19]各文は仮定、またはシーケンス内の前の文に証明規則を適用した結果です。^[19]各証明行は、証明文、その注釈、仮定セット、および現在の行番号で構成されます。^[19]仮定セット は、指定された証明文が依存する仮定をリストし、行番号で参照されます。^[19]注釈 は、現在の文を生成するために、どの証明規則が以前のどの行に適用されたかを指定します。^[19]証明の例を次に示します。

サップス・レモン式証明（最初の例）

${\displaystyle P\to Q,\neg Q\vdash \neg P}$
仮定セット	行番号	式（wff）	注釈
1	1	${\displaystyle P\to Q}$	あ
2	2	${\displaystyle \neg Q}$	あ
3	3	${\displaystyle P}$	あ
1、3	4	${\displaystyle Q}$	1, 3 →東
1、2	5	${\displaystyle \neg P}$	2、4 RAA
QED

この証明は、推論規則とその適切な注釈が指定されるとより明確になります。§ 命題推論規則 (Suppes–Lemmon スタイル) を参照してください。

命題言語の構文

このセクションでは、命題論理言語の正式な構文を定義し、一般的な方法とゲンツェン風の方法とを対比します。

一般的な定義スタイル

古典的な 命題計算では、形式言語 は通常（ここでは再帰によって）次のように定義されます。^[20] ${\displaystyle {\mathcal {L}}}$

1. 各命題変数は式です。
2. 「」は数式です。 ${\displaystyle \bot }$
3. およびが公式である場合、、、、も同様です。 ${\displaystyle \varphi }$ ${\displaystyle \psi }$ ${\displaystyle (\varphi \land \psi )}$ ${\displaystyle (\varphi \lor \psi )}$ ${\displaystyle (\varphi \to \psi )}$ ${\displaystyle (\varphi \leftrightarrow \psi )}$
4. それ以外は公式ではありません。

否定（ ）は偽りの含意として定義される ${\displaystyle \neg }$

${\displaystyle \neg \phi \;{\overset {\text{def}}{=}}\;\phi \to \bot }$、

ここで（falsum）は矛盾または絶対的な虚偽を表す。^{[21] [22] [23] [24] [25]} ${\displaystyle \bot }$

古い出版物や、極小論理システム、直観主義論理システム、ヒルベルト論理システムなどの論理システムに焦点を当てていない出版物では、否定を原始論理接続詞として扱っています。つまり、否定は基本的な演算であると想定されており、他の接続詞では定義されていません。^{[26] [27]}ボストックなどの著者は、およびを使用し、を原始として定義しています。^{[28] [29]} ${\displaystyle \bot }$ ${\displaystyle \top }$ ${\displaystyle \neg }$

ゲンツェン式の定義

構文定義は、§ゲンツェンのツリー記法を使って与えることもできる。これは、推論線の下に整形式の式を書き、その式で使用される図式的変数をその上に書くことによって行う。^[26]例えば、上記のボストックの定義の規則3と4に相当するものは、次のように書くことができる。

${\displaystyle {\frac {\varphi }{(\neg \varphi )}}\quad {\frac {\varphi \quad \psi }{(\varphi \lor \psi )}}\quad {\frac {\varphi \quad \psi }{(\varphi \land \psi )}}\quad {\frac {\varphi \quad \psi }{(\varphi \rightarrow \psi )}}\quad {\frac {\varphi \quad \psi }{(\varphi \leftrightarrow \psi )}}}$。

別の表記法では、言語の構文は、記号 で表される単一のカテゴリ「式」を持つ範疇文法とみなされます。したがって、構文の要素はすべて範疇化によって導入され、その表記法は となり、「はカテゴリ 内のオブジェクトを表す式である」という意味になります。^[30]次に、文文字は、  、 などの範疇化によって導入されます。^[30]接続詞は、上記と同様の文で定義されますが、以下のように範疇化表記法が用いられます。 ${\displaystyle {\mathcal {F}}}$ ${\displaystyle \varphi :{\mathcal {F}}}$ ${\displaystyle \varphi }$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle P:{\mathcal {F}}}$ ${\displaystyle Q:{\mathcal {F}}}$ ${\displaystyle R:{\mathcal {F}}}$

範疇文法によって定義された接続詞^[30]

接続詞（&）	論理和（∨）	含意（→）	否定（¬）
${\displaystyle {\frac {A:{\mathcal {F}}\quad B:{\mathcal {F}}}{\&(A)(B):{\mathcal {F}}}}}$	${\displaystyle {\frac {A:{\mathcal {F}}\quad B:{\mathcal {F}}}{\vee (A)(B):{\mathcal {F}}}}}$	${\displaystyle {\frac {A:{\mathcal {F}}\quad B:{\mathcal {F}}}{\supset (A)(B):{\mathcal {F}}}}}$	${\displaystyle {\frac {A:{\mathcal {F}}}{\neg (A):{\mathcal {F}}}}}$

この記事の残りの部分では、言語の文法を定義する Gentzen 表記法のステートメントにはカテゴリ化表記法が使用されます。Gentzen 表記法のその他のステートメントは推論となり、式が整形式の式であることを示すのではなく、シーケントが続くことを主張します。 ${\displaystyle \varphi :{\mathcal {F}}}$

ゲンツェン流命題論理

ゲンツェン式推論規則

命題言語を帰納的に次のように定義します。 ${\displaystyle {\mathcal {L}}}$ ${\displaystyle \Phi ::=p_{1},p_{2},\dots \mid \bot \mid (\Phi \to \Phi )\mid (\Phi \land \Phi )\mid (\Phi \lor \Phi )}$

否定を と定義します。 ${\displaystyle \neg \Phi \,{\overset {\text{def}}{=}}\,(\Phi \to \bot )}$

以下は命題論理における自然演繹のための基本的推論規則のリストである: ^{[31] [26]}

命題論理の規則

導入ルール	排除ルール
${\displaystyle {\begin{array}{c}\varphi \qquad \psi \\\hline \varphi \land \psi \end{array}}(\land _{I})}$	${\displaystyle {\begin{array}{c}\varphi \land \psi \\\hline \varphi \end{array}}(\land _{E})}$
${\displaystyle {\begin{array}{c}\varphi \\\hline \varphi \lor \psi \end{array}}(\lor _{I})}$	${\displaystyle {\cfrac {\varphi \lor \psi \quad {\begin{matrix}[\varphi ]^{u}\\\vdots \\\chi \end{matrix}}\quad {\begin{matrix}[\psi ]^{v}\\\vdots \\\chi \end{matrix}}}{\chi }}\ \lor _{E^{u,v}}}$
${\displaystyle {\begin{array}{c}[\varphi ]^{u}\\\vdots \\\psi \\\hline \varphi \to \psi \end{array}}(\to _{I})\ u}$	${\displaystyle {\begin{array}{c}\varphi \qquad \varphi \to \psi \\\hline \psi \end{array}}(\to _{E})}$
	${\displaystyle {\begin{array}{c}\bot \\\hline \varphi \end{array}}(\bot _{E})}$
	[32] ${\displaystyle {\begin{array}{c}(\varphi \to \bot )\to \bot \\\hline \varphi \end{array}}(\neg \neg _{E})}$

この表では、ギリシャ文字はスキーマを表し、これは原子命題だけでなく論理式全体にわたって適用されます。規則の名前は、その論理式ツリーの右側に示されています。例えば、最初の導入規則は で、これは「接続詞導入」の略です。 ${\displaystyle \varphi ,\psi ,\chi }$ ${\displaystyle \land _{I}}$

• 最小限の論理:自然演繹規則は次のとおりです。 ${\displaystyle ND_{MPC}=\{\land _{I},\land _{E},\lor _{I},\lor _{E},\to _{I},\to _{E}\}}$

ルールがなければ、システムは最小限のロジックを定義します（ヨハンソンが議論したように）。^[33] ${\displaystyle \bot _{E}}$ ${\displaystyle \neg \neg _{E}}$

• 直観主義論理:自然演繹規則は次のとおりです。 ${\displaystyle ND_{IPC}=ND_{MPC}\cup \{\bot _{E}\}}$

最小論理の規則に爆発の原理という規則を追加すると、直観主義論理が定義されます。 ${\displaystyle \bot _{E}}$

この文は、排中律を伴う逆の含意とは異なり、有効です (すでに最小論理では有効です。以下の例 1 を参照)。 ${\displaystyle P\to \neg \neg P}$

• 古典論理：自然演繹規則は^[32]である。 ${\displaystyle ND_{CPC}=ND_{IPC}\cup \{\neg \neg _{E}\}}$

列挙された自然演繹規則がすべて認められる場合、そのシステムは古典論理を定義する。^{[34] [35] [36]}

ゲンツェン式の例証

例1 : ^[24]最小限の論理による証明。 ${\displaystyle P\to \neg \neg P}$

目標:証明: ${\displaystyle P\to ((P\to \bot )\to \bot )}$

${\displaystyle {\cfrac {{\cfrac {[P]^{v}\qquad [P\to \bot ]^{u}}{\bot }}\to _{E}}{{\cfrac {((P\to \bot )\to \bot )}{P\to ((P\to \bot )\to \bot )}}\to _{I^{v}}}}\to _{I^{u}}}$

例 2 : 最小限の論理による次の証明: ${\displaystyle A\to \left(B\to \left(A\land B\right)\right)}$

${\displaystyle {\cfrac {{\cfrac {[A]^{u}\quad [B]^{w}}{A\land B}}\ \land _{I}}{{\cfrac {B\to \left(A\land B\right)}{A\to \left(B\to \left(A\land B\right)\right)}}\ \to _{I^{u}}}}\ \to _{I^{w}}}$

フィッチ流命題論理

フィッチは自然演繹のシステムを開発したが、それは次のような特徴がある。

• 証明をツリー形式で提示するのではなく、線形形式で提示する。
• 従属証明では、仮定を下位導出内で展開し、後で解除することができます。

その後、パトリック・サップス^[37]やEJ・レモン^[38]といった論理学者や教育者たちがフィッチの体系を改名しました。彼らはインデントを縦棒に置き換えるなど、図式的な変更を加えましたが、フィッチ流の自然演繹の基本的な構造はそのまま残されました。これらのバリエーションはしばしばサップス・レモン形式と呼ばれますが、基本的にはフィッチのオリジナルの記法に基づいています。

サップス・レモン型命題論理

サップス・レモン型推論規則

フィッチ式およびサッペス＝レモン式の証明で用いられる線型的な表現（行番号と垂直な配置／仮定集合）は、部分証明を明確に示します。フィッチは（控えめかつ慎重に）導出規則を使用しました。サッペス＝レモンはさらに進み、導出規則を自然演繹規則のツールボックスに追加しました。

サッペスはゲンツェン風の規則を用いた自然演繹を導入した。^[37]

• 彼は否定を矛盾の観点から定義した。 ${\displaystyle \neg P\equiv (P\to \bot )}$
• 彼は派生ルールについて明示的に議論しましたが、レイアウトにおいては派生ルールと基本的なルールを必ずしも明確に区別していませんでした。
• 彼のシステムは最小限に近いですが、簡潔にするために派生的な手順を許可しています。

レモンはさらに派生的な規則を形式化した。^[38]彼は否定を偽への含意として定義した。これは『論理学入門』では正式な定義として述べられていないが、体系全体を通して暗黙的に想定されている。その理由は以下の通りである。 ${\displaystyle \neg P\equiv P\to \bot }$

• RAA (Reductio ad Absurdum) の使用: Lemmon は、 を仮定し、 を導き、 を結論付けるという形式で RAA を頻繁に使用しました。 ${\displaystyle P}$ ${\displaystyle \bot }$ ${\displaystyle \neg P}$

これはが として理解される場合にのみ機能します。 ${\displaystyle \neg P}$ ${\displaystyle P\to \bot }$

• 矛盾を含む証明: レモンは、 からを導き出せるという事実を利用しました。 ${\displaystyle \neg P\land P}$ ${\displaystyle \bot }$

これにはを として扱う必要があり、その結果、 modus ponens によって矛盾が生じます。 ${\displaystyle \neg P}$ ${\displaystyle P\to \bot }$

• 原始的な「¬」規則の欠如：レモンは「¬」を導入または除去するための独立した規則を設けなかった。代わりに、彼は含意と矛盾を用いて否定を導出した。

下の表は、Lemmon (1978) ^[39]および Allen & Hand (2022) ^[19]に基づいており、 Lemmon の導出ルールが強調表示されている。これらのルールは、（強調表示されていない） Gentzenルールから導出できる。

証明には9つの基本的な規則があり、それらは規則の仮定、二項接続詞の導入規則と除去規則の4組、そして二重否定と不合理化規則で、必要なのはそのうちの1つだけです。^{[32] [19]} 選言三段論法は、適切な∨-除去のより簡単な代替手段として使用できます。^[19]また、MTTはよく使用される規則ですが、^[39]基本的ではありません。^[19]

推論規則のリスト

ルール名	別名	注釈	仮定セット	声明
仮定のルール	予測	あ	現在の行番号。	議論のどの段階でも、議論の前提として命題を導入します。
接続詞の紹介	アンパサンド導入、接続詞（CONJ）[40]	m、n、I	仮定の和集合は、行mと行nに設定されます。	行mと行 nのおよびから、 と推論します。 ${\displaystyle \varphi }$ ${\displaystyle \psi }$ ${\displaystyle \varphi \land \psi }$
接続詞の除去	簡略化（S）、アンパサンドの削除	自分	m行目と同じです。	m行目から、およびを推論します。 ${\displaystyle \varphi \land \psi }$ ${\displaystyle \varphi }$ ${\displaystyle \psi }$
論理和の導入	加算（ADD）	m ∨I	m行目と同じです。	m行目から、何であれを推論します。 ${\displaystyle \varphi }$ ${\displaystyle \varphi \lor \psi }$ ${\displaystyle \psi }$
論理和除去	ウェッジ除去、ジレンマ（DL）[40]	j,k,l,m,n ∨E	j、k、l、m、nの行。	j行目の、 k行目の の仮定、 l行目のの導出、 m行目の の仮定、 n行目のの導出から、 を推論します。 ${\displaystyle \varphi \lor \psi }$ ${\displaystyle \varphi }$ ${\displaystyle \chi }$ ${\displaystyle \varphi }$ ${\displaystyle \psi }$ ${\displaystyle \chi }$ ${\displaystyle \psi }$ ${\displaystyle \chi }$
矢印の紹介	条件付き証明（CP）[40] 、条件付き導入	n, →I (m)	前提が想定された 行mを除く、行nに設定された仮定内のすべて。	n行目から、 m行目の仮定に従って、 を推論します。 ${\displaystyle \psi }$ ${\displaystyle \varphi }$ ${\displaystyle \varphi \to \psi }$
矢印の除去	Modus ponendo ponens (MPP)、Modus ponens (MP)、[40]条件付き消去	m, n →E	仮定の和集合は、行mと行nに設定されます。	m行目およびn行目から、 を推論します。 ${\displaystyle \varphi \to \psi }$ ${\displaystyle \varphi }$ ${\displaystyle \psi }$
二重否定[40]	二重否定除去	m DN	m行目と同じです。	m行目から、 を推論します。 ${\displaystyle \neg \neg \varphi }$ ${\displaystyle \varphi }$
アブスルドゥムへの還元	間接証明（IP）、否定導入（¬I）、否定除去（¬E）	m、 n  RAA  (k)	仮定の和集合は、k (否定された仮定)を除いて、行mと行nに設定されます。	規則の記述を簡略化するために、ここでは「否定」という語を次のように使用します。否定でない式の否定は ですが、否定には と の2 つの否定があります。行mとnでは、証明に現れる仮定 (行k ) の否定を推論します。 ${\displaystyle \varphi }$ ${\displaystyle \neg \varphi }$ ${\displaystyle \neg \varphi }$ ${\displaystyle \varphi }$ ${\displaystyle \neg \neg \varphi }$
選言三段論法	ウェッジ除去 (∨E)、トレンド ポネンス法 (MTP)	m,n DS	仮定の和集合は、行mと行nに設定されます。	m行目とn行目から、 を推論します。m行目とn行目から、 を推論します。 ${\displaystyle \varphi \lor \psi }$ ${\displaystyle \neg \varphi }$ ${\displaystyle \psi }$ ${\displaystyle \varphi \lor \psi }$ ${\displaystyle \neg \psi }$ ${\displaystyle \varphi }$
二重矢印の紹介	双条件定義（Df ）、双条件導入 ${\displaystyle \leftrightarrow }$	m、n私 ${\displaystyle \leftrightarrow }$	仮定の和集合は、行mと行nに設定されます。	行mと行 nのおよびから、 と推論します。 ${\displaystyle \varphi \to \psi }$ ${\displaystyle \psi \to \varphi }$ ${\displaystyle \varphi \leftrightarrow \psi }$
ダブルアローエリミネーション	二条件定義（Df ）、二条件消去 ${\displaystyle \leftrightarrow }$	自分​ ${\displaystyle \leftrightarrow }$	m行目と同じです。	m行目から、 または のいずれかを推論します。 ${\displaystyle \varphi \leftrightarrow \psi }$ ${\displaystyle \varphi \to \psi }$ ${\displaystyle \psi \to \varphi }$
Modus tollendo tollens	Modus tollens（MT）	m、n MTT	仮定の和集合は、行mと行nに設定されます。	m行目およびn行目から、 を推論します。 ${\displaystyle \varphi \to \psi }$ ${\displaystyle \neg \psi }$ ${\displaystyle \neg \varphi }$

サッペス・レモン式の例による証明

§ Suppes–Lemmon記法を導入した際に、既に例の証明を示しました。これは2つ目の例です。

例2

サップス・レモン式証明（2番目の例）

${\displaystyle P\lor Q,\neg P,\neg P\to \neg Q\vdash \bot }$矛盾
仮定セット	行番号	式	注釈
1	1	${\displaystyle P\lor Q}$	あ
2	2	${\displaystyle \neg P}$	あ
3	3	${\displaystyle \neg P\to \neg Q}$	あ
2,3	4	${\displaystyle \neg Q}$	2, 3 →東
1、2、3	5	${\displaystyle P}$	A（サブプルーフ）
1、2、3、5	6	${\displaystyle \bot }$	2、5 RAA [41]
1、2、3	7	${\displaystyle Q}$	A（サブプルーフ）
1、2、3、7	8	${\displaystyle \bot }$	4、7 RAA [41]
1、2、3	9	${\displaystyle \bot }$	1、5–6、7–8 東方
QED

例3

次の導出は 2 つの定理を証明します。

• 1行目から8行目は最小限の論理で証明されています:

${\displaystyle \vdash _{MPC}\neg \neg (P\lor \neg P)}$。

• 1行目から9行目は古典論理の範囲内で証明されています。

${\displaystyle \vdash _{CPC}P\lor \neg P}$。

目標:

• 1行目 - 8行目: . ${\displaystyle \vdash _{MPC}((P\lor (P\to \bot ))\to \bot )\to \bot }$
• 1行目 - 9行目: . ${\displaystyle \vdash _{CPC}P\lor (P\to \bot )}$

サップス・レモン式証明（3番目の例）

${\displaystyle \vdash P\lor \neg P}$
仮定セット	行番号	式	注釈
1	1	${\displaystyle (P\lor (P\to \bot ))\to \bot }$	あ
1、2	2	${\displaystyle P}$	あ
1、2	3	${\displaystyle P\lor (P\to \bot )}$	2、∨I
1、2	4	${\displaystyle \bot }$	1、3、→E
1	5	${\displaystyle P\to \bot }$	2、4、→I（2を放電）
1	6	${\displaystyle P\lor (P\to \bot )}$	5、∨I
1	7	${\displaystyle \bot }$	1、6、→E
∅	8	${\displaystyle ((P\lor (P\to \bot ))\to \bot )\to \bot }$	1, 7, →I（1を排出）
∅	9	${\displaystyle P\lor (P\to \bot )}$	8、DN
QED

注:ヴァレリー・グリヴェンコは 次の定理を証明しました。

が命題式である場合、が直観主義トートロジーである場合に限り、は古典的トートロジーです。 ${\displaystyle \varphi }$ ${\displaystyle \varphi }$ ${\displaystyle \neg \neg \varphi }$

これは、すべての古典的な命題定理がこの例のように証明できることを意味します。 ${\displaystyle \varphi }$

1. 直観主義論理の範囲内で（つまり なしで）証明します。 ${\displaystyle \neg \neg \varphi }$ ${\displaystyle \neg \neg _{E}}$
2. から取得するには申請してください。 ${\displaystyle \neg \neg _{E}}$ ${\displaystyle \varphi }$ ${\displaystyle \neg \neg \varphi }$

一貫性、完全性、正規形

理論は、偽が（いかなる仮定からも）証明できない場合に一貫性があり、すべての定理またはその否定が論理の推論規則を使用して証明できる場合に完全であると言われます。これらは論理全体についてのステートメントであり、通常、モデルの概念に結び付けられています。ただし、推論規則の純粋に構文的なチェックであり、モデルへの参照を必要としない一貫性と完全性のローカルな概念があります。 1 つ目は、ローカル一貫性、またはローカル還元可能性としても知られるローカルな一貫性で、これは、接続詞の導入と直後のその除去を含む任意の導出が、この迂回なしで同等の導出に変換できるというものです。これは、除去規則の強度のチェックです。除去規則は、前提にまだ含まれていない知識を含むほど強力であってはなりません。例として、連言を考えてみましょう。

${\displaystyle {\begin{aligned}{\cfrac {{\cfrac {{\cfrac {}{A\ }}u\qquad {\cfrac {}{B\ }}w}{A\wedge B\ }}\wedge _{I}}{A\ }}\wedge _{E1}\end{aligned}}\quad \Rightarrow \quad {\cfrac {}{A\ }}u}$

局所完全性とは、消去規則が接続詞をその導入規則に適した形式に分解できるほど強力であることを意味する。接続詞についても同様である。

${\displaystyle {\cfrac {}{A\wedge B\ }}u\quad \Rightarrow \quad {\begin{aligned}{\cfrac {{\cfrac {{\cfrac {}{A\wedge B\ }}u}{A\ }}\wedge _{E1}\qquad {\cfrac {{\cfrac {}{A\wedge B\ }}u}{B\ }}\wedge _{E2}}{A\wedge B\ }}\wedge _{I}\end{aligned}}}$

これらの概念は、カリー・ハワード同型性を用いたラムダ計算におけるβ-簡約（ベータ簡約）とη-変換（エータ変換）にちょうど対応する。局所完全性により、すべての導出は、主結合子が導入された同等の導出に変換できることがわかる。実際、導出全体が、除去とそれに続く導入の順序に従っている場合、それは正規であると言われる。通常の導出では、すべての除去は導入より前に行われる。ほとんどの論理では、すべての導出には、正規形と呼ばれる同等の通常の導出がある。正規形の存在は、自然演繹のみを使用して証明するのは一般に困難であるが、そのような説明は、 1961 年のDag Prawitzによるものなど、文献には存在する。^[42]カットフリーのシーケント計算の表現によって間接的にこれを示す方がはるかに簡単である。

第一および高階拡張

一次システムの概要

前の節の論理は、単一ソート論理、すなわち命題という単一のオブジェクトを持つ論理の例です。この単純な枠組みには多くの拡張が提案されていますが、本節では、個体または項という第二の種類を用いてこれを拡張します。より正確には、項という新しいカテゴリを追加します。これは と表記されます。可算な変数の集合 と、可算な関数記号の集合 を固定し、以下の構成規則に従って項を構築します。 ${\displaystyle {\mathcal {T}}}$ ${\displaystyle V}$ ${\displaystyle F}$

${\displaystyle {\frac {v\in V}{v:{\mathcal {T}}}}{\hbox{ var}}_{F}}$

そして

${\displaystyle {\frac {f\in F\qquad t_{1}:{\mathcal {T}}\qquad t_{2}:{\mathcal {T}}\qquad \cdots \qquad t_{n}:{\mathcal {T}}}{f(t_{1},t_{2},\cdots ,t_{n}):{\mathcal {T}}}}{\hbox{ app}}_{F}}$

命題については、述語の3番目の可算集合Pを考慮し、次の形成規則に従って項上の原子述語を定義します。

${\displaystyle {\frac {\phi \in P\qquad t_{1}:{\mathcal {T}}\qquad t_{2}:{\mathcal {T}}\qquad \cdots \qquad t_{n}:{\mathcal {T}}}{\phi (t_{1},t_{2},\cdots ,t_{n}):{\mathcal {F}}}}{\hbox{ pred}}_{F}}$

最初の2つの形成規則は、項代数やモデル理論で定義されているものと実質的に同一の項の定義を提供しますが、これらの研究分野の焦点は自然演繹とは全く異なります。3つ目の形成規則は、一階述語論理やモデル理論と同様に、原子式を実質的に定義します。

これらに、量化命題の表記法を定義する一対の形成規則が追加されます。1つは全称量化( ∀ )、もう1つは存在量化( ∃ )です。

${\displaystyle {\frac {x\in V\qquad A:{\mathcal {F}}}{\forall x.A:{\mathcal {F}}}}\;\forall _{F}\qquad \qquad {\frac {x\in V\qquad A:{\mathcal {F}}}{\exists x.A:{\mathcal {F}}}}\;\exists _{F}}$

全称量指定子には導入規則と除去規則があります。

${\displaystyle {\cfrac {\begin{array}{c}{\cfrac {}{a:{\mathcal {T}}}}{\text{ u}}\\\vdots \\{}[a/x]A\end{array}}{\forall x.A}}\;\forall _{I^{u,a}}\qquad \qquad {\frac {\forall x.A\qquad t:{\mathcal {T}}}{[t/x]A}}\;\forall _{E}}$

存在量指定子には導入規則と除去規則があります。

${\displaystyle {\frac {[t/x]A}{\exists x.A}}\;\exists _{I}\qquad \qquad {\cfrac {\begin{array}{cc}&\underbrace {\,{\cfrac {}{a:{\mathcal {T}}}}{\hbox{ u}}\quad {\cfrac {}{[a/x]A}}{\hbox{ v}}\,} \\&\vdots \\\exists x.A\quad &C\\\end{array}}{C}}\exists _{E^{a,u,v}}}$

これらの規則において、[ t / x ] Aという表記は、 Aにおけるxの（目に見える）すべてのインスタンスをtに置き換え、捕捉を回避することを表す。^[43]前述のように、名前の上付き文字は、解放される要素を表す。すなわち、項a はککI の結論には現れない（このような項は固有変数またはパラメータと呼ばれる）。また、∃E における仮説uおよびvは、仮説的導出における第二前提に局所化される。前節の命題論理は決定可能であったが、量指定子を追加すると論理は決定不可能となる。

ここまでの量化拡張は一階的であり、命題と量化される対象の種類を区別する。高階論理は異なるアプローチを取り、命題の種類は一種類だけである。量化子は、形成規則に反映されているように、量化の対象として全く同じ種類の命題を持つ。

${\displaystyle {\cfrac {\begin{matrix}{\cfrac {}{p:{\mathcal {F}}}}{\hbox{ u}}\\\vdots \\A:{\mathcal {F}}\\\end{matrix}}{\forall p.A:{\mathcal {F}}}}\;\forall _{F^{u}}\qquad \qquad {\cfrac {\begin{matrix}{\cfrac {}{p:{\mathcal {F}}}}{\hbox{ u}}\\\vdots \\A:{\mathcal {F}}\\\end{matrix}}{\exists p.A:{\mathcal {F}}}}\;\exists _{F^{u}}}$

高階論理の導入形式と消去形式については、この記事の範囲を超えています。第一階論理と高階論理の中間の論理も考えられます。例えば、第二階論理には2種類の命題があり、1つは項を量化する命題、もう1つは第一種の命題を量化する命題です。

証明と型理論

これまでの自然演繹の提示は、命題の性質に焦点を当てており、証明の正式な定義は示していない。証明の概念を形式化するために、仮説的導出の提示を少し変更する。前提を証明変数（可算な変数集合Vから）でラベル付けし、後続を実際の証明で修飾する。前提または仮説は、回転式改札口（⊢）によって後続から分離される。この変更は、局所的仮説と呼ばれることもある。次の図は、この変更をまとめたものである。

──── u 1 ──── u 2 ... ──── u n J 1 J 2 J n ⋮ J

⇒

u 1 :J 1、u 2 :J 2、...、u n :J n ⊢ J

仮説の集合は、その正確な構成が重要でない場合は、Γと表記されます。証明を明確にするために、証明のない判断「A」から、「πは (A) の証明である」という判断へと移ります。これは記号的に「π : A 」と表記されます。標準的なアプローチに従い、証明は「π証明」という判断のための独自の形成規則を用いて規定されます。最も単純な証明は、ラベル付けされた仮説を用いることです。この場合、証拠はラベルそのものです。

u∈V──────── 証明-F証明

────────────────────── ヒプu:A ⊢ u : A

明示的な証明を伴う接続詞のいくつかを再検討してみましょう。連言については、導入規則 ∧I を見て、連言の証明の形式を見つけます。つまり、2つの連言の証明のペアでなければなりません。つまり、

π 1証明 π 2証明──────────────────── ペアF(π 1 , π 2 ) の証明

Γ ⊢ π 1  : A Γ ⊢ π 2  : B────────────────────────── ∧IΓ ⊢ (π 1 , π 2 ) : A ∧ B

消去規則 ∧E ₁と ∧E _{2 は}左または右の連言のいずれかを選択します。したがって、証明は 1 つ目の射影 ( fst ) と 2 つ目の射影 ( snd ) のペアになります。

πの証明────── fst -F fst π証明		Γ⊢π：A∧B──────── ∧E 1 Γ ⊢ fst π : A
πの証明──────────── snd -F snd π 証明		Γ⊢π：A∧B──────── ∧E 2 Γ ⊢ snd π : B

含意については、導入形式はλを用いて記述され、仮説を局所化または束縛する。これは放出されたラベルに対応する。規則において、「Γ, u : A」は、仮説Γの集合と、追加の仮説uを表す。

πの証明────── λ-Fλu.πの証明		Γ, u:A ⊢ π : B────────────────── ⊃私Γ ⊢ λu. π : A ⊃ B
π 1証明 π 2証明──────────────────── アプリFπ 1 π 2の証明		Γ ⊢ π 1  : A ⊃ B Γ ⊢ π 2  : A──────────────────────────── ⊃EΓ ⊢ π 1 π 2  : B

証明が明示的に利用可能であれば、証明を操作し、推論することができます。証明における重要な操作は、ある証明で用いられている仮定を別の証明で置換することです。これは一般に置換定理として知られており、第二の判断の深さ（または構造）に基づく帰納法によって証明できます。

置換定理

Γ ⊢ π ₁  : A およびΓ、u : A ⊢ π ₂  : Bの場合、Γ ⊢ [π ₁ / u ] π ₂  : Bとなります。

これまで、「Γ ⊢ π : A」という判断は純粋に論理的な解釈がなされてきました。型理論では、この論理的な見方は、より計算的なオブジェクトの見方に置き換えられます。論理的解釈における命題は型として、証明はラムダ計算におけるプログラムとして扱われるようになります。したがって、「π : A 」の解釈は「プログラムπは型Aを持つ」となります。論理接続詞にも異なる解釈が与えられます。連言は積（×）、含意は関数の矢印（→）などとして扱われます。ただし、これらの違いは表面的なものです。型理論は、形成、導入、除去の規則によって自然な演繹表現が可能です。実際、読者は前のセクションから、いわゆる単純型理論を簡単に再構築することができます。

論理と型理論の違いは、主に焦点が型（命題）からプログラム（証明）に移っている点にあります。型理論は主にプログラムの変換可能性または還元可能性に着目します。あらゆる型には、その型に還元不可能な標準的なプログラムが存在します。これらは標準形または値と呼ばれます。あらゆるプログラムが標準形に還元できる場合、その型理論は正規化（または弱正規化）していると言われます。標準形が一意である場合、その理論は強く正規化していると言われます。正規化可能性は、ほとんどの非自明な型理論では稀な特徴であり、論理の世界とは大きく異なります。（ほとんどすべての論理的導出には、それと同等の正規導出があることを思い出してください。）その理由を概説すると、再帰定義を許容する型理論では、値に還元されないプログラムを書くことが可能です。このようなループプログラムには、一般に任意の型を与えることができます。特に、ループプログラムは型⊥を持ちますが、「⊥」の論理的証明はありません。このため、命題を型、証明をプログラムとするパラダイムは、仮に機能したとしても一方向にしか機能しません。つまり、型理論を論理として解釈すると、一般的に矛盾した論理が生じます。

例: 依存型理論

論理と同様に、型理論にも多くの拡張と変種があり、一階述語版や高階述語版などがあります。依存型理論として知られる分野の一つは、多くのコンピュータ支援証明システムで使用されています。依存型理論では、量化子がプログラム自体を範囲とすることができます。これらの量化型は、 ک と ∃ の代わりに Π と Σ と表記され、以下の形成規則に従います。

Γ ⊢ A型 Γ, x:A ⊢ B型─------------------------------------------ Π-FΓ⊢Πx:A. B型

Γ ⊢ A型 Γ, x:A ⊢ B型─------------------------------------------ Σ-FΓ ⊢ Σx:A. B型

これらの型は、導入規則と除去規則からもわかるように、それぞれ矢印型と積型の一般化です。

Γ, x:A ⊢ π : B──────────────────── ΠIΓ ⊢ λx. π : Πx:A. B

Γ ⊢ π 1  : Πx:A。 B Γ ⊢ π 2  : A───────────── ΠEΓ ⊢ π 1 π 2  : [π 2 /x] B

Γ ⊢ π 1  : A Γ, x:A ⊢ π 2  : B────────────────────────────── ΣIΓ ⊢ (π 1 , π 2 ) : Σx:A。 B

Γ⊢π:Σx:A.B─────────── ΣE 1 Γ ⊢ fst π : A

Γ⊢π:Σx:A.B───────────── ΣE 2 Γ ⊢ snd π : [ fst π/x] B

完全な一般性を備えた依存型理論は非常に強力です。プログラムの考えられるほぼあらゆる特性を、プログラムの型で直接表現できます。この一般性には大きな代償が伴います。型検査が決定不可能（外延型理論）であるか、外延的推論がより困難（内包型理論）であるかのどちらかです。このため、一部の依存型理論では、任意のプログラムに対する量化を許容せず、整数、文字列、線形計画法など、 特定の決定可能なインデックスドメインのプログラムに限定しています。

依存型理論では型がプログラムに依存できることが認められているため、当然、プログラムが型、あるいは他の組み合わせに依存できるかどうかという疑問が生じる。こうした疑問には多くの種類の答えがある。型理論で人気のアプローチは、型に対してプログラムを量化できるようにするもので、パラメトリック多態性とも呼ばれる。これには主に 2 種類ある。型とプログラムを分けておけば、述語的多態性と呼ばれる、いくぶん行儀のよいシステムが得られる。プログラムと型の区別があいまいな場合は、非述語的多態性としても知られる、高階論理の型理論的類似物が得られる。文献では依存性と多態性のさまざまな組み合わせが検討されているが、最も有名なのはHenk Barendregtのラムダ キューブである。

論理と型理論の交わる領域は、広範かつ活発な研究分野です。新しい論理は通常、論理枠組みとして知られる一般的な型理論の設定に基づいて形式化されます。構成計算やLFといった現代の一般的な論理枠組みは、高階依存型理論に基づいていますが、決定可能性と表現力に関して様々なトレードオフがあります。これらの論理枠組み自体は常に自然演繹システムとして規定されており、これは自然演繹アプローチの汎用性を証明しています。

古典論理と様相論理

これまで示してきた論理は簡潔にするために直観主義的であった。古典論理は、直観主義論理に排中公理または排中原理を加えて拡張したものである。

任意の命題pに対して、命題p∨¬pは真である。

この記述は明らかに導入でも排除でもない。実際、2つの異なる接続詞を含んでいる。ゲンツェンによる排中律の元々の扱いは、以下の3つの（同値な）定式化のいずれかを規定していたが、これらはヒルベルトとハイティングの体系にも類似の形で既に存在していた。

────────────── XM 1A ∨ ¬A

¬¬A────────── XM2あ

────────あなた¬A⋮p ────── XM 3 u、pあ

(XM ₃は単にE で表現されたXM _{2です。) この排中律の扱いは、純粋主義者の観点からは好ましくないだけでなく、正規形の定義にさらなる複雑さをもたらします。}

導入規則と除去規則のみによる古典的な自然演繹の比較的満足のいく処理は、1992 年に Parigot によってλμと呼ばれる古典的なラムダ計算の形で初めて提案されました。彼のアプローチの重要な洞察は、真理中心の判断A を、シーケント計算を彷彿とさせるより古典的な概念で置き換えたことでした。つまり、局所的な形式で、 Γ ⊢ Aの代わりにΓ ⊢ Δ を使用し、 Δ は Γ に類似した命題のコレクションです。 Γ は連言として、 Δ は選言として扱われました。この構造は、本質的には古典的なシーケント計算から直接取り入れられたものですが、 λμ での革新性は、 LISPとその派生で見られるcallccまたは throw/catch メカニズムの観点から、古典的な自然演繹の証明に計算上の意味を与えたことです。( 「ファースト クラス制御」も参照)

もう一つの重要な拡張は、真理性に関する基本的な判断以上のものを必要とする様相論理やその他の論理への拡張でした。これらは、 1965年にプラウィッツによって自然演繹様式で、論理学的様相論理S4およびS5について初めて記述され、 ^[5]、それ以来、関連研究が数多く蓄積されてきました。簡単な例を挙げると、様相論理S4は、真理性に関して定言的な 「 Aは有効である」という新たな判断を一つ必要とします。

「B」が真であるという仮定なしに「A」が真であれば、「A」は有効です。

この断定的な判断は、次のような導入および除去規則を持つ単項接続詞◻A（「必然的にA」と読む）として内部化されます。

有効な──────── ◻私◻ あ

◻ あ──────── ◻Eあ

前提「A は有効」には定義規則がなく、代わりに妥当性の定性的定義が用いられることに注意してください。このモードは、仮説が明示的な場合の局所的な形でより明確になります。「Ω;Γ ⊢ A」と書きます。ここで、Γ は前述のように真の仮説を含み、Ω は有効な仮説を含みます。右側には単一の判断「A 」があります。「Ω ⊢ A は有効」は定義上「Ω;⋅ ⊢ A 」と同じであるため、ここでは妥当性は必要ありません。導入形式と除去形式は以下のようになります。

Ω;⋅ ⊢ π : A────────────────────── ◻私Ω;⋅ ⊢ボックスπ : ◻ A

Ω;Γ ⊢ π : ◻ A─────────── ◻EΩ;Γ ⊢アンボックスπ : A

モーダル仮説には、仮説規則と置換定理の独自のバージョンがあります。

────────────────────────────────── 有効な仮説Ω, u: (A 有効) ; Γ ⊢ u : A

様相置換定理

Ω;⋅ ⊢ π ₁  : A およびΩの場合、u : ( A valid ) ; Γ ⊢ π ₂  : C、次にΩ;Γ ⊢ [π ₁ / u ] π ₂  : C。

判断を異なる仮説の集合（マルチゾーン・コンテキストまたはポリアディック・コンテキストとも呼ばれる）に分割するこの枠組みは、非常に強力で拡張性が高い。多くの異なる様相論理、さらには線型論理やその他の部分構造論理にも適用されており、その例をいくつか挙げることができる。しかし、様相論理の体系のうち、自然演繹に直接形式化できるものは比較的少ない。これらの体系に証明理論的特徴を与えるには、ラベリングや深層推論の体系といった拡張が必要となる。

式にラベルを付加することで、規則が適用される条件をより細かく制御できるようになり、ラベル付き演繹の場合と同様に、より柔軟な解析的タブロー技法を適用できるようになります。また、ラベルはクリプキ意味論における世界の命名を可能にします。シンプソン (1994) は、クリプキ意味論における様相論理のフレーム条件を、ハイブリッド論理の自然演繹形式化における推論規則に変換する影響力のある技法を提示しています。ストウッパ (2004) は、アヴロンとポッティンジャーのハイパーシークエントやベルナップの表示論理など、多くの証明理論のS5 や B のような様相論理へ の適用を調査しています。

シーケント計算との比較

シーケント計算は、数理論理学の基礎として自然演繹に代わる主要な選択肢である。自然演繹では情報の流れは双方向である。すなわち、消去規則は分解によって情報を下向きに流し、導入規則は組み立てによって情報を上向きに流す。したがって、自然演繹の証明は純粋なボトムアップやトップダウンの読み方を持たないため、証明探索の自動化には適さない。この事実に対処するため、ゲンツェンは1935年にシーケント計算を提案したが、当初は述語論理の整合性を明確にするための技術的手段を意図していた。クリーネは、1952年の著書『メタ数学入門』で、現代的なスタイルでシーケント計算を初めて定式化した。^[44]

シークエント計算では、すべての推論規則は純粋にボトムアップの解釈を持ちます。推論規則は、ターンスタイルの両側の要素に適用できます。（自然演繹と区別するため、この記事ではシークエントを表す際に右矢印 ⊢ ではなく二重矢印 ⇒ を使用します。）自然演繹の導入規則は、シークエント計算では右規則として扱われ、構造的に非常に似ています。一方、消去規則はシークエント計算では左規則になります。例として、選言を考えてみましょう。右規則はよく知られています。

Γ ⇒ A────────── ∨R 1Γ ⇒ A ∨ B

Γ ⇒ B────────── ∨R 2Γ ⇒ A ∨ B

左に：

Γ, u:A ⇒ C Γ, v:B ⇒ C──────────────────────────── ∨LΓ, w: (A ∨ B) ⇒ C

局所的な形での自然演繹の∨E規則を思い出してください。

Γ ⊢ A ∨ B Γ、u:A ⊢ C Γ、v:B ⊢ C────────────────────────────────────────── ∨EΓ⊢C

∨E の前提の後続である命題A ∨ Bは、左規則 ∨L において結論の仮定となる。したがって、左規則は一種の逆消去規則と見ることができる。この観察は以下のように説明できる。

自然演繹		シーケント計算
────── ヒプ | | 排除ルール | ↓ ────────────────────── ↑↓会う ↑ | | はじめに。ルール | 結論	⇒	─------------------------------------------ 初期化 ↑↑ | | | 左ルール | 右ルール | | 結論

シークエント計算では、左規則と右規則は、自然演繹における除去規則と導入規則の交点に相当する初期シークエントに到達するまで、同期して実行されます。これらの初期規則は、表面的には自然演繹の仮説規則に似ていますが、シークエント計算では、左命題と右命題の転置、つまり握手を記述します。

────── 初期化Γ, u:A ⇒ A

シーケント計算と自然演繹の間の対応は健全性定理と完全性定理のペアであり、どちらも帰納的議論によって証明可能です。

⇒ ⊢に対する健全性

Γ ⇒ AならばΓ ⊢ A。

⇒ ⊢に対する完全性

Γ ⊢ AならばΓ ⇒ A。

これらの定理から、シーケント計算は真理の概念を変えないことが明らかである。なぜなら、同じ命題の集合は真のままだからである。したがって、シーケント計算による導出において、以前と同じ証明対象を用いることができる。例として、連言を考えてみよう。右辺の規則は導入規則と実質的に同一である。

シーケント計算		自然演繹
Γ ⇒ π 1  : A Γ ⇒ π 2  : B──────────────────────────── ∧RΓ ⇒ (π 1 , π 2 ) : A ∧ B		Γ ⊢ π 1  : A Γ ⊢ π 2  : B────────────────────────── ∧IΓ ⊢ (π 1 , π 2 ) : A ∧ B

ただし、左のルールでは、対応する除去ルールでは実行されない追加の置換がいくつか実行されます。

シーケント計算		自然演繹
Γ, u:A ⇒ π:C────────────────────────────────── ∧L 1 Γ, v: (A ∧ B) ⇒ [最初v/u] π : C		Γ⊢π：A∧B──────── ∧E 1 Γ ⊢ fst π : A
Γ, u:B ⇒ π:C─-------------------------------------------------------- ∧L 2 Γ, v: (A ∧ B) ⇒ [ snd v/u] π : C		Γ⊢π：A∧B──────── ∧E 2 Γ ⊢ snd π : B

したがって、シークエント計算で生成される証明の種類は、自然演繹の証明の種類とは大きく異なります。シークエント計算は、 β正規η長形式と呼ばれる形式で証明を生成します。これは、自然演繹証明の正規形の標準的な表現に対応します。これらの証明を自然演繹自体を用いて記述しようとすると、インターカレーション計算（ジョン・バーンズによって初めて記述された）と呼ばれるものが得られ、これを用いて自然演繹の正規形の概念を形式的に定義することができます。

自然演繹の置換定理は、シーケント計算におけるカットとして知られる構造規則または構造定理の形をとります。

カット（交代）

Γ ⇒ π ₁  : A およびΓ、u : A ⇒ π ₂  : Cの場合、Γ ⇒ [π ₁ /u] π ₂  : Cとなります。

ほとんどの行儀の良い論理では、カットは推論規則としては不要ですが、メタ定理として証明可能です。カット規則の不要性は通常、カット除去と呼ばれる計算プロセスとして提示されます。これは自然演繹に興味深い応用があります。通常、自然演繹では特定の特性を直接証明するのは、場合の数が無限にあるため非常に面倒です。たとえば、与えられた命題が自然演繹では証明できないことを示すことを考えてみましょう。単純な帰納的議論は、∨E や E などの任意の命題を導入できる規則のために失敗します。しかし、シーケント計算は自然演繹に関して完全であることがわかっているので、この証明不可能性をシーケント計算で示せば十分です。さて、カットが推論規則として利用できない場合、すべてのシーケント規則は右または左に接続詞を導入するため、シーケント導出の深さは最終結論の接続詞によって完全に制限されます。したがって、証明不可能性の証明ははるかに容易になります。なぜなら、考慮すべきケースは有限個しかなく、各ケースは結論の部分命題のみで構成されるからです。この単純な例として、大域無矛盾定理が挙げられます。「⋅ ⊢ ⊥」は証明不可能です。シーケント計算版では、「⋅ ⇒ ⊥」を結論として持つ規則は存在しないため、これは明白に真です。証明理論家は、このような性質のため、カットフリーなシーケント計算の定式化を好んで研究することがよくあります。

参照

• 哲学ポータル

• 数理論理学
• シーケント計算
• ゲルハルト・ゲンツェン
• システムL（表形式の自然演繹）
• 議論マップ、ツリー状の論理表記法の総称

注記

1. インジェチャク。
2. ヤシュコフスキ 1934.
3. ゲンツェン 1935a、ゲンツェン 1935b。
4. ゲンツェン 1935a、176ページ。
5. プラヴィッツ 1965 年、プラヴィッツ 2006 年。 harvnb error: no target: CITEREFPrawitz1965 (help) harvnb error: no target: CITEREFPrawitz2006 (help)
6. マーティン・レーフ 1996.
7. ペルティエ & ヘイゼン 2024.
8. Quine (1981). Quineによる先行詞依存関係の行番号表記については、特に91～93ページを参照。
9. クリーネの表形式自然演繹体系の特に優れた点は、命題論理と述語論理の両方の推論規則の妥当性を証明していることである。クリーネ 2002, pp. 44–45, 118–119 を参照。
10. プラトン 2013、9ページ。
11. ワイスタイン。
12. フォン プラトン 2013、9、32、121。
13. サトクリフ。
14. Restall 2018。
15. Magnus et al. 2023, p. 142、第20章、証明理論的概念。
16. パソー＆リーク。
17. パソー＆プレゲル 2023.
18. Magnus et al. 2023, p. 82, 12.5 二重回転式改札口。
19. アレン＆ハンド 2022.
20. アレン＆ハンド 2022年、12ページ。
21. クリーネ 2002.
22. プラウィッツ 1965年。 sfn error: no target: CITEREFPrawitz1965 (help)
23. プラトン 2013、18ページ。
24. Van Dalen 2013より。
25. ハンソン＆ヘンドリックス 2018、179ページ。
26. アヤラ＝リンコン＆デ・モウラ 2017、2、20ページ。
27. ハンソン＆ヘンドリックス 2018、38ページ。
28. ボストック 1997年、21ページ。
29. これは、と を同値として扱わない矛盾のない論理では必要です。 ${\displaystyle \neg }$ ${\displaystyle (\phi \to \bot )}$
30. フォン プラトン 2013、12–13 ページ。
31. プラウィッツ 1965年、20ページ。 sfn error: no target: CITEREFPrawitz1965 (help)
32. Eの代わりに、古典論理を得るための規則として、逆理屈を^{加えることができる： [34] [35]} ${\displaystyle \neg \neg }$

    ${\displaystyle {\frac {\begin{array}{c}[\varphi \to \bot ]\\\vdots \\\bot \end{array}}{\varphi }}}$（RAA）

33. ヨハンソン 1937.
34. Prawitz 1965、p. 21を参照。 sfn error: no target: CITEREFPrawitz1965 (help)
35. アヤラ リンコン & デ モウラ 2017、17–24 ページ。
36. テナント 1990、48ページ。
37. Suppes 1999より。
38. Lemmon 1978より。
39. Lemmon 1978、pp. passim、特に39-40。
40. アーサー 2017.
41. これはRAA規則に従わない。暗黙的に適用される規則は→Eである。否定は含意として定義されていないため、この発生法は文書化されていない。 ${\displaystyle \varphi ,\varphi \to \bot }$
42. 彼の著書『Prawitz 1965』、『Prawitz 2006』も参照。 harvnb error: no target: CITEREFPrawitz1965 (help) harvnb error: no target: CITEREFPrawitz2006 (help)
43. 置換の概念の詳細については、ラムダ計算の記事を参照してください。
44. Kleene 2009, pp. 440–516. Kleene 1980も参照。

参考文献

一般的な参考文献

• アレン、コリン; ハンド、マイケル (2022). 『論理学入門（第3版）』 マサチューセッツ州ケンブリッジ: MIT出版. ISBN 978-0-262-54364-4。
• アーサー、リチャード・TW (2017). 『論理学入門：自然演繹、実在論、ちょっとした歴史、そしてユーモア』（第2版）. ピーターボロ、オンタリオ州: ブロードビュー・プレス. ISBN 978-1-55481-332-2. OCLC  962129086.
• マウリシオ州アヤラ・リンコン。デ・モウラ、フラヴィオ LC (2017)。コンピュータ科学者のための応用ロジック。コンピューターサイエンスの学部トピック。スプリンガー。土井：10.1007/978-3-319-51653-0。ISBN 978-3-319-51651-6。
• バーカー・プラマー, デイブ;バーワイズ, ジョン;エチェメンディ, ジョン(2011).言語の証明と論理(第2版). CSLI Publications. ISBN 978-1575866321。
• ボストック、デイヴィッド（1997年）『中級論理学』オックスフォード、ニューヨーク：クラレンドン・プレス、オックスフォード大学出版局、ISBN 978-0-19-875141-0。
• Gallier, Jean (2005). 「構成的論理 パート1：証明システムと型付きλ計算のチュートリアル」. 2017年7月5日時点のオリジナルよりアーカイブ。 2014年6月12日閲覧。
• ゲンツェン、ゲルハルト・カール・エーリッヒ（1935a）。 「Untersuhungen über das logische Schließen. I」。数学的ツァイシュリフト。39 (2): 176–210。土井:10.1007/bf01201353。S2CID  121546341。2015 年 12 月 24 日のオリジナルからアーカイブ。

— (1964) [1935].「論理的演繹の探究」アメリカ哲学季刊誌. 1 (4): 249– 287.

• ゲンツェン、ゲルハルト・カール・エーリッヒ（1935b）。 「Untersuchungen über das logische Schließen. II」。数学的ツァイシュリフト。39 (3): 405–431 .土井:10.1007/bf01201363。S2CID  186239837。2012 年 7 月 9 日時点のオリジナルからアーカイブ。

— (1965) [1935].「論理的演繹の探究」アメリカ哲学季刊誌2 ( 3): 204– 218.

• ジャン＝イヴ・ジラール（1990年）「証明と型」『ケンブリッジ理論計算機科学論集』ケンブリッジ大学出版局、ケンブリッジ、イギリス。2016年7月4日時点のオリジナルよりアーカイブ。 2006年4月20日閲覧。ポール・テイラーとイヴ・ラフォンによる翻訳と付録。
• ハンソン、スヴェン・オーヴェ著、ヘンドリックス、ヴィンセント・F.著 (2018). 『形式哲学入門』シュプリンガー大学哲学テキスト. シュプリンガー出版. ISBN 978-3-030-08454-7。
• ヤシュコフスキ、スタニスワフ（1934）『形式論理における仮定の規則について』ストーズ・マッコール編『ポーランド論理学 1920-39』に再録。
• ヨハンソン、インゲブリクト(1937)。 「Der Minimalkalkül、ein reduzierter intuitionistischer Formalismus」。Compositio Mathematica (ドイツ語)。4：119～ 136。
• クリーネ、スティーブン・コール(1980) [1952].メタ数学入門（第11版）. ノースホランド. ISBN 978-0-7204-2103-3。
• クリーネ、スティーブン・コール(2009) [1952].メタ数学入門. イシ・プレス・インターナショナル. ISBN 978-0-923891-57-2。
• クリーネ、スティーブン・コール(2002) [1967].数理論理学. ミネオラ、ニューヨーク: ドーバー出版. ISBN 978-0-486-42533-7。
• レモン、エドワード・ジョン(1978) [1965]. 『Beginning Logic』（第5刷、1985年版）. フロリダ州ボカラトン：ハケット出版社. ISBN 0915144-50-6。
• Magnus, PD; Button, Tim; Trueman, Robert; Zach, Richard (2023). forall x: An Introduction to Formal Logic (2023年秋版). Open Logic Project . 2025年5月4日閲覧。
• Martin-Löf, Per (1996). 「論理定数の意味と論理法則の正当化について」(PDF) . Nordic Journal of Philosophical Logic . 1 (1): 11– 60. 2023年12月8日時点のオリジナル(PDF)からアーカイブ。 2010年7月2日閲覧。1983年4月、シエナ大学での短期コースの講義ノート。
• パソー, A.C.; リーク, ロバート. 「コンパクト性定理」. インターネット哲学百科事典. 2024年3月22日閲覧。
• パソー、アレクサンダー、プレゲル、ファビアン（2023年）「数学の哲学における演繹主義」、ザルタ、エドワード・N、ノーデルマン、ウリ（編）『スタンフォード哲学百科事典』（2023年秋版）、スタンフォード大学形而上学研究室、2024年3月22日閲覧。
• ペルティエ、フランシス・ジェフリー、ヘイゼン、アレン（2024年）「論理における自然演繹システム」、ザルタ、エドワード・N、ノーデルマン、ウリ（編）、スタンフォード哲学百科事典（2024年春版）、スタンフォード大学形而上学研究室、2024年3月22日閲覧。
• Pfenning, Fr​​ank; Davies, Rowan (2001). 「様相論理の判断的再構築」(PDF) .コンピュータサイエンスにおける数学的構造. 11 (4): 511– 540. CiteSeerX  10.1.1.43.1611 . doi :10.1017/S0960129501003322. S2CID  16467268.
• プラヴィッツ、ダグ(1965)。自然演繹: 証明理論的研究。ストックホルミエンシス大学;ストックホルム哲学研究、3。ストックホルム、ヨーテボリ、ウプサラ：アルムクヴィストとヴィクセル。OCLC  912927896。
• プラウィッツ、ダグ（2006年）『自然演繹：証明理論的研究』ミネオラ、ニューヨーク：ドーバー出版。ISBN 9780486446554. OCLC  61296001。
• クワイン、ウィラード・ヴァン・オーマン(1981) [1940].数理論理学（改訂版）. マサチューセッツ州ケンブリッジ: ハーバード大学出版局. ISBN 978-0-674-55451-1。
• クワイン、ウィラード・ヴァン・オーマン(1982) [1950]. 『論理学の方法』（第4版）. マサチューセッツ州ケンブリッジ: ハーバード大学出版局. ISBN 978-0-674-57176-1。
• レストール、グレッグ（2018）「サブストラクチュラル・ロジック」、ザルタ、エドワード・N.（編）、スタンフォード哲学百科事典（2018年春版）、スタンフォード大学形而上学研究室、2024年3月22日閲覧。
• シンプソン、アレックス・K. (1994). 直観主義様相論理の証明論と意味論(PDF) (学位論文).エディンバラ研究アーカイブ (ERA) . hdl :1842/407.
• ストール、ロバート・ロス (1979) [1963].集合論と論理. ミネオラ、ニューヨーク: ドーバー出版. ISBN 978-0-486-63829-4。
• Stouppa, Phiniki (2004).様相証明理論の設計：S5 の事例. ドレスデン大学. CiteSeerX  10.1.1.140.1858 .修士論文。
• サッペス、パトリック・コロネル(1999) [1957].論理学入門. ミネオラ、ニューヨーク: ドーバー出版. ISBN 978-0-486-40687-9。
• サトクリフ、ジェフ. 「命題論理」. www.cs.miami.edu . マイアミ大学. 2025年5月4日閲覧。
• テナント、ニール (1990) [1978]. 『自然論理』（初版、訂正版再版）.エディンバラ大学出版局. ISBN 0852245793。
• ヴァン・ダーレン、ダーク(2013) [1980]。ロジックと構造。ユニバーシティテキスト (第 5 版)。ロンドン、ハイデルベルク、ニューヨーク、ドルドレヒト: Springer。土井：10.1007/978-1-4471-4558-5。ISBN 978-1-4471-4558-5。
• フォン・プラトン、ヤン（2013年）『論理的推論の要素』（第1版）ケンブリッジ：ケンブリッジ大学出版局、ISBN 978-1-107-03659-8。
• Weisstein, Eric W. 「Connective」. mathworld.wolfram.com . 2024年3月22日閲覧。

外部リンク

• インジェイチャク, アンジェイ. 「自然演繹」.インターネット哲学百科事典. 2025年5月4日閲覧。
• ラボレオ、ダニエル・クレメンテ (2004 年 8 月)。 「自然控除入門」（PDF）。
• 「Domino On Acid」 。 2023年12月10日閲覧。ドミノゲームとして視覚化された自然推論
• ペルティエ、フランシス・ジェフリー。「自然演繹と初等論理学教科書の歴史」（PDF）。
• スタンフォード哲学百科事典、2021年10月29日、ペルティエ、フランシス・ジェフリー、ヘイゼン、アレンによる「論理における自然演繹システム」の記事
• レヴィ、ミシェル。「命題証明器」

Retrieved from "https://en.wikipedia.org/w/index.php?title=Natural_deduction&oldid=1306485576"