自然演繹法を使いこなそう AI A つまり , 【攻略法 とせよ , 第 9 章 ということだ。だからこの場合は , 2 2 1 とすればよ Q → (P → R) →を目指すには】 A → B に達したいとき , A を前提とし , 一番下に B が出てく るような導出を構成し , → intro によって A → B を得るようにするとよい。 例題の場合 , Q → (P → R) に達したいのだから , 次の ( 1 ) のように Q を前提し P → R が出てくる さて , 問題は ( 2 ) の左から 3 つ目の導出線に沿って , P から R をどのようにして導くかだ。そ り , 次の ( 2 ) のようにしろ , ということ。 → intro により P → R を得ればよいから , だいたい次のような演繹ができればよいわけだ。つま てくるような導出を構成するためには , 同様に P を前提とし R が出てくるような導出をつくり ような導出を構成し→ intro によって Q → ( P → R ) を得るようにすればよい。さらに , P → R が出 れには次の攻略法が役に立つ。 【攻略法 : 復活はいつでも OK 】ある論理式に達したいなら , 他の攻略法を試した後で , れに役立ちそうな論理式をとにかく復活させてみるとよい。 そ いまは 2 つしか復活させる論理式がないので , とりあえず両方復活させてみる。そうすると ( 3 ) になる。 ( 1 ) P → Q → (P → R) P → R Prem —->intro ( 2 ) P → R Prem Prem ( 3 ) P Q → R Prem P Prem Q → (P → R) P → R → intro - → intro P → (Q → R) Reit Reit Q → (P → R) P → R → intro - → intro さらに次の攻略法を導入する。 【攻略法 : 除去はいつでも OK 】除去規則が使えそうなときはとにかく使うべし。

第 9 章 自然演繹法を使いこなそう 231 9.2.5 最後の手段としての間接証明 間接証明の攻略法 これまでに紹介してきた攻略法はかなりの場合に有効だが , ある。そういうときは次のやり方を試みてみよう。 どうしてもうまくいかない場合が 【攻略法 : 最後の手段は間接証明】 A に至りたいのに , その他の方法がすべてダメだったと き , まず -•A を仮定において矛盾を導き , ¯lintro で A を得て , •elim で 2 重否定を 除去して A を得るという方法を試みよ。 対偶法則を導いてみよう。つまり , P → Q と Q → P が互いに演繹できることを示してみよ う。まず P → Q から Q → P はこれまでの攻略法だけでできてしまう ( 練習問題 68 をみよ ) 。 逆に Q → P から P → Q を演繹するのも簡単そうに見える。しかし , これが実はくせ者なの 0 ( 2 ) ( 3 ) ( i ) までで攻略法が尽きてしまう。そこで , Q を得るために間接証明を試みる。つまり , (ii) のようにして Q を得ることにしよう。そのためには (iii) のようにやるしかない。 → P Prem P Prem ¯lintro •P Prem P Prem Q •elim P → Q ¯nintro → P Prem P Prem contradiction ! Q ¯lintro Q ¯nelim P → Q ¯nintro 問題はどうやって矛盾をつくるかだ。とにかく復活と除去のできるやつはしてしまおう。 というわけで復活できるものを復活させると , (iv) → P Prem P Prem Q → P Reit P Reit •P → elim Q ¯lintro Q •elim P → Q •intro うまい具合に矛盾が生じてくれた。

