情報論理学第11回講義復習問題

2014 年 7 月 8 日
情報論理学第 11 回講義復習問題
問題 1 以下の述語論理式の証明図を書け．
(1) ∀x ∀y P(x, y) → ∃z P(z, z)
(2) ∀x P(x, f(x)) → ∀x ∃y P(x, y)
(3) ¬∃x (¬P(x) ∧ P(x))
(4) ∀x (P(x) ∧ Q(x)) → (∃x P(x) ∧ ∃x Q(x))
(5) ∃x (P(x) → Q(x)) → (∀x P(x) → ∃x Q(x))
(6) ∃x P(x) ∨ ∃x Q(x) → ∃x (P(x) ∨ Q(x))
問題 2 以下の述語論理式について，恒真ならばその証明図を示し，恒真でないな
ら反例を与えよ．
(1) ∀x ∀y (P(x) → P(y))
(2) ∃x ∃y (P(x) → P(y))
問題 3 以下の述語論理式の証明図を書け．
(1) ∀x ∀y ∃z (x + y ≈ z)
(2) ∀x ∀y (P(x) ∧ x ≈ y → P(y))
問題 4 以下の述語論理式の証明図を書け．
(1) ∀x P(x) ∧ ∀y Q(y) → ∃z (P(z) ∧ Q(z))
(2) ∀x P(x) → ∃z P(z) ∧ ∃y P(y)
(3) ∃x P(x) → ∃y ∃z (P(y) ∧ P(z))
(4) ∃x P(x) → ∀x ∀y (P(x) → Q(y)) → ∀y Q(y)
(5) ∃x (Q → P(x)) → (Q → ∃x P(x))
(6) ∃x P(x, x, x) → ∃y ∃z P(y, y, z)
(7) ∃x ∀y P(x, x, y) → ∃x ∃y P(x, y, y)
(8) ∀x ∃y (P(x) → P(y))
(9) ∀x (P(x) ∨ Q(x)) → ∃x ¬P(x) → ∃x Q(x)
(10) ∃x ¬P(x) → ¬∀x P(x)
(11) ¬∀x P(x) → ∃x ¬P(x)
1
情報論理学第 11 回講義復習問題解答
問題 1
(1)
(2)
[∀x ∀y P(x, y)]1
∀E
∀y P(z, y)
∀E
P(z, z)
∃I
∃z P(z, z)
→I1
∀x ∀y P(x, y) → ∃z P(z, z)
[∀x P(x, f(x))]1
∀E
P(x, f(x))
∃I
∃y P(x, y)
∀I
∀x ∃y P(x, y)
→I1
∀x P(x, f(x)) → ∀x ∃y P(x, y)
(3)
[P(z) ∧ ¬ P(z)]1
[P(z) ∧ ¬ P(z)]1
∧E
∧E
¬ P(z)
P(z)
¬E
[∃x (P(x) ∧ ¬ P(x))]1
⊥
1
∃E
⊥
¬I2
¬∃x (¬P(x) ∧ P(x))
(4)
[∀x (P(x) ∧ Q(x))]1
[∀x (P(x) ∧ Q(x))]1
∀E
∀E
P(x) ∧ Q(x)
P(x) ∧ Q(x)
∧E
∧E
P(x)
Q(x)
∃I
∃I
∃x P(x)
∃x Q(x)
∧I
∃x P(x) ∧ ∃x Q(x)
→I1
∀x (P(x) ∧ Q(x)) → (∃x P(x) ∧ ∃x Q(x))
(5)
[∀x P(x)]2
∀E
P(x)
[P(x) → Q(x)]1
→E
Q(x)
∃I
∃x Q(x)
[∃x (P(x) → Q(x))]3
∃E1
∃x Q(x)
→I2
∀x P(x) → ∃x Q(x)
→I3
∃x (P(x) → Q(x)) → (∀x P(x) → ∃x Q(x))
(6)
[∃x P(x) ∨ ∃x Q(x)]3
[Q(x)]1
[P(x)]1
∨I
∨I
P(x) ∨ Q(x)
P(x) ∨ Q(x)
∃I
∃I
[∃x Q(x)]2 ∃x (P(x) ∨ Q(x))
[∃x P(x)]2 ∃x (P(x) ∨ Q(x))
1
∃E
∃E1
∃x (P(x) ∨ Q(x))
∃x (P(x) ∨ Q(x))
∨E2
∃x (P(x) ∨ Q(x))
→I3
∃x P(x) ∨ ∃x Q(x) → ∃x (P(x) ∨ Q(x))
2
問題 2
(1) 解答例． L-構造として， M = h{0, 1}, PAi， PA = {0} をとる． v を付値とする
とき， [[P(x)]]v[0/x][1/y] = T， [[P(y)]]v[0/x][1/y] = F より， [[P(x) → P(y)]]v[0/x][1/y] = F と
なる．よって， [[∀y (P(x) → P(y))]]v[0/x] = F．よって， [[∀x ∀y (P(x) → P(y))]]v = F．
(2)
[P(x)]1
→I1
P(x) → P(x)
∃I
∃y (P(x) → P(y))
∃I
∃x ∃y (P(x) → P(y))
問題 3
(1)
REFL
∀x (x ≈ x)
x + y ≈ x + y ∀E
∃I
∃z (x + y ≈ z)
∀I
∀y ∃z (x + y ≈ z)
∀I
∀x ∀y ∃z (x + y ≈ z)
(2)
[P(x) ∧ x ≈ y]1
[P(x) ∧ x ≈ y]1
∧E
∧E
x≈y
P(x)
SUBST
P(y)
→I1
P(x) ∧ x ≈ y → P(y)
∀I
∀y (P(x) ∧ x ≈ y → P(y))
∀I
∀x ∀y (P(x) ∧ x ≈ y → P(y))
問題 4
(1)
(2)
[∀x P(x) ∧ ∀y Q(y)]1
[∀x P(x) ∧ ∀y Q(y)]1
∧E
∧E
∀x P(x)
∀y Q(y)
∀E
∀E
P(z)
Q(z)
∧I
P(z) ∧ Q(z)
∃I
∃z (P(z) ∧ Q(z))
→I1
∀x P(x) ∧ ∀y Q(y) → ∃z (P(z) ∧ Q(z))
[∀x P(x)]1
[∀x P(x)]1
∀E
∀E
P(z)
P(y)
∃I
∃I
∃z P(z)
∃y P(y)
∧I
∃z P(z) ∧ ∃y P(y)
→I1
∀x P(x) → ∃z P(z) ∧ ∃y P(y)
3
(3)
(4)
[P(y)]1 [P(y)]1
∧I
P(y) ∧ P(y)
∃I
∃z (P(y) ∧ P(z))
∃I
[∃x P(x)]2 ∃y ∃z (P(y) ∧ P(z))
∃E1
∃y ∃z (P(y) ∧ P(z))
→I2
∃x P(x) → ∃y ∃z (P(y) ∧ P(z))
[∀x ∀y (P(x) → Q(y))]2
∀E
∀y (P(z) → Q(y))
∀E
P(z) → Q(y)
[P(z)]1
→E
Q(y)
∀I
[∃x P(x)]3
∀y Q(y)
∃E1
∀y Q(y)
→I2
∀x ∀y (P(x) → Q(y)) → ∀y Q(y)
→I3
∃x P(x) → ∀x ∀y (P(x) → Q(y)) → ∀y Q(y)
(5)
(6)
[Q → P(x)]1 [Q]2
→E
P(x)
∃I
∃x P(x)
[∃x (Q → P(x))]3
∃E1
∃x P(x)
→I2
Q → ∃x P(x)
→I3
∃x (Q → P(x)) → (Q → ∃x P(x))
[P(y, y, y)]1
∃I
∃z P(y, y, z)
∃I
[∃x P(x, x, x)]2 ∃y ∃z P(y, y, z)
∃E1
∃y ∃z P(y, y, z)
→I2
∃x P(x, x, x) → ∃y ∃z P(y, y, z)
(7)
(8)
[∀y P(z, z, y)]1
∀E
P(z, z, z)
∃I
∃y P(z, y, y)
∃I
[∃x ∀y P(x, x, y)]2 ∃x ∃y P(x, y, y)
∃E1
∃x ∃y P(x, y, y)
→I2
∃x ∀y P(x, x, y) → ∃x ∃y P(x, y, y)
[P(x)]1
→I1
P(x) → P(x)
∃I
∃y (P(x) → P(y))
∀I
∀x ∃y (P(x) → P(y))
(9)
[¬P(z)]2 [P(z)]1
¬E [Q(z)]1
[∀x (P(x) ∨ Q(x))]
⊥
∀E
⊥
∃I
P(z) ∨ Q(z)
∃x Q(x)
∃x Q(x)
∨E1
∃x Q(x)
[∃x ¬P(x)]3
∃E2
∃x Q(x)
→I3
∃x ¬P(x) → ∃x Q(x)
→I4
∀x (P(x) ∨ Q(x)) → ∃x ¬P(x) → ∃x Q(x)
4
4
(10)
[∀x P(x)]1
∀E
[¬P(y)]2
P(y)
¬E
⊥
1
¬I
[∃x ¬P(x)]3
¬∀x P(x)
∃E2
¬∀x P(x)
→I3
∃x ¬P(x) → ¬∀x P(x)
(11)
[¬P(x)]1
∃I
[¬∃x ¬P(x)]2 ∃x ¬P(x)
¬E
⊥
1
RAA
P(x)
∀I
3
[¬∀x P(x)]
∀x P(x)
¬E
⊥
2
RAA
∃x ¬P(x)
→I3
¬∀x P(x) → ∃x ¬P(x)
5

Download Report