1 はじめに

1.1 論証の形式

論理学は伝統的に「論証や推論についての科学」だと言われてきた。この言い方は基本的にいまでも正しい。しかし問題は、論証や推論といわれるものがどのようなものか、それらについての「科学」と言う場合の「科学」とはどのようなものを指すのか、である。

そこでまず、誰かがある議論・論証を行なった場面を考えてみよう。その議論や論証を他の人達が「論理的だ」と評価した場合、それは一般にどのような評価なのだろうか。一つの解釈は、その論証が筋の通った論証であり、説得力のあるよい論証だという肯定的な評価である。もう一つの評価は、筋は通っているかもしれないが形式的で実質がないという否定的な評価である。論理学の観点から見たとき、たぶん、この評価のどちらにもいくらかの真実が含まれているように思われる。

否定的な評価の方から考えてみよう。論理学は多分に形式的である。それは例えば、

魚は卵生である。 \underline{クジラは魚である。} クジラは卵生である。

のような推論を論理学では妥当な（正しい）推論とみなすことからもわかる。つまり、論理学では論証や推論を構成している個々の文（命題）が「実際に正しいか否か」を問題にはしないのである。上の推論に関して重要なのは、最初の二つの前提が（正しいにしろ間違っているにしろ）与えられたとき、それらの前提から結論が導かれるか否かであって、それらの前提や結論が（生物学や分類学の）正しい事実かどうかではない。

次に肯定的な評価を検討しよう。論証が肯定的に評価されるとき、そこには様々な要因があると考えられる。例えば、誰もが思いもつかなかったような前提を明らかにしている、等々。そしてもう一つの重要な要因はその論証が説得的であるということであろう。その点で言えば、上述のクジラの例は確かに説得的ではない。論証が説得的であるためには、（たとえ結論が思いがけないものであるとしても）少なくとも前提は正しくなければならないはずである。そしてこの点に論理学が関与しないことは既に述べた。けれども、例えば

日本の首都は東京である。

\underline{神奈川県の県庁所在地は横浜である。} 北海道で一番大きな都市は札幌である。

のようなものはどうであろうか。この推論（？）に現われている前提も結論もすべて正しい。しかしながら、このようなものは推論でもなんでもないように思われる。問題は、この例では前提と結論の間に何のつながりもない、ということであろう。つまり、ある文（命題）の集まりが正しい推論になっていると言えるためには、単にそれらの文が真であるというだけではだめで、

前提から結論が導かれる

ということ、言い換えれば、前提を真と認めたならば結論が必ず真になる、ということを示す必要がある。それをどのように示すかが以下の基本的な課題である。

1.2 自然言語の推論を形式化すること

われわれが普段実際に使っている言語、日本語やスワヒリ語やウルドゥ語やその他もろもろの言語は、プログラム言語やエスペラントのように特定の目的のために作られた言語（人工言語）とは違って、自然言語と呼ばれている。論理学では、推論の構造を記述するために特別に人工的な言語を作り、自然言語によってなされている推論をその人工言語の推論に翻訳しようとする。では、なぜそのような回りくどいやり方をするのであろうか。その理由は大雑把に言って三つある。 1. 使用と言及の区別、さらに言えば対象言語とメタ言語の区別を体系的に行うため。

2. 自然言語のもつあいまいさや多義性を除去する。

3. 論証の構造をあからさまに示すため。

この最後の点についてはもう少し詳しく説明する必要がある。重要なのは、論証の構造を明らかにする方法は一つではないということである。ある方法を採用すると、その方法の下ではある論証が正しいと考えられるような構造が得られるが、別な方法の下ではそのような構造が得られないことがある。これを具体的に検討しよう。

1.3 命題論理と述語論理

例えば、論証の構造を取り出すための一方法として、

命題と命題をつなぐ接続詞と否定詞に注目し、それらを含まない命題を単独の文字で置き換える

方法を考えてみよう。いくつかの接続詞と否定詞を次のような記号で表すことにする。

記号対応する日本語
否定  ¬  「… でない」
連言  ∧  「かつ」、「そして」
選言  ∨  「または」
条件法 →  「もし… ならば… 」

これに加えて、「雪は白い」のような、接続詞も否定詞も含まない命題（原子命題）を P, Q, … のような文字で表すこととする。

その上で、つぎのような論証を考えてみよう。

気温が日陰で華氏 96 度あるか、または湿度が異常に高いかである。もし気温が日陰で華氏 96 度あるならば、人々は泳ぎに行く。もし湿度が異常に高いならば、人々は高台に行く。もし人々が泳ぎに行くならば、町は無人になる。もし人々が高台に行くならば、町は無人になる。したがって、町は無人になる。

この論証の原子命題として「気温が日陰で華氏 96 度ある」を P 、「湿度が異常に高い」を Q、「人々は泳ぎに行く」を R、「人々は高台に行く」を S、「町は無人になる」を T で表し、上記の記号を用いるならば、結果は次のようになる。（ただし、同じ原子命題がいくつも登場する場合は、同じ文字で置き換えることとする。）

P ∨ Q, P → R, Q → S, R → T, S → T ⊢ T

このような作業によってあらわにされた論証の構造が、論証の正しさを決定するのにどう役立つかということはまだ述べられていない。しかし、とりあえず、論理的に一定の役割を果たす部分（接続詞や否定詞）とそうでない部分とがはっきり区別できるようになっていることが重要である。

しかし、次のような論証の場合はどうか。

魚は卵生である。 \underline{クジラは魚である。} クジラは卵生である。

もしこの論証を上記の方法に従って置き換えたとしても、論証の構造は明らかにはならない。この論証の構造を明らかにするには別の方法が必要なのである。それゆえ、論証の構造をあらわにする方法は一つではないこと、どの方法を採用するかによって扱える論証の範囲が変わることがわかる。

上のような推論の構造を明らかにするには、（接続詞や否定詞を含まない）単純な文を単独の文字 P, Q 等で表すのでは不充分である。ここではむしろ単純な文そのものに一定の内部構造を割り当てなくてはならない。そうした内部構造を割り当てる一つのやり方を明らかにし、そのような構造をもつ文からなる推論の妥当性の基準を明らかにすることが、この講義の中心的な目標である。そのような論理を（一階の）述語論理という。これに対し、少し前に見た接続詞と否定詞の論理は命題論理と呼ばれる。この両者は、まったく無関係なわけではない。述語論理は、命題論理をベースにして構成される。したがって、われわれの目標（述語論理）に取りかかる前に、ここしばらくは命題論理に焦点を合わせることにしたい。

2 命題論理の形式化

以下では、命題論理の形式化をどのように行うかについて具体的に見てゆくことにしよう。命題論理の形式化は次の二つのプロセスからなる。

1. 命題論理の形式言語を提示する

2. 妥当な命題（真なる命題）ないし妥当な推論を得る方法を示す

2.1 命題論理の言語

定義 1 命題論理の言語は次のような語彙からなる。

1. 命題記号: P, Q, R, … P_{1}, P_{2}, …

2. 論理結合子: ¬, ∧, ∨, →, ↔, ⊥

3. 補助記号: ( , ) .

論理結合子のリスト（の一部）はすでに示しておいたが、ここでもう一度完全なリストを提示しておこう。

記号対応する日本語
否定 negation  ¬  「… でない」
連言 conjunction  ∧  「かつ」、「そして」
選言 disjunction  ∨  「または」
条件法 conditional  →  「もし… ならば… 」
双条件法 biconditional ↔  英語の ‘if and only if’ に相当
矛盾 absurdity  ⊥

定義 2 命題の集合 PROP は、次の性質をもつ最小の集合 X である。

1. P, Q, R, … ∈ X, ⊥∈ X

2. φ, ψ ∈ X ならば、 (φ ∧ ψ), (φ ∨ ψ), (φ → ψ), (φ ↔ ψ) ∈ X

3. φ ∈ X ならば、 (¬φ) ∈ X

このような定義は、帰納的定義と呼ばれている。そのポイントは（１）最初に、それ以上命題に分解できないような（もはや否定詞や接続詞を含まない）最小の命題を与える、（２）次に、すでに与えられた命題から複合命題をどのように構成するか、その手続きを与える、という点にある。このような帰納的定義によって定義されたものについては、帰納法による証明が可能となるが、それについては後述する。

その他に注意すべき点は、 φ や ψ が何かということである。これらは（１）命題論理の言語の語彙には含まれていないのだから、メタ言語の側で使われる記号であり、（２）特定の命題を表しているのではなく、それまでに構成された様々な命題を表している点で一種の変数・変項と見なされる。このようなものは通常、メタ変項と呼ばれる。

また、矛盾記号 ⊥ は一種の原子命題、つまりそれ以上分解できない命題と見なされる記号である。その意味では、論理結合子のリストにあるのはいささか奇妙であるが、 P, Q, … が特定の命題ではなく、いろいろな命題を表し得るのに対し、 ⊥ はつねに定まった意味をもつ点では結合子にも似ている。この記号は内容的にはつねに偽な命題を表わす記号であり、実際には、なくてもかまわない。しかし、あると便利な記号である。どういう点でこの記号が役に立つかは後で触れることにしたい。