228 第Ⅲ部論理をもう 1 つの目で見る 矛盾の作り方についての攻略法 以上の例は , 今までの攻略法だけで首尾良く矛盾が出た都合のよいケースだった。いつもそん のようにしなければならない。 こで , Pe-»Q が得られるようがんばってみる , すべきなのは , 復活で出てきた•(P—Q) だ。 れる攻略法があると都合がよい。•(PAQ) を ( P ← Q ) から演繹する場合を例にとろう。 なにうまくいくと思ったら大間違い。そこで , という方針が立つ。 Pe»Q をみちびくには次の ( ii ) もし P ← Q が得られれば , 矛盾が得られる。そ 従来の攻略法でたどり着けるのは , ( i ) まで。さて , どのような矛盾を導くべきか。こで注目 どのような方針で矛盾を導けばよいかを教えてく そして , それぞれの下位導出で Q と P をそれぞれ導出するためには P ^ Q を復活させればよ い。というわけで , (iii) のようにして演繹が完成する。 - ーー 1 ←分 -•(P (Q) •intro contradiction ! •(P—Q) Reit (iii) - ー←今 Prem Prem -•(P—Q) Reit P Prem P → Q → intro prem ー ) intro Pe->Q +intro •(P (Q) •intro •(P—Q) Reit P Prem PAQ Reit Q Aelim P → Q → intro Prem P △ Q Reit P Aelim ー ) intro Pe->Q e-+intro •(PAQ) •intro 以上の例の下線部は次の攻略法を示唆している。 のまわりにある論理式を見よ。もしそこに¯•B の形の式があったら , B を得るようにせ 【攻略法 : 矛盾の見つけ方】 A の仮定のもとで , 矛盾を見つけたいが見つからないとき , A 練習問題 68 ( 1 ) ( 2 ) 次の演繹を構成せよ。 (b) •P から•(PAQ) •(P → Q) から -•(P—Q) (d) P → Q から Q → P (e) P と—nQ から -•(P → Q) 次の proof を構成せよ。 (a) P → P (b) •(PA•P) —n(PAQ) から P → -•Q

これは , ようするに枝分かれせざるをえない場合でも , 片方の経路が閉じるような行を優先さ せるということである。以上からタブローを実際に構成する際に従うべき攻略法としては , 【攻略法】 ( 1 ) 枝分かれしない展開規則を先に適用する。 ( 2 ) 枝分かれする場合は少なくとも一方の経路が閉じるような行に先に展開規則を適用す 練習問題 22 く書くことはできるからだ。 る。 これはタブローを楽して書くためのコツなのである。 これを「攻略法」と呼び , 規則と呼ばない理由は , この攻略法に従わなくてもタブローを正し ( 1 ) 次の論理式の集合はそれぞれ矛盾しているだろうか。タブローを使ってチェックせよ。 か。 ・神は存在する (c) {P 、 vQ, Q → R, P → S, •(RVS)} (a) {P → Q, P →ーーー IQ } (b) {P, P → Q, P → - ー IQ } この世には悪がある ・神が造り給いしこの世が最善の世界であるならば悪はこの世にない ・神が存在するならば神が造り給いしこの世は最善の世界である 100 第 I 部論理学をはじめる めればよい。そうすると , 例えば ( b ) のようになる ( 第 4 行 , 2 , た ) 。さらに順序を工夫するとさらに ( c ) のようにスッキリしたタブローになる ( 第 4 行 , 1 , ( 2 ) 次の 4 つのことを同時に信じている人がいる。その人の信念は矛盾しているかそれとも整合的 3 行の順に規則を当てはめ 3 行の順に規則を当てはめた ) 。 A → B B → C C → D •(A → D) ! X ーー 1 C •A B (c) A → B ! B → C ! C → D ! •(A → D) ! X X X

