407 70 P prem Prem ¯Q Prem P Reit —nP Reit - ー nQ ¯lintro Q •elim P → Q → intro —nP → Q Prem ¯IQ Prem •P Prem —nP → Q Reit Q → elim ¯IQ Reit P •intro P •elim —•Q → P → intro •P V Q Prem •P Prem P Prem ¯IQ Prem P Reit •P Reit Q ¯nintro Q •elim P → Q → intro •P → (P → Q) ¯+intro Q Prem P Prem Q Reit P → Q → intro Q → (P → Q) ーⅱ ntr 0 P → Q VeIim •(P → Q) Prem —•P Prem P Prem ¯•Q Prem •P Reit P Reit Q ¯lintro Q •elim P → Q → intro —n(P → Q) Reit ー一丁ー IP •intro P •elim Q Prem P Prem Q Reit P → Q → intro •(P → Q) Reit Q ¯lintro P , へ•Q △ intro ( 7 ) P V Q Prem •P Prem P Prem —•Q Prem P Reit Reit Q ¯lintro Q ¯nelim P → Q → intro Q Prem Q Rep Q → Q → intro Q Velim B. 練習問題解答 -•(P △—•Q) Prem P Prem ¯•Q Prem P Reit P △—Q △ intro —n(P △ -•Q) Reit Q ¯lintro Q ¯nelim P → Q → intro —•(P △ Q) Prem •(•PV —-Q) Prem •P Prem —nP V —Q V intro P —nintro P •elim ¯IQ Prem •P\v/ —•Q Vintro •(•PV—•Q) Reit Q ¯lintro Q ¯nelim P AQ Aintro •(PAQ) Reit •PV•Q •elim ( P V (Q) •intro

406 68 ( 1 ) 69 付録 (l)(d) (l)(a) •(P → Q) Prem P+-+Q Prem P Prem Pe-+Q Reit Q —elim P → Q → intro •(P → Q) Reit -•(P—Q) —nintro P → Q Prem ¯nQ Prem P Prem P → Q Reit Q → elim ¯nQ Reit —IP —nintro Q → P → intro (l)(b) (l)(e) •P Prem P △ Q Prem P Aelim Q Aelim —nP Reit —n(PAQ) •intro P Prem ¯IQ Prem P → Q Prem P Reit Q → elim ¯nQ Reit -n(P → Q) ¯lintr O •(PVQ) Prem P Prem PVQ Vintro •(PVQ) Reit —nP —nintro Q Prem P V Q V intro •(PVQ) Reit Q ¯nintro P △ Q Aintro (l)(c) (2Xa) (2Xb) (PVQ) → R Prem P Prem PVQ Vintro (PVQ) → R Reit R → elim P → R → intro Q Prem PVQ Vintro (PVQ) → R Reit R → elim Q → R → intro (P → R)A(Q → R) △ intro •(PAQ) Prem P Prem Q Prem P Reit PAQ Aintro •(PAQ) Reit Q •intro P →—nQ → intro P Prem •P Prem P Reit P •intro ー ) i ntro P △•P Prem P Aelim •P Aelim P △ P ) ¯li ntro •P V —Q Prem •P Prem P △ Q Prem P Aelim Q AeIim •P Reit •(PAQ) •intro •P →•(PAQ) → intro ¯-Q Prem P △ Q Prem P Aelim Q Aelim ー→ i ntro •(PAQ) velim ¯Q →•(PAQ) •(PAQ) •intro ¯nQ Reit

