パズルで学ぶ論理学
久木田

水生

i

目次

前書き

iii

第1章 序

1

1.1

論理学の目的 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.2

論理学の意義 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

1.2.1

数学基礎論 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

1.2.2

推論の機械化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

1.2.3

分析哲学 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

集合論の用語解説 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

1.3

第 2 章 論理的推論とは何か

23

2.1

Who’s Who . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

2.2

命題論理の体系 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

2.2.1

命題論理の言語 L . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

2.2.2

L に対する意味論 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

2.2.3

論理的推論の特徴づけ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

38

2.2.4

トートロジー . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39

第 3 章 形式的体系における導出

41

3.1

Bullet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42

3.2

命題論理の形式的体系 ND . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

45

第 4 章 形式的体系と解釈，健全性，完全性

51

4.1

Measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

51

4.2

ND の健全性と完全性

55. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

iii

前書き

「人間は理性的な動物である」というのは良く耳にする言葉である．しかし，「理性的である」というのはどういうことか，と問われれば，これはなかなか答えるのが難しい．ところで「理性」という言葉は，英語では「reason」にあたる．一方「reason」には動詞で「推論する，推理する」という意味もある．従ってこの定義は「人間とは推論する動物である」とも言い換えられる．この定義が過不足なく人間を定義できているとは言えないが，推論し，判断し，それによって知識を拡張していく能力は，人間の持つ重要な性質の一つであることは確かである．ソクラテスは，人間の本質は「正しく考える」能力にあり，そしてこの能力を最大限発揮するよう努力することが人間にとっての徳（正しい行い）だと述べている．
しかしながら人間以外の生物もある意味では推論を行ない，それに基づいて判断を下している．例えば多くの動物は他の個体が自分の肉親であるかどうかを判断している．また彼らはある対象が食べられるもの
かどうか，自分たちにとって脅威となるものかどうかを常に判断している．高等な生物になれば期待や予測といった高度な判断も下すことが出来る．それでは人間と彼らの違いはどこにあるのだろうか．一つの答え
は，動物は何らかの快をもたらす対象（食物や配偶者）を得ることや，苦をもたらす対象（毒物や捕食者）を避けることを目的としてのみ，推論を働かせるのに対して，人間は推論し答を見つけること自体を純粋に楽しんでいる，ということである．
古代ギリシャの数学者・物理学者アルキメデスは湯船に浸かっていて，王冠の金の純度を求める方法を思いついたとき，裸のまま表に飛び出し，「ユリイカ（分かったぞ）！」と叫びながら町中を走り回ったと伝えられている．同じく古代ギリシャの哲学者デモクリトスは「ペルシャの王国を手に入れるよりも，一つの原因を発見したい」と述べたという．20 世紀のイギリスの数学者ハーディは，友人である哲学者バートラン
ド・ラッセルに向かって数学的証明の魅力について語り，「もし君が 5 分後に死ぬということを私が数学的に証明できたとしたら，君を失う悲しみは大きいだろうが，しかしそれを証明できたことの喜びが勝るだ
ろう」と述べている．
これらのエピソードが示すように，推論によってある問題に対する解を発見するという行為は，人間にとって説明の付かない大きな喜びをもたらすようである．これはおそらく他の動物には見られない特徴だろう（もっとも漱石の「猫」のようにあれこれと思弁を巡らせて楽しんでいる動物がいないとは断言できないが）．だとすると人間は「考えることを楽しむ動物」として特徴付けられるかもしれない．
人間が推理，推論を楽しんでいるということは，古くから世界中で「謎解き」，「パズル」という文化が発達しているという事実によっても示されている．ギリシャの伝説に登場するスフィンクスの謎は最も古典的な謎解きの一つである．スフィンクスはオイディプスに「朝は四本足，昼は二本足，夜は三本足になるものは何だ？」と問いかける．オイディプスはこれに対して「それは人間だ．生まれたばかりのときは両手両足

iv

前書き

を使って這い，成長すると二本の足で歩き，年老いては杖をついて歩く」と答える．このような謎解きというモチーフはあらゆる文化の伝説や神話に登場する．
今日でも書店に行けばパズルの本や雑誌のコーナーがあり，多種多様なパズルが並べられている．また推
理小説の類もパズルの一種といって差し支えないだろう．パズルとは何かを正確に説明することは難しいが，それでもパズルにはいくつかのパターンがあることは確かである．一つのパターンは，まず何らかの謎が与えられ，推論によってその謎を解き明かす，というパターンである．もう一つは，何らかの目標が与えられ，決められた手続きを繰り返すことでその目標に到達する，というパターンである．パズルのパターン
はこれだけではないが，ここで取扱いたいのはこの種のパズルである．そこでとりあえず，パズルとは「与えられた問題に対し，定められた規則・手続きに従って解を導き出すゲーム」としておこう．
パズルの中には実際的な関心から生まれたものもあるが，単なる知的な好奇心から，あるいは単なる娯楽として生まれたものの方が圧倒的に多い．最近は「右脳を鍛える」とか「脳年齢が若返る」といった効果がうたわれているのもしばしば目にする．しかしパズルが愛好される第一の理由は，それが私たちに快感をもたらしてくれるからである．そしてパズルの面白さは，困難な問題について推理をめぐらせ，そして自らの力で答を導き出すことのうちにある．答が自明でなければないほど

言いかえればその答えにたどり着くまでにつみかねる推理（手続き）の道のりが長ければ長いほどその答えにたどり着いたときのユ

リイカの喜びは大きい．そしてただそのユリイカの喜びを得るためだけに，実に多くの人間がパズルに熱中している．
ところで，パズルの解き方には大きくいって二種類ある．一つは論理的な推論によって解に到る方法，もう一つはそのような推論によらず，直観的なひらめきによって解に到る方法である．たとえば「数独」（「ナンバープレイス」），「虫食い算」などは純粋に論理的な推論によって解くことが出来る．これに対して「なぞなぞ」，「マッチ棒パズル」，「タングラム」（いくつかの木片または紙片を組み合わせて求められた形を作るパズル），「知恵の輪」などを解くには直観によるひらめきが必要とされる．前者のタイプのパズルを解くことは，論理的に推論することの楽しみを知り，かつ論理的に思考するということがどういうことかを知る役に立つ．またそういったパズルの様々な性質について考えることは論理学という学問の本質を理解する役に立
つ．また後者のようなパズルを解くことは論理的な思考と直観的な思考の違いを理解するのに有用である．
そこでこの講義では様々なパズルを解き，その本質について考えることを通じて論理学を学ぶことを目指したい．そして何よりも受講生諸君には，困難な問題を自ら解決することの楽しさを味わってもらいたい．

久木田 水生minao_kukita@hotmail.com
http://www.geocities.jp/minao_kukita/

1

第1章 序

1.1

論理学の目的

哲学や数学を専門にしているのでなければ，多くの人にとって論理学（特に記号論理学，形式論理学）というものに触れる機会は皆無に等しい．そこで実際に論理学を学ぶ前に，論理学がどのようなものであるかを大雑把に紹介しておこうと思う．他のあらゆる学問と同様，「記号論理学とは何か」という質問に正確な答を与えることは難しいのであるが，何の予備知識もなくはじめるより，少なくとも論理学が何を主題とし，何を目指しているのかを知っておくことは有益である．
論理学の主題を理解してもらうためには例を挙げるのが一番手っ取り早い．最初に一つ問題を出そう1 ．
問題 1.1.1. クル島の住人はすべて，武士と盗人と商人の三つグループに分けられる．また一人の住人が複数のグループに属することはない．武士は常に本当のことを言い，盗人は常に嘘をつく．商人は本当のことを言うこともあるし嘘をつくこともある．いずれにせよクル島の住民の口にすることは必ず本当か嘘かのどちらかである．クル島の住人の一人である次郎吉が「私は盗人です」と言った．次郎吉はどのグループに属するか？
おそらく多くの人が難なく正解にたどり着いたことと思う．しかしこの問題に正解すること自体はそれほど重要ではない．重要なのはあなたがどのようにしてその正解にたどりついたかである．そこで今度は次の問題を考えてもらいたい．
問題 1.1.2. 上の問題に対してあなたが出した答が正しいことを論証によって正当化しなさい．
論証によって正当化するというのはつまり証明を与えるということである．証明というのは皆さんが高校まで数学でやってきたものと同じと考えてもらって構わない．さて今度はどうだろうか．先の問題が，簡単に見えて実際にはなかなか複雑な推論の過程を含んでいることが理解されただろう．
大体，答えは次のようになったと思う．
解答例
次郎吉はクル島の住人なので，武士か，盗人か，商人かのいずれかである．
次郎吉が武士であると仮定する．このとき，次郎吉が「私は盗人です」と言っていることから，次郎吉は盗人であるということになり，仮定と矛盾する．従って次郎吉は武士ではない．

1 この手の論理パズルのもっと複雑なものがレイモンド・スマリヤン『無限のパラドクス-パズルで学ぶカントールとゲーデル』（長尾確訳，白揚社）に数多く含まれている．この本はパズルを考えることを通して集合論と論理学の深い問題にアプローチしたもので
ある．

2

第1章 序

次に次郎吉が盗人であると仮定する．このとき，次郎吉が「私は盗人です」と言っていることから，次郎吉は盗人ではないということになり，仮定と矛盾する．従って次郎吉は盗人ではない．
従って次郎吉は商人である．
（証明終）
この証明は悪くない．もしこれが数学の問題として出されているならば，この証明で満点がもらえるだろう．しかし実のところ，この証明には明示化されていない暗黙の前提がいくつかある．この証明を正しい証明たらしめているのはその暗黙の前提なのである．そのような，私たちが推論（論証，証明）を行なっているときに暗黙のうちに従っている前提・原則を明らかにして，正しい推論を特徴付ける，ある論証が，本当に正しい推論に基づいているかを判定するための規準を明確に与えることが論理学の一つの目的である．
そこで次の問題を考えて欲しい．
問題 1.1.3. 上の証明はなぜ正しい証明と言えるのか？
数学では証明のやり方は（大雑把にではあるが）教わるけれど，なぜその証明が正しい証明なのかということまでは教えられない．この問題について考えることによって，あなたは論理学の領域に足を踏み入れたことになる．答えはいますぐには与えられない．実際，これに答えられるようになるのが，この講義の目的であると言っても良い．
問題 1.1.4. 次の質問に答え，その答を論証によって正当化しなさい．

(a) クル島で殺人事件が起こり，容疑者として A と B が挙げられた．二人のうちに犯人がいることは確実である．A は「私がやった」といい，B は「私たちのうちのどちらかは嘘をついている」と答えた．犯人はどちらだろうか．

(b) クル島の中にはロビン村という村があり，ここの住民はすべて武士か盗人のどちらかである．あるときロビン村で詐欺事件が起こり（つまり犯人は嘘をついた），容疑者として C と D が挙げられた．二人のうちに犯人がいることは確実である．C は「私が武士だとすれば，私は犯人ではない」という．犯人はどちらだろうか．

(c) 旅人がロビン村に行く途中，道が二本に分かれていた．どちらか一方だけがロビン村に通じている．
そこにロビン村の住民が通りかかったので，旅人はその住民に一つ質問をして，正しい道を知った．彼は何と質問したのだろうか．
論理学は推論（特に数学における推論）についての研究である．推論とは，何らかの前提から何らかの結論を導き出す思考の様式のことである．私たちは既に持っている知識から，推論によって新しい信念や知識を得る．例えば次のように．

(1)

前提 1：

A は B の父である．

Z は X の妻である．

前提 2：

B は C の父である．

Z は Y の母親である．

結論：

A は C の祖父である．

前提 1：

X は Y の父親である．

前提 2：
結論：

(2)

ところで，この二つの推論には大きな違いがある．それは (1) の推論が誤っている可能性があるのに対して，(2) の推論にはそのような可能性はない，ということである．
問題 1.1.5. (1) の推論が誤っているのはどのような場合か？

1.1. 論理学の目的

3

ある推論が誤りであるのは，その前提が正しいにもかかわらず結論が誤っている場合である．従って上の(1) の例で言えば，X が Y の父親であり，Z が X の妻であるにもかかわらず，Z が Y の母親ではない場合である．私たちはそのような例を実際に考えることが出来る．例えば Z が X の後妻で，Y が X と前妻との間に出来た子供であるような場合である．ある推論が誤りになる例をその推論に対する反例という．(2) の推論に関しては私たちは反例を考えることが出来ない．
このように推論には，前提が正しくても結論が誤りである可能性がある推論（蓋然的推論）と，前提が正しいときには結論が誤っているという可能性がない推論（必然的推論）がある．通常，論理学が扱うのは後者のタイプの推論である．
ただし実際に論理学は上のような具体例をいちいち取り扱うものではない．論理学が扱うのは抽象的な個々の言葉の定義に依存しない

必然的推論の形式である．論理学は正しい推論が持つ，共通の形

式（型，構造，パターン）についての研究である．正しい推論の持つ形式を抽象することによって，私たちはあらゆる具体的事例について成り立つ推論の規則を取り出すことが出来るのである．
一方で (2) の推論の必然性は「父」「祖父」といった具体的な言葉の意味に依存している．そもそも A がC の祖父であるということは，A が C の父または母の父であるということによって定義されている．従って(2) の推論において，「父」「祖父」という言葉を別な言葉に置き換えた場合には (2) の必然性は保たれない．
これに対して論理学が扱う推論というのは，そこに現れる言葉を別な言葉に置き換えたときでも必ず成り立
つような推論

つまり純粋にその推論の形式によって正しいと決定される推論でなければならない．

ところで (2) の推論に「ある人の父の父，または母の父は祖父である」であるという前提を加えてみよう．

(2)’

前提 0：

ある人の父の父，または母の父は祖父である．

前提 1：

A は B の父である．

前提 2：

B は C の父である．

結論：

A は C の祖父である．

するとこれは論理的な推論になる．実際「父」という言葉を例えば「母」という言葉に置き換えてみよう（このとき「父」という言葉が現れるすべての箇所で置き換えを行なわなければならないことに注意せよ）．

(2)*

前提 0：

ある人の母の母，または母の母は祖父である．

前提 1：

A は B の母である．

前提 2：

B は C の母である．

結論：

A は C の祖父である．

ここにおいてもやはり，前提のすべてが正しいとしたら，この結論が帰結しなければならない．従ってこれは必然的な推論である．
必然性がそこで用いられている言葉の意味に依存しているような推論においては，明示化されていない前提がある．その前提を付け加えることによって私たちはそれを論理的な推論に変えることが出来る．論理学の数学や哲学に対して果たしている大きな貢献の一つは，隠された前提を発見し，その推論を論理的な推論にすることである．これをラカトシュにならって推論の自明化と呼ぶことにしよう2 ．これは数学にお
2 Cf. Lakatos, ‘Infinite regress and foundations of mathematics,’ Mathematics, Science and Epistemology (Philosophical

4

第1章 序

いては，体系の公理化ということによって行なわれている（公理化については後述）．
問題 1.1.6. 以下の推論について，それが (i) 蓋然的推論，(ii) 必然的であるが論理的ではない推論，(iii) 論
理的な推論のいずれであるかを考えよ．(i) であるならば，その反例を考えよ．

(a)

(b)

(c)

(d)

前提 1：

X と Y は兄弟である．

前提 2：

Y と Z は兄弟である．

結論：

X と Z は兄弟である．

前提 1：

A は B より背が高い．

前提 2：

B は C より背が高い．

結論：

A は C より背が高い．

前提 1：x, y は自然数．

前提 2：

x < y ではない．

前提 3：

y < x ではない．

結論：

x = y．

前提 1：

哺乳類は卵を産まない．

前提 2：

カモノハシは卵を産む．

結論：

カモノハシは哺乳類ではない．

答え．(a) は蓋然的推論である．反例は X と Y が異母兄弟で Y と Z が異父兄弟である場合，X と Z が同一人物である場合など．(b)(c) は必然的だが論理的ではない．(d) だけが論理的な推論である．

(d) が論理的な推論であるというのは奇妙に思われるかもしれない．というのも (d) は前提も結論も誤っているからである．しかし推論の正しさというのは前提や結論それ自体の正しさに依存するのではないことに注意しなければならない．推論が正しいというのは，前提条件が成り立っているときには，必ず結論も成り立っていなければならない，ということである．そして (d) は確かにこのような性質を持っている．
またこの性質は「哺乳類」，「カモノハシ」，「卵を産む」などを他の言葉に置き換えても保存される．論理的な推論というのはそのようなものを指すのである．
論理学の起源をたどれば，古代ギリシャのアリストテレス（前 384-322）による三段論法の定式化にまでさかのぼる（上の問題の (d) も三段論法の一種）．三段論法には様々な形式があるが，最も典型的なものは
次のようなものである．
大前提：

すべての人間は死ぬ．

小前提：

ソクラテスは人間である．

結論：

ソクラテスは死ぬ．

この推論が正しい推論であることは誰でも認めるだろう．ここで重要なのは，この推論の正しさが，「人間」
Papers Vol. 2), Cambridge University Press, 1978, pp. 3-23.

1.1. 論理学の目的

5「死ぬ」「ソクラテス」などの言葉の意味内容には依存していないということである．例えば「人間」の代わりに「犬」を，「死ぬ」の代わりに「飛ぶ」を，「ソクラテス」の代わりに「アレキサンダー」を入れてみる．
大前提：

すべての犬は飛ぶ．

小前提：

アレキサンダーは犬である．

結論：

アレキサンダーは飛ぶ．

この推論が，私たちが通常「犬」や「飛ぶ」や「アレキサンダー」という言葉が指すものについて何かを主張していると考えるならば，これは誤りのように思われる．しかしここで問題にしているのはこの推論の形式であり，もしもこの大前提と小前提が正しければ，この結論が導かれるということである．つまり論理学は現実の事物について何かを主張するのではなく，ある推論が正しいのはそれがどのようなパターンに従っている場合であるか，ということを問題にする．
推論のパターンを明確に描き出すためには，そのパターンの中心的な骨格，本質的な性質を取り出し，抽象化・一般化しなければならない．この抽象化・一般化が現代の記号論理学への第一歩である．一般化を行
なうためには具体的な例をいくつも挙げて考察するのが手っ取り早い．そこで次のような推論を考えてみ
よう．
大前提：

すべてのギリシャ人は人間である．

小前提：

ソクラテスはギリシャ人である．

結論：

ソクラテスは人間である．

大前提：

すべてのギリシャ人は信心深い．

小前提：

ソクラテスはギリシャ人である．

結論：

ソクラテスは信心深い．

大前提：

すべての巧言なるものは徳が少ない．

小前提：

ソクラテスは巧言だ．

結論：

ソクラテスは徳が少ない．

これらはすべて同じパターンの推論であることが理解されるだろう．これらの推論に共通のパターンは，小前提の述語によって表される属性を持つものすべてが大前提の主語になっているということである．しかしそのことを私たちはどのように形式的に表現したらよいだろう？
ここから次の段階へのステップは論理学の長い歴史の中で最も革命的な出来事の一つであった．その革命はドイツの数学者・哲学者ゴットロープ・フレーゲ（1848-1925）によってもたらされた．
フレーゲは，「すべての人間は死ぬ」という文を，主語「すべての人間」に対して属性「死ぬ」を帰属させている単一の文とは考えなかった．その代わりに彼はこの文を，「x が人間であるならば，x は死ぬ」という表現の二つの空所に同じ固有名詞を入れたときに，その結果として得られる文は必ず正しい，ということを主張するものとして解釈した．
この解釈によれば上の三段論法はすべて