230 第Ⅲ部論理をもう 1 つの目で見る 【 v 除去規則 (v elim) 】 AvB, A → C, その導出に書き加えてよい。 B → C がすでに同じ導出に出てきているなら , C を うーむ。書き足される式 C にはもともとの V が含まれていないから , 確かに v の除去規則 にはなっているのだが・・ これは , 構成的両刀論法を背景にもっている。 A と B の 2 つの場 合で場合分けが尽くされていることが分かっており , どちらの場合をとっても C ということが 演繹できるのだったら , 場合分けなしにつねに C と言ってよい , という規則である。したがっ て , この規則に対応する攻略法は , 【攻略法 : v からスタートしたなら】 A V B という選言から C にいたるためには , C と B → C という 2 つの式を導け。 まず A → この攻略法はこれまでのものと少し毛色が異なる。これまでの攻略法 というものになるだろう。 は特定の形をした式に至りたいのだったらこうすべし , というものがほとんどだった。これは逆 に , 特定の形から出発したらどうすべきかをアドバイスしてくれている。しかし , この攻略法も なかなか有用だ。例えば , P → Q と R → S から (PVR) → (QVS) を演繹せよという場合。 ( i ) まで は簡単に【演繹の枠組みをまずつくれ】と【→を目指すには】でできる。問題は , どうやって Q ' こで P V R という仮定からの導出が必要になることに気づいて【 v から v S を導くかである。 スタートしたなら】を用いると , (ii) のように進む。あとはやってみよう。 (i) P → Q P V R QVS Prem (PVR) → (QVS) 練習問題 69 ーラ intro (ii) P → Q Prem R → S Prem P V R Prem P → (Q v s) R → ()v s) QVS VeIim (PvR) → (Qvs) ーラ intro 次の演繹を構成せよ。 ( 1 ) と ( 2 ) は velim を使わずにできる。 から ( PVQ ) への演繹はすごく技巧的になる。しばらくおあずけ。 ( 2 ) と ( 3 ) はド・モルガンの法則の半分だ。残りの ( P △ Q ) から PV Q への演繹と , •PA•Q (I)(PVQ) → R から (P → R) A(Q → R) (2H(PVQ) から P △ Q ( 3 ) Pv Q から•(PAQ)

224 第Ⅲ部論理をもう 1 つの目で見る 【攻略法 : △を目指すには】 A △ B に至りたかったら , A と B をそれぞれ別個に得るように し , その後に Aintro を用いるとよい。 攻略法だけで演繹できちゃう ? ( 1 ) まず【演繹の枠組みをまずつくれ】により ( i ) までいく。 ^ ( R → S ) から ( P ^ R ) → ( Q △ S ) の演繹をとってそのことを納得してもらおう。 攻略法は , 自然演繹法をかなりの程度まで機械的方法に近づけてくれる。例として , (P → Q) ( 2 ) 【→を目指すには】により , ( P △ R ) → ( Q △ S ) を導くために , P △ R を仮定して Q ^ S を導 くという方針をとる。これが ( ii ) の段階。 (i) (P → Q)A(R → S) Prem (PAR) → (QAS) (ii) P →△ R → S Prem PAR Prem QAS (PAR) → (QAS) ー→ intro ( 3 ) 【△を目指すには】により , Q △ S を導くためには Q と S をそれぞれ導けばよい (iii)o ( 4 ) 次に , Q と S をどのように導くかだが , 【復活はいつでも OK 】を使ってこれらを導く材 料を手に入れる必要がある。ところが復活させることができるのは ( P → Q ) △ ( R → S ) の 1 つだけ だ。これをとにかく復活させておこう (iv)o (iii) P →△ R → S Prem P △ R Prem Q △ S Aintro (PAR) → (QAS) → intro (iv) P →△ R → S Prem P ^ R Prem (P → Q) △ (R → s) Reit QA S Aintro (PAR) → (QAS) → intro ( 5 ) 【除去はいつでも OK 】ということだから , こいつの△を除去してやる。 P △ R からも△ を除去してやる。そうすると・・・・・ (v) になる。 ( 6 ) あとは , もういちど【除去はいつでも OK 】にしたがって P → Q と R → S の→を除去して やる。そうすると , 目指す Q と S は簡単に出てきてしまう。つまり (vi)o という具合で , 攻略法 だけで完全に演繹ができるというわけだ。

