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

●問1

自然演繹で命題 (¬P⇒¬Q) ⇒ (Q⇒P) を証明せよ．背理法規則 ⊥c を使うこと．

●問2

次に示すのは，命題 ∃x¬P(x) ⇒ ¬∀xP(x) を導く，自然演繹による誤った証明である．
どの規則の適用が誤っているか，理由と共に答えよ．

           2             1       3
        ∀xP(x)      ∃x¬P(x) ¬P(a)
        ────∀E  ────────∃E 3
          P(a)            ¬P(a)
          ───────────⇒E
                    ⊥
                ─────⇒I 2
                ¬∀xP(x)
          ───────────⇒I 1
          ∃x¬P(x) ⇒ ¬∀xP(x)

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

●答1 (背理法を使う自然演繹による証明)

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

［解説］

派生規則である排中律(EM)を使う証明は，以下の通りである．

               4     1
              ¬P ¬P⇒¬Q
            2 ──────⇒E
            Q      ¬Q
            ─────⇒E
                ⊥
   ━━━EM  3  ─⊥
   P∨¬P    P  P
   ───────∨E 3,4
         P
        ──⇒I 2
        Q⇒P
──────────⇒I 1
(¬P⇒¬Q) ⇒ (Q⇒P)

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

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

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

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