6

第1章 序

大前提：

「x が P1 ならば x は P2 」は x にどんな固有名詞を入れても正しい文になる．

小前提：

a は P1 ．

結論：

a は P2 ．

という形式を持つものであるということになる（ただし P1 , P2 には任意の述語，a1 には任意の固有名詞が入る）．この定式化によって私たちは個々の語の意味だけでなく，品詞の違いまでも度外視して，きわめて抽象的かつシンプルな推論の形式を取り出すことが出来た．
このような抽象化・単純化の利点は大きく言って二つある．一つはその応用の範囲の広さである．私たちは a1 に対しては，任意の固有名詞を代入することが出来る．また P1 と P2 に対しては，述語になるような表現ならば名詞でも，動詞でも，形容詞でも何でも代入することが出来る．そのような代入によって私たちは正しい推論の具体例を手にすることが出来るのである．
もう一つの利点は，上の分析によってもともとの三段論法が正しい推論である理由が明瞭になるということである．私たちは正確にはここで次の二つの推論を実行している．

• 「x が P1 ならば x は P2 」の x にどんな固有名詞を入れても正しい文になる，ということから「a1 がP1 ならば a1 は P2 である」という個別的な条件文を推論する．
• 「a1 が P1 ならば a1 は P2 である」と「a1 は P1 である」から「a1 は P2 である」を推論する．
この推論の背後には「すべてのものについて成り立つことは特定のものについて成り立つ」という原則と，「(A ならば B) が成り立っており，かつ A が成り立っているならば，B を導いても良い」という原則がある．このようなことはアリストテレスの三段論法の定式化からは理解することが出来なかったものである．
この結果だけを見ると「革命的」などという言葉を使うことはいささか大げさに聞こえるかもしれない．
そう聞こえたとしても無理のないことで，もともと三段論法自体がかなり自明なものなので，これだけの説明ではフレーゲの分析がどれだけ優れたものなのかが実感しにくいのである．しかしフレーゲの本当の目的は何も三段論法を洗練させることにあったのではない．フレーゲの分析が真価を発揮するのは，もっともっと複雑な議論においてである．フレーゲはもともと算術・数論の言明や推論の過程をより正確に，そして厳密に表現し導くための道具として記号論理学を作り上げたのだった．そしてその成果は掛け値なしに驚嘆するべきものである．そのことを実感してもらうには，実際に記号論理学を多少なりとも実践してもらう他はないのであるが，しかしその前に少しだけ，記号論理学が実際にその威力を発揮する文脈というものを知ってもらうことは，これから論理学を学ぶ人々にとっての動機付けになるかもしれない．

1.2

論理学の意義

1.2.1

数学基礎論

数学の研究には二つの方向性がある．一つは既存の概念や知識を前提として，そこからさらに新しい概念や知識を導き出そうとする前進的な研究である．もう一つは既存の概念や知識の前提となっているより原
初的な概念や原則を追求しようとする遡及的な研究である．通常，ほとんどの数学者たちは前者の方向で1.2. 論理学の意義

7

研究をしている．しかしその研究に何らかの支障が生じたときに，後者の方向での研究に着手する者が現れる．そしてそのような研究の中で記号論理学は発展してきた．

19 世紀から 20 世紀の初頭にかけて記号論理学が飛躍的に発展したのには，当時の解析学の厳密化，自然数論の基礎付けなどの運動が関係している．この運動の中でそれまで正確な定義を与えられず，多かれ少な
かれ曖昧にあるいは直観的に扱われていた多くの概念に厳密な定義が与えられた．中にはそれまで数学者たちが当たり前のものと考え，その意味について考えようと思ったことすらなかったような概念も含まれていた．その最たるものが自然数の概念である．ドイツの数学者クロネッカー（1823-1891）は「整数は神が創造した．他のすべての数は人間が作った」と言ったと伝えられている．クロネッカーと同様に，ほとんどの数学者たちは整数は与えられたものとして認め，それをどのように定義するべきかという問題については真剣に考えようとはしていなかった．まして自然数についてはなおさらである．
しかし様々な概念がより基本的な概念に還元されていくにつれて，ついには自然数とそのの上での算術さえもより基本的な概念，理論へと還元することが試みられた．この試みには三つの異なるアプローチがあった．一つはドイツの数学者デデキント（1831-1916）とカントール（1845-1918）による算術の集合論への還元，一つはイタリアの数学者ペアノ（1858-1932）による算術の公理化，もう一つはフレーゲによる算術の記号論理学への還元である．彼らの試みのためには記号論理学的な手法が不可欠であり，それゆえに彼らは自分たちが利用することの出来る記号論理学の体系を構築しながら，その上に算術の体系を構築していった．
論理を厳密に定式化することがこのような研究に役立つのは何故だろうか？ 私たちは上で次のような推論の例を見た．
前提 1：

x, y は自然数．

前提 2：

x < y ではない．

前提 3：

y < x ではない．

結論：

x = y．

既に述べたようにこの推論自体は論理的な推論ではない．なぜならば < という記号を例えば | に置き換えたならばこの推論は成り立たないからである（x | y という表現は x は y の約数であるということを意味する）．また = を 6= に置き換えてもこの推論は成り立たない．
従ってこの推論の正しさは，自然数の間に定義された，<, = という記号によって表される関係の性質に依存している．このように特定の性質に依存するような推論は論理的な推論とは言わない．この例が必然的な推論になっているのは，すべての自然数 x, y について，x < y, y < x, x = y のいずれかが成り立つ，という前提を私たちが了解していたからである．この前提と，前提 1（x < y ではない），および前提 2（y < xではない）からは純粋に論理的な推論の規則を適用することによって x = y という結論が導き出せる．
従って先ほどの推論は，正しくは次のように自明化される．

8

第1章 序

前提 0：

すべての自然数 x, y について，

x < y, y < x, x = y のいずれかが成り立つ．
前提 1：x, y は自然数．

前提 2：

x < y ではない．

前提 3：

y < x ではない．

結論：

x = y．

これは純粋に論理的な推論である．このように論理的な推論が何かを明確に特徴付けることは，ある推論における論理的な要素とそうでない要素を区別することを助ける．そのことによって私たちは，それまで暗黙のうちに了解されていた前提を明示化することができるのである．
記号論理学が数学の基礎に対して果たす貢献の一つはここにある．つまり数学の推論を自明化することによって，私たちは数学の必然性がどのような前提に依存しているかを明らかにすることができるのである．
デデキント，カントール，ペアノ，フレーゲたちは，このように数学における推論の過程を厳密に明示化することによって，数学において何が前提とされているのかを明らかにしていった．同時に彼らはそうやって発見した前提が自明な真理であることと，数学において採用されている推論が純粋に論理的な推論であることつまり前提が真であるならば，結論も真であるような推論であることから，数学のすべての定理が確かに真であるあることの保証を得ようとしていた．その結果，デデキントとカントールは，数論，解析学，代数学，幾何学などの体系を基礎付けることが出来る，集合論という強力な理論を構築した．
またペアノは自然数論の全体が，現在ペアノの公理と呼ばれている，わずか 8 個の前提から導き出せることを明らかにした．これだけでも十分に驚嘆に値する結果であったが，フレーゲがたどり着いた結論はさらに驚くべきものだった．フレーゲは算術の体系を導出するのには集合論もペアノの公理も必要ではなく，純粋に論理的な法則だけで十分であると主張したのである．フレーゲはこのことを示すために記号論理学の体系を厳密に定式化し，そこから算術のすべてを導出しようとした．
実際にはフレーゲの計画は完全には実現しなかった．その原因は，カントールの集合論とフレーゲの記号論理学において，導出されることが証明されたパラドクスの発見である．そのうちの一つは，フレーゲと同様に，数学を論理学によって基礎付ける試みに取り組んでいたイギリスのラッセル（1872-1970）によって発見されたものである．それは次のようなものであった．
集合とは任意の対象の集まりである．ところで集合には自分自身を要素として含むものがある．例えば，
人間ではないものすべての集合というものを考えると，これ自身はもちろん人間ではないので，自分自身を要素として含んでいる．いま W は「自分自身を要素として含まない集合すべての集合」であるとする．
このとき W は自分自身を含むということと，W は自分自身を含まないということが共に帰結する．
問題 1.2.1. 上の集合 W について，それが自分自身を含むということと，自分自身を含まないということの両方が帰結することを示せ．
（ヒント：まず W が自分自身を含むということを仮定して矛盾が導かれることを示す）
このような矛盾が導出されたことは非常に深刻な問題であった．というのもカントールの集合論やフレー
ゲの論理学は，数学の最も基本的な部分である自然数論に基礎を与えるものだと考えられたからである．彼

1.2. 論理学の意義

9らの体系から矛盾が生じるということは数学全体が矛盾を含むということになりかねない．そこで多くの数学者たちがこの困難を回避するための様々なプロジェクトに着手した．
ドイツの数学者ヒルベルト（1862-1943）は有限主義という立場からペアノ算術の無矛盾性を証明しようとした．オランダの数学者ブラウワー（1881-1966）はそれまで無制限に使われていた推論規則に制限を加えることで，矛盾を生じさせない論理体系を作り出した．ラッセルは集合や述語の適用に制限を加えたタイ
プ理論という論理体系によって矛盾を回避しようとした．
彼らのプロジェクトはそれぞれに長所と短所があり，どれも決定的な解決策にはならなかった．しかし彼らの試みからは様々な実りある結果が生まれ，記号論理学のさらなる発展と数学基礎論という分野の確立を促した．皮肉なことにこういった運動が結局，数学を形式的に捉えることには限界があるということを明らかにすることになった．しかしこのことが明らかになったということは，それはそれで一つの大きな発見である．この発見は数学の確実性を減じることにはなったが，しかし数学の豊かさを減じたわけではない．
問題 1.2.2. 以下の問題について考えよ．

(a) ある床屋が「私はこの町の自分でひげをそらない男全員のひげをそっているんだ」と言った．彼の発言のおかしなところはどこか．

(b) 形容詞には「日本語の」とか「四文字の」など，その形容詞自身に当てはまるようなものがある．このような形容詞を自己形容的形容詞と呼ぼう．一方「英語の」とか「五文字の」など，その形容詞自身には当てはまらないものがある．このような形容詞を非自己形容的な形容詞と呼ぼう．ところで「非自己形容的な」という形容詞は自己形容的だろうか，非自己形容的だろうか．

(c) 次の文は正しい．前の文は誤りだ．正しい文はどちらだろう．

1.2.2

推論の機械化

推論の規則を明示化し，かつその推論の前提を明らかにするということは，ある結論を導き出すための手
続きをはっきりさせ，その過程を機械的な手続きにするということを助ける．このようなことは計算における問題解決という文脈では古くから行なわれてきたものである．例えば次のようなアルゴリズムを考えてみよう3 ．このアルゴリズムが何を意味するのかということを考えずに，とりあえずは指示に従って欲しい．
アルゴリズム 1.2.3. 二つの自然数が与えられたとき，以下の手続きに従って出力を求めよ．

1. m, n に与えられた自然数を入力して 2 に進む．
2. p := 0 と置く．3 に進む．
3. n < (p + 1) · m ならば 5 に，そうでなければ 4 に進む．
4. p := p + 1 と置く．3 に進む．
5. q := n − p · m と置く．6 に進む．
6. q = 0 ならば 8 に，そうでなければ 7 に進む．
7. n := m, m := q と置く．2 に進む．
3 「アルゴリズム」という言葉の形式的な定義はここでは与えない．とりあえずは，ある課題を遂行するために与えられる明確な指示の組み合わせ，と理解しておこう．

10

第1章 序

8. z := m と置く．9 に進む．
9. z の値を出力して手続きを終了する．
「n := x と置く」は「パラメーター n の値として，パラメーター x の値を入れる」ということを意味する．
「p := p + 1 と置く」は「現在のパラメーター p の値に 1 を加えたものを，新しく p の値とする」ということを意味する．
例 1.2.4. 104 と 273 が与えられたとして，アルゴリズム 1.2.3 に従って p の値を求めてみよう．

m に 104 を，n に 273 を入れて 2 に進む．
p に 0 を入れて 3 に進む．n = 273 > (p + 1) · m = 104 なので 4 に進む．p = 0 にを 1 加えた 1 を新しいp の値とし，3 に進む．n = 273 > (p + 1) · m = 208 なので 4 に進む．p = 1 に 1 加えた 2 を新しい p の値とし，3 に進む．n = 273 < (p + 1) · m = 312 なので 5 に進む．n − p · m = 273 − 2 · 104 = 65 を q の値として 6 に進む．q = 0 ではないので 7 に進む．n に 104 を，m に 65 を入れて 2 に進む．

p に 0 を入れて 3 に進む．n = 104 > (p + 1) · m = 65 なので 4 に進む．p に 1 加えた 1 を新しい p の値とし，3 に進む．n = 104 < (p + 1) · m = 130 なので 5 に進む．n − p · m = 104 − 1 · 65 = 39 の値を q に入れて 6 に進む．q = 0 ではないので 7 に進む．n に 65 を，m に 39 を入れて 2 に進む．

p に 0 を入れて 3 に進む．n = 65 > (p + 1) · m = 39 なので 4 に進む．p に 1 加えた 1 を新しい p の値とし，3 に進む．n = 65 < (p + 1) · m = 2 · 39 = 78 なので 5 に進む．n − p · m = 65 − 39 = 26 の値を q に入れて 6 に進む．q = 0 ではないので 7 に進む．n に 39，m に 26 を入れて 2 に進む．

p に 0 を入れて 3 に進む．n = 39 > (p + 1) · m = 26 なので 4 に進む．p に 1 加えた 1 を新しい p の値とし，3 に進む．n = 39 < (p + 1) · m = 2 · 26 = 52 なので 5 に進む．n − p · m = 13 の値を q に入れて 6 に進む．q = 0 ではないので 7 に進む．n に 26 を，m に 13 を入れて 2 に進む．

p に 0 を入れて 3 に進む．n = 26 > (p + 1) · m = 13 なので 4 に進む．p に 1 加えた 1 を新しい p の値とし，3 に進む．n = 26 = (p + 1) · m = 2 · 13 = 26 なので 4 に進む．p に 1 加えた 2 を新しい p の値とし，3に進む．n = 26 < (p + 1) · m = 3 · 13 = 39 なので 5 に進む．n − p · m = 26 − 2 · 13 = 0 の値を q にいれて6 に進む．q = 0 なので 8 に進む．
z に m の値 13 を入れる．9 に進む．
z の値 13 を出力して手続きを終了する．
というわけで，アルゴリズム 1.2.3 は 104 と 273 という二つの自然数の組み合わせに対しては 13 という値を出力することが分かった．実のところ，アルゴリズム 1.2.3 はどんな二つの自然数の組に対しても必ず一つの決まった自然数を出力する．
問題 1.2.5. 以下の自然数の組が与えられたとき，上の手続きに従って z の値を求めよ．

(a)21, 6.

(b)24, 32.

(c)8, 12.

(d)77, 161.

(e)

171, 95.

(f)

232, 87.

(g)

869, 1817.

(h)6325, 2484.

1.2. 論理学の意義

11

この手続きが何を意味しているかを説明しよう．中には問題を解きながら気付いた方もいるかもしれな
いが，実のところこの手続きの結果得られる z の値は，入力した二つの自然数の最大公約数の値になっているのである．この手続きは，任意の自然数 m, n, p, q について n = p · m + q ならば n と m の最大公約数
は m と q の最大公約数に等しい，という定理に基づいて，大きな自然数同士の最大公約数を求める問題を，どんどんと小さい自然数同士の最大公約数を求める問題へと還元していっているのである．最終的にはある数と 0 との最大公約数にまで問題は還元され，そして任意の自然数について，その自然数と 0 との最大公約数はその自然数自身であるから，簡単に最大公約数を求めることが出来る．このような手続きをユーク
リッドの互除法という．
実際には上の手続きは，「n を m で割った余り」という概念を使えばもっと簡単に記述することが出来る．

mod(n, m) という記号で「n を m で割った余り」という関数を表わすことにすれば，次のアルゴリズムはアルゴリズム 1.2.3 とまったく同等の結果を出す．
アルゴリズム 1.2.6. 二つの自然数が与えられたとき，以下の手続きに従って出力を求めよ．

1. m, n に与えられた自然数を入力して 2 に進む．
2. q := mod(n, m) と置く．3 に進む．
3. q = 0 ならば 5 に，そうでなければ 4 に進む．
4. n := m, m := q と置く．2 に進む．
5. z := m と置く．6 に進む．
6. z の値を出力して手続きを終了する．
こちらの方が短いので，それゆえに「良い」アルゴリズムに思われるかもしれない．しかしそれは私たちが割り算という手続きを理解しており，mod 関数を適切に計算する能力を持っているからである．割り算の手続きや mod 関数を計算する手続きを知らない人間にはアルゴリズム 1.2.6 を遂行することは出来ない．
一方でアルゴリズム 1.2.3 は，自然数の足し算，引き算，掛け算が出来，自然数同士の同一性と大小関係の判定ができる人間ならば誰でも遂行できる．従って見かけに反して，アルゴリズム 1.2.3 の方がアルゴリズ
ム 1.2.6 よりも単純なアルゴリズムなのである．この二つのどちらが良いアルゴリズムであるかは状況に依存する．割り算の手続きに熟達した人間にとっては 1.2.6 の方がだいぶ効率が良いのは明らかである．
これらのアルゴリズムは，そこに前提されている知識は異なるが，同等のアルゴリズム
じ入力に対しては必ず同じ出力を返すアルゴリズム

すなわち同である．注目するべき点は，最大公約数という概念を全く持たない人間でも，これらのアルゴリズムに従うことで最大公約数を求めることが出来るということである（私たちがこの手続きの意味を教えられないまま問題を解いたときのように）．
もう一つ，別なアルゴリズムを考えてみよう．与えられた自然数 m と n の最大公約数を求める最も原始的な方法は，1 からスタートして，順にそれが与えられた二つの数を割り切るかを調べ，m か n のうちの小さい方に到達するまで繰り返し，その最大値を出すというものだろう．それは次のようなアルゴリズムとして表現できる．
アルゴリズム 1.2.7. 二つの自然数が与えられたとき，以下の手続きに従って出力を求めよ．

1. m, n に与えられた自然数を入力して 2 に進む．
2. m · n = 0 ならば 3 に，そうでなければ 4 に進む．

12

第1章 序

3. z := m + n と置く．17 に進む．
4. p := 1 と置く．5 に進む．
5. q := 0 と置く．6 に進む．
6. m = p · q ならば 9 に，そうでなければ 7 に進む．
7. p · (q + 1) > m ならば 14 に行く．そうでなければ 8 に進む．
8. q := q + 1 と置く．6 に進む．
9. q := 0 と置く．10 に進む．
10. n = p · q ならば 13 に進む．そうでなければ 11 に進む．
11. p · (q + 1) > n ならば 14 に進む．そうでなければ 12 に進む．
12. q := q + 1 と置く．10 に進む．
13. z := p と置く．14 に進む．
14. p + 1 > m ならば 17 に進む．そうでなければ 15 に進む．
15. p + 1 > n ならば 17 に進む．そうでなければ 16 に進む．
16. p := p + 1 と置く．5 に進む．
17. z の値を出力して手続きを終了する．
このアルゴリズムと同じような手続きの流れを，やはり mod 関数を使って表現することが出来る．それは次のようなアルゴリズムになる．
アルゴリズム 1.2.8. 二つの自然数が与えられたとき，以下の手続きに従って出力を求めよ．