233 (iv) PV —nP Prem contradiction ! •(P v (P) Reit 第 9 章自然演繹法を使いこなそう P ▽•P Prem •(P v (P) Reit P ▽ー卍 P V —nl) P V ーー - コ P P ▽ - ー -1 P ¯lintro Vintro ¯nintro ¯lelim V intro ¯lintro Vintro ¯lintro ¯lelim 9.3 9.3.1 矛盾記号を導入した方がよいかも 超絶技巧の演繹 ? 仕上げにド・モルガンの法則の残っていた半分 , ¯IP △ -•Q から¯•(P ▽ Q) への演繹にチャレ ンジしよう。 ( 1 ) まず , ( i ) のように方針が立つ。 る。 らそんなものに→ intro の規則を当てはめて P → contradiction ! などという式を作ることはで は A と¯IA が同時に出てくるということを表しているのであり , これは論理式ではない。だか ( 3 ) 素直に考えると , (iii) のような方針がたつ。しかし , 困ったことがある。 contradiction ! ( 2 ) 次に , P v Q から矛盾を導くわけだから , 【 v からスタートしたなら】に従うと , (ii) にな きない。 P V Prem contradiction ! •(PVQ) (ii) Prem P 、 V Prem P → contradiction . Q → contradiction . contradiction ! •(PVQ) Prem P ▽ Prem P Prem contradiction ! P-•contradiction ! Prem contradiction ! Q—»contradiction ! —>intro —+intro contradiction ! Velim ー・コ ( P vQ) ¯lintro の部分を何らかの矛盾式にする必要がある。そこで ( i 、うのように ( 4 ) だから , contradiction ! 考えた。 ( 5 ) これが素直なやり方だろうが , 困ってしまう。 * をつけたところの式がそれぞれ異なり ,

409 74 ( 1 ) (2)(b) Ka ASao Prem ヨ x(KxASxa) Prem VxVyVz((SxyASyz) → Sxz) Kb △ Sba Prem Kb Aelim Sba Aelim Ka ASao Reit Ka Aelim Sao Aelim Sba ASao Aintro (2Xa) Prem B. 練習問題解答 ¯> intro ヨ xPx →ヨ xQy ヨ yQy ヨ elim ー→ elim ヨ yQy Pa → 3yQy Velim Pa Prem ヨ xPx Prem Vx()x →ヨ Q ) Prem VxVyVz((SxyASyz) → Sxz) Reit Vx ヨ yLxy ヨ elim Vx ヨ yLxy Vintro ヨ yLby ヨ intro Lba VeIim V xLxa Prem ヨ VxLx Prem ヨ x(KxASxa ASxo) ヨ elim ヨ x(KxASxa ASxo) ヨ intro Kb / \ Sba △ Sbo △ intro Sba ASbo Aintro Sbo → elim (SbaA Sao) → Sbo Velim Vz((SbaA Saz) → Sbz) Velim VyVz((SbyASyz) → Sbz) Velim (2)(c) Vx()x → (x) Prem ¯1Qa Prem Pa Prem Vx()x → (x) Reit Pa → Qa Velim Qa → elim ¯nQa Reit ¯1Pa ¯lintro ¯nQa —>¯lPa ー→ intro Vx(- ・•Qx →¯lPx) Vintro

(3Xa) (2)(a) (1Xa) 75 付録 410 a = a ヨ xPxV ヨ xQx Prem ヨ xPx Prem Pa Prem Pa V Qa V intro ヨ x(PxVQx) ヨ intro ヨ x(PxVQx) ヨ elim ヨ xPx →ヨ x(PxVQx) → intro ヨ xQx Prem Qa Prem Pa V Qa V intro ヨ x(PxVQx) ヨ intro ヨ x(PxVQx) ヨ elim ヨ xQx →ヨ x(PxVQx) → intro ヨ x(PxVQx) velim (3)(b) ヨ x()x VQx) Prem PaVQa Prem Pa Prem ヨ xPx ヨ intro ヨ xPxV ヨ xQx Vintro Pa → ( ヨ xPxV ヨ xQx) → intro Qa Prem ヨ xQx ヨ intro ヨ xPxV ヨ xQx Vintro Qa → ( ヨ xPxv ヨ xQx) → intro ヨ xPxV ヨ xQx Velim ヨ xPxV ヨ xQx ヨ elim ヨ x(PxVQx) → ( ヨ xPxv ヨ xQx) -- 今 i ntro ( ヨ xPxv ヨ xQx) →ヨ x(PxVQx) a = b Prem •Lab Prem VxLxx Prem Laa VeIim a = b Reit •Lab Reit ¯nLaa =elim - ー 1 ・ xLxx ¯lintro (l)(b) 一分 intro ヨ x(PxAx=a) ヨ intro Pa △ a = a △ intro a = a = intro Pa Prem (2Xb) Prem = intro =elim a = b → b = a → intro VxVy(x=y → y=x) Vintro Vy(a=y → y=a) Vintro Pa △•Pb Prem a = b Prem PaA •Pb Reit Pa Aelim •Pb Aelim •Pa ==elim a =#b ¯nintro Vy((PaA•Py) → a*y) Vintro ()a △ Pb ) → a*b → intro VxVy((PxA•Py) → x*y) Vintro

