Yabu.log

ITなどの雑記

論理学をつくる練習問題80(2)解答

本に回答が乗っておらず、ネットに載せておく意義があると思ったので公開。 練習問題80(2)はND公理系(自然演繹)で式集合が矛盾するか、どうかの解答と矛盾していればそれを証明(自然演繹で示す)をする問題。 (a),(b),(c)とあるが式集合は全て矛盾しているためその証明(自然演繹による⊥の導出)のみを示す。

※間違ってたらすいません

論理学をつくる

論理学をつくる

問題

Γ⊢NDA, Γ⊢ND¬Aなる論理式Aがあるとき、ΓをND矛盾しているということにする。次の うちND矛盾している論理式の集合はどれか、そしてそれがND矛盾していることを示せ。

  • (a) {P∨Q, ¬P→Q, ¬P}
  • (b) {P∨Q, ¬(P∧Q), P↔︎Q}
  • (c) {P→Q, P, ¬Q}

回答

(a)

P∨Q      Prem
¬P→¬Q    Prem
¬P        Prem
--------------
¬P→¬Q    Rep
¬P        Rep
¬Q        → elim

    Q    Prem
    ---------
    ¬Q    Reit
    ⊥    ¬intro*

Q→⊥    →intro

    P    Prem
    ---------
    ¬P   reit
    ⊥   ¬intoro*

P→⊥   →intro
Q→⊥   Rep
P∨Q    Rep
⊥      ∨elim

ポイント:演繹三行目で∧intoroをつかって¬P∧¬Qを導けるが、これが前提のP∨Qと矛盾していることは明らか(真理値表を書けば真になる割当が見つからない)。またド・モルガンの法則により¬P∧¬Q = ¬(P∨Q))だが、自然演繹に¬P∧¬Q,P∨Qからを導くルールがなく、自然演繹の中のルールで他の式からを導く必要がある。

(b)

P∨Q       Prem
¬(P∧Q)    Prem
P↔Q       Prem
---------------
    P    Prem
    ---------
    P↔Q    Reit
    Q       ↔elim
    P∧Q    ∧intro

P→(P∧Q)    →intro
     
    Q    Prem
    ---------
    P↔Q    reit
    P       ↔elim
    Q       Rep
    P∧Q    ∧intro

Q→(P∧Q)    →intro
P→(P∧Q)    Rep
P∨Q         Rep
P∧Q         ∨elim
¬(P∧Q)      rep
⊥           ¬intoro*

(c)

一番簡単と解答に書いてあったやつ。これを(a)にして最初に解かせてほしかったな。

P→Q
P
¬Q    Prem ⊥
--------------
P→Q    Rep
P       Rep
Q       →elim
¬Q      Rep
⊥      ¬intor*

なにかあればコメントください。

ちなみに、論理学をつくるはまだ挫折しておらず、ノートをサブブログの方に書き出しています。Twitterやめた僕が悪いんだけど、アクセス数3とかなので悲しい(涙)

yuyubu-sub.hateblo.jp