1. m, n に与えられた自然数を入力して 2 に進む．
2. m · n = 0 ならば 3 に，そうでなければ 4 に進む．
3. z := m + n と置く．11 に進む．
4. p := 1 と置く．5 に進む．
5. mod(m, p) = 0 ならば 6 に，そうでなければ 8 に進む．
6. mod(n, p) = 0 ならば 7 に，そうでなければ 8 に進む．
7. z := p と置く．8 に進む．
8. p + 1 > m ならば 11 に，そうでなければ 9 に進む．
9. p + 1 > n ならば 11 に，そうでなければ 10 に進む．
10. p := p + 1 と置く．5 に進む．
11. z の値を出力して手続きを終了する．
さてこのアルゴリズム 1.2.7 も 1.2.8 前の二つのアルゴリズム 1.2.3，1.2.6 と同等のアルゴリズムである．
これら 4 つのアルゴリズムの利点と欠点を比較することによって，私たちは重要な点をいくつか理解することが出来る．以下でアルゴリズム 1.2.3，1.2.6，1.2.7，1.2.8 をそれぞれ GCM1，GCM2，GCM3，GCM4と呼ぶことにする．

GCM3 と GCM4 の手続きの流れにおいては，二つの自然数の最大公約数を求めようとしているのだということが比較的理解しやすい．しかしこのアルゴリズムを使って例えば前問の (h) を解いてみると，膨大な

1.2. 論理学の意義

13

時間がかかることが分かる．GCM3 は最大公約数という概念についての私たちの理解にとって自然なアルゴリズムである．しかしこのアルゴリズムに従って計算を行なうことは非常に効率が悪い．
一方で GCM1 と GCM2 は，「任意の自然数 m, n, p, q について n = p · m + q ならば n と m の最大公約数
は m と q の最大公約数に等しい」という，それほど自明ではない定理に基づいているために，直観的に何を計算しているのかが分かりにくい．しかし計算の効率は GCM3 とは比べ物にならないくらい良い．

GCM1 と GCM2 を比較した場合，GCM1 の方は割り算や mod 関数の計算方法を知らなくても計算を実行できるという利点がある．しかしその分だけプログラムの表現は長くなっているし，割り算や mod 関数の計算の手続きに慣れた人間にとっては GCM2 の方が効率よく計算が出来る．これは GCM3 と GCM4 を比較した場合も同様である．
前節で見たとおり，論理学というのは私たちが普段使っている推論の隠れた前提を明示化するという役割を持っている．これは上の例で言えば，GCM2, 4 方式で書かれた推論を，GCM1, 3 方式のより単純で基本的な形に書き直すということである．このことの利点は上でみた通り，計算に熟達していない人間でも，黙って指示に従うだけで，問題の正しい解決に到達できる，ということである．このことは推論の自動化，機械化ということをもたらす．現在のコンピューターの理論的な背景には，計算や情報処理の自動化・機械化という考えが横たわっている．
しかし推論を機械化することの意義は，誰にでも計算の遂行が可能になるということだけではない．GCM2-4 方式の推論を GCM1-3 方式の推論に書き換えることによって，私たちは GCM2, 4 方式の複雑な推論の過程の根底にある原理をよりよく理解できるようになる．確かに GCM1, 3 方式に書かれたアルゴリズムは長く煩雑なものになるが，しかしその過程の一歩一歩は誰にでもフォローできるものになっているし，ひとたびその過程の一歩一歩がどのようになっているが理解できたら，その後は GCM2-4 方式の推論を実行する
ことは比較的容易である．
一方で GCM1, 2 方式と GCM3, 4 方式との対照は論理学の観点からどのように評価できるだろうか．

GCM3, 4 方式のアルゴリズムは最大公約数の定義から自然に導かれるアルゴリズムである．これは，いわば最大公約数を計算する正規のアルゴリズムであるといえる．最大公約数という概念を理解している人間
は，何かしら GCM3-4 方式のアルゴリズムを理解していなければならない．言ってみれば GCM3-4 の形で提示されたアルゴリズムは単なる問題解決の方法というだけではなく，人間が最大公約数という概念を理解する仕方の一つのモデルになっている．
以下では論理的な推論を特徴付けるために，いくつかの異なる体系が提案される．それらは同等な体系なのであるが，それらにはそれぞれに長所と短所がある．それはちょうど私たちが上の GCM アルゴリズムのそれぞれにおいて見出したものとパラレルなものである．
つまりある推論を論理的な推論として定式化することは，(1) 推論を遂行するための指針を与えて，誰にでも同じ推論が出来るようにする，(2) その推論によって導かれる結論の意味を明確にする，という役割がある．機械的な手続きとその手続きが持つ意味，この二つは論理学において極めて重要なものである．このことは常に意識しておいて欲しい．

14

第1章 序

問題 1.2.9. 次のアルゴリズムが与えられたとする．

1. n に与えられた自然数を入力して 2 に進む．
2. p := 0, z := 1 と置く．3 に進む．
3. n = p ならば 6 に進む．そうでなければ 4 に進む．
4. p := p + 1 とする．5 に進む．
5. z := z · p とする．3 に進む．
6. z の値を出力して手続きを終了する．
このアルゴリズムに従って 3，5，10 という値を入力したときのそれぞれの出力を求めよ．またこのアル
ゴリズムが何を意味しているかを考えよ．
問題 1.2.10. 次のアルゴリズムが与えられたとする．

1. n に与えられた自然数を入力して 2 に進む．
2. n < 2 ならば 8 に進む．そうでなければ 3 に進む．
3. p := 2 と置く．4 に進む．
4. n > p ならば 5 に進む．そうでなければ 7 に進む．
5. mod(n, p) = 0 ならば 8 に進む．そうでなければ 6 に進む．
6. p := p + 1 と置く．4 に進む．
7. YES を出力して手続きを終了する．
8. NO を出力して手続きを終了する．
このアルゴリズムに従って 1，2，4，7，10，11 という値を入力したときのそれぞれの出力を求めよ．またこのアルゴリズムが何を意味しているかを考えよ．

1.2.3

分析哲学

証明の過程を厳密に定式化し，同時にそれまで曖昧に使われていた概念を分析して正確な定義を与える
ことは，例えば連続や無限などといった概念をめぐる多くの形而上学的な論争に終止符を打つことになった．さらに記号論理学を用いた概念の明晰化，隠された前提の発見という手法は数学の中だけにとどまらず，哲学においても大きな威力を発揮し，20 世紀の哲学の一つの主流を形成した．この流れは分析哲学と呼ばれている．分析哲学とは，ある概念について議論をする際に，言語的分析を通じてその概念の意味を明確にすることを目指す哲学である．
前節での説明によれば，「すべての人間は死ぬ」という文は，「x が人間ならば x は死ぬ」という表現の xにどんな固有名詞を入れても，その結果できあがる文は正しい，ということを主張しているということであった．ここから「すべての人間」というような表現は，一般的に考えられるように，名詞として何らかの対象を名指しているのではない，ということが結論される．
このように日常言語の文の中では名詞として何かを名指しているように思われていた語が，論理学の言1.2. 論理学の意義

15

語に翻訳した後の文には現れなくなるということが，現代論理学の大きな発見であった．というのもそれま
では名詞というのは常に何かの実体を指すものと考えられ，したがってすべての名詞に対してその指示対象が存在しなければならないと考えられていたからである．それゆえに哲学者たちは何かの名詞によって表わされているものについて，それが「何であるか？」と問い続けてきたのである．たとえば「時間とは何か？」，「空間とは何か？」，「存在とは何か？」，「数とは何か？」などなど．
従来の言語観では，例えば(1) ユニコーンは存在しないという文はいささかパラドキシカルな文であると考えられる．というのもこの文は「ユニコーン」という語句が指示する対象に対して，「存在する」という述語によって表される性質が帰属されない，ということを述べていると考えられたからである．そもそもユニコーンというような対象が存在しないのであれば，「ユニコーン」という語は意味内容を欠いているように思われる．だとすればこの文全体も無意味になりはしないだろうか？ しかしなおこの文は私たちにとって理解可能であるように思われる．
この困難はどこから生じるのだろうか？ この議論の前提には，有意味な文の構成要素はそれぞれ独立に意味を持っている，という前提がある．この前提はあまりにも自明すぎてほとんど疑う人間はいなかった．
この点に異論を唱えたのが分析哲学の創始者でもあったフレーゲである．フレーゲは，ある語が文脈から独立に意味・指示対象を持つと考えるのは誤りだと主張した．フレーゲによれば，すべての語の意味は何らかの文の中に置かれて初めて決定される．これを「文脈原理」という．つまり上の例で言えば「ユニコーン」という語が，それ自体として意味を持つと考えるべきではない，ということである．私たちが意味を考慮す
るべき単位は (1) という文の全体である．それではこの文の意味はどのように決定されるのであろうか．
まず「ユニコーン」という語が単純な固有名詞ではなく，複合的な概念を意味していることに注目しよう．この語は実際には「角を持った馬」として定義することが出来る．そこで (1) は(2) 角を持った馬は存在しないと言い換えることが出来る．さらにこれは(3) 馬でありかつ角を持っているようなものは存在しないと表現できる．さらにこれは(4) すべての馬は角を持っていないという文と同値だということは認められるだろう．ここで前節の議論に沿って考えると，(4) は(5) 「x が馬ならば x は角を持っていない」という表現の x にどんな固有名詞を入れても，出来上がる文は正しいということを表現しているものと考えられる．従って私たちは (1) は (5) を意味しているものと考えることができる．ここにはもはや「ユニコーン」という名詞も「... が存在する」という述語も現れない．従って
何もパラドキシカルな事態は生じていない．

16

第1章 序

(5) は日本語としてはいささか奇妙な言い回しであるが，その意味（真理条件）は明白である．(5) が真かどうかを確かめるためには私たちはすべての馬を調べ，それが角を持つかどうかを見れば良いのである．
もちろんすべての馬を調べるということは現実には困難だろうし，本当にすべての馬を調べたということを立証することは不可能である．しかし私たちが今問題にしているのは，(5) が真であるための条件である．
従って重要なのは，(5) が真であることを知るために，私たちが何を確かめなければならないか，という問題である．
このようにフレーゲは，日常言語の複雑で曖昧な文を，より明白で誤解の余地のない文（実際には記号論理学の言語で表現される）に翻訳する．この手法は哲学に大きなインパクトを与え，ラッセルなどへと引き継がれる分析哲学の大きな流れを作ったのである．
問題 1.2.11. 上の方法に習って以下の文を翻訳せよ．

(a)

ペガサスは存在しない．

(b)

例外のない規則はない．

(c)最小の自然数が存在する．

(d)

過ちを犯すのが人間だ．

1.3

集合論の用語解説

本題に入る前に，以下でしばしば集合論の概念，用語，記号を用いるので，必要なことをここで説明して
おく4 ．
定義 1.3.1 (集合，要素). 集合 set とは任意の対象の集まりである．任意の対象 a, b, c, . . . を { } でくくった表現，すなわち {a, b, c, . . . } は a, b, c, . . . からなる集合を表す．このとき a, b, c, . . . はこの集合の要素または元element であるという．
対象 a が集合 S の要素であるということを a ∈ S と表現する．また a が S の要素ではないということをa∈/ S と表現する．
集合の表記において，要素の並び方の順序は問われない．従って {a, b} と {b, a} は同じ集合を表現している．
また一つの集合に同じ対象は一個しか属さない．従って {a, a} は {a} と同じ集合を表現している．
定義 1.3.2 (空集合). 要素を一つも持たない集合を空集合empty set といい，∅ によって表す．
定義 1.3.3 (集合の内包的表記). C(x1 , x2 , . . . , xn ) によって n 個の変数5 x1 , x2 , . . . , xn を含む何らかの条件
例えば「x1 はアルファベットの文字である」，「x1 を 3 で割った余りと x2 を 3 で割った余りは等しい」，「x21 + x22 = x23 」等々を表わす．このとき条件 C(x1 , x2 , . . . , xn ) 満たすような対象 x1 , x2 , . . . , xn の組

4 集合論は数学や論理学を記述するための強力で豊かな道具である．ここでは最低限の用語の定義しか与えないが，論理学や数学の基礎に興味を持たれた方は，一通り集合論を勉強しておくことをお勧めする．例えば松阪和夫『集合・位相入門』（岩波書店）の前
半，小野寛晰『情報代数』（共立出版）の第 2-3 章などを読んでおくと良いだろう．
5 変数は数だけではなく，任意の対象を値にとることが出来る．

1.3. 集合論の用語解説

17hx1 , x2 , . . . , xn i すべてからなる集合を {hx1 , x2 , . . . , xn i | C(x1 , x2 , . . . , xn )} で表す．例えば {x | x は 5 以
下の自然数 } は 5 以下の自然数すべてからなる集合，すなわち {0, 1, 2, 3, 4, 5} である6 ．
定義 1.3.4 (部分集合). 集合 S のすべての要素が集合 T の要素でもあるとき，S は T の部分集合または単に部分subset であるという．このことを S ⊆ T によって表す．
任意の集合 S について，∅ ⊆ S, S ⊆ S が成り立つ．
定義 1.3.5 (集合の同一性). S ⊆ T と T ⊆ S の両方が成り立っているとき，つまり S のすべての要素がT の要素であり，かつ T のすべての要素が S の要素であるとき，S と T は同一であるといい，このことを
S = T によって表す．これは，集合の同一性はその要素の同一性に帰されるということを意味する．
定義 1.3.6 (真部分集合). S ⊆ T であり，かつ S = T でないとき S は T の真部分集合または単に真部
分proper subset であるといい，このことを S ( T によって表現する．
定義 1.3.7 (集合の和，共通部分，差). S の要素と T の要素のすべてからなる集合を S と T の和または合併union といい，S ∪ T によって表す．

S と T に共通の要素からなる集合を S と T の共通部分または交わりintersection といい，S ∩ T によって表す．
より一般的に，集合を要素として持つ集合 M に対して，M の合併と交わりを次のように定義する．

[\

M = {x | ∃M ∈ M(x ∈ M )}M = {x | ∀M ∈ M(x ∈ M )}S の要素であるが，T の要素ではないものすべてからなる集合を S と T の差subtraction といい，S \ T
または S − T によって表す．
例 1.3.8. S = {0, 1, 2}, T = {2, 3, 4} であるとき，

S ∪ T = {0, 1, 2, 3, 4}，
S ∩ T = {2}，S \ T = {0, 1}．
この定義では例えば S1 ∪ S2 ∩ S3 が，S1 ∪ S2 と S3 との共通部分を表わしているのか，それとも S1 とS2 ∩ S3 との和を表わしているのかが不明である．そこで前者を指すためには (S1 ∪ S2 ) ∩ S3 と表記し，後者を指すためには S1 ∪ (S2 ∩ S3 ) と表記して，集合に対する操作が行なわれた順番を明記することにする．
しかし例えば S1 ∪ (S2 ∪ S3 ) = (S1 ∪ S2 ) ∪ S3 ，S1 ∩ (S2 ∩ S3 ) = (S1 ∩ S2 ) ∩ S3 なので，このような場合は操作の順番を括弧で表わす必要はない．
事実 1.3.9. 任意の集合 A, B, C に対して，以下の事実が成り立つ．
6 本テキストでは 0 は自然数として扱う．

18

第1章 序

• A∪B =B∪A
• A ∪ (B ∪ C) = (A ∪ B) ∪ C• A∩B =B∩A
• A ∩ (B ∩ C) = (A ∩ B) ∩ C• A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ B)
• A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ B)
• (A \ B) ∪ B = A• (A \ B) ∩ B = ∅• A \ (B ∪ C) = (A \ B) ∩ (A \ C)
• A \ (B ∩ C) = (A \ B) ∪ (A \ C)• A⊆A
• A ⊆ B かつ B ⊆ C ならば A ⊆ C• A∩B ⊆A
• A⊆A∪B• B ⊆ A かつ C ⊆ A ならば B ∪ C ⊆ A• A ⊆ B かつ A ⊆ C ならば A ⊆ B ∩ C• 任意の x に対して条件 C(x) が条件 C 0 (x) にとって十分ならば，{x | C(x)} ⊆ {x | C 0 (x)}定義 1.3.10 (べき集合). S の部分集合のすべてからなる集合を S のべき集合power set といい，P(S) ま
たは 2S によって表す．例えば S = {0, 1, 2} であるとき，P(S) = {∅, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2}}である．
定義 1.3.11 (直積). S の任意の要素 x と T の任意の要素 y との対 hx, yi のすべてからなる集合 {hx, yi | x ∈S, y ∈ T } を S と T の直積cartesian product といい，S × T によって表す．例えば S = {0, 1}, T = {a, b, c}であるとき，

S × T = {h0, ai, h0, bi, h0, ci, h1, ai, h1, bi, h1, ci}である．

S1 × (S2 × S3 ) は S1 × S2 × S3 と表記するものとする．直積 S1 × S2 × · · · × Sn の要素は正式にはhx1 , hx2 , h. . . hxn−1 , xn i . . .iii と書かれるのであるが，これを hx1 , x2 , . . . , xn i と表わすことにする．
集合 S だけで直積を作る操作を n 回繰り返して作られる集合を S n によって表わす．つまり

1.3. 集合論の用語解説

19

S 1 = S,
S n+1 = S × S n ．
定義 1.3.12 (関係). 任意の S1 , S2 , . . . , Sn について S1 × S2 × · · · × Sn の任意の部分集合 R を（n 項）関係n-ary relation という（ただし n ≥ 1）．R が特に S n の部分集合であるとき，R を S 上の（n 項）関係という．
例 1.3.13. N によってすべての自然数の集合を表し，N2 = N × N の部分集合 L として {hx, yi | hx, yi ∈N2 , x < y} という集合を考える．このとき hx, yi が L の要素であるということと，x, y が自然数でありか
つ x < y が成り立つということは等しい．
二項関係 R に対して，しばしば hx, yi ∈ R を xRy と略記する．
定義 1.3.14 (反射性，対称性，推移性，反対称性). R は S 上の二項関係とする．

(1) 任意の x ∈ S に対して xRx が成り立つとき，R は反射的reflexive であるという．
(2) 任意の x, y ∈ S に対して，xRy ならば yRx が成り立つとき，R は対称的symmetrical であるとという．
(3) 任意の x, y, z ∈ S に対して，xRy かつ yRz ならば xRz が成り立つとき，R は推移的transitive であるとという．

(4) 任意の x, y ∈ S に対して，xRy かつ yRx ならば x = y が成り立つとき，R は反対称的antisymmetricであるという．
定義 1.3.15 (順序，全順序). S 上の二項関係 ≤ が反射性，対称性，反対称性を持つとき，R は S 上の順
序または半順序semiorder, partial order であるという．さらに任意の x, y ∈ S に対して，x ≤ y またはy ≤ x が成り立つとき，≤ は S 上の全順序total order であるという．
定義 1.3.16 (順序集合，部分順序集合). 集合 S と S 上の順序 ≤ の対，(S, ≤) を順序集合partially orderedset; poset と言う．≤ が全順序であるとき (S, ≤) を全順序集合totally ordered set という．どの順序を指しているかが明らかな場合，(S, ≤) を単に S と書く場合もある．

(S, ≤) は順序集合であるとする．M は S の部分集合，かつ M 上の順序 ≤M が，任意の x, y ∈ M に対して，