第 9 章 xPx からヨ x•Px を演繹する 自然演繹法を使いこなそう 245 この逆はとてつもなく技巧的になる。まず , 【演繹の枠組みをまずつくれ】にした ところが , がって , ( i ) のように始めざるをえないが , これをじっと見ていて困るのは , 前提の▽で始ま る式に直接当てはめることのできる規則がないということだ。一般に量化された式を否定した式 に適用できる推論規則は自然演繹には用意されていない。そこで困ったときの間接証明を試み る。つまり , (ii) のようにする。 問題はどのようにして矛盾をつくるかだ。とりあえず復活できるものは復活させておく。そう すると , 【矛盾の作り方】によって , この矛盾をつくるのに xPx をまるごとつかえばよい のではないかということがひらめく。つまり何とかして VxPx を導けば次のようにうまく矛盾 がつくれるのではないだろうか。こうして (iiD まで進む。 •VxPx Prem ヨ x•Px (ii) ーーー 1 ▽ xPx Prem ヨ x•Px Prem contradiction ! ー一ヨ x¯lPX ・—nintro ヨ x¯lPx •elim ーー 1 ▽ xPx Prem ヨ x•Px Prem VxPx ¯nVxPx Reit 一丁一一 1 ヨ x¯1Px —lintro ヨ x•Px •elim 今度はどのようにして V xPx を導くことができるかを考えなくてはならない。【 Y を目指すに は】により , 任意の個体定項 a について Pa を導いてそれに V 導入規則を当てはめればよいだ ろうから , Pa を導くことにしよう。というのが ( iv ) の段階である。 それはよいのだが , この下位導出で前提されているのがまた一で始まる式だ。これには直 接適用できる規則がない。だから , また間接証明を行うことになる。つまり , •Pa を仮定して 矛盾を導くのだが , その矛盾をつくるのにヨ x ¯lPx という式をまるごと使うのだろう。そこ で , ( v ) のようにして演繹が完成する。 (iv) ー 1 ▽ xPx Prem ー一日 x•Px Prem Pa VxPx Vintro •VxPx Reit ー一ヨ x¯lPx —nintro ヨ x•Px •elim •VxPx Prem - ー 1 ヨ x•Px Prem ¯1Pa Prem ヨ x¯1Px ヨ intro ヨ x¯nPx Reit —nintro Pa •elim VxPx Vintro V xPx Reit - ・ 1- コヨ x—lPx —lintro ヨ x¯lPx •elim

第 9 章 自然演繹法を使いこなそう 235 ¯lintro* ¯lelim* 矛盾記号を認めると演繹がずいぶんと楽になる。 このため , 次の ようにこれまでの¯lintro を¯lintro* と•elim* に置き換えた規則 を自然演繹の規則体系としている教科書も多い。まとめると , 次の 図のようになる。 ' こで DN とは double negation ( 2 重否定 ) の 略である。これまでは•elim と呼ばれていたが , それだと ¯nelim* と紛らわしいので名前を付け替えた。 Prem P Prem •P ^ •Q Reit •P Aelim ↓•elim* P →↓ intro •PA —•Q Reit ¯Q AeIim ↓•elim* Q →工→ intro ↓ Velim •(PVQ) •intro* その他の規則 →△ V ←▽ヨ = についての 導入規則と除去規則 その他の規則 → ^ V → V ヨ = についての 導入規則と除去規則 2 重否定除去の規則 - ー -1e1 i m 2 重否定除去の規則 DN ( 呼び名の変更 ) これまでの規則 矛盾記号を使っ たときの規則 ¯nintro ¯nelim* ¯lintro* 練習問題 71 矛盾記号を使って次の演繹を構成せよ。 ( 1 ) Pv Q から一ゴ P △ Q ) ( ド・モルガンの法則の最後の残り ) ( 2 ) P → Q から -•Q → P ( 3 ) PvQ, P から Q

索引 ( 記号 ) 432 97 97 97 96 ー 97 97 97 97 127 127 127 127 [UI] [EI] 8 6 8 8 9 9 6 6 8 —IL ートー 6 ←導入規則 、→ intro, 226 Yelim, V 除去規則 236 Vintro, V 導人規則 237 , 240 ヨ除去規則 ヨ elim, 241 ヨ導入規則 ヨ intro, 236 △を目指すには 224 V からスタートしたなら v を目指すには 229 →を目指すには を目指すには 249 254 255 267 351 351 CJ 353 n 353 C 353 C 352 U An 353 A x B 354 A2 An D2, L)n 354 P(A) 355 230 d f 2 2 1 227 129 129 205 204 Vintro への但し書き 239 V を目指すには 3elim への但し書き 241 -- 42 ヨからスタートしたなら 243 •V, ヨからスタートしたなら 246 240 ( △ ) (V) 106 106 106 105 106 = 除去規則 =elim, 246 = 導入規則 = intro, 246 139 177 139 140 142 143 n=0 106 106 106 106 106 195 195 195 195 【 TI 】 【 T 1 ' 】 【 T2 】 【 T 2.9 】 【 T2.99 】 【 T2.999 】 【 T3 】 【 S 0.9 】 【 S 1 】 【 S 1' 】 【 S 2 】 【 S 3 】 / 356 f(a) 356 / : A → B 356 f(A) 356 144 146 148 177 146 147 B 358 B 358 B 358 B 358 △除去規則 Aelim, 223 △導入規則 △ intro, 223 v 除去規則 Velim, 230 v 導入規則 V intro, 229 →除去規則 ー elim, 2 19 →導入規則 ー今 intro, 2 19 除去規則 ¯nelim, 227 ¯lelim* 導入規則 ¯lintro, 227 ¯lintro* ←除去規則 ←み , 226 onto intO 1 50 50 , 52 167 98 , 130 67 , 1 5 1 A 359 凱ー 36 。 364 235 360 360 235 ト

