━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
数理論理学 確認問題12
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

●問1

自然演繹で命題 P∨Q ⇒ Q∨P (選言の交換法則) を証明せよ．

●問2

自然演繹で命題 (P∨Q)∧¬P ⇒ Q を証明せよ．

──────────────────────────────────────

●答1 (自然演繹による証明)

      2        3
      P        Q
 1   ──∨I2 ──∨I1
P∨Q Q∨P     Q∨P
─────────∨E 2,3
       Q∨P
   ──────⇒I 1
   P∨Q ⇒ Q∨P

［解説］

下から 2 段目に ∨E でなく ∨I1 や ∨I2 を使ってしまうと，
仮定 P∨Q から P や Q を導出しなくてはならず，証明に失敗する．

選言の除去規則 ∨E

　　　　　ｉ　　ｊ
　　　　〈Ａ〉〈Ｂ〉
　　　　　：　　：
Ａ∨Ｂ 　 Ｃ  　Ｃ
─────────∨E ｉ,ｊ
       　Ｃ

の結論 Ｃ は，選言 Ａ∨Ｂ に現れる Ａ や Ｂ とは独立に自由に選んでよい．

なお，最上段で使っている規則の名前 ∨I1 や ∨I2 に現れる 1 や 2 は，
二つの∨I規則を区別するための名前の一部分であり，仮定番号とは無関係である．
一方，∨E 2,3 の 2,3 や ⇒I 1 の 1 は，解消する仮定の番号を示している．

●答2 (自然演繹による証明)

(教科書 p.113 確認問題3.7 の解答と解説を参照)

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
授業のホームページ

山田 俊行
https://www.cs.info.mie-u.ac.jp/~toshi/