第 9 章自然演繹法を使いこなそう 243 【攻略法 : ヨからスタートしたなら】存在量化された式からスタートして目標となる式を導 くにあたり , いったんはその存在量化子をはずさなければならないと思われるとき , その目 標となる式をゴールとするような下位導出をつくってヨ除去規則を適用することを試み ヨ xQx VxVy((LxyAPy) → Qx) ヨ yPy Prem (i) ヨ xVyLxy Prem この攻略法の使用例 略法に従う。このとき第 2 下位導出で前提する式に使う個体定項は a ではダメである ( 但し書き 第 2 の前提も存在量化された式で , しかもヨをはずさないといけないのだから , もう一度攻 1 , 第 2 の前提のヨが除去されてなければならない。ここで攻略法に従うと (ii) になる。 →除去規則をつかうのでないといけないはずだ。そうすると L と P が裸で出てくるためには第 提から出てくる他はない。しかし Q だけが出てくるためには , L と P が単独で出てきていて , ( i ) のような演繹を行えと言われたとしよう。さて , 目標の式ヨ xQx に出てくる Q は第 3 の前 の ( a ) に違反しないため ) 。だから b を使う。こうして (iii) までたどりつく。 ( ⅱ ) ヨ x ▽ yLxy Prem ヨ yPy Prem V x ▽ Lx ^ P → V La Prem ヨ xQx ヨ xQx ヨ elim (iii) ヨ x V yLxy Prem ヨ yPy Prem V x ▽ Lx △ P → V La Prem Pb Prem ヨ xQx ヨ xQx ヨ elim ヨ xQx ヨ elim あとはに従って復活できるものはすべて復活させて , 除去規則をうまく適用していけば ( ▽ を除去するときには何を代入するかをよく考えること ) , かなり自動的に演繹ができあがる。最後に 3 つもヨ xQx が並ぶので技巧的に思われるが , 攻略法に従えば自然に思いつけるはずだ。