408 71 - → Q 72 ( 1 ) 73 付録 •P V —Q Prem P ^ Q Prem •P V •Q Reit —nP Prem PAQ Reit P Aelim ↓¯nelim ー IP →↓→ intro ¯IQ Prem PAQ Reit Q Aelim ↓•elim* ¯Q →↓→ intro ↓ VeIim •(PAQ) •intro* Vx()x → (x) Prem ( 2 ) P ( 2 ) prem Prem Prem P → Q Reit ー ) elim Q P ー今 intro •intro ↓ -ー・ lelim* ¯Q Reit ( 3 ) P V Q Prem —nP Prem P Prem ¯-Q Prem P Reit •P Reit 、 L ・一 lel i m Q ¯lintro* Q DN P → Q → intro Q Prem Q Rep Q → Q → intro Q VeIim Prem VxVy(Lxy → VzPz) Laa Prem Pa Prem Pa → Qa VeIim Qa → elim ヨ xQx ヨ intro VyPy Vintro Pa ▽ elim ▽ xPx Prem Yy(Lay → VzPz) VeIim Laa → VzPz VeIim ヨ xPx ヨ intro Pa VeIim VzPz → elim (l)(a) (l)(b) VxLxx Pa VeIim Laa Velim VyPy Prem Vx(LxxA (x) Vintro Laa / \ Pa △ intro ( 2 ) VxVy( ヨ zHyz → Hxy) Hab Prem ヨ zHaz ヨ intro Prem Vy( ヨ zHyz → Hcy) VeIim 3zHaz → Hca VeIim Hca ー→ elim ヨ zHcz ヨ intro Vy( ヨ zHyz → Hdy) VeIim ヨ zHcz → Hdc VeIim Hdc → elim VyHdy Vintro VxVyHxy Vintro

第 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 うまい具合に矛盾が生じてくれた。