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

●問1

仮定 Q⇒R から結論 P∧Q ⇒ R を導く自然演繹による次の証明図に，
適用する規則の名前 や 解消する仮定の番号 を書き足せ．

        P∧Q
        ──
         Q         Q⇒R
         ───────
               R
           ─────
           P∧Q ⇒ R

●問2

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

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

●答1 (自然演繹の推論規則の利用)

         1
        P∧Q
        ── ∧E2  
         Q         Q⇒R
         ───────⇒E
               R
           ───── ⇒I 1
           P∧Q ⇒ R

[解説]

仮定や結論の論理式に現れる論理記号である⇒と∧に関する推論規則を使う．
上の解答では，1段目の線の上のP∧Qの連言の記号∧を除去する規則∧E2を使い，
2段目の線の上のQ⇒Rの含意の記号⇒を除去する規則⇒Eを使い，
3段目の線の下のP∧Q⇒Rに含意の記号⇒を導入する規則⇒Iを使う．
この規則で設ける仮定はP∧Q(仮定番号1)で，規則の適用により仮定1が解消される．

論理式の主要な(木構造で書くと根の位置の)記号から，使える推論規則が分かる．
横線の上にある論理式の主要な記号を取り除くのが除去(E)規則であり，
横線の下に論理式の主要な記号を導入するのが導入(I)規則である．

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

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

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

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