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

●問1

P を0変数の述語記号(命題記号)，Q を1変数の述語記号とする．
自然演繹による次の証明図に，使っている規則 や 解消する仮定番号 を書き足せ．
ただし，∀I 規則を使うときは，変数条件を満たす理由を述べること．

                                 ∀xQ(x)
                                 ────
                       P           Q(a)
                    ────     ────
        P∨∀xQ(x)  P∨Q(a)      P∨Q(a)
        ────────────────
                    P∨Q(a)
                  ──────
                  ∀x(P∨Q(x))
           ─────────────
           P∨∀xQ(x) ⇒ ∀x(P∨Q(x))

●問2

(1) 整数に関する命題「非偶数が存在するならば，全てが偶数とはいえない」を
述語論理の論理式として表せ．ただし，x が偶数であることを P(x) で表す．

(2) 上記の命題の証明を以下に示す．これを自然演繹の証明図として表せ．
ただし，変数条件を満たす理由も述べること．

［証明］非偶数が存在し，かつ，全てが偶数であると仮定し，矛盾を導く．
第1の仮定より，非偶数があるから，それを a とおくと，a は偶数ではない．
第2の仮定より，全てが偶数なので，a は偶数である．
a が偶数ではなく，しかも，a が偶数である，という矛盾が導かれた．

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

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

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

［解説］

述語論理に対する自然演繹の導出では，∀I 規則を使うとき，
変数条件が満たされることを確認する．
なお，∨E と ∀I の適用順序を逆にした証明も作れる．

●答2 (自然演繹による形式化)

(1) ∃x¬P(x) ⇒ ¬∀xP(x)

(2) (教科書 p.79 例題3.8 を参照)

［解説］

述語論理におけるド・モルガンの法則の，自然演繹による証明を与えている．
なお，証明は含意命題の間接証明を形式化していることに注意する．

述語論理での自然演繹の導出では，∃E 規則を使うとき，
変数条件が満たされることを確認する．

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

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