225 (v) P → ^ R → S Prem P △ R Prem (P → Q)A(R → S) Reit (vi) 第 9 章 P → 自然演繹法を使いこなそう △ R → S Prem P △ R Prem (P → Q) △ (R → S) Reit P → Q R → S P R Aelim Aelim Aelim Aelim P → Q R → S P R Q Aelim Aelim AeIim Aelim -- → elim Q △ S Aintro (PAR) → (QAS) → intro Q △ S ^ intro (PAR) → (QAS) → intro ちょっとは頭を使うべし しかし , いつでも攻略法に頼りつばなしでうまくいくとは限らない。例えば , 「 (P △ Q) → R か ら P → ( Q → R ) を導け」と言われたとしよう。【演繹の枠組みをますっくれ】 , 【→を目指すには】 出てくるはずだ ( ' こが攻略法に尽くされない頭の使いどころ ) 。そこで (ii) までいく。 (P △ Q) → R を使うだろう。そうすると , P △ Q が出てくれば→ elim で R が しかし , これ以上は攻略法の単純な適用では無理。そこで頭を使う。 R が により ( i ) まではいく。 出てくるためには , (i) Q → R → intro Prem P Prem PA → R Prem ー ) intro P → (Q → R) ( ⅱ ) P △→ R Prem ー→ intro P → (Q → R) Q → R → intro R → elim (PAQ) → R Reit PAQ Prem P Prem 問題は P △ Q をどうやって手に入れるかだが , 前提に P も Q もあるからこれらを復活させて △を導入すればいいじゃないかということに気づく。

220 B っ (R → s) → (P → s) 第Ⅲ部論理をもう 1 つの目で見る ト A → B という事実である。 以上により , 演繹 ( a ) は最終的に , 右のような具合に完璧に形 式化され , それぞれのステップがどの規則にしたがっているの かがすべて明確になった。ここまでの段階で , →だけを結合子 として含む論理式だけからなる演繹はすべてできるようになっ た。あとは , どのような演繹もできるようにするために , 他の 結合子に対して , それぞれ導入規則と除去規則を立ててやれば よい。 練習問題 64 次の導出に規則の名前を補え。今までに出 てきたのは , Prem, Rep, Reit, → elim, → intro の 5 つである。 Q → P P → (Q → P) 9.1.5 演繹の攻略法 自然演繹での演繹は機械的にはできない P → Q Prem Q → R Prem R → S Prem —->intro - → intro ー→ el ⅱれ R → S Reit Q → R Reit P → Q Reit S タブローは , 規則を当てはめていけばいつでも結果が出る機械的方法だった。確かにタブロー を書くにはちょっとばかり頭を使う。しかしそれはそうしないとタブローが書けないからではな く , むやみに複雑なタブローにしないためにコツがいる , ということにすぎない。だから M PL までの範囲では , タブローが大きくなることを厭わなければ , 何も考えずに機械的に規則を当て はめていってもいつかは結果が出る。 これに対し , 自然演繹では , 「 ~ から・・・を導け」という具合に出発点と終点が指定され , その 間をつないでいかねばならない。したがって , どの式にどの規則をどういう順番に当てはめる か , どのような仮定を新たに立てるかの選択を誤ると目的の式にたどりつくことができない。 のように , 演繹を構成するのは完全に機械的な作業にはならない。つまり , 少しは頭を使わなく ちゃ。 しかしながら , 自然演繹法による演繹の構成をかなり「誰にでもできる方法」に近づけること はできる。そのためには試行錯誤に任せるのではなく , その手順に従ってやっていくとたいてい はうまく演繹が構成できるという方針 , つまり攻略法を編み出しておく必要がある。そこで , 次 に「 P → ( Q → R ) から Q → ( P → R ) を導け」という例題が与えられたとして , そうした攻略法を抽 出しておこう。 【攻略法 : 演繹の枠組みをまずつくれ】 AI, An を前提棒の上に縦に書き並べ , 導出線の一番下に B を書け。 ・ An から B の演繹が欲しいなら , まず AI ,

第 9 章 9.2.4 連言は簡単だったのに選言はややこしい v 導入規則 自然演繹法を使いこなそう 229 「 A か B v の導入規則はとっても簡単。何が言えていれば A \/ B を言ってよいか。それは , がすでに言えているなら A v B と言ってよい」というものだろう。そこで , 【 v 導入規則 ( v i ntro) 】 A か B が同じ導出において以前に一項目として出てきているな ら , A V B を書き加えてよい。 この規則を使うための攻略法も簡単に得られる。 【攻略法 : v を目指すには】 A ▽ B にいたるためには , A か B のどちらかに達すればよい。 例えば , P → Q から P → (Q v R) を演繹せよという場合 , ( 1 ) ( 2 ) から , 【演繹の枠組みをまずつくれ】によって ( i ) まで行く。 【→を目指すには】によって ( ⅱ ) 。これをにらんでいると , R は上には全く出てこないのだ Q を導けばよいのだということがわかる。そこで , (iii) を得る。 Prem P → (Q v R) 一→ intro (iii) Q 、 V R Vintro P → (Q v R) ー→ intro P → P P → Q Reit Prem —>intro P → (Q v R) Q ▽ R ▽ intro この攻略法は , どちらの選言肢を導くかの選択を誤るとどうしようもなくなる。そのときは , もう一方の選言肢を導くことを試みよう。 v 除去規則 問題なのは v の除去規則だ。これまでのように A 、 v B から▽を除去して A や B を引き出す ことはできない。というのも , A ▽ B は選言肢のどちらが成り立っているかということについて はまったく何も述べていないからだ。結合子 V の除去規則は , A ▽ B が言えているとして , そ こからさらにどのようなことが言えるかを述べたものであるはずなのだが , A ▽ B だけからは , これ以上 A と B については何も出てこないのである。そこで , 他の論理式の助けを借りること