情報論理学演習3解答

情報論理学演習３解答
1. 以下の自然演繹証明中の空欄を（関与した論理式や推論規則で）埋めよ。
(a) p → q, ¬q ⊢ ¬p
(b) p ∨ q, q → p ⊢ p ∨ r
1
p→q
prem
1
p∨q
prem
2
¬q
prem 2
q→p
prem
3
p
ass
3
p
ass
4
q
→e 1,3
4
p∨r
∨i 3
5
⊥
¬e 2,4
5
q
6
¬p
¬i 3-5
6
8
→e 2,5
p
p∨r
7
ass
p∨r
∨i 6
∨e 1,3-4,5-7
2. 以下のシーケントを自然演繹法で証明せよ。
(a) ¬(¬p ∨ q) ⊢ p
(b) p ∨ r, p → r ⊢ r
1
¬(¬p ∨ q) prem
1
p∨r
prem
2
¬p
ass
2
p→r
prem
3
¬p ∨ q
∨i 2
3
p
ass
4
⊥
¬e 1,3
4
r
→e 2,3
5
p
RAA 2-4
5
r
ass
6
r
∨e 1,3-4,5
(c) ¬q → ¬p ⊢ p → q
(d) p → r, q → r, p ∨ q ⊢ r
1
¬q → ¬p prem
1
p→r
prem
2
p
ass
2
q→r
prem
3
¬q
ass
3
p∨q
prem
4
¬p
→e 1,3
4
p
ass
5
⊥
¬e 2,4
5
r
→e 1,4
6
q
RAA 3-5
6
q
ass
7
p→q
→i 2-6
7
r
→e 2,6
8
r
∨e 3,4-5,6-7

Download Report