x ≤M y⇐⇒x≤yを満たすとき，(M, ≤M ) を (S, ≤) の部分順序集合という．またこのような ≤M は，≤ を M 上に制限した順序であると呼ばれる．
定義 1.3.17 (上界，下界，上限，下限). (M, ≤M ) は (S, ≤) の部分順序集合であるとする．M の任意の要
素 x に対して，S の要素 y が x ≤ y を満たすとき，y を M の（ひとつの）上界upper bound であるという．
逆に M の任意の要素 x に対して，S の要素 y が y ≤ x を満たすとき，y を M の（ひとつの）下界lower

bound であるという．
S の要素 ∨M が S における M の上限supremum であるのは，∨M が

20

第1章 序

(1) 任意の x ∈ M に対して，x ≤ ∨M(2) M の任意の上界 x に対して，∨M ≤ xを満たすときである．

S の要素 ∧M が S における M の下限infimum であるのは，∧M が(1) 任意の x ∈ M に対して，∧M ≤ x(2) M の任意の下界 x に対して，x ≤ ∧Mを満たすときである．
事実 1.3.18. 任意の (M, ≤M ) に対して，(M, ≤M ) の上限および下限は存在するならば一意である．
例 1.3.19. (1) ⊆S は P(S) 上の部分集合関係であるとする．つまり任意の M, N ∈ P(S) に対して，

M ⊆S N⇐⇒M は N の部分集合が成り立つとする7 ．このとき ⊆S は P(S) 上の順序である．
S
T
また P(S) の任意の部分集合 M に対して M, M はそれぞれ M の上限，下限である．

(2) N は自然数全体の集合とする．また任意の x, y ∈ N に対してx≤y⇐⇒

x が y と等しいか，より小さいが成り立つとする．このとき ≤ は N 上の全順序である．
定義 1.3.20 (極大元，極小元，最大元，最小元). (S, ≤) は順序集合かつ s ∈ S とする．任意の x ∈ S に対して，s ≤ x ならば s = x が成り立つとき，s は S の極大元maximal element と呼ばれる．また任意のx ∈ S に対して，x ≤ s ならば s = x が成り立つとき，s は S の極小元minimal element と呼ばれる．また任意の x ∈ S に対して x ≤ s が成り立つとき，s は S の最大元maximum element と呼ばれる．また任意のx ∈ S に対して s ≤ x が成り立つとき，s は S の最小元minimum element と呼ばれる．
事実 1.3.21. (S, ≤) の最大元，最小元は存在するならば一意である．また (S, ≤) の最大元，最小元はそれぞれ (S, ≤) の極大元，極小元でもあるが，逆は必ずしも成り立たない．(S, ≤) の部分順序集合 (M, ≤M ) に最大元が存在するならば，それは (M, ≤M ) の上限でもある．しかし逆は必ずしも成り立たない．
例 1.3.22. R をすべての実数の集合，Z+ はすべての正整数の集合とする．≤ は R 上の大小関係とする．

M = {1 − 1/n | n ∈ Z+ } とし，≤M は ≤ を M 上に制限した順序関係とする．このとき (M, ≤M ) の上限は 1 である．しかし 1 は M に属していないので，M の最大元ではない．
定義 1.3.23 (整列集合). (S, ≤) が全順序集合であり，かつ S の任意の部分順序集合 (M, ≤M ) に最小元が存在するとき，S を整列集合well-ordered set と呼ぶ．
7 ⇐⇒ は必要十分条件を表す．必要十分条件については 35 頁を参照．

1.3. 集合論の用語解説

21

例 1.3.24. (1) 自然数の集合 N とその上の大小関係 ≤ に対して，(N, ≤) は整列集合である．しかし有理数の集合 Q とその上の大小関係 ≤ に対して，(Q, ≤) は整列集合ではない．たとえば ({x ∈ Q | 0 < x}, ≤) が最小元を持たない (Q, ≤) の部分順序集合である．
定義 1.3.25 (同値関係). S 上の二項関係 ∼ が反射性，対称性，推移性を持つとき，∼ は S 上の同値関係equivalent relation であるという．
例 1.3.26. 任意の x, y ∈ Z に対して，

x ≡3 y⇐⇒x を 3 で割った余りと y を 3 で割った余りが等しいが成り立つとする．このとき ≡3 は Z 上の同値関係である．
定義 1.3.27 (同値類). ∼ は集合 S 上の同値関係であるとする．このとき，任意の x ∈ S に対して，[x]∼ ={y ∈ S | x ∼ y} と定め，これを x の ∼ による同値類equivalent class と呼ぶ．またS/∼ = {[x]∼ | x ∈ S}
によって定められる集合 S/∼ を，S の ∼ による商集合quotient set と呼ぶ．
事実 1.3.28. ∼ は集合 S 上の同値関係であるとする．このとき任意の x, y ∈ S に対して，[x]∼ = [y]∼ ⇐⇒ x ∼ yが成り立つ．
定義 1.3.29 (関数). A × B の部分集合 f で，次の二つの条件を満たすものを A から B への関数function
または写像mapping, map と呼ぶ．

(1) 任意の a ∈ A に対して，ある b ∈ B が存在して ha, bi ∈ f ．
(2) 任意の a ∈ A, b, b0 ∈ B に対して，ha, bi ∈ f かつ ha, b0 i ∈ f ならば，b = b0 .
言い換えると A の各要素 a に対して，ha, bi ∈ f なる B の要素 b が唯一つ存在するときに f ⊆ A × B は関数である．

f が A から B への関数であることを f : A → B によって表す．またこのとき A を f の始領域domain ，
B を f の終領域codomain と呼ぶ．a ∈ A, b ∈ B に対して ha, bi ∈ f であるとき，b を f (a) と表す．
始領域が直積集合 A1 × A2 × · · · × An である場合，ha1 , a2 , . . . , an i ∈ A1 × A2 × · · · × An に対して，

f (ha1 , a2 , . . . , an i) は通常 f (a1 , a2 , . . . , an ) と表記される．
例 1.3.30. Z によってすべての整数からなる集合を表わし，Q によってすべての有理数からなる集合を表わす．このとき f : Z × (Z \ {0}) → Q, f (x, y) = xy と定めると f は Z × (Z \ {0}) を始領域として持ち，Qを終領域として持つ一つの関数である．しかし f : Z × Z → Q, f (x, y) = xy と定めると，例えば h1, 0i は始領域の要素であるが，終領域に f (1, 0) に対応する要素が存在しないので，これは関数の定義として失敗していることになる．

22

第1章 序

定義 1.3.31 (恒等関数). 任意の集合 A に対して，idA (a) = a(∀a ∈ A)によって定められる関数 idA : A → A を A 上の恒等関数identity function と呼ぶ．
定義 1.3.32 (関数の合成). f : A → B, g : B → C は関数であるとする．このとき g ◦ f : A → C を次のように定義する．

g ◦ f (a) = g(f (a))(∀a ∈ A)g ◦ f を f と g の合成composition と呼ぶ．
定義 1.3.33 (像，逆像). 関数 f : A → B と A の部分集合 M に対して，集合 {f (x) ∈ B | x ∈ M } を M の f
による像direct image とよび，f [M ] によって表す．また B の部分集合 N に対して，集合 {x ∈ A | f (x) ∈ N }
を N の f による逆像inverse image と呼び，f −1 [N ] によって表す．
事実 1.3.34. 任意の写像 f : A → B ，g : B → C ，h : C → D に対して以下の事実が成り立つ．

• idB ◦ f = f = f ◦ idA• h ◦ (g ◦ f ) = (h ◦ g) ◦ f• g ◦ f [M ] = g[f [M ]](∀M ⊆ A)• (g ◦ f )−1 [M ] = f −1 [g −1 [M ]](∀M ⊆ C)• f [M ∩ M 0 ] = f [M ] ∩ f [M 0 ], f [M ∪ M 0 ] = f [M ] ∪ f [M 0 ](∀M, M 0 ⊆ A)

• f −1 [M ∩ M 0 ] = f −1 [M ] ∩ f −1 [M 0 ], f −1 [M ∪ M 0 ] = f −1 [M ] ∪ f −1 [M 0 ](∀M, M 0 ⊆ B)

定義 1.3.35 (単射，全射，全単射). 関数 f : A → B が，任意の x, y ∈ A に対して，

f (x) = f (y) ならば x = yを満たすとき，f は単射injection または一対一の写像one-to-one mapping であるという．
また任意の x ∈ B に対して y ∈ A が存在して，

f (y) = xを満たすとき f は全射surjection または上への写像onto mapping であるという．

f が全射でありかつ単射であるとき，f は全単射bijection であるという．

23

第 2 章 論理的推論とは何か

2.1

Who’s Who

論理パズルの一つのパターンは与えられた証言から対象を特定する，という問題である．次の一連の問題は与えられた図の中の誰が誰かを証言から推理するというパズルである．このパズルをWho’s Who と呼ぶことにしよう．まずは簡単な例題から．
例 2.1.1. 与えられた図と証言をもとに，White，Orange，Red，Blue の 4 人が図のどこにいるかを推理してみよう．ただし以下の証言において，「X が Y に接する」というのは X が Y の上下左右のどこかにいる
とき，「X が Y の隣にいる」というのは X が Y の左右どちらかにいるときである．

(1)

Â¿
Â¿
r r
r r
§¦
§¦
ÁÀ
ÁÀ
a
b
Â¿
Â¿
r r
u u
§¦
§¦
ÁÀ
ÁÀ
c
d

証言 1：
「Blue はサングラスを掛けていない」
証言 2：「Orange はサングラスを掛けた者に接していない」
証言 3：「White は Orange の隣にいる」
証言 4：「Red は White の上下にはいない」
解答：a-Blue，b-Red，c-White，d-Orange．
この問題は比較的簡単に解が出せるように思われる．しかし実のところこの解に到るまでの過程にはな
かなか複雑な論理的推論が含まれている．この解を導出する一つの過程を簡単に記述してみよう．

1．証言 2 から Orange は a か d のどちらかであることが決定する．
2．そこで Orange が a だと仮定する．
3．このとき証言 3 から White は b になる．
4．従って証言 4 より Red は c ということになる．
5．従って残る Blue は d になる．

24

第 2 章 論理的推論とは何か

6．しかしこれは証言 1 と矛盾する．
7．従って Orange は a であるという仮定は誤りである．
8．従って Orange は d であることになる．
9．このとき証言 3 より White が c であることが分かる．
10．従って証言 4 より Red が b であることになる．
11．従って残る Blue が a になる．
ここで使われている重要な論理的推論の規則をいくつか挙げてみよう．上では 2 の仮定から矛盾が生じることが示され，それによって 2 が否定されている．このように，あることを仮定することによって矛盾が導かれるならば，その仮定の否定を結論してよい．これを背理法と呼ぶ．

1 で Orange が a または d であることが主張され，7 で Orange が a であることが否定されていることから Orange が d であることが導かれている．このように，二つの選択肢があり，その一方の可能性がないとすれば，他方を結論してよい．さらに一般的に言えば，複数の選択肢があり，そのひとつの選択肢の可能性がないとすれば，残りのどれかが成り立つことを結論してよい．これを選言三段論法と呼ぶ．
以下で良く使われる推論規則を挙げておく．α，β は任意の言明，非 α，非 β 等はその否定を表わすことにする．

R1（二重否定律）：非 α が成り立たないということから，α を推論してもよい．
R2（肯定三段論法）：α ならば β が成り立っており，かつ α が成り立っているということから，
β を推論してもよい．
R3（否定三段論法）：α ならば β が成り立っており，かつ非 β が成り立っているということから，非 α を推論してもよい．

R4（背理法）：α を仮定して β と非 β の両方が導かれるということから，非 α を推論しても良い．

R5（選言三段論法）：α または β のどちらかが成り立ち，さらに非 α が成り立っているということから，β を推論してもよい．

R6（ド・モルガンの法則 1）：α と β が同時には成り立たないということから，非 α または非β のどちらかが成り立つことを推論してもよい．逆も同様．
R7（ド・モルガンの法則 2）：α か β のどちらかが成り立つということはないということから，
非 α かつ非 β を推論してもよい．逆も同様．

R8（対偶律）：α ならば β が成り立っているということから，非 β ならば非 α を推論してもよい．逆も同様．

R9（排中律）：α か非 α のどちらかが成り立つということを推論してもよい．
R10（矛盾律）：α と非 α の両方が成り立つということはないということを推論してよい．つまり α と非 α の両方が成り立つということは矛盾であると推論してもよい．

2.1. Who’s Who25

R11（構成的ジレンマ）：α または β が成り立っており，かつ α と β のいずれを仮定しても γが導かれるならば，γ が成り立つことを推論して良い．
これらの規則以外にも，重要な論理規則はある．厳密な形式論理学の議論をするならば全ての推論規則を明示する必要があるが，とりあえずここではそうしない．またこれらの規則のあるものは他の規則によって置き換えが可能である．例えば二重否定律は，肯定三段論法，選言三段論法と排中律から帰結する．ただしここでは規則の数を最少限することが目的ではなく，規則を実際に適用して問題を解決することが目的なので，この点にも立ち入らない．論理的な推論規則の完全なリストに関しては後で扱う．
では実際に問題を解いてみよう．
問題 2.1.2. 上の例と同様に，図と証言から，誰が図のどこにいるかを推理せよ．またその推論の過程を詳しく書き出し，上の推論規則が使われているときはそのことを明記せよ．

(1)
Â¿
Â¿
r r
u u
§¦
§¦
ÁÀ
ÁÀ
a
b
Â¿
Â¿
r
e
r e
r r
§¦
§¦
ÁÀ
ÁÀ
c
d

証言 1：
「Red と Orange のどちらかはメガネを掛けている」
証言 2：「Blue は Orange の隣にいるか Red の隣にいるかのどちらかである」
証言 3：「Blue はメガネかサングラスのどちらかを掛けている」
証言 4：「Red と Blue は接していない」

(2)
Â¿
Â¿
e
r e
r
r r
§¦
§¦
ÁÀ
ÁÀ
b
a
Â¿
Â¿
r r
u u
§¦
§¦
ÁÀ
ÁÀ
c
d

証言 1：
「Orange と Red の両方がメガネを掛けていないということはない」
証言 2：「White と Red は隣り合っていない」
証言 3：「White がサングラスを掛けていないならば Blue はメガネを掛けている」
証言 4：「Blue は Red の上にいるか White の隣にいるかのどちらかである」

26

第 2 章 論理的推論とは何か

証言 5：「Orange と Blue は接していない」

(3)
Â¿
Â¿
r r
r r
§¦
§¦
ÁÀ
ÁÀ
a
b
Â¿
Â¿
re re
u u
§¦
§¦
ÁÀ
ÁÀ
c
d

証言 1：
「Red と Blue の少なくとも一方はメガネかサングラスを掛けている」
証言 2：「Orange は Blue か White の上下にいる」
証言 3：「Red は Orange の隣にはいない」
証言 4：「White は Red の下にいるか左にいるかのどちらかである」
証言 5：「Orange と Blue の両方がメガネもサングラスも掛けていないということはない」
以上で使われた推論規則は全て命題論理と呼ばれる分野の推論規則である．命題論理においては，私た
ちは個々の言明（命題）を単位として扱い，それらの命題に「かつ」「または」「ではない」「ならば」などの論理結合子を適用して新しい命題を作り，そのようにして出来た命題の性質を研究する．上の問題は全て命題論理の範囲で解決できる問題である．しかし命題論理の推論規則だけでは扱えない問題を作ることも出来る．
例 2.1.3. 以下の証言をもとに図の誰がサングラスを掛けており，誰が掛けていないかを推論しよう．
Â¿
Â¿

§¦
§¦
ÁÀ
ÁÀ
a
b
Â¿
Â¿
§¦
§¦
ÁÀ
ÁÀ
c
d

証言 1：
「少なくとも一人，サングラスを掛けているものがいる」
証言 2：「サングラスを掛けている者すべての上にはサングラスを掛けていないものがいる」
証言 3：「サングラスを掛けている者すべての左にはサングラスを掛けていないものがいる」
解答：a，b，c はサングラスを掛けていない．d はサングラスを掛けている．
この解は次のような推論の過程で導かれる．

1．証言 1 より a，b，c，d のうちの誰かはサングラスを掛けているということが分かる．

2.1. Who’s Who

27

2．a がサングラスを掛けているとする．
3．このとき証言 2 より，a の上にはサングラスを掛けていないものがいるということになる．
4．従って a，b，c，d のうちの誰かは a の上にいて，かつその者はサングラスを掛けていない．
5．しかし図から分かるように a も b も c も d も a の上にはいない．
6．従って a，b，c，d のうちの誰かが a の上にいるということはない（R7）．
7．これは矛盾である（R10）．
8．よって a はサングラスを掛けていない（R4）．
9．b がサングラスを掛けているとする．
10．このとき証言 2 より，b の上にはサングラスを掛けていないものがいるということになる．
11．従って a，b，c，d のうちの誰かは b の上にいて，かつその者はサングラスを掛けていない．
12．しかし図から分かるように a も b も c も d も b の上にはいない．
13．従って a，b，c，d のうちの誰かが b の上にいるということはない（R7）．
14．これは矛盾である（R10）．
15．よって b はサングラスを掛けていない（R4）．
16．c がサングラスを掛けているとする．
17．このとき証言 3 より，c の左にはサングラスを掛けていないものがいるということになる．
18．従って a，b，c，d のうちの誰かは c の左にいて，かつその者はサングラスを掛けていない．
19．しかし図から分かるように a も b も c も d も c の左にはいない．
20．従って a，b，c，d のうちの誰かが c の左にいるということはない（R7）．
21．これは矛盾である（R10）．
22．よって c はサングラスを掛けていない（R4）．
23．よって d はサングラスを掛けている（R5）．
ポイントは「全ての...」とか「... が存在する」といった表現である．このような表現を含む言明についての規則の取り扱いは命題論理の範囲を超えている．これらは述語論理で取り扱われなければならない．命題論理が言明を単位として扱うのに対して，述語論理は言明を，対象名（個体を指示する記号）と述語（属性を指示する記号）に分析して扱う．ここでは述語論理で用いられる次の 6 個の規則を挙げておこう．

R12（存在一般化）：考慮している対象のうちのどれかが C という条件を満たすということから，C を満たす対象が存在するということを推論してよい．

R13（存在特例化）：条件 C を満たす対象が存在するということから，考慮している対象
t1 , t2 , . . . , tn の中のどれかが C を満たすことを推論してよい．

28

第 2 章 論理的推論とは何か

R14（全称一般化）：考慮している対象 t1 , t2 , . . . , tn の任意のものについて条件 C が成り立つということから，全ての対象が C を満たすことを推論してよい．

R15（全称特例化）：全ての対象について条件 C が成り立つということから，考慮している対象 t1 , t2 , . . . , tn のいずれについても C が成り立つことを推論してよい．

R16（一般化されたド・モルガンの法則 1）：全ての対象が条件 C を満たすわけではない，ということから C を満たさない対象が存在することを推論してよい．逆も同様．