例 1 (P → Q), ((⊥ ∨Q) ∧ (¬R)), (Q ↔ P) ∈ PROP Q ↔ P, ¬¬ ⊥, ((→ ∧ ∉ PROP

実際にある記号列が PROP に属するということを示すのは容易である。それには、定義 2 に従ってその記号列を分解していけばよい (この分解方法については後で示す)。

2.2 帰納的定義

上で見た帰納的定義 (inductive definition, definition by induction) は今後しばしば使用される。ここで、このタイプの定義を詳しく検討しよう。いま人間の集合を考え、それを H で表すことにする。いま「… は… の先祖である」という述語（関係語）を考えて、この関係によって H の上の部分集合を定義したい、と想定する。ある人物、例えばマイルス・ディヴィスをとり、次のように定義することにより、彼の先祖全体の集合を定義できる（「x の先祖」というとき、 x 自身も先祖に含まれることにする）。

A = {x|x is Miles Davis or x is an ancester of Miles Davis }

このとき、もし「… は… の先祖である」という関係を使わないでこの集合を定義しようとすればどのようにすればよいか。一つのやり方は、

A = { x| x は MD であるか、 x は MD の母であるか、 x は MD の父であるか、 x は MD の母の母であるか、 … }

のようにすることである。しかし、このやり方では一定の世代までの先祖しか含まない集合しか定義できないであろう。この困難をクリアする一つの方法は、この集合を

1. MD は A のメンバーである、

2. A のメンバーの父と母は A のメンバーである、

3. 上の１と２を満足するもの以外にはいかなるものも A のメンバーではない。

のように定義することである。これが帰納的定義である。１は帰納的定義の base と呼ばれる。これによって、樹形図のように広がっていく先祖の root にあるメンバーが A のメンバーであることが確定される。２は、 inductive clause と呼ばれ、これによって root にあるメンバーの父や母が A のメンバーであることが確定され、さらにそうやって確定されたメンバーの父・母が A のメンバーであることが確定され、そうして次々とメンバーが確定されていくのである。最後に３（closure clause と呼ばれる）が、 MD とその先祖以外のいかなるものも A のメンバーではないことを保証する。こうした帰納的定義は、与えられた集合に基づいて、その集合の部分集合を定義する方法である。（実際、定義された A は H の部分集合である。）どうして A を定義するのに、基盤となる集合 H が必要なのか。それを見るには、 inductive clause に注目する必要がある。 2 は、あるメンバー a が与えられたとき、その父がやはりメンバーであることを規定している。これは、

a ∈ A ならば f(a) ∈ A

という形になっている（この場合 f は、「… の父」という関数である）。一般に inductive clause は「a_{1}, a_{2}, … a_{n} ∈ B ⇒ f(a_{1}, … a_{n}) ∈ B」という構造を持っている。このとき使われる関数の定義域と値域が予め定まっていなくてはならない（さもなければ、この関数はきちんと定義されていないことになる）。したがって基盤となる集合が必要なのである。

帰納的定義の直観的なイメージは、「成長してゆく」集合である。ベースのメンバーから始まって次々とメンバーが構成されていくのである。この定義によって構成される集合は、もちろん無限集合であってよい。しかし、その集合のメンバーが一つ取り出されたならば、そのメンバーは１と２の有限回の適用によってその集合のメンバーであることが確かめられる、ということに注意しよう。

subsubsection*補足

しかし、上のような 1,2,3 によってちゃんと集合が定義されたことになるのか、それによってただ一つの集合が定まったことになるのか。これは、集合論の道具をつかって証明することができる。ここでは、上の例に則して、その証明の概略を見ておこう。そのために次のようなものを考える。

C = { X| X は人間の集合 H の部分集合であり、 MD は X のメンバーであり、 MD の母は X のメンバーであり、 MD の父は X のメンバーであり、かつ y が X のメンバーであるならば、 y の父と母も X のメンバーである }

C が集合の集合であることに注意しよう。 C のメンバーは集合である。このとき ⋂ C を考える。この ⋂ C は C のメンバーである集合を全部集めてそれらの積をとったものである。この集合が帰納的定義の 1,2,3 を満足し、かつそれらを満足する唯一の集合であることを証明しよう。

補題 1 ⋂ C は 1,2,3 を満足し、他のいかなる集合も 1,2,3 を満足することはない。

[証明]⋂ C が１を満足することは、 MD が C のメンバーであるどの集合にも属することと、 ⋂ C の定義とから帰結する。

次に ⋂ C が２を満足することを証明する。それには背理法を使う。背理法の仮定として ⋂ C が２を満足しないと仮定する。すなわち、ある人間 a が存在し、 a は ⋂ C のメンバーであるが、 a の父（あるいは母）が ⋂ C には属さない、と仮定する。このとき、 a は ⋂ C のメンバーなのだから、 a は C のメンバーであるすべての集合に属していなくてはならない。その上で、 C のメンバーである集合で a の父をメンバーとはしない集合が少なくとも一つは存在しなくてはならない。しかしこのことは、 C の定義における「y が X のメンバーであるならば、 y の父と母も X のメンバーである」と矛盾する。よって ⋂ C が２を満足することが証明された。

最後に ⋂ C が３を満足することを示す。背理法の仮定として、 ⋂ C が 3 を満たさないとする、すなわち、

ある集合 A が存在し、 MD がそのメンバー（元）であり、かつ A のメンバーの父と母も A のメンバーであり、かつ A は ⋂ C の真部分集合である、と仮定する。

このとき、 ⋂ の定義により、 A ∉ C である。（なぜなら、 C の定義により、 C は、上の 1,2 を満足する集合をすべて集めてできた集合である。そのような C のメンバーである集合を B_{1}, B_{2}, …, B_{n} とすると（実際は有限個でなく、無限個でよいが、話を簡単にするために n 個とする）、 ⋂ C = B_{1} ∩ B_{2} ∩ … ∩ B_{n} である。 A は ⋂ C の真部分集合なのだから、 A は B_{1}, B_{2}, …, B_{n} のいずれでもないことは明らかである。よって A は C のメンバーではない。）ところが、 C は、その定義により 1,2 を満たす集合をすべて含んでいなくてはならない。 A は 1,2 を満たすのだから、 A ∈ C でなくてはならない。これは矛盾である。 [証明終]

帰納的定義についてもう少し

帰納的定義はいろいろなところで使われる。例えば、有理数の集合 Q の上で正の整数 Z^{+} を帰納的に次のように定義できる。

1. Base : 1 ∈ Z^{+} 2. Inductive Clause : すべての x ∈ Z^{+} について、 x + 1 ∈ Z^{+}

3. 他のいかなるものも Z^{+} のうちにはない

問題 1 （Q の部分集合として）整数 Z を帰納的に定義せよ。

すでに見たように、論理学においては、形式言語や式などを定義するのに帰納的定義が頻繁に使用される。これは、有限の素材と有限個の規則から無限個のものの集まりを定義できる、という点で有用である。一方、帰納的に定義されたものについては、帰納法による証明が使える。これは、論理学において様々な事柄を証明するのに使われる大変強力な方法である。

帰納法による証明は次のような方法である。いま、無限個のものの集まり A(例えば命題論理の式からなる集合 A) について、そのすべてが P という性質をもつことを証明したい、としよう。その場合、まず Base になるものについて（命題記号について）、それらが P という性質をもつことを証明する。次に、あるものが性質 P をもつときに、それに Induction Clause の規則を適用してできるものも性質 P をもつということ（性質 P が Induction Clause によって保存されること）を示す。こうして、集合 A のすべてのものが性質 P をもつことが示されたことになる。（この最後の事柄が言えるのは、集合 A が Base と Inductive clause を満たす最小の集合だから、ということに注意。）

このような帰納法による証明の例を見ておこう。

例 2 どの命題も偶数個の括弧をもつ

証明

(i) どの原子命題も 0 個の括弧をもち、 0 は偶数である。

(ii) φ と ψ がそれぞれ 2n 個と 2m 個の括弧をもつとしよう。そのとき (φ ∘ ψ) は 2(n + m + 1) 個の括弧をもつ。

(iii) φ が 2n 個の括弧をもつとしよう。そのとき (¬φ) は 2(n + 1) 個の括弧をもつ。

この例はあまりおもしろい例ではないが、命題がある性質をもつことを示すための典型的な証明の例になっている。すべての命題がある一定の性質をもつことを示すには、定義 2 の帰納的定義にそった形で証明を行なえばよい。つまり、最初に原子命題が問題の性質をもつことを示し、その上で部分がその性質をもつとき、それらの部分を合成してできた命題もその性質をもつ、ということを示せばよいのである。実際、そのことは次のような定理としてきちんと示すことができる。

定理 1 A をある性質とする。もし

(i) φ が原子命題のとき、 A(φ) であり、かつ A(⊥) であり、

(ii) A(φ) かつ A(ψ) ならば、 A((φ ∘ ψ)) であり、

(iii) A(φ) ならば、 A((¬φ)) であるならば、

すべての φ ∈PROP について A(φ) が成り立つ。

証明

Y = {φ ∈PROP |A(φ)} としよう。このとき Y は定義２の（１） — （３）を満足する。 PROP は（１） — （３）を満足する最小の集合だったのだから、 PROP⊆ Y である。すなわち、すべての φ ∈ PROP について A(φ) が成り立つ。

定義 3 φ が ψ の部分式 subformula であるのは、

(i) φ = ψ であるか、

(ii) ψ = (ψ_{1} ∘ ψ_{2}) であり、 φ が ψ_{1} の部分式であるか、 ψ_{2} の部分式であるか、

(iii) ψ = (¬ψ_{1}) で φ が ψ_{1} の部分式である場合である。

例 3 P は ((Q ∨ (¬P)) → R) の部分式であり、 (Q →⊥) は (((P ∨ (Q ∧ R)) ↔ (Q →⊥)) の部分式である。問題 2 命題 ((¬P) ∧ (Q ∨ R)) の部分式をすべて示せ。

定義 4 構成樹 construction tree, parsing tree 命題 φ の構成樹は以下によって定義される。

(i) φ が原子命題の場合、ただ φ と書く。

(ii) φ が (φ_{1} ∘ φ_{2}) のとき、

(φ_{1} ∘ φ_{2})

φ_{1} φ_{2}

(iii) φ が (¬φ_{1}) のとき、

(¬φ_{1})

φ_{1}

例 4 命題 (P → (⊥ ∨(¬Q))) の構成樹

(P → (⊥ ∨(¬Q)))

P (⊥ ∨(¬Q))

⊥ (¬Q)

Q

問題 3 次の命題の構成樹を構成せよ。

(¬P → (Q ∨ (P ↔ R))) ∧ (¬(¬Q)))

注意：補助記号として括弧を使うのは、命題の多義性を排除するためである。例えば (¬P ∨ Q) のような記号列は (¬(P ∨ Q)) なのか ((¬P) ∨ Q) なのかが区別できないからである。しかし、これまでのように、結合子ひとつにつき必ず括弧を一組つけるというやり方は繁雑である。そこで、一応公式的にはこれまで通り括弧を使うことにしておきながら、実際に命題を扱う場合には若干の省略を行うことにする。それは具体的には、

（１）否定記号が、その直後にある最少の命題にかかるときには括弧はつけない（２）一番外側の括弧は省略するということである。それゆえ、 (¬P ∨ Q) はつねに ((¬P) ∨ Q) を表わし、 (¬(P ∨ Q)) を表わしたい場合には括弧をつけるという風になる。また一番外側の括弧を省略してよいのだから、 (¬P ∨ Q) は ¬P ∨ Q と書いてかまわないのである。

2.3 意味論

命題論理を解釈するには次の二つのことを行う必要がある。

1. 原子命題を解釈する

2. 論理結合子の意味を規定する

このうち、（１）については、われわれは原子命題が単純に真か偽であると仮定する。原子命題は、例えば「雪は白い」、「6 − 3 = 2」、「太郎は貧しい」のようなものであり、これらは明らかに真であったり偽であったりする。したがって、これらが真か偽かのいずれかであるとすることはごく自然であろう。とはいえ、これらの原子命題が単純に真か偽かであるということは、古典命題論理を解釈するためにわれわれが受け入れた前提ないし仮定であることに注意する必要がある。

では、原子命題から論理結合子を用いて構成される複合的な命題の真偽はどのようになるのであろうか。言い換えれば、 φ と ψ の真偽が与えられたら、そこから (φ ∘ ψ) と (¬φ) の真偽をどのように確定すればよいのだろうか。以下では、その方法を真理表 truth table を用いて示す。その際、真 true と偽 false の代わりに、 T と F を使うことにし、それらを真理値（真偽値）と呼ぶことにする。

2.3.1 真理表

最初に否定の真理表を考えてみよう。

\begin{matrix}φ & ¬φ \\ T & F \\ F & T \end{matrix}

この表が否定記号 ¬ の解釈を与えていることに注意してほしい。「… でない」という否定詞は、もとの（否定詞を含まない）命題の真偽を逆転させるのである。

次は連言と選言の真理表である。

\begin{matrix}φ & ψ & φ ∧ ψ & φ ∨ ψ \\ T & T & T & T \\ T & F & F & T \\ F & T & F & T \\ F & F & F & F \end{matrix}

連言と選言は、否定と違って二つの命題を結合するから、それらを解釈するには二つの部分（つまり φ と ψ）の解釈を与えてやらなくてはならない。したがって、それらの真偽の可能な組み合わせが全部で 4 通りあるから、真理表の行数も 4 行になる。

さて、連言命題 φ ∧ ψ と選言命題 φ ∨ ψ の φ と ψ をそれぞれ連言肢、選言肢と呼ぶことにしよう。この真理表による解釈では、連言命題は両方の連言肢がともに T のときにのみ、 T という値をとり、それ以外の場合には F になることがわかる。また選言命題は選言肢のどちらか一方が T であれば、全体は T になるということがわかる。これらの解釈は日常の「そして」や「または」の使い方をかなりうまく反映していることがわかる。（排反的選言と非排反的選言の違い）

最後に条件法と双条件法の真理表を見ておこう。

\begin{matrix}φ & ψ & φ → ψ & φ ↔ ψ \\ T & T & T & T \\ T & F & F & F \\ F & T & T & F \\ F & F & T & T \end{matrix}

ここで問題となるのは、条件法の解釈である。 φ → ψ の φ 部分を条件法の前件、 ψ 部分を後件と呼ぶことにすれば、奇妙に思われるのは前件が偽の場合である。「もし晴天ならば、運動会が行われる」の前件が偽であったならば、この文全体の真偽はどのように考えればよいのだろうか。真偽いずれでもない、というのも一つの考え方である。しかし、真理値の間隙を認めることは事態をいたずらに複雑にしてしまう。あくまで二値性を維持することには大きな利点がある。この点と、さらに他の結合子との解釈の衝突を避けることを考慮するならば、条件法は上のように定めるしかないのである。（この点については、含意のパラドクスを含めて後にもう一度検討する。）

さて、各論理結合子の意味を以上のように規定したならば、これに基づいて様々な命題の真理表を構成することができる。例えば、

¬(P ∨ Q) → (P ∧ ¬Q)

の真理表は次のように構成すればよい。

\begin{matrix}P & Q & (P ∨ Q) & ¬(P ∨ Q) & P ∧ ¬Q & ¬(P ∨ Q) → (P ∧ ¬Q) \\ T & T & T & F & F & T \\ T & F & T & F & T & T \\ F & T & T & F & F & T \\ F & F & F & T & F & F \end{matrix}

問題 4 次の命題の真理表を構成せよ。

1. P → (Q ∨ ¬P)

2. (¬P ∧ Q) → R

3. ¬(P ∧ Q) ↔ (¬P ∨ ¬Q)

定義 5 真理表のすべての行で値 T をとる命題をトートロジーという。

問題 5 以下の命題のどれがトートロジーかを真理表の方法でチェックせよ。

1. (¬P ∨ Q) ↔ (P → Q)

2. P → ((Q → R) → ((P → Q) → (P → R)

3. (P → (Q → R)) → ((P ∧ Q) → R)

4. P ∧ ¬P

5. ⊥↔ (P ∧ ¬P)

定義 6 (i) Γ を命題の集合とする。このとき、 Γ ⊧ φ であるのは、 Γ のすべての命題が T となる行で φ が T となるときであって、そのときにかぎる。

(ii) ⊧ φ は φ がトートロジーであることを表わす。

Γ ⊧ φ が成り立つとき、 φ は Γ の意味論的帰結 semantic consequence であるという。

問題 6 次を示せ。

1. P ∨ Q ⊧ Q ∨ P

2. P → Q, P ⊧ Q

2.4 付値関数

以上の真理表に基づいて行ってきたことを、真理表を用いずに表現しようとすればどのようになるだろうか。それを行う一つの方法は付値関数 valuation を用いる方法である。

定義 7 v を命題の集合から真理値への写像とする。すなわち、 v:PROP→ {T, F } とする。このとき、以下を満たす v は付値関数である。

1. v(¬φ) = T iff v(φ) = F

2. v(φ ∧ ψ) = T iff v(φ) = T and v(ψ) = T

3. v(φ ∨ ψ) = T iff v(φ) = T or v(ψ) = F

4. v(φ → ψ) = F iff v(φ) = T and v(ψ) = F

5. v(φ ↔ ψ) = T iff v(φ) = v(ψ)

6. v(⊥) = F

いま述べた付値関数は、ちょうど真理表による論理結合子の意味の規定に相当している。ところで、実際には原子命題（命題記号）のそれぞれに値が割り振られていなくてはならない。具体例で言えば、 ¬(P → (Q∨R) の値、すなわち v(¬(P → (Q∨R))) を計算するには、 P, Q, R の値が前もって与えられていなくてはならない。この、原子命題への値の割り当てを < P, Q, R >=< T, F, F > と書くことにする。これは、もちろん v(P) = T, v(Q) = F, v(R) = F を意味する。こうした割り当て assignment が与えられれば、われわれは付値関数の定義に基づいて v(¬(P → (Q∨R))) を計算することができる。この値を計算するにはまず v(P → (Q ∨ R) を計算すればよい。そして v(P → (Q ∨ R)) の値を計算するには v(P) と v(Q ∨ R) の値を計算すればよいのである。

問題 7 < P, Q, R >=< T, F, F > のもとで v(¬(P → (Q ∨ R))) の値を計算せよ。

さて、もちろん P, Q, R に対する値の割り当ては < P, Q, R >=< T, F, F > だけではない。すでに見たように、可能な値の割り当ては、全部で８通りある。ある与えられた命題についての真理表は、そうした可能な値の割り当てをすべて表の左側にリストし、その命題がそれぞれの割り当ての下でどのような値をとるかを、一挙に示した形になっている。その点で真理表は付値関数の方法よりも便利であるが、付値関数の方式で考えた方が都合のよい場合もある。以下ではしばらく付値関数の方法で話を進める。

このとき、こうした付値関数 v を使うならば、先のトートロジーと妥当性の定義は次のように言い換えることができる。

定義 8 (i) φ がトートロジーであるのは、（原子命題への値の）すべての割り当てのもとで v(φ) = T となるときである。

(ii) Γ ⊧ φ となるのは、すべての ψ ∈ Γ について v(ψ) = T ならば、 v(φ) = T ということが、あらゆる v について成り立つときであって、そのときにかぎる。

問題 8 α, β, γ を命題論理 (PL) の式とするとき、以下の主張が成り立つことを付値関数を使って示せ。

(1) α, β ⊧ (α ∧ β)

(2) (α ∧ β) ⊧ α および (α ∧ β) ⊧ β

(3) α ⊧ (α ∨ β) および β ⊧ (α ∨ β)

(4) (α ∨ β), (α → γ), (β → γ) ⊧ γ

(5) (α → β), α ⊧ β

(6) α, (¬α) ⊧ β

(7) ¬(β → α) ⊧ (α → β)

(8) (α ∨ β), ¬β ⊧ α

次に、 PL の体系においてもっと一般的に成り立つことを示そう。例えば φ, ψ を PL の式とし、 Γ, Δ を PL の式の集合とするとき次のものが成立する。

もし Γ ⊧ φ かつ Δ ⊧ ψ ならば、 Γ ∪ Δ ⊧ (φ ∧ ψ)

これは次のようにして証明すればよい。 v を Γ ∪ Δ に含まれる式すべてに T を割り当てるような付値関数だとする。そのとき v(φ) = T かつ v(ψ) = T である。したがって付値関数の定義 (2) により v((φ ∧ ψ)) = T となり、定義 8 の (ii) により上の関係が成り立つ。

問題 9 φ, ψ を PL の式、 Γ, Δ を PL の式の集合とするとき、以下のものが成立することを示しなさい。

(1) もし φ ∈ Γ ならば、 Γ ⊧ φ

(2) もし Γ ⊧ (φ ∧ ψ) ならば、 Γ ⊧ φ かつ Γ ⊧ ψ

(3) もし Γ ∪ {φ} ⊧ ψ ならば、 Γ ⊧ (φ → ψ)

(4) もし Γ ∪ {φ} ⊧ ψ かつ Δ ∪ {φ} ⊧ ¬ψ ならば、 Γ ∪ Δ ⊧ ¬φ

(5) もし Γ ⊧ φ かつ Γ ⊆ Δ ならば、 Δ ⊧ φ

2.5 Unique Readability

付値関数や真理表を操作してみてわかるのは、原子命題という PL の基礎にあるものに一定の値が割り当てられれば、そこから複合的な命題の値がいつでも算出できる、ということである。言い換えれば、原子命題の割り当てが決まれば、そこから無数にある PL の式（命題）すべてに一義的に値を割り当てることができる、ということである。しかし、これは本当なのか。いま原子命題への値の割り当てを一つ選択したとしよう。この割り当ての下で、同じ複合命題に二つの異なる値が割り当てられることはないのだろうか。原子命題へのどの割り当てもちゃんと複合命題に値を割り振るのだろうか。

いま問題になっているのは、上で定義した付値関数が原子命題へのどのような割り当ての下でもうまく働くのか（あらゆる割り当てのもとで働く関数が存在するのか）、もしそのような関数が存在するとしてそれが複数だということはないのか（唯一性）、ということである。いずれも肯定的に答えることができるが、ここでは唯一性をまず証明する。

定理 2 原子命題への値のある割り当て v が与えられたとする。その割り当ての下での複合命題への値の割り当てを v_{1}, v_{2} とする。このとき、 PL のあらゆる命題 φ に関して、 v_{1}(φ) = v_{2}(φ) である。

[証明] 帰納法によって証明すればよい。 α を原子命題とする。このとき複合命題への値の割り当て v_{1}, v_{2} は、ともに原子命題への値の割り当て v に基づいているのだから、原子命題への値の割り当てはどちらの場合も同じになる。すなわち、 v_{1}(α) = v_{2}(α) = v(α) である。 Induction step としては、 ¬ の場合だけ考える。他は同様である。示すべきことは、任意の命題 φ について、 v_{1}(φ) = v_{2}(φ) という仮定の下で、 v_{1}((¬φ)) = v_{2}((¬φ)) となる、ということである。いま、 v_{1}(φ) = v_{2}(φ) = T とする。そのとき、 v_{1}((¬φ)) = v_{2}((¬φ)) = F となり、 v_{1}(φ) = v_{2}(φ) = F とすると、 v_{1}((¬φ)) = v_{2}((¬φ)) = T となって、 v_{1}((¬φ)) = v_{2}((¬φ)) が示された。

上の定理で示されたのは、原子命題への値の割り当て v が与えられたとき、その割り当てに基づいて複合命題の真理値を算出できたならば、その答えは一義に定まる、ということである。次の問題は、原子命題への値のどのような割り当てが与えられても、必ず複合命題の値を算出できるか、そのような付値関数 v が本当に存在するのか、ということである^{1}。これに対する答えは、存在する、というものであるが、その証明はこの講義の範囲を超えているので、ここではその周辺的な事情を観察するだけにしたい。

そのような関数が存在すると言えなくなるのはどのような場合か、を考えよう。例えば、定義 9 命題の集合 PROP*は、次の性質をもつ最小の集合 X である。

1付値関数の存在（原子命題への割り当てが任意に与えられたとき、そこからあらゆる複合命題の値を算出する付値関数が存在するか）と唯一性の問題は、樹形図のレベルで考えることもできる。それは、どんな複合命題が与えられても、原子命題で終わる分解図が存在するか、その分解図（樹形図）は一通りに定まるか、という形になる。

1. P, Q, R, … ∈ X, ⊥∈ X

2. φ, ψ ∈ X ならば、 φ ∧ ψ, φ ∨ ψ, φ → ψ, φ ↔ ψ ∈ X

3. φ ∈ X ならば、 ¬φ ∈ X

のような定義を考える。本来の命題の定義との違いは、カッコがないことである。この場合、例えば a, b を原子命題とするとき、 ¬a ∧ b は PROP*のメンバーである。だが、もしこの（複合）命題が一つの真理値をもつとすると矛盾が生じてしまう。 v(b) = F としよう。この複合命題への値の割り当てを v′ とする。この v′ はもちろん原子命題への値の割り当て v をもとに考えられているのだから、 v′(b) = F である。ここで、もし ¬a ∧ b を ¬(a ∧ b) と解するならば、 v′(¬a ∧ b) = T になる。しかし、この命題を (¬a) ∧ b と解するならば、 v′(¬a ∧ b) = F になるが、これは矛盾である。よってこの命題に単一の値を割り当てる付値関数は存在しない。

このことからわかるように、与えられた原子命題への割り当てから、複合命題の値を計算する付値関数が存在すると言うためには、原子命題からの複合命題の構成が一意に定まっているということ、すなわち複合命題が多義的ではなく、一通りにしか分解できない (uniquly readable) ということをまずは示す必要がある。それを示す定理は以下のものである。

定理 3 Unique Readability Theorem:命題論理のあらゆる命題 φ について、高々以下の一つが成立する。

1. φ は原子命題である。

2. φ は、ある命題 α に対して (¬α) という形をもつ。

3. φ は、ある命題 α, β に対して (α ∧ β) という形をもつ。

4. φ は、ある命題 α, β に対して (α ∨ β) という形をもつ。

5. φ は、ある命題 α, β に対して (α → β) という形をもつ。

ただし、 3–5 は、 PL の命題 α, β の高々一つのペアについて成り立ち、 2 は高々一つの PL の命題 α について成り立つ。

再帰的定義

上でみたことから、先の付値関数の定義が、原子命題への真理値の任意の割り当てに対して、ただ一つの関数を定義していることがわかる（すべてを証明したわけではないが）。もう一度繰り返せば、それは次のような関数の定義である。

定義 10 v を原子命題への真理値の割り当てとする。そのとき、付値関数 v^{∗} は、以下を満足する、複合命題への真理値の割り当て関数である。

1. すべての原子命題 φ に対して、 v^{∗}(φ) = v(φ)

2. v^{∗}(¬φ) = T iff v^{∗}(φ) = F

3. v^{∗}(φ ∧ ψ) = T iff v^{∗}(φ) = T and v^{∗}(ψ) = T

4. v^{∗}(φ ∨ ψ) = T iff v^{∗}(φ) = T or v^{∗}(ψ) = F

5. v^{∗}(φ → ψ) = F iff v^{∗}(φ) = T and v^{∗}(ψ) = F

6. v^{∗}(φ ↔ ψ) = T iff v^{∗}(φ) = v^{∗}(ψ)

7. v^{∗}(⊥) = F

ここで再帰的定義の詳しい説明は述べられないが、一般に、帰納的定義によって定義されたものの集まりを定義域として一つの関数を定義する方法が再帰的な定義である。そのような方法によって定義された関数の例を以下に示す。定義 11 PL の命題の rank は、以下の条件を満足する関数である。

1. すべての原子命題 φ に対して、 r(φ) = 1

2. (¬φ) という形のすべての命題に対して、 r((¬φ)) = r(φ) + 1

3. すべての命題 (φ ∧ ψ) に対して、 r((φ ∧ ψ)) = Max(r(φ), r(ψ)) + 1

4. すべての命題 (φ ∨ ψ) に対して、 r((φ ∨ ψ)) = Max(r(φ), r(ψ)) + 1

5. すべての命題 (φ → ψ) に対して、 r((φ → ψ)) = Max(r(φ), r(ψ)) + 1

2.6 置換

ところで、 P ∨¬P がトートロジーだとすると、その P に例えば (P → Q) を代入してできる命題 (P → Q)∨¬(P → Q) もまたトートロジーになる。これは、 P ∨ ¬P において P の中味が何であるかとは無関係にその形式だけでトートロジーであることが決っているという点に注意すれば、後者がトートロジーになることは明らかである。したがって、次のものが成り立つ。（以下で F (A_{1}, A_{2}, …, A_{n}) という表記を使う。これは、 F (A_{1}, A_{2}, …, A_{n}) という命題に登場する命題記号が A_{1}, A_{2}, …, A_{n} からなることを意味する。このとき、 F (X_{1}, …, X_{n}) によって、 F (A_{1}, A_{2}, …, A_{n}) における A_{1}, A_{2}, …, A_{n} の出現箇所を同時に X_{1}, …, X_{n} によって置き換えてできる命題を意味する。例えば、 F (A, B) = (A → B)∨¬B であるならば、 F (P → Q, P ∨R) = (((P → Q) → (P ∨R))∨¬(P ∨R)) となる。）

定理 4 ( 置換定理その１ ) F (P), X, Y をそれぞれ命題とする。また、 v を付値関数とする。このとき、もし v(X) = x(Y) ならば、 v(F (X)) = v(F (Y)) である。

[証明] もし

v(X) = x(Y) ならば、 v(F (X)) = v(F (Y)) （任意の X, Y, v について） (*)

が成り立つならば、そのとき F (P) は good である、と言うことにする。帰納法によって、すべての命題が good であることを示せばよい。

まず、 F (P) が原子命題（命題記号）だとする。この場合、二つのケースがある。つまり、 F (P) = P かまたは F (P) ≠ P である。もし前者ならば、 F (P) = P だから、 F (X) = X かつ F (Y) = Y であり、 (*) はトリヴィアルに成り立つ。もし後者ならば、 F (X) = F (Y) = F (P) であり、再び (*) はトリヴィアルに成り立つ。

G(P) と H(P) とがどちらも good であり、 F (P) = (G(P) ∘ H(P)) であると仮定する。（∘ は二項結合子のどれかとする。）このとき、もし v(X) = v(Y) ならば、

v(F (X)) = v(G(X) ∘ H(X))  (F の定義による）
= v(G(X)) ∘ v(H(X)) (付値関数の定義）
= v(G(Y)) ∘ v(H(Y)) (帰納法の仮定）
= v(G(X) ∘ H(X))  (付値関数の定義）
= v(F (Y))  (F の定義）

したがって、 F (P) は good であることがわかった。否定については省略。 Q.E.D.

定理 5 ( 置換定理その２ ) もし X ↔ Y がトートロジーならば、 F (X) ↔ F (Y) もトートロジーである。

[証明] X ↔ Y がトートロジーで、 v を任意の付値関数とする。示すべきことは、 v(F (X) ↔ F (Y)) = T である。 X ↔ Y がトートロジーなのだから、 v(X ↔ Y) = T であり、付値関数の定義により、 v(X) = v(Y) となる。このとき、前の定理により v(F (X)) = v(F (Y)) である。ふたたび付値関数の定義により、 v(F (X) ↔ F (Y)) = T である。 Q.E.D.

問題 10 付値 valuation の種類はいくつあるか。

問題 11 原子命題が 2 つのとき、異なる真理関数は全部でいくつあるか。

2.7 命題論理のいくつかの性質

定理 6 以下の命題はトートロジーである。

((A ∨ B) ∨ C) ↔ (A ∨ (B ∨ C)

((A ∧ B) ∧ C) ↔ (A ∧ (B ∧ C)  結合則 associativity

A ∨ B ↔ B ∨ A

A ∧ B ↔ B ∧ A  交換則 commutativity

A ∨ (B ∧ C) ↔ (A ∨ B) ∧ (A ∨ C)

A ∧ (B ∨ C) ↔ (A ∧ B) ∨ (A ∧ C) 分配則

¬(A ∨ B) ↔ ¬A ∧ ¬B

¬(A ∧ B) ↔ ¬A ∨ ¬B  ド・モルガンの法則

A ∨ A ↔ A

A ∧ A ↔ A  べき等 idempotency
¬¬A ↔ A  二重否定 double negation

問題 12 以下を示せ。

\begin{matrix}(a) & ⊧ (φ ↔ ψ) ↔ (φ → ψ) ∧ (ψ → φ) \\ (b) & ⊧ (φ → ψ) ↔ (¬φ ∨ ψ) \\ (c) & ⊧ φ ∨ ψ ↔ (¬φ → ψ) \\ (d) & ⊧ φ ∨ ψ ↔ ¬(¬φ ∧ ¬ψ) \\ (e) & ⊧ φ ∧ ψ ↔ ¬(¬φ ∨ ¬ψ) \\ (f) & ⊧ ¬φ ↔ (φ →⊥) \\ (g) & ⊧⊥↔ φ ∧ ¬φ \end{matrix}

上の問題によれば、どの論理結合子も {∨, ¬}, {∧, ¬}, {→, ¬}, {→, ⊥} で表現することができる。（論理的に同値なものは等しいと考えることにすれば。）

しかしながら、シェファーの棒を使えば、ただ一つの結合子ですべての真理関数を表現することができる。シェファーの棒は次のような結合子である。

\begin{matrix}φ & ψ & φ | ψ \\ T & T & F \\ T & F & F \\ F & T & F \\ F & F & T \end{matrix}

これまで扱ってきた結合子は、否定を除けば、すべて二つの命題に作用する結合子であった。否定のように一つの命題に作用する結合子を一項結合子（一項真理関数）、その他の二つの命題に作用する結合子を二項結合子と呼ぶことにすれば、いつでも n-項結合子（n-項真理関数）を新たに考えることができる。けれども、これまで考えてきた以上の新たな結合子を導入する必要はない。というのも、次の定理が成立するからである。

定理 7 もし f が n-項結合子ならば、 n 個の命題 P_{1}, …, P_{n} をもつ命題 φ が存在し、 P_{1}, …, P_{n} のすべての付値 v について v(φ) = f(v(P_{1}), …, v(P_{n})) となる。

この事実を命題論理の関数的完全性とよぶ。証明の概略は、以下のようになる。まず、次のような 3 項結合子を考えてみよう。

\begin{matrix}x & y & z & f(x, y, z) \\ T & T & T & F \\ T & T & F & F \\ T & F & T & T \\ T & F & F & F \\ F & T & T & T \\ F & T & F & T \\ F & F & T & F \\ F & F & F & F \end{matrix}

かりにこのような真理関数が与えられたら、これと同値な真理関数を ¬, ∧, ∨ の三つを使って容易に構成することができる。それには、まずこの関数が値 T をとる行を見つけ出せばよい。例えば三行目は x が T 、 y が T 、 z が F であるから、 (x ∧ y ∧ ¬z) という関数を構成する。この関数は上の三行目でのみ値 T をとる関数である。このような関数を五行目と六行目のそれぞれについて構成し、それらを ∨ で結合するならば、

(x ∧ y ∧ ¬z) ∨ (¬x ∧ y ∧ z) ∨ (¬x ∧ y ∧ ¬z)

という関数ができるが、これはちょうど上の f(x, y, z) と同値な関数になっている。

いま示したのは、あくまでも具体的な例に基づくものであって、ちゃんとした証明ではない。きちんと証明するには、 n （命題変数の数）についての帰納法を使えばよい。帰納法のベースは容易だが、次の段階では若干の技巧を必要とする。

3 命題論理の証明論

これまで、命題論理を真理表に基づくものとして扱ってきた。これは、言い換えれば、命題論理を意味論的な観点から見てきた、ということである。しかし、意味論的な観点が論理を見る唯一の観点ではない。以下では、与えられた論証が妥当であることを示すための（真理表に基づく方法とは異なる）もうひとつの方法を提示する。それは、自然演繹と呼ばれる推論規則の体系に基づく方法である。具体的には、論証が与えられたとき、その論証の前提から、それらの推論規則を使って結論が証明できるとき、その推論は妥当だ、と言われる。

3.1 自然演繹

自然演繹では最終的に 9 個の規則（命題論理に限れば）を導入することになるが、ここでは、そのような規則のうち、比較的簡単な規則を三つ導入し、それらを使って証明の書き表し方や証明の構成法をざっと見ておきたい。

まず、規則によって論証の正しさを示すということがどういうことなのかを考えてみよう。与えられた論証が妥当であることを示すためのもっとも簡単な方法は何か。ひとつは、妥当な論証の形式をすべて枚挙してしまうことであろう。その上で、与えられた論証が枚挙された形式に一致するかどうかをチェックしてやればよい。だが、それは実際には不可能である。妥当な論証形式は無数にあるからである。それゆえ、妥当なものを単純に枚挙するのではない、何か別の方法を考え出さなくてはならない。

ひとつの手掛かりとして、自分たちが足し算をどう学んだか、を思い出してみよう。足し算を学び始めた当初は、正しい足し算をしたり、誤った足し算をしたり、誰でも試行錯誤を繰り返すはずである。しかし、いったん足し算を学んでしまえば、なおミスを犯すことがあるにしても、どれが正しい足し算でどれが誤りかは問題なく指摘できるはずである。では、われわれはどうやって足し算の正誤を判別しているのだろうか。もちろん、正しい足し算をすべて枚挙することによってではない。足し算を学ぶときに、われわれは個々の正しい足し算を次々と暗記したのではなく、おそらくは足し算の規則を理解するようになったはずである。無数の足し算を覚える代わりに、それらをすべて扱えるような有限個の規則とその使い方を学んだのではないだろうか。

ここでも同様な方針を採用したい。つまり、足し算の正誤を判定するのに足し算の規則が使われるのをまねて、論証の妥当性を示すのに何らかの規則が使えるようにしよう、というわけである。では、それはどのような規則なのだろうか。

もっとも代表的な規則は、

\frac{A A → B}{B} (→ −除去則)

という形の規則である。これは、

A と A → B の形の二つの式が与えられたとき、 B を導いてよい

ということを示している。ここではさらに二つの規則、 ∧-導入則と ∧-除去則を導入しておこう。

\frac{A B}{A ∧ B} (∧ − 導入則)

\frac{A ∧ B}{A} , \frac{A ∧ B}{B} (∧ − 除去則)

∧-導入則が述べているのは、

前もって A と B が導かれているならば、それより後の段階で A ∧ B を導いてよい

ということである。また二つの ∧-除去則は、

A ∧ B が前もって成り立っているならば、それより後の段階で A を導いてもよいし、 B を導いてもよい

ことを示している。

規則を上のような図式で書いたのは、どういう形の式からどういう形の式を導いてよいか、を理解しやすくするためである。しかし、ここで採用する証明の表記法では、証明は、式を縦に一列に並べたものである。それゆえ、 →-除去則

\frac{A A → B}{B}

は、実際の証明では、

a_{1}, … a_{n}  (i) A
⋮
b_{1}, … b_{n}  (j) A → B
⋮
a_{1}, … a_{n}, b_{1}, … b_{n} (k) B  i,j. →-除去

のように書かれるのである。これは、証明の (i) 行目で A が導かれ、 (j) 行目で A → B が導かれている場合、 (i),(j) より後の (k) 行目で B を導いてよいということを示している。そして、 (k) 行目の右端の欄には、この (k) 行目の出自、つまりこの行が (i) および (j) 行目から →-除去則によって導かれたことが記されている。（一番左端の a_{1}, … a_{n} は、 (i) 行目を導くにあたって使った前提の番号を表わしているが、これについては後に触れるまで無視してかまわない。）

これらの規則がどうして論証の妥当性を示すための規則として認められるのか。あるいは、これらが先に述べた推論規則としての条件を本当に満たしているかどうか。こうした疑問については後で規則ごとに検討することにして、ここではまず、これらの規則から証明がどのように作られるのかを実際に見ておこう。

3.2 証明の書き方

すでに見てきたように、与えられた論証が妥当であることを示すには、

その論証の前提から、結論が推論規則に従って導かれること

を示せばよい。それを示すことが論証を証明することなのである。具体的に考えてみよう。いま、次のような論証が与えられたとしよう。

P, P → Q, P → R ⊢ Q ∧ R

これは、 P と P → Q と P → R の三つの式を前提とし、 Q ∧ R を結論とする論証である。これは妥当な論証である。なぜなら、これら三つの前提から Q ∧ R が導かれるという証明を構成することができるからである。われわれが採用する方式に従って、まずその証明を書いてみよう。

\begin{matrix}1 & (1) & P & 前提 \\ 2 & (2) & P → Q & 前提 \\ 3 & (3) & P → R & 前提 \\ 1,2 & (4) & Q & 1,2.→-除去 \\ 1,3 & (5) & R & 1,3.→-除去 \\ 1,2,3 & (6) & Q ∧ R & 4,5.∧-導入 \end{matrix}

これを見ればわかるように、証明は番号を付した式の列として表現される。ただしこの場合、その番号は、左から二列目の（１）から（６）という数字で表わされている。（一番左の数字はしばらくの間無視することにしよう。）番号の次には式そのものが書かれ、最後に、その式の身分、つまりそれが前提であるのか、あるいは他の前提から推論規則の適用によって導かれたものであるのかが記される。それぞれの行を順に確認してゆこう。

i. 上の証明の場合、（１）行目から（３）行目までは前提である。それを示すのに、それらの行の右端には「前

提」という語が書かれている。もちろん、これらの前提は、元の論証の前提に対応していなくてはならない。 ii. （４）行目の式 Q は、（１）と（２）の二つの行にある式に、 →-除去則という規則を適用して導かれた式で

ある。そして（４）がそのようにして導かれた式であることは、その行の一番右に‘ 1,2 →-除去’と書いてあることからわかるようになっている。

iii. 同様に、（５）は、（１）と（３）の式に →-除去を適用して導かれた式である。 iv. （６）行目は、（４）と（５）で導かれた式に ∧-導入を適用して導かれた式である。そして、この（６）は、

この証明の最後の式であり、結論と呼ばれる。

ここに示された証明と上で示された →-除去という推論規則との関係はもはや明らかであろう。証明の（４）行目と（５）行目では、いずれもこの推論規則が用いられている。例えば、（４）行目で行った推論は、元の推論規則の図式に当てはめてみると、次のようになる。

\frac{P P → Q}{Q}

この図式は、直線によって上下に分けられている。直線より上の式は、この推論の前提であり、下は結論である。この場合、この推論の前提は P と P → Q であり、これらはいずれも上の証明においても前提である。一方、（５）行目では、次のような推論が行われている。

\frac{P P → R}{R}

この推論は、前提のひとつが（２）ではなく（３）の P → R であることを除けば、（４）行目と同様である。最後に（６）行目では、

\frac{Q R}{Q ∧ R}

という推論が行われている。この推論の前提である Q と R は、最初から前提として置かれた式ではない。 Q も R もともに、それ以前の式から推論規則を使って導かれた式である。このことからわかるように、証明の中で推論規則を適用する場合は、その規則によって導かれる式よりも上にある式を、いずれもその推論の前提として利用することができる。言い換えれば、証明の各行にある式は、

a. 前提であるか

b. その式よりも上の行にある（複数または単数の）式に、推論規則を適用して導かれた式であるか

のいずれかである。

例題 1 次を証明しなさい。

P → (Q ∧ R), P, S ⊢ R ∧ S

\begin{matrix}1 & (1) & P → (Q ∧ R) & 前提 \\ 2 & (2) & P & 前提 \\ 3 & (3) & S & 前提 \\ 1,2 & (4) & Q ∧ R & 1,2 →-除去 \\ 1,2, & (5) & R & 3,4 ∧-除去 \\ 1,2,3 & (6) & R ∧ S & 3,5.∧-導入 \end{matrix}

3.3 前提への依存

ここで、上の証明の一番左に書き込まれている数字を説明しよう。この数字は、各行の式がどの前提に依存しているかを示している。ただし、（１）のような前提である式については、それが依存するのは自分自身だとする。つまり、（１）は自分自身、つまり（１）に依存する。同様に、（２）もそれ自身が前提であるから、やはり（２）に依存する。一方、（４）は前提（１）と前提（２）から推論規則を介して導かれたのであるから、（４）が依存している前提は（１）と（２）である。（５）は（３）と（４）から導かれた。そのうち、（３）は前提であるから、（５）がこれに依存していることに間違いはない。では（４）の方はどうか。（４）は確かにこの証明の前提ではない。しかし、（４）は（１）と（２）に依存しており、（５）は（４）に依存しているのであるから、（５）は間接的に（１）、（２）に依存している、と言えるであろう。ここでは間接的な依存も依存のうちに含めることとする。それゆえ、（５）行目は（１） — （３）のすべてに依存する。

したがって、以上をまとめると、各行の式がどの前提に依存するかを示す数字の記入方法は、次のようになる。

a. 問題の式が前提ならば、その行番号をそのまま記入する。 b. 問題の式がそれ以前の行にある式から推論規則によって導かれている場合、推論規則の前提となった式に記

入されている数字をすべて記入する。

問題 1 次を証明しなさい。

1. P, P → Q ⊢ Q

2. (P ∧ (P → Q)) ⊢ Q

3. P → Q, Q → R, P ⊢ R

4. P ∧ (Q ∧ R), R → S ⊢ P ∧ S

3.4 → 導入規則

この節からは、自然演繹の規則の全体を、すでに出てきたものを含めてひとつづつ検討してゆく。次の規則は → 導入規則（以下、 →-I）である。これは、図式で表わすと次のようになる。

[A] ; ⋮ ; B ; \overline{A → B}

この規則の直観的な内容を考えてみよう。この規則が述べているのは、「A を仮定し、その仮定のもとで B が導かれるとき、（A という仮定なしに） A → B を導くことができる」ということである。これだけでは何が言われているのかよくわからないかもしれない。しかし、実際にはこの規則はひどく単純なことを述べた規則である。例えば、次のような論証を考えてみよう。

A, B, C ⊢ D

この論証が妥当だとしよう。ということは、 A, B, C という三つの前提がすべて真のとき、 D は必ず真でなくてはならない。言い換えれば、 A, B, C 三つの前提が成り立つという条件のもとで、 D は必ず成り立つ。このとき、例えば前提のひとつ C を取り去り、代わりに、結論 D を C → D で置き換えたとしても、状況に何ら実質的な変化はない。つまり、上の論証を、

A, B ⊢ C → D

のように書き換えても、その妥当性に変わりはない。というのも、第二の形の論証は、 A, B 二つの前提が成り立つという条件のもとで、もし C が成り立つならば、 D が成り立つ、ということを述べているにすぎないからである。第一の論証で、結論が成り立つための前提であったもののひとつが、第二の論証では、結論の中に条件文の形で入り込んだのである。このような書き換えが許されるのは、 A → B という形の条件文を「A が成り立つならば、 B が成り立つ」と読むことができるからである。

ところで、このような書き換えが許されるならば、上の論証で前提がひとつしかない場合を考えてみればよい。そのような場合には、この論証の書き換えは、規則 →-I が述べていることとまったく同じになる。

ここで規則 →-I を、証明の中に入れ込んだ形で書いておこう。

1  (1)  …  …
⋮  ⋮  ⋮
…  (m)  A  前提
⋮  ⋮  ⋮
m,… (n)  B  …
x–m (n+1) A → B m-n,→-I

証明は（１）行目から書き始めなくてはならないから、この図の証明も（１）行目から始まっている。いま、（m）行目で A という式を仮定（前提）した。それは、（m）行目の式の身分が‘前提’となっていることからもわかるだろう。その仮定のもとで、（n）行目で B という式が導かれた。（この式がどの前提からどういう規則によって導かれたかは、場合ごとに異なるから、式の身分のところは‘ … ’にしてある。）このとき、規則 →-I によって、次の行、つまり（n+1）行目で、 A → B を導くことができる。

ここでは、次の点に注意するのが重要である。（n）行目で B を導いたが、それは、あくまでも（m）行目の A という仮定のもとでのことである。だから、（n）行目の式が依存する前提の欄には、 m という数字が必ず書き込まれていなくてはならない。（もちろん、その他に依存する前提があれば、それらの行番号も書き込む必要がある。）しかし、（n+1）行目では、つまり規則 →-I が使われた行では、依存する前提から m が除かれなくてはならない。（上の図では、それを表わすのに–m、つまりマイナス m という書き方をした。）というのも、最初は単独で仮定された A が、規則 →-I を使うことによって、仮定から取り除かれ、結論 A → B の前件に組み込まれたからである。 →-I のような規則の適用によって、ある式を仮定から取り除くことを、通常「仮定を落とす」と言う。仮定を落とす規則は、今後 →-I 以外にもいくつか登場するであろう。

これまで述べてきたのは、推論規則 →-I の内容的な意味と、この規則を証明の中で書き表す際のいくつかの注意である。しかし、実際にこの規則を証明の中で使うには、見方を変えた方がよいかもしれない。「A と仮定して、その仮定のもとで B が導かれるとき、その仮定を落として A → B を導いてよい」というのが、この規則の内容であった。だが、これをむしろ逆に考えた方が、規則としては使いやすくなる。すなわち、

A → B を導くには、まず A と仮定して、その仮定のもとで B を導いてやればよい。

と理解するのである。その上で、 →-I 規則を使って、 A → B を導けばよい。これを実際の証明で確認してみよう。

例題 2 次を証明せよ。

P → Q, Q → R ⊢ P → R

\begin{matrix}1 & (1) & P → Q & 前提 \\ 2 & (2) & Q → R & 前提 \\ 3 & (3) & P & 前提 \\ 1,3 & (4) & Q & 1,3 →-E \\ 1,2,3 & (5) & R & 2,4 →-E \\ 1,2 & (6) & P → R & 3-5 →-I \end{matrix}

前にも述べたように、（６）行目の、依存する前提の欄（一番左の欄）では３という数字が落ちていることに注意してほしい。つまり（３）行目の P は、（６）行目では前提ではなくなって、代わりに P → R という条件式の前件に組み込まれている。最初に問題として出された論証では、前提は（１）と（２）のみであったから、（３）が残ったままでは、この証明は元の論証には対応しない。（３）が落とされて初めて、この証明は元の論証の証明になる。そのことが、（６）行目の一番左の欄に示されているのである。

問題 2 1. P ⊢ (P → Q) → Q 2. P → (Q → R), Q ⊢ P → R

3. (P ∨ Q) → ((P ∨ Q) → R) ⊢ (P ∨ Q) → R

例題 3 次を証明せよ。

P → S, Q → (S → R) ⊢ P → (Q → R)

→-E を二回にわたって適用すれば、証明は次のようになる。

1  (1) P → S  Ass
2  (2) Q → (S → R) Ass
3  (3) P  H
4  (4) Q  H
1,3  (5) S  1,3 →-E
2,4  (6) S → R  2,4 →-E
1,2,3,4 (7) R  5,6 →-E
1,2,3 (8) Q → R  4–7, →-I
1,2  (9) P → (Q → R) 3–8, →-I

→-E のように仮定を立て、後にその仮定をキャンセルするような規則を複数回使用する場合は、次のことに注意する必要があるだろう。すなわち、

証明の中に複数の仮定がある場合、仮定のキャンセルは、仮定が導入された順序とは逆の順序で行われなければならない。つまり、後から導入された仮定を先にキャンセルしなくてはならない

のである。このルールさえ守られていれば、仮定を必ず証明の最初で導入する必要はないのであって、必要になったときに導入すればよいのである。

3.5 ∨-導入則

\frac{φ}{φ ∨ ψ} , \frac{ψ}{φ ∨ ψ}

この規則も、 ∧-E の場合と同様に、二つで一組の規則であり、場合に応じていずれを用いてもよい。そして、特に注意して欲しいのは、例えば左側の規則で言えば、 ψ はどんな式でもよいということである。極端なことを言えば、「1+1=2」が前提として与えられたなら、そこからこの規則を使って、「(1+1=2) または (日本の首都は東京である)」を導いてもよい。こんな推論は、正しいかもしれないが、ひどく奇妙だし、なんだか日本語の「または」の使い方とはかけ離れているのではないか、という疑問が生ずるかもしれない。確かに、日本語で「または」を使う場合、「巨人が優勝するか、または阪神が優勝するだろう」のように、「または」の両側には互いに何らかの関係のある文や共通の話題に関する文が現れるのが普通である。しかし、それは日本語の中で「または」が実際に使われる際の使われ方の問題であって、「または」という語の論理的な働きに関わる問題ではない。

例題 4 次を証明しなさい。

P ∧ Q ⊢ P ∨ Q

\begin{matrix}1 & (1) & P ∧ Q & Ass \\ 1 & (2) & P & 1.∧-E \\ 1 & (3) & P ∨ Q & 2. ∨-I \end{matrix}

問題 3 次を証明しなさい。

1. P, P → (Q ∧ R) ⊢ R ∨ S

2. ¬P → R ⊢ (¬P ∧ Q) → (R ∨ (¬Q ∧ P))

3.6 ∨-除去則

∨-除去則は、これまでの規則よりもいくらかやっかいである。というのも、「カルナップが演壇に立ったか、またはポパーが演壇に立った」という主張からは、連言の場合のような確定した情報を引き出すことはできないからである。「または」を含む主張は、「または」の両辺にある主張（これら選言肢という）のどちらが確定的に成り立っているかを言えない場合に使われる。したがって、選言肢のいずれか一方を導くような規則はあきらめなくてはならない。

しかし、「または」の主張は、選言肢のどちらが成り立っているのかを確定はできないが、どちらかが成り立っている、ということは確かである。つまり、 A ∨ B から、 A という情報や B という情報を単独で引き出すことはできないが、 A か B のどちらかは必ず成り立つはずである。それゆえ、選言肢 A,B のどちらが成り立つにしても、そこからある同一の情報 C を引き出せるならば、 A ∨ B と合わせて単独で C を結論できるはずである。

これを具体的な事例で考えてみよう。例えば、プロ野球のペナントレースで巨人と阪神が優勝争いをしており、他のチームには優勝の可能性がなくなったとしよう。このとき、「巨人が優勝するか、または阪神が優勝する」という選言文は確かに成り立つ。一方、あなたが前もって巨人の優勝と阪神の優勝にそれぞれお金を賭けていたとする。したがって「巨人が優勝すれば、賞金をもらえる」も「阪神が優勝すれば、賞金がもらえる」もいずれも成り立っている。このとき、これらの前提がすべて成り立つとすれば、「賞金がもらえる」ことは確定した、といってよいだろう。（胴元が夜逃げする、というような余計なことはここでは考慮の外においておく。）このような推論を規則の形で表示すると、次のようになる。

\frac{φ ∨ ψ φ → ξ ψ → ξ}{ξ}

この規則の前提には φ ∨ ψ が含まれているが、結論の ξ （「クシィ」と読む）には ∨ は含まれていない。その意味で、この規則を ∨-除去則と見ることができるだろう。この規則を実際に証明の中で使うには次の点に留意しなくてはならない。

1. いま、証明すべき論証の前提に φ ∨ ψ という形の式が含まれており、その前提から結論 ξ を導かねばならない、とする。

2. このとき、最初になすべきことは、 φ → ξ を導くことである。（つまり、 φ を仮定し、そのもとで ξ を導く。） 3. もし、この導出がうまくいったならば、次になすべきことは、 ψ → ξ を導くことである。（これも同様に ψ を

仮定し、その仮定のもとで ξ を導くのである。）

4. 以上がなされたならば、 ∨-E 規則を用いて、結論 ξ を導けばよい。

これが、 ∨-E 規則を使う場合の基本方針である。この方針に従って、次の例題をやってみよう。

例題 5 次を証明しなさい。

P ∨ Q ⊢ Q ∨ P
1 (1) P ∨ Q  Ass
2 (2) P  H
2 (3) Q ∨ P  2. ∨-I
(4) P → (Q ∨ P) 2-3. →-I
5 (5) Q  H
5 (6) Q ∨ P  5.∨-I
(7) Q → (Q ∨ P) 5-6.→-I
1 (8) Q ∨ P  1,4,7.∨-E

問題 4 次を証明しなさい。

1. P ∨ Q ⊢ (P ∨ R) ∨ (Q ∨ R)

2. P → R, Q → R, R → S ⊢ (P ∨ Q) → S

演習問題 1 次を証明せよ。

1. P → Q ⊢ P → (Q ∨ R)

2. P ∧ (Q ∨ R) ⊢ (P ∧ Q) ∨ (P ∧ R)

3. (P ∧ Q) ∨ (P ∧ R) ⊢ P ∧ (Q ∨ R)

（演習問題の最後の二つは、分配法則と呼ばれるものである。分配法則には、これら以外に、 P ∨ (Q ∧ R) ⊢ (P ∨ Q) ∧ (P ∨ R) と (P ∨ Q) ∧ (P ∨ R) ⊢ P ∨ (Q ∧ R) という形のものもある。これらも証明してみてほしい。）

3.7 否定

矛盾を表わす命題として ⊥ が使えるならば、 ¬-導入則は次のように書き表すことができる。

[φ]
⋮
⊥
¬φ

この規則が語っているのは、ある式 φ を仮定して論証を進めた結果、矛盾が導かれたならば、最初に仮定した式の否定 ¬φ を導いてよい、ということである。したがって、逆に ¬A という式を証明したい場合には、まず A を仮定し、そこから矛盾を導く、という基本方針を立てることができる。

しかしながら、どういう場合に矛盾（つまり ⊥）を導いたことになるのかは、この規則だけからはわからない。「⊥ は何か A ∧ ¬A のようなもの」ということはすでにわかっているにしても、それはあくまでも記号 ⊥ の説明であって、規則として明示されているわけではない。それゆえ、 ¬-導入則だけが単独で与えられても使いものにはならないのであり、この規則は次に示す ¬-除去則といっしょになって初めて意味をもつのである。

\frac{φ ¬φ}{⊥}

この ¬-除去則は、ある式とその否定の両方が導かれるとき、矛盾を表わす式 ⊥ を導入してよい、ということを示している。これは、 ⊥ が A ∧ ¬A のような式の省略だという説明の言い換えにほぼ等しい。というのも、二つの式 A、 B が導かれるならば、 ∧-I 規則によって直ちに A ∧ B を導けるからである。この場合は、二つの式が A と ¬A という形をしているにすぎない。

この規則によって ⊥ の導き方が与えられたのだから、再び ¬-導入則に戻って、証明の基本方針を確認しておこう。 ¬-導入則からわかることは、例えば ¬A を証明するには、最初に A を仮定し、そこから ⊥ を導けばよい、ということである。そして ⊥ を導くには、何か適当な式 B とその否定 ¬B とを導出すればよい。具体例でこのことを確認しよう。

例題 6 次を証明しなさい。

P → Q, ¬Q ⊢ ¬P
1  (1) P → Q Ass
2  (2) ¬Q  Ass
3  (3) P  H
1,3 (4) Q  1,3. →-E
1,2,3 (5) ⊥  2,4. ¬-E
1,2 (6) ¬P  3-5. ¬-I

¬-I 規則では、最後のステップで、付け加えた仮定の否定が導かれるが、その際に、付け加えた仮定自体は落とされることに注意してほしい。 ¬-I 規則が述べているのは、「A を仮定すると矛盾が生ずる」場合には、 ¬ A を主張してかまわない、ということである。したがって、 A という仮定から矛盾が生ずるプロセス全体が ¬A 自体に含まれると考えられる。この意味で negA は仮定 A には依存していない。

例題 7 次を証明しなさい。

⊢ ¬(P ∧ ¬P)

1 (1) P ∧ ¬P  H
1 (2) P  1. ∧-E
1 (3) ¬P  1. ∧-E
1 (4) ⊥  2,3. ¬-E
(5) ¬(P ∧ ¬P) 1-4. ¬-I

問題 5 次を証明しなさい。

1. ⊢ P → ¬¬P

2. ¬(P ∨ Q) ⊢ ¬(P ∧ Q)

3. ⊢ (P → Q) → (¬Q → ¬P)

前節では、否定に関する導入則と除去則を見てきた。しかしながら、これらの規則に問題がないわけではない。問題があるように思われるのは、これらの規則がいずれも矛盾記号を用いて書かれているからである。その一方で、矛盾は否定記号をもちいて説明されている。したがって、連言や選言の場合のように、その記号に関わる推論規則がその記号の論理的な働きや論理的な意味を示すものであるならば、否定に関する二つの規則は、そうした働きや意味を示すものではなく、矛盾との相互関係を示しているにすぎない。

実際、否定については、その導入則と除去則だけでは不十分であって、さらに別の規則が必要だ、と考えられてきた。しかしながら、では、別の規則としてどのような規則を付け加えるべきか、という点については全面的な意見の一致があるわけではない。この節では、まずひとつの提案を示し、次節においてもうひとつの規則を提示することにしたい。

3.8 二重否定除去規則

新たに付け加えられる規則は、次のような二重否定除去規則（以下、 DN 規則と表示する）である。

\frac{¬¬φ}{φ}

この規則の実際の書き表わし方は、

a_{1}, …, a_{n} (i) ¬¬φ
⋮
a_{1}, …, a_{n} (j) φ  i. ¬¬-E

となる。この規則は一見すると、 P ∨ ¬P の証明には無関係に見えるかもしれないが、そうではない。実際にそれが証明できることを示しておこう。

例題 8 次を証明しなさい。

⊢ P ∨ ¬P
1 (1) ¬(P ∨ ¬P) H
2 (2) P  H
2 (3) P ∨ ¬P  2.∨-I
1,2 (4) ⊥  1,3. ¬-E
1 (5) ¬P  2-4. ¬-I
1 (6) P ∨ ¬P  5.∨-I
1 (7) ⊥  1,6. ¬-E
(8) ¬¬(P ∨ ¬P) 1-7.¬-I
(9) ¬(P ∨ ¬P) 8.DN-E

例題 9

P ∧ ¬P ⊢ Q
1 (1) P ∧ ¬P  Ass
2 (2) ¬Q  H
1,2 (3) (P ∧ ¬P) ∧ ¬Q 1,2.∧-I
1,2 (4) P ∧ ¬P  3. ∧-E
1,2 (5) P  4. ∧-E
1,2 (6) ¬P  4.∧-E
1,2 (7) ⊥  5,6. ¬-E
1 (8) ¬¬Q  2-7.¬-I
1 (9) Q  8.DN-E

4 健全性と完全性

4.1 命題論理の完全性と無矛盾性

最初に ⊢ について注意をひとこと。 A ⊢ B は前提 A から結論 B を証明できる、ということを意味していた。しかし、「証明できる」というのは必ずしも絶対的な概念ではない。つまり、「証明できる」ということは、何らかの体系において「証明できる」ということであり、われわれの場合はその体系として自然演繹（の規則の体系）を採用してきたのであった。したがって、自然演繹の体系を N で表わすことにすれば、 A ⊢ B を A ⊢_{N} B と書くのがより正確な書き方である。

さて、われわれはこれまでに論証の正しさについて二つの規準を手に入れた。一つは、 X ⊧ A であり、もう一つは X ⊢_{N} A である。（X はここで前提のあつまりとする。）はたしてこれらの規準の間に齟齬はないのか。つまり、一方の規準によれば正しいとされる論証がもう一方の規準では妥当ではない、というような事態は生じないのか。そのような事態が生じないということを保証するのが命題論理の完全性定理である。通常

⊢_{N} A ⇒⊧ A

を命題論理の健全性 soundness と言い、

⊧ A ⇒⊢_{N}

を命題論理の完全性 completeness と言う。つまり完全性とは「ある命題がトートロジーならば、その命題は前提なしに証明できる」ということを意味する。また場合によっては、健全性と完全性をまとめて

⊧ A ⇔⊢_{N} A

を（広い意味での）完全性ということもある。（ここで ⇒, ⇔ はメタ言語の記号であることに注意。また、健全性も完全性も前提のない場合について述べているが、前提のあるケースは前提のないケースに帰着させられることを思い出してほしい。以下では、めんどうなので ⊢_{N} の N はいちいち表示しないことにする。）

以下では、 Kalmar の方法によって^{2}健全性と完全性を証明しよう。

定理 8 健全性 ⊢_{N} A ⇒⊧ A つまり、 A が（自然演繹の）定理ならば、 A はトートロジーである

2Kleene,S.C. Mathematical Logic pp.46-49.

[証明] 健全性定理は前提の一切ない形で述べられているが、それは X ⊢ A の X が空であるような特殊なケースであるから、以下では一般的に X ⊢ A から X ⊧ A が言えることを示す。われわれの体系では一般に証明は有限個の命題から構成されている。したがって、健全性の証明は証明の各行の長さ n についての帰納法による。

自然演繹の体系でなされる最も単純な証明は

1 (1) A Ass.

である。これは、 A ⊢ A の証明にほかならない。帰納法のベースは、それゆえ、この一行の証明が意味論的に妥当であることを示すことからなる。これを示すのは簡単である。前提 A について v(A) = T となるような任意の v を考える。このとき明らかに結論 A について v(A) = T である。したがって A ⊧ A。これで、帰納法のベースが示された。

次に、すでに与えられた行から次の行に進む場合を考える。この移行を可能にするのは各規則であるから、それらの規則が前提の真理を保存することを示せばよい。例えば、 ∧-導入の規則は A, B ⊢ A ∧ B のように書き表せる。このとき、 ∧-導入の規則を適用する以前に、その証明では単独の A と単独の B とが前もって導かれていなくてはならない。いま、そこまでの証明ができているとしよう。そのとき、 A を導くのに使われた前提全部を X とする。（X′ は、 A が書かれる行番号の左側にある数字で指示されるすべての前提からなる。）同様に B を導くのに使われた前提全部を X′ とする。このとき、帰納法の仮定として

X ⊢ A ⇒ X ⊧ A
X′ ⊢ B ⇒ X′ ⊧ B

がすでに成り立っているとする。その上で X′′ = X ∪ X′ としよう。このとき φ ∈ X′′ であるようなすべての φ について v(φ) = T となるような付値 v を任意にとると、 v(A) = T かつ v(B) = T であるから、 v(A ∧ B) = T となる。したがって X′′ ⊧ A ∧ B が示された。

次に、 →-I のケースを考えよう。 A から B を導くプロセスで使われた（A 以外の）前提を X で表すことにする。このとき、帰納法の仮定により、 X ∪ {A} ⊧ B が成立しているとしよう。すると、 X ⊧ A → B が成立する。このことは問題 9 の (3) によりすでに示されている。

さて、以上のような証明を他の規則についても行うことができるから、よって命題論理の自然演繹体系の健全性が証明された。

（証明終）

問題 13 ∨-除去規則が健全であることを確かめよ。

以上から、命題論理の自然演繹体系の健全性、すなわち ⊢ A ⇒⊧ A が証明できた。この定理の対偶をとってみよう。それは

|̸= A ⇒⊬ A

となる。ということは、トートロジーでない命題は証明できないということである。そして、 A ∧ ¬A という矛盾を表わす命題は確かにトートロジーではないから、この命題は自然演繹の体系では証明できないことになる。したがって、健全性定理から命題論理の無矛盾性 consistency が導かれる。

定理 9 命題論理の自然演繹体系は無矛盾である。

もちろん、他の形の矛盾命題はないか、という疑問が生じるかもしれない。しかし、上で示されたのは少なくとも A ∧ ¬A という形の命題は証明できないということである。ところで、もしある体系が矛盾しているならば、どのような命題でも導くことができるから、一つでも導けない命題があることが示されれば、それでその体系の無矛盾性が示されたことになる。

問題 14 もしある体系が矛盾しているならば、どのような命題でも導くことができることを示せ。

4.2 命題論理の完全性

命題論理の完全性を証明するには、以下の四つの補題が必要になる。以下は完全な証明というよりも、具体例でもって内容をイラストレートするようなものであり、証明の概略にすぎないことに注意してほしい。

補題 2 四つの結合子に関する真理表のそれぞれにおいて、どの行に対してもそれに対応する証明がある。

例えば、 → に関する真理表を考えてみよう。

\begin{matrix}A & B & A → B \\ T & T & T \\ T & F & F \\ F & T & T \\ F & F & T \end{matrix}

この表の四つの行のそれぞれに対応して、次のような証明関係が成り立つ。

\begin{aligned}A, & B & ⊢ & A → B & (1) \\ A, & ¬B & ⊢ & ¬(A → B) & (2) \\ ¬A, & B & ⊢ & A → B & (3) \\ ¬A, & ¬B & ⊢ & A → B & (4) \end{aligned}

[証明] 例えば、 (1) と (2) は次のように証明される。

\begin{matrix}1 & (1) & A & Ass. \\ 2 & (2) & B & Ass. \\ 1,2 & (3) & A → B & 1-2.→-I \end{matrix} 1 (1)  A  Ass.

2 (2)  ¬B  Ass.
3 (3) A → B  H.
1,3 (4)  B  1,3.→-E
1,2,3 (5)  ⊥  2,4.¬-E
1,2 (6) ¬(A → B) 3-5.¬-I

このような証明を 14 の行すべてについて行えばよい。

補題 3 任意の命題 E についての真理表を考えよう。 E は命題記号 P_{1}, P_{2}, … P_{n} を含むとする。このとき、その真理表の 2^{n} 行のそれぞれについて、それに対応する証明関係が成り立つ。

[証明] まず例で考えてみよう。 E として P → ((Q ∨ R) → (R → ¬P)) という命題を取り上げる。この命題の真理表を作ってみると、その三行目は次のようになる。

\begin{matrix}P & Q & R & P → ((Q ∨ R) → (R → ¬P)) \\ T & F & T & F \end{matrix}

これに対応して、次のような証明関係が成立する。

P, ¬Q, R ⊢ ¬(P → ((Q ∨ R) → (R → ¬P)))

これが一般に成り立つことは、次のようにして示すことができる。真理表のこの行においてこの命題の真理値を計算するには、まず第一にこの命題の部分命題の真理値を計算しなくてはならない。例えば Q ∨ R の真理値を計算するには、この行の Q と R の値がそれぞれ F, T であるから、あとは ∨ の真理表から Q ∨ R の値を割り出せばよい。いまの場合その値は T になる。したがって、補題 1 により、

P, ¬Q, R ⊢ Q ∨ R

という証明関係が成り立つ。一般に、 E の各部分命題 D に関して、 P, ¬Q, R ⊢ D または P, ¬Q, R ⊢ ¬D のいずれかが、 D の真理値に応じて成立する。この手順を繰り返していくことによって、最終的に P, ¬Q, R ⊢ ¬(P → ((Q ∨ R) → (R → ¬P))) という証明関係を得ることができるのである。

補題 4 もし補題 2 の命題 E が妥当（トートロジー）ならば、 P_{1} ∨ ¬P_{1}, …, P_{n} ∨ ¬P_{n} ⊢ E が成立する。

[証明] いま n = 2 の場合を例にとって考察する。補題 2 により

\begin{aligned}P_{1}, & P_{2} & ⊢ & E \\ P_{1}, & ¬P_{2} & ⊢ & E \\ ¬P_{1}, & P_{2} & ⊢ & E \\ ¬P_{1}, & ¬P_{2} & ⊢ & E \end{aligned}

が成り立つ。 ∨-E の規則を適用することによって、

\begin{aligned}P_{1}, & P_{2} ∨ ¬P_{2} & ⊢ & E \\ ¬P_{1}, & P_{2} ∨ ¬P_{2} & ⊢ & E \end{aligned}

が得られる。これにさらに ∨-E の規則を適用すれば、

P_{1} ∨ ¬P_{1}, P_{2} ∨ ¬P_{2} ⊢ E

が得られる。

補題 5 任意の命題 A について、 ⊢ A ∨ ¬A

[証明] すでにやったことから明らか。

定理 10 どの妥当な命題（どのトートロジー） E も証明可能である。すなわち、 ⊧ E ⇒⊢ E

[証明] 補題 3 と補題 4 による。