R17（一般化されたド・モルガンの法則 2）：条件 C を満たす対象が存在しないということから，どの対象も C を満たさないということを推論してよい．逆も同様．
上の論証では 3，10，17 において全称特例化が，4，11，18 において存在特例化が使われている（ただし述語論理で標準的な存在特例化の規則はここで述べられたような形式ではないのであるが，ここでは詳し
くは論じない）．
さて，以上の問題に関して，論理的な推論規則を使うことによって解を発見することができることを私た
ちは見てきた．誰が図のどこにいるかを考える問題は，図の 4 箇所に 4 人の人間を並べる問題であるから，可能な配列は 4 の階乗通り，つまり 4 × 3 × 2 × 1 = 24 通り存在する．また誰がサングラスを掛けており，
誰が掛けていないかを推理する問題では，4 人のそれぞれについてサングラスを掛けている可能性と掛けていない可能性があり，従って全部で 16 通りの可能性がある．従って前者の問題に関しては 24 通りの可能性全てについて，後者については 16 通りの可能性の全てについて，証言と矛盾しないかどうかを調べることによっても解くことが出来る．実際，前問の (2) などはそのように解いた方が早く解けるかもしれない．
しかし問題がより複雑になると，そのような枚挙による方法では効率が悪い．次の例を考えてみよう．
例 2.1.4. 与えられた図と証言をもとに，Violet，White，Orange，Blue，Pink，Yellow，Green，Scarlet，

Red の 9 人が図のどこにいるか推理しよう．
Â¿
Â¿
Â¿
u u
r r
r r
§¦
§¦
§¦
ÁÀ
ÁÀ
ÁÀ
b
c
a
Â¿
Â¿
Â¿
r r
r r
u u
§¦
§¦
§¦
ÁÀ
ÁÀ
ÁÀ
d
e
f
Â¿
Â¿
Â¿
r r
u u
r r
§¦
§¦
§¦
ÁÀ
ÁÀ
ÁÀ
g
h
i

証言 1：
「Pink はサングラスを掛けた者に接していない」
証言 2：「Blue の隣の隣にはサングラスを掛けていない者（Blue 本人ではない）がいる」
証言 3：「Violet は Pink の上にいる」
証言 4：「Red は Blue の斜め上にいる」

2.1. Who’s Who

29

証言 5：
「Green と White は同じ横列にいる」
証言 6：「Yellow は Red の下の下にいる」
証言 7：「Scarlet は White と同じ縦列にいる」
解答：a-Violet，b-Red，c-Scarlet，d-Pink，e-Orange，f-Blue，g-Green，h-Yellow，i-White．
この問題では 9 箇所に 9 人を配置しなければならない．可能な並べ方は 9 の階乗通り，すなわち 362,880
通りある．この配置をひとつずつ証言と照らして正しい配置を探すのはあまりにも非効率的である．このような場合はやはり与えられた証言から徐々に条件を狭めていく方が良い．
この解は次のような推論によって導かれる．
まず Blue の位置を考えよう．証言 6 より Red は a，b，c のどれかである．従って証言 4 より Blue は d，e，f のどれか．これと証言 2 より Blue は f であると決定できる．またこれより Red は b であることが分かる．さらに証言 6 より h は Yellow と決まる．
次に Pink について考えよう．証言 1 より Pink は b，d，f，h のどれか．しかし b，f，h は既にそれぞれ

Red，Blue，Yellow と決まっているので Pink は d である．これと証言 3 より a は Violet であると分かる．
残りについては証言 5 と 7 から直ちに c が Scarlet，g が Green，i が White であると決定できる．
問題 2.1.5. 上の例と同様，図と証言をもとに誰が図のどこにいるかを推理せよ．

(1)
Â¿
Â¿
Â¿
r r
r r
r r
§¦
§¦
§¦
ÁÀ
ÁÀ
ÁÀ
a
b
c
Â¿
Â¿
Â¿
u u
u u
r r
§¦
§¦
§¦
ÁÀ
ÁÀ
ÁÀ
d
e
f
Â¿
Â¿
Â¿
r r
r r
e
r e
r
§¦
§¦
§¦
ÁÀ
ÁÀ
ÁÀ
g
h
i

証言 1：
「Red はメガネかサングラスを掛けている」
証言 2：「Pink は White に接している」
証言 3：「Scarlet と Blue は同じ横列にいる」
証言 4：「Yellow の隣にはサングラスを掛けている者がいる」
証言 5：「Yellow と Violet は同じ横列にいる」
証言 6：「White は Scarlet と Red にはさまれている（ただし縦，横，斜めのどれかは分からない）」
証言 7：「Orange は Yellow の上にいる」

(2)

30

第 2 章 論理的推論とは何か

Â¿
Â¿
Â¿
r r
u u
r r
§¦
§¦
§¦
ÁÀ
ÁÀ
ÁÀ
a
b
c
Â¿
Â¿
Â¿
e
r e
r
r r
r r
§¦
§¦
§¦
ÁÀ
ÁÀ
ÁÀ
d
e
f
Â¿
Â¿
Â¿
r r
u u
r r
§¦
§¦
§¦
ÁÀ
ÁÀ
ÁÀ
g
h
i

証言 1：
「White と Scarlet は隣り合っている」
証言 2：「Violet は横列の端にいる」
証言 3：「Pink はメガネを掛けた者とサングラスを掛けた者の両方に接している」
証言 4：「Pink と Green は同じ横列にいる」
証言 5：「Scarlet はサングラスを掛けた者とは接していない」
証言 6：「Pink は Violet の下にいる」
証言 7：「Yellow は Blue と Violet の両方に接している」
証言 8：「Blue と Red は同じ横列にいる」
証言 9：「Blue はサングラスを掛けた者とは接していない」
証言 10：「Orange はサングラスを掛けていない」

(3)
Â¿
Â¿
Â¿
r r
r r
u u
§¦
§¦
§¦
ÁÀ
ÁÀ
ÁÀ
b
c
a
Â¿
Â¿
Â¿
r r
re re
r r
§¦
§¦
§¦
ÁÀ
ÁÀ
ÁÀ
d
e
f
Â¿
Â¿
Â¿
r r
u u
r r
§¦
§¦
§¦
ÁÀ
ÁÀ
ÁÀ
g
h
i

証言 1：
「Orange は四隅のどこかにいる」
証言 2：「Red は Blue と接していない」
証言 3：「Scarlet は Green と同じ横列にいる」
証言 4：「White はサングラスを掛けていなければメガネを掛けている」

2.2. 命題論理の体系

31

証言 5：
「Violet はサングラスを掛けた者に接していない」
証言 6：「Orange は Violet と同じ横列にいる」
証言 7：「White は Green か Red の上にいる」
証言 8：「Pink と Red は同じ横列にいる」
証言 9：「Violet は少なくとも 3 人に接している」
証言 10：「Blue は Scarlet よりも接している相手の数が多い」
証言 11：「Yellow は Red と接している」
以上の問題はすべて解が一意的に定まるように作られている．しかし証言の与え方によっては解が一意的に定まらないような問題を作ることもできる．解が一意的に定まるようにしながら，ある程度の難易度を問題に持たせるためには相応の工夫が必要である．そこで次の問題を考えてもらおう．
問題 2.1.6. 上の問題に習って，Who’s Who の問題を作れ．その際，解が一意的に定まるように気をつけること．コツは，最初に簡単に解が分かるような証言を作っておいて，後から複雑にしていくことである．

2.2

命題論理の体系

前節では論理的な推論規則に従って，実際に推論を行った．しかし上では論理的な推論の基準というもの
は示されていない．ここでそのような基準を与えることを試みよう．
推論とは，与えられた前提から，一定の帰結を導くことである．その際，私たちは何かしらの規則に従って推論を行っていることが多い．推論には大きく次の二種類がある．
必然的推論：前提がすべて正しければ結論も必ず正しい．
蓋然的推論：前提がすべて正しくても結論が必ず正しいとは限らない．
前節で上げた推論規則はすべて必然的推論の例である．形式論理学で扱う推論は必然的な推論である．以下では必然的推論を論理的推論と同一視する．
論理的推論のパターンは無限にたくさんある．ある推論が与えられたときに，それが論理的推論であるかどうかを判断する明確な基準はなんだろうか？
このことを考えやすくするために，以下では形式化された言語を作り，その言語の文に意味を与えるための規則を与える．また簡単のために前節の R1 から R10 の規則で表現されるタイプの推論だけを考え，R11
から R16 の規則によって表現されるタイプの推論は扱わない．

2.2.1

命題論理の言語 L

本小節では，命題論理において扱われる言語 L を定義する．
定義 2.2.1 (言語 L の文).

(1) >, ⊥, A, B, C, D, A1 , B1 , C1 , D1 , A2 , B2 , C3 , D3 , ... は文記号と呼ばれる．文記号はすべて L の文である．>, ⊥ は特に文定数，それ以外は文変数と呼ばれる．

32

第 2 章 論理的推論とは何か(2) α, β が L の文であるとき，(¬α), (α ∧ β), (α ∨ β), (α ⊃ β), (α ≡ β) は L の文である1 ．
(3) 以上によって L の文であると決定されるものだけが L の文である．
¬, ∧, ∨, ⊃ を L の結合子と呼ぶ．また (¬α) の形式の文を否定，(α ∧ β) の形式の文を連言，(α ∨ β) の形
式の文を選言，(α ⊃ β) の形式の文を条件文または含意，(α ≡ β) の形式の文を双条件文または同値文と呼ぶ．条件文 (α ⊃ β) に対して，α を (α ⊃ β) の前件，β を (α ⊃ β) の後件と呼ぶ．
［補足］
数学や論理学では無限に多くの対象からなる集まりを取り扱う．その際，帰納的定義または再帰的定義という方法がよく使われる．上の L の文の定義は帰納的定義である．帰納的定義は次の二つの手順からなっている．

(i) 基本的な対象について定義を与える．
(ii) 既に定義が与えられた対象を使って，新しい対象を定義する．
例えば上ではまず (1) で >, ⊥, A, B, . . . が L の文の基本的な対象として定義されている．ここから (2)によって (¬A), (B ∨ ⊥) などが L の文であるとされる．さらにこれらが L の文であることから，再び (2)によって ((¬A) ∧ (B ∨ ⊥))，((B ∨ ⊥) ⊃ (¬A)) などが L の文であるとされる．このようにして私たちは無限に多くの L の文を手に入れるのである．
帰納的に定義された対象の集まりに対して，帰納法と呼ばれる証明が可能になる．この証明は次の二つの手順からなっている．

Base：基本的な対象についてある性質 P が成り立つことを示す．
Step：ある対象について性質 P が成り立つと仮定し，その対象を使って定義される新しい対象についても性質 P が成り立つということを示す．
これによって考慮しているすべての対象について，性質 P が成り立つことが証明できるのである．
例 2.2.2. L の任意の文 α に対して，α に現れる結合子の数を C(α) によって表し，これを α の長さと呼ぶことにする．α に現れる文記号の数の合計を S(α) によって表すことにする．このとき，¬ を含まない任意の L の文 α に対して，S(α) = C(α) + 1 が成り立つ，ということを帰納法を使って証明しよう．
証明

α の長さに関する帰納法で示す．

(Base): α の長さが 0，すなわち C(α) = 0 の時．このとき α は単独の文記号だから，S(α) = 1．よってS(α) = C(α) + 1 が成り立っている．
(Step): 長さ n 以下の任意の文 δ に対して，δ に ¬ が現れないならば S(δ) = C(δ) + 1 が成り立っていると仮定する（帰納法の仮定）．

α は長さが n + 1 で，α に ¬ は現れないものとする．α には少なくとも一個の結合子が現われ，それは ¬ではないので，α は (β ∗ γ) という形をしていることが分かる．ただしここで ∗ は ∧, ∨, ⊃, ≡ のいずれかを表すものとする．α が ¬ を含まないので，β, γ も ¬ を含まない．また α の長さが n + 1 なので，β ，γ の長さは n 以下．よって帰納法の仮定より，S(β) = C(β) + 1, S(γ) = C(γ) + 1 が成り立つ．
1 α, β, . . . は任意の文を表すために用いられる変数で，これらの記号自体は L の言語の構成要素ではない．数学で任意の数を表すのに x, y などの文字を用いるのと同様である．

2.2. 命題論理の体系

33(β ∗ γ) に現れる文記号の数の合計は，明らかに β に現れる文記号の数の合計と，γ に現れる文記号の数の合計の和に等しい．よって S(α) = S(β) + S(γ)．一方，(β ∗ γ) に現れる結合子の数は β に現れる結合子の数と γ に現れる結合子の数の和よりも，∗ の分だけ多い．よって C(α) = C(β) + C(γ) + 1．従ってS(α)= S(β) + S(γ)= (C(β) + 1) + (C(γ) + 1)
= (C(β) + C(γ) + 1) + 1= C(α) + 1

以上から L の任意の文 α に対して，α が ¬ を含まないならば S(α) = C(α) + 1 が成り立つことが示された．

上の規則によって例えば (A ∧ (B ⊃ C)), (¬(B ∨ (A ⊃ A))) などが L の文であることが分かる．一方，(A¬)，(B ∧ C ，(⊃ A) などは L の文ではない．以下では L の文のことを単に文と呼ぶ．
文が複雑になると括弧が多くなって煩雑である．そこで以下のように，括弧を省略するための規則を定める．
括弧省略の規則(1) 文の一番外側の括弧は省略してもよい．
(2) (¬α) は ¬α と略記してもよい．
(3) ∗ が ¬, ∧ 以外の結合子であるとき，((α ∧ β) ∗ γ)，(α ∗ (β ∧ γ)) を，それぞれ (α ∧ β ∗ γ)，(α ∗ β ∧ γ)と略記してもよい．

(4) ∗ が ¬, ∧, ∨ 以外の結合子であるとき，((α ∨ β) ∗ γ)，(α ∗ (β ∨ γ)) を，それぞれ (α ∨ β ∗ γ)，(α ∗ β ∨ γ)と略記してもよい．

(5) ((α ⊃ β) ≡ γ)，(α ≡ (β ⊃ γ)) を，それぞれ α ⊃ β ≡ γ)，(α ≡ β ⊃ γ) と略記してもよい．
(6) ∗ を任意の結合子とするとき，(α ∗ (β ∗ γ)) を，(α ∗ β ∗ γ) と略記してもよい．
例 2.2.3. (¬(¬((A ∧ B) ⊃ (B ⊃ (A ∨ (B ∨ C)))))) の括弧を出来る限り省略してみよう．
まず (1) によって一番外側の括弧を省略することができる．したがってこの文は¬(¬((A ∧ B) ⊃ (B ⊃ (A ∨ (B ∨ C)))))と等しい．次に (2) によって (¬((A ∧ B) ⊃ (B ⊃ (A ∨ (B ∨ C))))) の外側の括弧を省略することが出来る．
従ってこれは¬¬((A ∧ B) ⊃ (B ⊃ (A ∨ (B ∨ C))))に等しい．(3) によって (A ∧ B) の括弧を省略できる．従ってこれは

34

第 2 章 論理的推論とは何か¬¬(A ∧ B ⊃ (B ⊃ (A ∨ (B ∨ C))))に等しい．(4) によって (A ∨ (B ∨ C)) の外側の括弧を省略できる．従ってこれは¬¬(A ∧ B ⊃ (B ⊃ A ∨ (B ∨ C)))に等しい．最後に (6) によって (B ⊃ A ∨ (B ∨ C)) の括弧をすべて省略できる．従ってこれは¬¬(A ∧ B ⊃ B ⊃ A ∨ B ∨ C)に等しい．
問題 2.2.4. 以下の文の括弧を可能な限り省略せよ．

(a)(A ∧ (¬(A ∨ B)))(b)

(A ⊃ ((¬B) ∨ (C ≡ D)))(c)((A ∨ B) ⊃ (¬(¬((C ∧ B) ∧ D))))(d)((A ⊃ (B ⊃ C)) ⊃ ((A ⊃ B) ⊃ (A ⊃ C)))(e)(((A ∧ B) ∨ C) ⊃ ((A ≡ (B ⊃ D)) ≡ A))(f)((¬((¬A) ∧ (¬B))) ≡ (A ∨ B))

問題 2.2.5. 以下の文において省略されている括弧をすべて復元せよ．

(a)A ⊃ B ∨ C ≡ B ∧ ¬A(b)¬¬A ∧ B ∨ C ∨ C ⊃ D(c)(A ⊃ B ⊃ C) ⊃ A ∧ B ⊃ C(d)¬(A ⊃ ¬B ∨ C) ⊃ A ⊃ B ∧ ¬C(e)

A ∧ B ≡ ¬C ≡ D ⊃ A ∨ B(f)¬(A ⊃ B) ∨ C ∧ D ≡ C ⊃ D ⊃ D

2.2.2

L に対する意味論

以上で命題論理の言語 L が定義された．このようにある記号体系を与えるための理論を構文論という．
しかし，ここで定義された記号がどのような意味を持つかということは，まだ説明されていない．ある記号体系に対して，その意味を付与する理論を意味論という．以下では L に対する意味論を提示しよう．
結合子を含んだ文の直観的な意味は次の通りである．以下はインフォーマルな説明であり，定義ではない．

¬α：α ではない
α ∧ β ：α かつ βα ∨ β ：α または βα ⊃ β ：α ならば βα ≡ β ：α ならば β ，かつ β ならば α
この意味づけに従って，前節の規則 R6（ド・モルガンの法則 1）を書き換えてみよう．R6 は次のような規則だった．

α と β が同時には成り立たないということから，非 α または非 β のどちらかが成り立つことを推論してもよい．逆も同様．

2.2. 命題論理の体系

35

まず前半の前提の部分に注目しよう．
「α と β が同時には成り立たない」は「α と β が同時に成り立つ」ということの否定である．
「α と β が同時に成り立つ」ということは「α かつ β 」と言い換えられる．すなわ
ち「α ∧ β 」である．従ってその否定は「¬(α ∧ β)」と書ける．前半の帰結は「α ではない，または，β ではない」と読めるから，「¬α ∨ ¬β 」と書ける．従ってこの規則の前半は，¬(α ∧ β) から ¬α ∨ ¬β を推論してもよいと言い換えられる．後半は前提と帰結を逆にして，¬α ∨ ¬β から ¬(α ∧ β) を推論してもよいと表現できる．
問題 2.2.6. 上の例にならって前節の R1-R5，R7，R8，R11 の推論規則を言い換えよ．

L の文に対する意味論を与えよう．L の文について，私たちはその文の内容は問題にせず，その真偽のみを考慮する．ここでは文の意味とは，その文の真偽のことである．文の真偽のことを以下では真理値と呼ぶ．真理値は t と f という二つの値のどちらかである．ここまではある文が「正しい」とか「成り立つ」
とかいう表現を使ってきた．以後はこれをある文が「真である」または「真理値 t を持つ」と言うことにする．またある文が「正しくない」ということは，「偽である」または「真理値 f を持つ」ということにする．
結合子は，その結合子が適用される文の真理値に対する計算の仕方を表すものと考える．文変数 A, B, C, . . .
の真理値は任意に決めることが出来る．しかしそれらは必ず t か f のどちらかの真理値（そして一方だけ）を持つものとされる．文変数の各々に対して t か f のどちらかの真理値を与える方法を真理値付値または
単に付値という．任意の真理値付値 v に対して，文変数以外の文の真理値は次の規則に従って計算される．
定義 2.2.7 (真理値計算の規則).

(1) v は > に真理値 t を与え，⊥ に真理値 f を与える．
(2) v が ¬α に真理値 t を与える⇐⇒

v が α に真理値 f を与える．

(3) v が α ∧ β に真理値 t を与える⇐⇒

v が α と β の両方に真理値 t を与える．

(4) v が α ∨ β に真理値 t を与える⇐⇒

v が α と β の少なくとも一方に真理値 t を与える．

(5) v が α ⊃ β に真理値 t を与える⇐⇒

v が α に真理値 f を与えるか，または v が β に真理値 t を⇐⇒

v が α と β に同じ真理値を与える．

与える．

(6) v が α ≡ β に真理値 t を与える

以上の規則によって，任意の真理値付値 v に対して，L のすべての文の真理値が一意的に決定する．これは文の構成に関する帰納法によって証明できる．
真理値付値 v が文 α に真理値 t または f を与えるということを v(α) = t または v(α) = f と表す．
［補足］⇐⇒ はこの記号の両辺が互いの必要条件かつ十分条件であるということを表している．必要条件，十分条件という概念は数学や論理学において証明を行うときに重要な概念である．ここで，これらについて少し説明しておこう．

36

第 2 章 論理的推論とは何か

必要条件と十分条件

X が Y の必要条件であるというのは，Y が成り立つときには必ず X が成り立っているということである．
言い換えれば，X が成り立たずに Y が成り立つことはないということである．

X が Y の十分条件であるというのは，X が成り立つときには必ず Y が成り立っているということである．
言い換えれば，Y が成り立たずに X が成り立つことはないということである．
従って「X が Y の必要条件である」ということは「Y が X の十分条件である」ということに等しい．従って「X が Y の必要十分条件である」ということと「Y が X の必要十分条件である」ということは互いに等しい．

X が Y にとって十分条件であるということを証明するには，X が成り立っていると仮定して，そのときには必ず Y が成り立つことが導かれることを示せばよい．または Y が成り立たないと仮定して，そのときには決して X が成り立たないことを示せばよい．
従って X にとって Y が必要十分条件であることを示すには，典型的には次の二つの方法がある．

(1) X が成り立つと仮定し，そのときには必ず Y が成り立つこと示す．さらに Y が成り立つと仮定し，そのときには必ず X が成り立つことを示す．

(2) X が成り立つと仮定し，そのときには必ず Y が成り立つことを示す．さらに X が成り立たないと仮定し，そのときには決して Y が成り立たないことを示す．
それぞれの例を上げよう．
例 2.2.8. 「任意の自然数 x, y について，x が y の約数であるための必要十分条件は，x2 が y 2 の約数になっていることである」の証明を考えよう．
証明

x が y の約数であると仮定する．このときある自然数 k が存在して y = k · x が成り立つ．このとき

y 2 = (k · x)2 = k 2 · x2 ．k が自然数だから k 2 も自然数である．従って x2 は y 2 の約数である．これで必要条件の部分が示された．

√
逆に x2 が y 2 の約数であるとする．このときある自然数 k が存在して y 2 = k · x2 ．よって y = k · x2 =√√k · x．x, y が自然数なので， k は自然数でなければならない．よってこのとき x は y の約数である．これで十分条件の部分が示された．
例 2.2.9. 「任意の整数 x に対して，x が偶数であるための必要十分条件は x2 が偶数であることである」の証明を考えよう．
証明

x が偶数であるとする．このときある整数 k が存在して，x = 2 · k が成り立つ．従って x2 = (2 · k)2 =2 · (2 · k 2 )．k が整数なので，2 · k 2 も整数．従って x2 は偶数である．これで必要条件の部分が示された．
逆に x が偶数ではないとしよう．このときある整数 k が存在して，x = 2 · k + 1 が成り立つ．従ってx2 = (2 · k + 1)2 = 2 · (2 · k 2 + k) + 1．k が整数なので，2 · k 2 + k も整数．よって x2 は偶数ではない．これで十分条件の部分が示された．
問題 2.2.10. 以下の文章の（ ）内に(a) 必要条件であるが十分条件ではない(b) 十分条件であるが必要条件ではない

2.2. 命題論理の体系

37(c) 必要十分条件である(d) 必要条件でも十分条件でもないのいずれかを入れよ．

(1) ポチが犬であることは，ポチが哺乳類であるための（ ）．
(2) 太郎が次郎の兄であることは，次郎が太郎の弟であるための（ ）．
(3) ジョンがメアリーの夫であることは，メアリーがジョンの妻であるための（ ）．
(4) 任意の整数 x, y に対して，x ≤ y が成り立つことは，x < y + 1 が成り立つための（ ）．
(5) 任意の有理数 x, y に対して，x ≤ y が成り立つことは，x < y + 1 が成り立つための（ ）．
(6) 付値 v が文変数 A に真理値 t を与えることは，v が文 A ∧ B に真理値 t を与えるための（ ）．
(7) 付値 v が文変数 A に真理値 f を与えることは，v が文 A ∧ B に真理値 t を与えるための（ ）．
(8) 付値 v が文変数 A に真理値 f を与えることは，v が文 A ⊃ B に真理値 t を与えるための（ ）．
(9) 付値 v が文変数 A に真理値 f を与えることは，v が文 A ∨ B に真理値 t を与えるための（ ）．
(10) 付値 v が文変数 A に真理値 t を与えることは，v が文 A ≡ B に真理値 t を与えるための（ ）．

例 2.2.11. v は真理値付値で，v(A) = t, v(B) = f とする．このとき v(¬A), v(¬B), v(A ∧ B), v(A ∨B), v(A ⊃ B), v(A ≡ B) の値を考えよう．
¬A について．v(A) = t だから，真理値計算の規則 (2) より，v(¬A) = f ．
A ∧ B について．v(A) = t，v(B) = f だから，真理値計算の規則 (3) より，v(A ∧ B) = f ．
同様に真理値計算の規則 (4)(5)(6) より，v(A ∨ B) = t, v(A ⊃ B) = f, v(A ≡ B) = f となる．
真理値計算の規則は以下の表によっても表現することが出来る．以下の表の一つの横列は，ある真理値付値に対応していると考えることが出来る．

α

¬α

α

β

α∧β

α

β

α∨β

t

f

t

t

t

t

t

t

f

t

t

f

f

t

f

t

f

t

f

f

t

t

f

f

f

f

f

f

α

β

α⊃β

α

β

α≡β

t

t

t

t

t

t

t

f

f

t

f

f

f

t

t

f

t

f

f

f

t

f

f

t

このように，複合的な文と，その構成要素になっている文の真理値を，結合子の規則に従って対応させた
表を真理表と呼ぶ．

38

第 2 章 論理的推論とは何か

私たちは単純な文 A, B, C, . . . から始めて，結合子を繰り返し用いることで新しい文を無限に生成することができる．しかしそれらの文の真理値はすべてその構成要素になっている文記号の真理値に基づいて決定される．任意の文の真理値は真理表を作成することによって容易に確かめられる．
例 2.2.12. (¬(A ⊃ B)) の真理表．

A

B

A⊃B

¬(A ⊃ B))

t

t

(a)

(b)

t

f

(c)

(d)

f

t

(e)

(f)

f

f

(g)

(h)

括弧の付き方からこの文は，条件文 A ⊃ B の否定だと分かる．そこでまず A ⊃ B の真理値を調べよう．
これは A が真で B が偽のときのみ偽になり，それ以外は真になるのだった．そこで A ⊃ B の下にそのように書き込んでいけばよい．つまり (c) に f を書き，(a)(e)(g) には t を書き込むのである．次に ¬(A ⊃ B)の下には，(a)(c)(e)(g) の真理値を逆にしたものをそれぞれ (b)(d)(f)(h) に書き込めばよい．従って出来上がった真理表は次のようになる．

A

B

A⊃B

¬(A ⊃ B))

t

t

t

f

t

f

f

t

f

t

t

f

f

f

t

f

問題 2.2.13. 上の方法にならって以下の文が表現する真理表を作れ．

(a)¬(A ∨ B)(b)¬(A ∧ B)(c)

¬A ∨ ¬B(d)¬A ∧ ¬B

(e)

A⊃B⊃C

(f)

A ⊃ ¬(B ∧ C)(g)¬(A ∧ ¬A)(h)¬(A ∨ ¬A)(i)¬(A ≡ B)

(j)

A≡B≡C

2.2.3

論理的推論の特徴づけ

以上の準備のもとに，論理的推論がどのように特徴付けられるかを見てみよう．推論とは一定の前提から一定の帰結を導くものであり，論理的推論とは前提のすべてが真であるときは，結論が必ず真になるものである．このことを形式的に表現すると以下のようになる．
定義 2.2.14 (論理的含意，論理的帰結). 任意の真理値付値 v に対して，v(α1 ) = v(α2 ) = · · · = v(αn ) = t
ならば v(β) = t が成り立つとき，文 α1 , α2 , . . . , αn は文 β を論理的に含意するという．

α1 , α2 , . . . , αn が β を論理的に含意するということを，2.2. 命題論理の体系

39

α1 , α2 , . . . , αn |= βによって表現する．α1 , α2 , . . . , αn |= β が成り立っているとき，β は α1 , α2 , . . . , αn からの論理的帰結であるという．
言語 L における私たちの推論が論理的であるというのは，その前提が帰結を論理的に含意する時である．
例 2.2.15. A ∧ B, C ∧ D から A ∧ C が論理的に推論できることを確かめよう．
まず A ∧ B, C ∧ D が真理値 t を持つとする．このとき ∧ の真理値計算の規則より，A, B, C, D はすべて
真理値 t を持つことが分かる．従って再び ∧ の真理値計算の定義より，A ∧ C が真理値 t を持つことが分
かる．
問題 2.2.16. 推論規則 R1，R2，R3，R5，R6，R7，R8 によって表されている推論が論理的推論になっていることを確かめよ．
問題 2.2.17. 以下が成り立つことを確かめよ．またこれらの表す直観的な意味は何かを答えよ．

(a) α, β |= α ∧ β(b) α ∧ β |= α(c) α |= α ∨ β(d) α ⊃ β, β ⊃ γ |= α ⊃ γ(e) α ⊃ β, β ⊃ α |= α ≡ α(f) α ≡ β |= ¬α ≡ ¬β(g) α ∨ β, α ⊃ γ, β ⊃ γ |= γ(h) α ⊃ ⊥ |= ¬α

2.2.4

トートロジー

上の論理的含意の例で n = 0 のときは，前提がない推論になる．例えば推論規則 R9，R10 はこれに相当する．前提なしに β を結論することが論理的推論であるというのは，任意の真理値付値 v に対して v(β) = tが成り立つということである．このような場合，β はトートロジーであると呼ばれる．

β がトートロジーであることを|= βによって表す．
例 2.2.18. α ⊃ α がトートロジーであること，すなわち |= α ⊃ α が成り立つことを確かめよう．

v は任意の真理値付値であるとする．v(α) = t とする．このとき α ⊃ α の後件が真理値 t を持つことになるから，条件文の真理値計算の規則により v は α ⊃ α に真理値 t を与える．

v(α) = f とする．このとき α ⊃ α の前件が真理値 f を持つことになるから，条件文の真理値計算の規則
により v は α ⊃ αni 真理値 t を与える．

40

第 2 章 論理的推論とは何か

従っていずれの場合も v は α ⊃ α に真理値 f を与えることになる．よって α ⊃ α は任意の真理値付値に対して真理値 t を持つ．よって |= α ⊃ α が成り立つ．
問題 2.2.19. 規則 R9，R10 が表す推論が前提なしの論理的推論，すなわちトートロジーになっていることを確かめよ．
問題 2.2.20. 以下が成り立つことを確かめよ．

(a) |= (> ∧ α) ≡ α(b) |= (⊥ ∨ α) ≡ α(c) |= α ⊃ (¬α ⊃ β)(d) |= (α ∧ (β ∨ γ)) ≡ ((α ∧ β) ∨ (α ∧ γ))(e) |= (α ∨ (α ∧ β)) ≡ α(f) |= (α ∧ (α ∨ β)) ≡ α
以上によって命題論理における論理的推論の特徴づけが出来た．ポイントは次の通りである．

• 推論とは，ある前提（0 個でも複数個でも良い）からある結論（ここでは一つの推論に対して結論は一つであると考えた）を導き出すことである．

• 前提や帰結を構成するのは文である．従って任意の推論は，ある文 α1 , α2 , . . . , αn から，ある文 β を導き出すこと，として表現される．例えば肯定三段論法は，任意の文 α, β に対して，α ⊃ β, α からβ を導き出す推論である．
• 論理的推論とは，前提を構成する文がすべて真である時には結論も必ず真であるような推論である．
より詳しく言えば，ある推論が論理的ならば，前提と結論を構成する文変数に対する任意の真理値付
値 v に対して，v が前提を構成する文をすべてに真理値 t を与えるならば，v は結論を構成する文にも t を与える．言い換えれば，前提を構成する文をすべてに t を与えながら，結論を構成する文に fを与えるような真理値付値 v は存在しない．

• 文の真偽は，それぞれの文を構成する文変数に対する真理値付値によって一意的に決定される．
• トートロジーとは空なる前提からの論理的帰結である．
しかしながら実際に私たちはこのような仕方で，それが論理的であるかを確かめながらいちいち推論を行っているわけではない．実際に推論を行うとき，私たちは一定の基本的な規則を受け入れ，その規則の適用を積み重ねることによって推論を行っているのである．それでは論理的推論を行うために必要かつ十分であるような基本的原則の組み合わせというのはどのようなものだろうか？ またそれが必要かつ十分であるということはどのようにして確かめられるのだろうか？ 次節以降ではこの問題を考えよう．

41

第 3 章 形式的体系における導出

前節では論理的推論を使って図と証言から問題の答えを探すということを行った．そこでは図の見方，証言で使われる言語，そして論理的推論についての私たちの常識的な理解を前提としていた．従って正しい論証であるかどうか，つまり推論のあるステップが正確に論理的なものであるかどうかの判断には食い違いが生じる可能性があった．証明が厳密であるためには，このような論証の過程がすべて明示化され，正しいと明確に認められる推論以外はどのステップでも使われていないということが誰の目にも明らかにならなければならない．数学においてこのことを目指したのがペアノ，フレーゲなどの現代論理学の創始者たちである．
現代論理学の革命は，従来常識的な理解に頼っていたことすべてを明示化するという努力から始まった．
彼らが使った方法は，公理的方法として知られているものである．公理的方法とは，ある知識体系

理を整理するために，いくつかの前提（公理）を立て，規則を規定し，その前提と規則から当の理論に論属するすべての知識を

あるいはその理論の持つ特定の側面を抽象した部分を論理的に導けるようにすることである．このような公理と推論規則からなる形式的な体系を公理系という．
公理的方法が使われた最も古い事例は，紀元前 300 年頃のユークリッド幾何学の成立にまでさかのぼる．
ユークリッド幾何学においては，23 個の定義，5 個の公準（要請），そして 9 個の公理が最初に立てられ，すべての定理はそこから論理的に証明されている．
ある理論を公理化することの利点はいくつかある．一つは，前提を公理として明示化することによって，正しい論証と正しくない論証を明確に区別することができるということである．公理体系においてはある言明がその体系の定理であるための条件が厳密に規定されている．従ってその条件に適うものだけがその体系の正しい定理であるということになる．
もう一つの利点は，公理的方法が当の理論体系の真理性の保証を与えうるということである．ある公理系で，推論規則が論理的な推論だけを許すようなものであるとする．前節で確認したように，論理的推論（演繹的推論）においては，前提が真であれば必ず結論も真である．従ってこの公理系では，前提となっている公理の真理性が体系全体の真理性を保証するのである．
しかしながら数学において興味深いのは，一度公理体系が確立し，数学者の社会に受け入れられると，もはや既存の理論とは独立に，公理系そのものが研究の対象になるということである．公理系がもとの理論を正確にシミュレートしている場合は，その公理系の性質や振る舞いを研究することは，もとの理論の性質や振る舞いを研究することにつながる．しかし数学ではもとの理論の振る舞いを忠実に反映していないとわかった後でも，その公理系に対する興味が失われることはない．言い換えれば，数学においては，公理体
系は純粋な形式的体系（内容や意味を捨象された記号の体系）としても扱われる．実際，数学者の中には数学（のある分野）はただ単に抽象的な記号を操るゲームであると主張する者もいる．
この節では形式的体系とはどのようなものであるかについて学ぼう．そのために非常に単純な形式的体

42

第 3 章 形式的体系における導出系をまず紹介し，その後で命題論理の形式的体系を紹介する．

3.1

Bullet

まず形式的体系とは何かということを説明しておこう．一般的に形式的体系とは一定の規則に従って対象や式を導出する体系である．形式的体系は以下のような要素からなる．
対象：その形式的体系において扱われる対象．項とも呼ばれる．多くの場合，単純な対象が与えられ，それらが一定の規則によって組み合わされることによってより複雑な対象が作られる．
例えば 26 字のアルファベットから様々な語が作られたり，0 から 9 の数字を組み合わせて任意の自然数が作られるように．
式：対象を特定の仕方で組み合わせることによって得られる表現．例えば自然数論においては，任意の対象 m, n に対して m = n, m ≥ n などは式である．対象と式の区別がない体系もある．
公理：式の中には公理と呼ばれる特殊な地位を持ったものがある．公理はその体系で無条件に導出可能と見なされる．
導出規則：ある条件のもとで，新しい式を導出するための規則．
定理：その形式的体系で導出可能な式．
証明：ある定理が導出される過程を明示的に表わしたもの．図や式の列で表わされることが多い．
ここで一つ単純な形式的体系の例を挙げよう．これは完全に無意味で人工的なゲームであって，もちろんその意味などは問題にならない．しかし体系そのものの振る舞いや性質についての研究はできる．そのような研究は論理学や数学の本質的な部分を理解する役に立つだろう．以下の形式的体系をBullet と呼ぶ．

Bullet の式：Bullet では対象と式の区別がない．Bullet の式は次のように帰納的に定義される．
(1) • と ◦ は Bullet の式である．
(2) X と Y がともに Bullet の式であるとき，XY も Bullet の式である．
(3) (1) と (2) によって Bullet の式と決まるものが Bullet の式のすべてである．
上の定義から ••，◦•，• • ◦ • ◦ などが Bullet の式であることが分かる．しかし例えば ∗• や ◦• などは Bulletの式ではない．

Bullet の公理：•
従って • は Bullet において無条件に導出可能と見なされる．

Bullet の導出規則：

3.1. Bullet

43

B1：式 X の右端に • があったら，式 X から式 X◦ を導出してよい．
B2：式 X から，式 XX を導出してよい．
B3：式 X に含まれる • • • を ◦ で置き換えて式 Y が得られるとする．このとき式 X から式 Yを導出してよい．

B4：式 X に含まれる ◦ ◦ ◦ を • で置き換えて式 Y が得られるとする．このとき式 X から式 Yを導出してよい．

B5：式 X に含まれる ◦ • ◦ を ◦ ◦ ◦ で置き換えて式 Y が得られるとする．このとき式 X から式Y を導出してよい．
定義 3.1.1. Bullet における導出列を次のように帰納的に定義する．

(1) • は Bullet の導出列である．
(2) X1 , X2 , . . . , Xn が Bullet の導出列であり，Xn から Xn+1 が導出規則のいずれかによって導出されるとき，X1 , X2 , . . . , Xn , Xn+1 は Bullet の導出列である．

X1 , X2 , . . . , Xn が Bullet の導出列であるとき，Xn は Bullet の定理と呼ばれる．またこのとき X1 , X2 , . . . , Xn
は Bullet における Xn の証明と呼ばれる．
例 3.1.2. • ◦ ◦◦ が Bullet の定理であることを示そう．次の 1 − 4 の式を並べると，• ◦ ◦◦ の証明になる．

1. •2. •◦ (B1)
3. • ◦ •◦ (B2)
4. • ◦ ◦◦ (B5)
問題 3.1.3. 例にならって以下の式が Bullet の定理であることを示せ．

(1) ◦ • •◦(2) • ◦ ◦(3) ◦•(4) ◦◦(5) ◦ ◦ • • ◦◦(6) ◦ ◦ ◦•(7) • ◦ •(8) ◦ ◦ ◦ ◦ ◦(9) ◦(10) • • • • •Bullet の定理を証明するばかりでなく，私たちは Bullet が持つ様々な性質を研究することができる．たとえば Bullet に関して以下の事実が成り立つ．

44

第 3 章 形式的体系における導出

事実 3.1.4.

(1)

X が Bullet の定理であり，かつ X から導出規則のいずれかによって X 0 が導出されるとき，X 0 もBullet の定理である．
(2)

任意の自然数 n に対して，• または ◦ を 2n 個ならべた式は Bullet の定理である．

(3)

任意の式 X に対して X の長さとは X に現れる • と ◦ の数の合計であるとする．ある導出列

X1 , X2 , . . . , Xn において，R1 が一度も使われていないならば，Xn の長さが偶数であるか，n = 1 であるかのどちらかである．

(4)

任意の自然数 n と，3m ≤ 2n である任意の自然数 m に対して，2n − 3m 個の • と m 個の ◦ からなる任意の式は Bullet の定理である．また 2n − 3m 個の ◦ と m 個の • からなる任意の式は Bullet の定理である．

(1)(2) の証明を与えておこう．
(1) の証明

X が Bullet の定理であるとする．このとき定義より Bullet のある導出列 X1 , X2 , . . . , Xn が存在して，X = Xn が成り立つ．X から推論規則のいずれかによって X 0 が導出されるとする．このとき導出列の定義より X1 , X2 , . . . , Xn , X 0 は Bullet の導出列になっている．従って X 0 は Bullet の定理である．¤(2) の証明では帰納法を使う．
(2) の証明n に対する帰納法を使う．

(Base）：n = 0 の時．2n = 20 = 1．• を 1 個ならべた式とはすなわち • そのものである．これが Bulletの定理であることは自明．
2nz }| {(Step)：X = • • · · · • が Bullet の定理であるとする（帰納法の仮定）．X から R2 によって XX =2n2nz }| { z }| {• • · · · • • • · · · • が導出できる．従って (1) より XX も Bullet の定理である．明らかに XX は • を 2n + 2n =2n+1 個ならべた式である．
以上より任意の自然数 n に対して，• を 2n 個並べた式は Bullet の定理であることが示された．

¤

問題 3.1.5. 上の事実 (3)(4)(5) が成り立つことを確かめよ．
以上では Bullet で定理になる式について調べてきたが，Bullet の定理ではないような式について考えることは一層興味深い．なぜならばある式が Bullet の定理であることは，その式の Bullet における証明を与えることによって示されるが，ある式が Bullet の定理ではないということを示すための一般的な方法は存在しないからである．Bullet における証明不可能性の問題はより高度な数学的手法が必要となるだろう．具
体的には次の問題を考えてみれば良い．
問題 3.1.6. Bullet の定理ではない Bullet の式の具体例を挙げよ．
少し考えてみれば読者はこの問題に答えることが予想以上に難しいことに気づくだろう．実はこの答え
は作者も知らない．

3.2. 命題論理の形式的体系 ND

3.2

45

命題論理の形式的体系 ND

前節で私たちは命題論理の形式的な言語 L を導入し，意味論によって，論理的含意，論理的帰結，トー
トロジーなどの概念を正確に与えた．しかしながら，このやり方は私たちが普段行っている推論の方法を反映していない．私たちが推論をするときに行っているのは，一定の規則に従ってある文から別の文を導き出すことである．前節での論理的推論の特徴づけは，ある推論が論理的推論であるかを確かめる方法ではあるかもしれないが，推論を導く規則を与えてはくれない．そこでこの節では，推論規則によって，論理的推論を特徴づけることを考えよう．以下で扱われる体系を命題論理の形式的体系ND と呼ぶ．

ND の対象：L のすべての文．
ND の式：任意の文 α1 , α2 , . . . , αn , β(n ≥ 0) に対して，
α1 , α2 , . . . , αn ` β
を ND の式とする．

ND の公理：任意の文 α0 , α1 , . . . , αn (n ≥ 0) に対して
A1: α0 , α1 , . . . , αn ` αk(0 ≤ k ≤ n)

A2: α1 , α2 , . . . , αn ` >を ND の公理とする1 ．

Bullet では公理として具体的な式が一つ与えられただけだったが，ND では具体的な式ではなく，ある形
式を持ったすべての式が公理として与えられる．このため A1, A2 は公理図式または公理型と呼ばれる．たとえば A1 に属する具体的な公理は，A ∧ B, C ` A ∧ B ，A ⊃ B, ¬B ` ¬B などである．

ND の導出規則：ND は導出規則として次のものを持っている．以下の図は水平線の上の式から下の式を導出することが出来る，ということを表している．Γ は任意の文の列を表すものとする．

(⊃I)Γ, α ` β
Γ`α⊃β

(∧I)

Γ`α
Γ`β
Γ`α∧β

(∧EL)

Γ`α∧β
Γ`α

(∧ER)

Γ`α∧β
Γ`β

(∨IL)

Γ`α
Γ`α∨β

(∨IR)

Γ`β
Γ`α∨β

(⊃E)

Γ`α⊃β
Γ`α
Γ`β

1 A1 の式の左辺が α から始まっているのに対して，A2 の式の左辺は α から始まっていることに注意しよう．これは A1 におい
0
1ては左辺には少なくとも 1 個の文が現れるのに対して，A2 においては左辺が空な列であることも許されるということを表している．

46

第 3 章 形式的体系における導出

Γ`α∨β

(∨E)

Γ, α ` γΓ`γ(¬I)Γ, α ` ⊥Γ ` ¬α(≡I)Γ, α ` β
Γ, β ` α
Γ`α≡β

(≡EL)

Γ`α≡β
Γ`β
Γ`α

(¬¬E)

Γ ` ¬¬αΓ`αΓ, β ` γ

Γ`α

(¬E)

(≡ER)

Γ ` ¬α
Γ`⊥

Γ`α≡β
Γ`α
Γ`β

定義 3.2.1. ND における導出木，導出木の根を次のように定義する．

(1) Γ ` α が ND の公理であるとき，Γ ` α は ND の導出木であり，その根は Γ ` α である．
(2) D1（と D2 )（と D3 ）が ND の導出木であり，D1 の根（と D2 の根）（と D3 の根）から，NDの導出規則によって Γ ` α が導出できるならば，

D1

(D2 )
Γ`α

(D3 )

は，ND の導出木であり，その根は Γ ` α である．
定義 3.2.2. Γ ` α を根として持つ ND の導出木 D が存在するとき，Γ ` α は ND の定理であるといわれる．またこのとき D を，Γ ` α の証明と呼ぶ．Γ ` α が ND の定理であるということを，Γ `ND αによって表す．
例 3.2.3. (1) A ⊃ (B ⊃ C) ` B ⊃ (A ⊃ C) が ND の定理であることを示す．まずA ⊃ (B ⊃ C), B, A ` A ⊃ (B ⊃ C)
A ⊃ (B ⊃ C), B, A ` A
はそれぞれ ND の公理である．従ってこれらは導出木であり，それ自体がその根になっている．ここから導出規則 ⊃E より，

A ⊃ (B ⊃ C), B, A ` A ⊃ (B ⊃ C)
A ⊃ (B ⊃ C), B, A ` A
A ⊃ (B ⊃ C), B, A ` B ⊃ C
が導出木になることが分かる．次に3.2. 命題論理の形式的体系 ND

47

A ⊃ (B ⊃ C), B, A ` B
も ND の公理だから，導出木であり，それ自身が根である．従って再び導出規則 ⊃E より，

A ⊃ (B ⊃ C), B, A ` A ⊃ (B ⊃ C)
A ⊃ (B ⊃ C), B, A ` A
A ⊃ (B ⊃ C), B, A ` B ⊃ C
A ⊃ (B ⊃ C), B, A ` B
A ⊃ (B ⊃ C), A, B ` C
が ND の導出木になることが分かる．これと導出規則 ⊃I より，

A ⊃ (B ⊃ C), B, A ` A ⊃ (B ⊃ C)
A ⊃ (B ⊃ C), B, A ` A
A ⊃ (B ⊃ C), B, A ` B ⊃ C
A ⊃ (B ⊃ C), B, A ` B
A ⊃ (B ⊃ C), B, A ` C
A ⊃ (B ⊃ C), B ` A ⊃ C
が ND の導出木になることが分かる．これと再び導出規則 ⊃I より，

A ⊃ (B ⊃ C), B, A ` A ⊃ (B ⊃ C)
A ⊃ (B ⊃ C), B, A ` A
A ⊃ (B ⊃ C), B, A ` B ⊃ C
A ⊃ (B ⊃ C), B, A ` B
A ⊃ (B ⊃ C), B, A ` C
A ⊃ (B ⊃ C), B ` A ⊃ C
A ⊃ (B ⊃ C) ` B ⊃ (A ⊃ C)
が ND の導出木になることが分かる．従ってA ⊃ (B ⊃ C) ` B ⊃ (A ⊃ C)
は ND の定理である．

(2) A ∧ (B ∨ C) ` (A ∧ B) ∨ (A ∧ C) が ND の定理であることを示す．以下で α によって文 A ∧ (B ∨ C)を表すものとする．まず

α, B ` A ∧ (B ∨ C)α, B ` A
α, B ` B
α, B ` A ∧ B
α, B ` (A ∧ B) ∨ (A ∧ C)
およびα, C ` A ∧ (B ∨ C)
α, C ` A
α, C ` C
α, C ` A ∧ C
α, C ` (A ∧ B) ∨ (A ∧ C)
はともに ND の導出木であり，その根はそれぞれ α, B ` (A ∧ B) ∨ (A ∧ C)，α, C ` (A ∧ B) ∨ (A ∧ C) である．そこでこの二つの導出木の，根よりも上の部分をそれぞれ D1 ，D2 によって表すと，次の図が NDの導出木になる．

α ` A ∧ (B ∨ C)
α`B∨C

D1
D2
α, B ` (A ∧ B) ∨ (A ∧ C)
α, C ` (A ∧ B) ∨ (A ∧ C)
α ` (A ∧ B) ∨ (A ∧ C)

48

第 3 章 形式的体系における導出

問題 3.2.4. 上の例の (2) において，どこでどの規則が使われているかを答えよ．
問題 3.2.5. 以下の式が ND の定理であることを，導出木を作って示せ．

(1) α ∧ β ` β ∧ α(2) ` ¬(α ∧ ¬α)(3) α ⊃ β, β ⊃ γ ` α ⊃ β(4) α ⊃ (β ⊃ γ) ` (α ⊃ β) ⊃ (α ⊃ γ)(5) α ∨ β ` β ∨ α(6) α ≡ β, ¬α ` β(7) α ≡ β ` β ≡ α(8) α ∨ β, ¬α ` β(9) ¬α ⊃ ¬β ` β ⊃ α(10) ` α ∨ ¬α(11) ` α ≡ ¬¬α(12) α ⊃ β ` ¬α ∨ β
この形式的体系 ND は Bullet とは異なり，単に無意味な記号操作の体系ではない．これは論理的な推論を特徴付けるという意図の下に作られた体系である．具体的に言えば，前章で特徴付けた文の間の論理的含意関係と，ND での定理の間には次のような関係が成立する．

(1) α1 , α2 , . . . , αn ` β が ND の定理であるならば，α1 , α2 , . . . , αn は β を論理的に含意する．
(2) α1 , α2 , . . . , αn が β を論理的に含意するならば，α1 , α2 , . . . , αn ` β は ND の定理である．
この証明は次章で与える．

(1) が意味するのは，ND の導出規則に従って推論を進めている限りは，その推論が論理的な推論になっていることが保証される，ということである．このような形式的体系の性質を，形式的体系の健全性という．

(2) が意味するのは，命題論理の範囲に話を限れば，ある前提から論理的な結論を導くために，ND の導出規則以外の規則は必要ない，ということである．形式的体系のこのような性質を，形式的体系の完全性という．
これまでのポイントをまとめよう．

• 形式的体系とは，一定の公理から出発し，一定の規則に従って式を導出する体系である．
• 形式的体系は通常，既存の知識体系（あるいはその一部）を厳密に体系化することを意図して作られる．そのために形式的体系の式には一定の意味（解釈）が与えられる．

• 形式的体系 F で導出できる式のすべてが，既存の理論 T において真とされる言明に解釈されるなら
ば，F は T に対して健全であるといわれる．

• 既存の理論 T において真とされる言明に解釈される，形式的体系 F の式のすべてが F で導出できる
とき，F は T に対して完全であるといわれる．

3.2. 命題論理の形式的体系 ND• 命題論理の形式的体系 ND は，言語 L の意味論にたいして健全かつ完全である．
次章では，形式的体系と意図された解釈との関係について論じる．

49

51

第 4 章 形式的体系と解釈，健全性，完全性
Bullet は単純な形式的体系だが，様々な自明ではない

従って「証明」1 されなければならない

性質を持っていることが分かる．また「証明できない Bullet の式が存在するかどうか」という問題のように，

Bullet の性質として「証明」できるか出来ないか不明な問題も存在する．
数学においてはこのように人工的に作られた形式的体系の性質が研究の対象になりうるのである．特にその体系が公理化を意図している理論を持っている場合，その理論との関わりが重要になっていく．このことを見るために，もう一つ，ごく単純な形式的体系を紹介して，その意図された解釈との関わりについて考えてみよう．

4.1

Measures

次の体系をMeasures と呼ぶ．Bullet と異なり，Measures は恣意的に作られた無意味な体系ではない．

Measures の対象：
(1) − は Measures の対象である．
(2) X が Measures の対象であるとき，X◦ も Measures の対象である．
(3) (1) と (2) によって Measures の対象と決まるものが Measures の対象のすべてである．
この定義から一般に Measures の対象は − の後ろに n 個の ◦ が並んだ形をしていることが分かる（ただし n ≥ 0）．そこで以下では ◦ が n 個並んでいる列を表わすのに ◦n という表現を使うことにする．従って
一般に Measures の対象は −◦n によって表わすことが出来る．特に −◦0 は − を表わしている．以下で断りがなければ k, m, n は任意の自然数を表わすこととする（自然数には 0 も含まれるに注意）．

Measures の式：任意の Measures の対象 −◦m , −◦n に対して，− ◦m | − ◦ n
は Measures の式である．

Measures の公理：−|−
1 ここでは証明という語が二つの意味で使われてる．一つは ND，Bullet，Measures などの形式的体系で定義された証明，一つは日常言語における証明である．紛らわしさを避けるためにここでは後者の意味で証明という場合は「」をつけて使う．

52

第 4 章 形式的体系と解釈，健全性，完全性

Measures の導出規則：
M1：任意の n に対して，− ◦n |− から − ◦n ◦|− を導出してよい．
M2：任意の m, n に対して，− ◦m | − ◦n から − ◦m | − ◦n+m を導出してよい．
Measures の導出列，定理，証明は Bullet の場合と同様に定義される．
例 4.1.1. − ◦ ◦| − ◦ ◦ ◦ ◦ ◦◦ は Measures の定理である．証明は次の 1-6 の式を並べたもの．

1. −|−
2. − ◦ |− (M1)
3. − ◦ ◦|− (M1)
4. − ◦ ◦| − ◦◦ (M2)
5. − ◦ ◦| − ◦ ◦ ◦◦ (M2)
6. − ◦ ◦| − ◦ ◦ ◦ ◦ ◦◦ (M2)
問題 4.1.2. 以下の式が Measures の定理であるかどうかを判断せよ．もし定理であるならばそのことを示せ．

(1) − ◦ | − ◦ ◦ ◦(2) − ◦ ◦| − ◦(3) − ◦ ◦ ◦ ◦| − ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦◦(4) − ◦ ◦ ◦ | − ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦◦(5) − ◦ ◦ ◦ |−問題 4.1.3. Measures の定理は一般にどのような特徴を持っているか？ つまり，式 − ◦m | − ◦n が Measuresの定理であるための必要十分条件は何か？
上の問題は形式的体系 Measures がどのような意図された解釈を持っているかということを聞いている．
これは Measures の定理の証明をいくつか試みてみれば明らかだろう．式 − ◦m | − ◦n が Measures の定理であるのは，m が n の約数になっている時，そしてその時に限られる．そもそも Measures はそのような解釈が出来るように作られているのである．つまり Measures に対して意図された解釈とは，−◦n を自然数 nとして解釈し，| を自然数の間の約数関係として解釈する，というものである．Measures はこの解釈に対して健全性と完全性を持っている．以下でこのことを確かめてみよう．そのためには，Measures が意図している理論を正確に述べておく必要がある．いまその理論をMOD と呼ぶことにする．
自然数全体の集合を N によって表す．MOD において，N の任意の要素 m, n に対して，m が n の約数であるというのは，ある N の要素 k が存在して，n = k · m が成り立つこととする．m が n の約数であるとき，hm, ni を理論 MOD の定理と呼ぶ．なお，N の任意の要素 n に対して，0 = 0 · n が成り立つので，Nのすべての要素 n に対して hn, 0i が MOD の定理であることに注意しよう．
私たちが「証明」しなければいけないのは次の二つである．

4.1. Measures

53(S) 任意の自然数 m, n に対して，− ◦m | − ◦n が Measures の定理であるならば，hm, ni は理論 MOD の定理である．

(C) 任意の自然数 m, n に対して，hm, ni が理論 MOD の定理であるならば，− ◦m | − ◦n は Measures の定理である．

(S) は Measures の式 − ◦m | − ◦n を hm, ni と対応させて解釈したとき，Measures では MOD の定理と対応付けられないような式は証明されないということ，すなわち Measures が MOD に対して健全であるということを述べている．(C) は，同じ解釈のもとで，MOD の定理に対応する式のすべてが Measures で導出できるということ，すなわち Measures が MOD に対して完全であるということを述べている．これを以下で証明しよう．

(S) の「証明」− ◦m1 | − ◦n1 , − ◦m2 | − ◦n2 , . . . , − ◦mk | − ◦nk は Measures の導出列であるとする．このとき任意の − ◦mi | − ◦ni (1 ≤ i ≤ k) について，hmi , ni i が MOD の定理であることをによって示そう．

(Base)：i = 1 とする．このとき mi = ni = 0．h0, 0i が MOD のていりであることは明らか．よって
hmi , ni i が MOD の定理であることが示された．
(Step)：hmi , ni i が MOD の定理であるとする（帰納法の仮定）．− ◦mi+1 | − ◦ni+1 は，(i)M1 によって− ◦mi | − ◦ni から導出されているか，(ii)M2 によって導出されているかのどちらかである．
(i) の場合，このとき ni = ni+1 = 0．上に述べたように任意の N の要素 k に対して hk, 0i は MOD の定理だから，hmi+1 , ni+1 i は MOD の定理である．

(ii) の場合．このとき −◦mi+1 は −◦mi に等しく，−◦ni+1 は −◦ni +mi に等しい．従って mi+1 = mi , ni+1 =ni + mi ．帰納法の仮定より hmi , ni i は MOD の定理である．従って N のある要素 j が存在して ni = j · miが成り立つ．よって

ni+1 = ni + mi
= j · mi + mi
= (j + 1) · mi
= (j + 1) · mi+1が成り立つ．j が N の要素だから，j + 1 も N の要素である．従って hmi+1 , ni+1 i は MOD の定理である．
以上から任意の i(1 ≤ i ≤ k) に対して hmi , ni i が MOD の定理になっていることが示された．従ってこれは特に i = k の時も成り立つ．よって Measures の任意の定理 − ◦m | − ◦n に対して，hm, ni が MOD の定理であることが示された．

(C) の「証明」¤

N の任意の要素 m, n に対して，hm, ni が MOD の定理であれば，ある N の要素 k が存在して，k · m = n が成り立つ．従って (C) を証明するには N の任意の要素 k, m に対して − ◦m | − ◦k·m がMeasures の定理であることを示せばよい．これを k に対する帰納法で示そう．
(Base)：k = 0 とする．このとき任意の m に対して，以下の導出列が − ◦m | − ◦k·m の証明になる．

54

第 4 章 形式的体系と解釈，健全性，完全性m−1mz }| {z }| {−|−, − ◦ |−, − ◦ ◦|−, . . . , − ◦ ◦ · · · ◦ |−, − ◦ ◦ · · · ◦ |−
|
{z
}
m+1

従って − ◦m | − ◦k·m は Measures の定理．

(Step)：− ◦m | − ◦k·m が Measures の定理になっているとする．このとき Measures の導出列
− ◦m1 | − ◦n1 , − ◦m2 | − ◦n2 , . . . , − ◦mj | − ◦njが存在し，mj = m, nj = k · m．M2 より − ◦m |◦k·m から − ◦m | − ◦k·m+m が導出できるので，次の列がMeasures の導出列になる．
− ◦m1 | − ◦n1 , − ◦m2 | − ◦n2 , . . . , − ◦mj | − ◦nj , − ◦m | − ◦k·m+m
よって − ◦m | − ◦k·m+m は Measures の定理．k · m + m = (k + 1) · m だから − ◦m | − ◦(k+1)·m が Measuresの定理である．
以上で，N の任意の要素 m に対して − ◦m | − ◦k·m が Measures の定理ならば，− ◦m | − ◦(k+1)·m もMeasures の定理であることが示された．
従って N の任意の要素 k, m に対して − ◦m | − ◦k·m は Measures の定理である．

¤

前章で私たちは Bullet の様々な性質を調べた．同様に私たちは Measures の持つ様々な性質を研究することができる．そして健全性は Measures の性質の多くが，そのまま MOD の性質であると解釈することを許す．逆に完全性は MOD について成り立つ性質の多くが，Measures についても成り立つことを保証してくれる．たとえば任意の自然数 n について − ◦ | − ◦n が Measures の定理であることは容易に示される．このことと Measures の健全性から，任意の自然数 n に対して h1, ni が MOD の定理であることを結論することができる．また私たちは 2 は任意の偶数の約数であることを知っている．このことと Measures の完全性か
ら，n が偶数ならば − ◦2 | − ◦n が Measures の定理であるということを結論できる．
問題 4.1.4. Measures の健全性，完全性を使って以下のことを示せ．

(1) 任意の自然数 n は n 自身の約数である．
(2) 任意の自然数 k, m, n に対して，− ◦k | − ◦m ，− ◦m | − ◦n がともに Measures の定理であるならば，− ◦k | − ◦n も Measures の定理である．
(3) 任意の自然数 m, n に対して，− ◦m | − ◦n ，− ◦n | − ◦m がともに Measures の定理であるならば，
m = n．
(4) 任意の自然数 k, m, n に対して，− ◦k | − ◦n ，− ◦m | − ◦n がともに Measures の定理であるならば，− ◦k∪m | − ◦n も Measures の定理である．ただし k ∪ m は k と m の最小公倍数を表す．
(5) 任意の自然数 k, m, n に対して，− ◦n | − ◦k ，− ◦n | − ◦m がともに Measures の定理であるならば，− ◦n | − ◦k∩m も Measures の定理である．ただし k ∩ m は k と m の最大公約数を表す．
(6) 任意の素数 p に対して，− ◦n | − ◦p が Measures の定理であるならば，n = 1 または n = p．
(7) 任意の自然数 n に対して，n は 0 の約数である．
(8) 任意の自然数 m, n に対して，m が n の約数ならば m は n + m の約数である．

4.2. ND の健全性と完全性

55

問題 4.1.5. 次のような理論MOD+ を考えよう．MOD+ は 1 以上の自然数全体を対象とする．1 以上の自然数全体の集合を N+ と表す．N+ の任意の要素 m, n に対して，N+ のある要素 k が存在して n = k · m が成り立つとき，MOD+ において m は n の約数であるという．MOD+ において m が n の約数であるとき，hm, ni を MOD+ の定理であるという．
Measures+ は Measures と同じ対象と式を持つ形式的体系であるとする．これに適当な公理と導出規則を付け加えて，MOD+ に対して健全かつ完全な形式的体系を作れ．

4.2

ND の健全性と完全性

この節では形式的体系 ND の健全性と完全性を証明する．これらはどちらも ND の導出木の構成に関する帰納法によって示される．帰納法を分かりやすく記述するために，いくつか定義をしておこう．
定義 4.2.1. ND の式 α1 , α2 , . . . , αn ` β が恒真であるのは，α1 , α2 , . . . , αn |= β が成り立つとき，すなわ
ち，任意の真理値付値 v について，v が α1 , α2 , . . . , αn のすべてに真理値 T を与えるならば，v は β に真理
値 T を与えるときである．
定理 4.2.2 (ND の健全性). 式 α1 , α2 , . . . , αn ` β が ND の定理ならば，α1 , α2 , . . . , αn ` β は恒真である．
証明

証明のアウトラインは次のようになる．まず (1)ND の公理がすべて恒真式であることを示す．次に(2)ND のすべての導出規則について，その前提となる式がすべて恒真式ならば，その帰結となる式も恒真式になることを示す．このことによって ND の定理がすべて恒真な式であることが示される．

(1) α1 , α2 , . . . , αn ` β が ND の公理であるとする．この式が公理 A1 の時は，β は α1 , α2 , . . . , αn のいず
れかに等しい．従って真理値付値 v が α1 , α2 , . . . , αn のすべてに真理値 T を与えるならば，v は β にも Tを与える．またこの式が公理 A2 であるならば β は > である．いかなる付値 v も β に真理値 T を与える．
従っていずれの場合も α1 , α2 , . . . , αn ` β は恒真である．

(2) ⊃I について．α1 , α2 , . . . , αn , α ` β が恒真であるとする．このとき α1 , α2 , . . . , αn , α のすべてに真理
値 T を与える真理値付値は必ず β にも真理値 T を与える．
いま真理値付値 v は α1 , α2 , . . . , αn のすべてに真理値 T を与えるとする．この v が α に真理値 T を与えるとすると，v は α1 , α2 , . . . , αn , α のすべてに T を与えることになる．従って v は β に真理値 T を与える．
従って真理値計算の規則 (5) より，v は α ⊃ β に T を与える．また v が α に真理値 F を与えるとすると，同じく真理値計算の規則 (5) より，v は α ⊃ β に真理値 T を与える．従っていずれにしても v は α ⊃ β に
真理値 T を与える．従って任意の付値 v について，v が α1 , α2 , . . . , αn のすべてに T を与えるならば，v はα ⊃ β に T を与える．従って α1 , α2 , . . . , αn ` β は恒真である．
他の導出規則についても，同様にして，その前提となる式がすべて恒真ならば，その帰結となる式も恒真になることが確かめられる．よって ND の定理はすべて恒真式である．
問題 4.2.3. ⊃I 以外の導出規則についても，その前提となる式がすべて恒真ならば，帰結となる式も恒真であることを示せ．

56

第 4 章 形式的体系と解釈，健全性，完全性

次に ND の完全性を示す．その前にいくつか準備をしておこう．以下で Γ, Σ は文の列（空であってもよい）であるとする．
補題 4.2.4. (1) α1 , α2 , . . . , αn |= β が成り立つための必要十分条件は |= α1 ⊃ (α2 ⊃ . . . (αn ⊃ β) . . . ) が成り立つことである．

(2) Γ ` β が ND の定理ならば，Γ, α ` β および α, Γ ` β も ND の定理である．
(3) Γ, α1 , α2 , Σ ` β が ND の定理ならば，Γ, α2 , α1 , Σ ` β も ND の定理である．
(4) Γ, > ` β または Γ, ¬⊥ ` β が ND の定理であるならば，Γ ` β も ND の定理である．
(5) Γ ` α ⊃ β が ND の定理であるならば，Γ, α ` β も ND の定理である．
証明(1) の証明は容易なので練習問題とする．

(2) について．α1 , α2 , . . . , αn ` β を根として持つ ND の導出木が存在するとする．ND の導出規則では ` の左辺に現れる文の数が減ることはあっても，増えることはない．また ND の導出規則によって左辺の文が減らされるときは，必ず右端から一個ずつ減らされる．従ってこの導出木に現れる式はすべて

α1 , α2 , . . . , αn , γ1 , γ2 , . . . , γm ` δ（ただし m ≥ 0）という形をしている．この導出木のすべての式の左辺のα1 , α2 , . . . , αn の右に , α を加えて得られる図は，明らかに ND の導出図になっている（厳密には導出図の構成に関する帰納法を使う）．従って α1 , α2 , . . . , αn ` β は ND の定理である．α, α1 , α2 , . . . , αn ` β についても同様．

(3) について．(2) と同様の議論で証明できる．
(4) について．Γ ` > および Γ ` ¬⊥ が ND の定理であることを示せばよい．
(5) について．練習問題とする．
問題 4.2.5. 補題 4.2.4(1)(2)(5) の証明を完成させよ．
定義 4.2.6. 任意の文 α と任意の真理値付 v に対して，αv を次のように定義する．以下で等号 = は両辺が記号として同一であるということを表している．

αv =



 α

（v が α に T を与えるとき） ¬α （v が α に F を与えるとき）

定義 4.2.7. 文 α に対して，α に含まれるすべての文記号からなる集合を ∆(α) と表す．
補題 4.2.8. 任意の文 α と任意の真理値付値 v に対して，∆(α) の要素 p1 , p2 , . . . , pn が存在して，

pv1 , pv2 , . . . , pvn ` αv
が ND の定理になる．
証明

α は任意の文，v は任意の付値とする．α の長さ（α に現れる結合子の数）に対する帰納法によって補題を示そう．

(Base): α の長さが 0 のとき．α は文記号．従って pv1 , pv2 , . . . , pvn として αv を取ればよい．
(Step): α は長さ n + 1 であるとする．長さ n 以下の任意の文 β と任意の付値 u に対して，∆(β) の要素
q1 , q2 , . . . , qn が存在して，

4.2. ND の健全性と完全性

57u
q1u , q2u , . . . , qm
` βuが ND の定理になっているとする（帰納法の仮定）．

α が ¬β のとき，β の長さは n である．従って帰納法の仮定より ∆(β) の要素 q1 , q2 , . . . , qn が存在して，v
q1v , q2v , . . . , qm
` βv

(i)

が ND の定理になっている．

v(β) = T とする．このとき β v = β ．また v(α) = v(¬β) = F より，αv = ¬α = ¬¬β ．ところで ND では，v` β ⊃ ¬¬βq1v , q2v , . . . , qmが証明可能なので，これと上の (i) より，v
q1v , q2v , . . . , qm
` ¬¬β

すなわち
v
` αv
q1v , q2v , . . . , qm

が ND で証明可能であるということが帰結する．また q1 , q2 , . . . , qm は ∆(α) の要素なので，p1 , p2 , . . . , pn
として q1 , q2 , . . . , qm をとればよい．
次に v(β) = F とする．このとき β v = ¬β ．また v(α) = v(¬β) = T だから，αv = α．従って，(i) より
直ちに
v
` αv
q1v , q2v , . . . , qm

が ND で証明可能であるということが帰結する．q1 , q2 , . . . , qm は ∆(α) の要素であるから，p1 , p2 , . . . , pn
として q1 , q2 , . . . , qm をとればよい．

α が β ∧ γ のとき．β, γ はどちらも長さ n 以下だから，帰納法の仮定より，∆(β) の要素 q1 , q2 , . . . , qm ，および ∆(γ) の要素 r1 , r2 , . . . , rk が存在してv
q1v , q2v , . . . , qm
` βv

(ii)

r1v , r2v , . . . , rkv ` γ v(iii)

が ND の定理である．

v(β ∧ γ) = T とする．このとき v(β) = v(γ) = T より，β v = β, γ v = γ ．また v(α) = v(β ∧ γ) = T より，αv = α = β ∧ γ = β v ∧ γ v ．

(ii)(iii) と補題 4.2.4 より，v
q1v , q2v , . . . , qm
, r1v , r2v , . . . , rkv ` β vv
q1v , q2v , . . . , qm
, r1v , r2v , . . . , rkv ` γ v

58

第 4 章 形式的体系と解釈，健全性，完全性

は ND の定理である．ここから導出規則 ∧I より直ちに，v
q1v , q2v , . . . , qm
, r1v , r2v , . . . , rkv ` β v ∧ γ v

すなわちv
q1v , q2v , . . . , qm
, r1v , r2v , . . . , rkv ` αv

が ND の定理であることが帰結する．q1 , q2 , . . . , qm , r1 , r2 , . . . , rk は ∆(α) の要素である．従って p1 , p2 , . . . , pn
として q1 , q2 , . . . , qm , r1 , r2 , . . . , rk をとればよい．
次に v(β ∧ γ) = F とする．このとき v(β) = F または v(γ) = F ．

v(β) = F とする．このとき β v = ¬β ．また v(α) = v(β ∧ γ) = F より，αv = ¬α = ¬(β ∧ γ)．
(ii) より，v
q1v , q2v , . . . , qm
` ¬β

(ii)’

が ND の定理である．ところで ND でv
` ¬β ⊃ ¬(β ∧ γ)
q1v , q2v , . . . , qmが証明できるので，これと (ii)’ よりv` ¬(β ∧ γ)
q1v , q2v , . . . , qm

すなわち，
v
` αv
q1v , q2v , . . . , qmv
ND の定理であることが分かる．q1v , q2v , . . . , qm
は ∆(α) の要素だから，p1 , p2 , . . . , pn として q1 , q2 , . . . , qm

を取ればよい．v(γ) = F のときもまったく同様に証明が出来る．

α が β ∨ γ ，β ⊃ γ ，β ≡ γ の時も同様にして補題が成り立つことが示される．
問題 4.2.9. α が β ∨ γ ，β ⊃ γ ，β ≡ γ のときの証明を加えて上の証明を完成させよ．
以上から次の定理が導かれる．
定理 4.2.10 (ND の完全性). a1 , a2 , . . . , an ` β が恒真式ならば，a1 , a2 , . . . , an ` β は ND の定理である．
証明

α1 , α2 , . . . , αn ` β が恒真式であるとする．このとき α1 , α2 , . . . , αn |= β が成り立つ．補題 4.2.4(1) より，これは |= α1 ⊃ (α2 ⊃ . . . (αn ⊃ β) . . . ) が成り立つということに等しい．α1 ⊃ (α2 ⊃ . . . (αn ⊃ β) . . . )を γ と表す．任意の真理値付値 v に対して，v(γ) = T である．

∆(γ) = {p1 , p2 , . . . , pm } とする．いま付値 v, u は pm が文変数の場合はそれぞれ T, F を与え，その他の
文変数に対しては同じ真理値を与えるような付値であるとする．従って pm が文定数の場合は v と u はまっ
たく同じ付値である．このとき補題 4.2.4(2)(3)，補題 4.2.8 より

4.2. ND の健全性と完全性

59

pv1 , pv2 , . . . , pvm ` γ v
pu1 , pu2 , . . . , pum ` γ v
すなわちpv1 , pv2 , . . . , pvm−1 , pvm ` γ(*)

pv1 , pv2 , . . . , pvm−1 , pum ` γ(**)

は ND の定理である．

pm が文変数のとき，pvm = pm , pum = ¬pm ．従って
pv1 , pv2 , . . . , pvm−1 , pm ` γ
pv1 , pv2 , . . . , pvm−1 , ¬pm ` γ
が ND の定理であるということになる．ND では

pv1 , pv2 , . . . , pvm−1 ` pm ∨ ¬pmが定理なので，これらから導出規則 ∨E より，

pv1 , pv2 , . . . , pvm−1 ` γが導出できる．

pm が文定数 > のとき．v(pm ) = u(pm ) = T ．従って pvm = pum = >．従って (*)(**) はどちらも，
pv1 , pv2 , . . . , pvm−1 , > ` γという式である．これが ND の定理であるということと，補題 4.2.4(4) より，

pv1 , pv2 , . . . , pvm−1 ` γ
が ND の定理であるということが帰結する．

pm が文定数 ⊥ のとき．v(pm ) = u(pm ) = F ．従って pvm = pum = ¬⊥．このときもやはり補題 4.2.4(4)を使って，

pv1 , pv2 , . . . , pvm−1 ` γ
が ND の定理であるということが帰結する．従って結局，

pv1 , pv2 , . . . , pvm−1 ` γは ND の定理である．
同じようにして pm−1 が文変数である場合に pm−1 に対する付値だけが v とは異なるような付値 w につ
いて，

60

第 4 章 形式的体系と解釈，健全性，完全性w
w
pw
1 , p2 , . . . , pm−1 ` γ

が ND の定理であることを示すことが出来る．ここから，同じ議論で，

pv1 , pv2 , . . . , pvm−2 ` γが ND の定理であることが導かれる．この議論を m 回繰り返すことで結局`γ即ち` α1 ⊃ (α2 ⊃ . . . (αn ⊃ β) . . . )が ND の定理であるということが帰結する．ここで補題 4.2.4(5) より

α1 , α2 , . . . , αn ` βが ND の定理であることが導かれる．

82

索引
Bullet, 42
Measures, 51

構文論, 34
公理, 42

Bullet の—, 42
Measures の—, 51

ND
命題論理の形式的体系—, 45

ND の—, 45
公理系, 41

意味論, 34
言語 L に対する—, 34

最小元, 20
最大元, 20

蓋然的推論, 31
下界, 19下限, 19
括弧省略の規則, 33
含意, 32
関係, 19関数, 21—の合成, 22
恒等—, 22
完全性, 48

ND の—, 58
帰納的定義, 32
帰納法, 32
逆像, 22
極小元, 20
極大元, 20
空集合, 16
形式的体系, 42結合子, 32
健全性, 48

ND の—, 55
後件, 32

三段論法, 4集合, 16—の共通部分, 17—の差, 17—の同一性, 17—の内包的表記, 16—の要素, 16—の和, 17
十分条件, 36
終領域, 21
順序, 19
順序集合, 19
上界, 19上限, 19
条件文, 32
始領域, 21真部分集合, 17
真理値, 35
真理値計算の規則, 35
真理値付値, 35
真理表, 37
推移性, 19

83

索引

整列集合, 20
選言, 32
前件, 32
全射, 22
全順序, 19

命題論理の言語 L , 31
ユークリッドの互除法, 11ラッセル, 8—のパラドクス, 8

全単射, 22

連言, 32

像, 22

論理的含意, 38

双条件文, 32

論理的帰結, 38対称性, 19
単射, 22
直積, 18導出木

ND の—, 46
導出規則, 42

Bullet の—, 42
Measures の—, 52
ND の—, 45
同値関係, 21
同値文, 32
同値類, 21
トートロジー, 39
反射性, 19
反対称性, 19
必然的推論, 31
必要条件, 36
否定, 32部分集合, 17
部分順序集合, 19
フレーゲ, 5
文
命題論理の言語 L の—, 31
文記号, 31
文定数, 31
文変数, 31
ペアノの公理, 8べき集合, 18