情報論理学 演習２ 解答例
1. ψ = ((p ∧ q) → (r ∨ s)) → ((p ∧ ¬r) → (¬q ∨ s)) とする。¬ψ を CNF（あるいは節形式）
に変換せよ。
⟨[¬ψ]⟩
= ⟨[(p ∧ q) → (r ∨ s)], [¬((p ∧ ¬r) → (¬q ∨ s))]⟩
= ⟨[¬(p ∧ q), (r ∨ s)], [(p ∧ ¬r)], [¬(¬q ∨ s)]⟩
= ⟨[¬p, ¬q, r, s], [p], [¬r], [q], [¬s]⟩
CN F (¬ψ) = ( ¬p ∨ ¬q ∨ r ∨ s) ∧ (p) ∧ (¬r) ∧ (q) ∧ (¬s)
あるいは、
CN F (¬ψ) = { {¬p, ¬q, r, s}, { p}, {¬r}, {q}, {¬s} }
. . . 節形式
や
CN F (¬ψ) = { ¬p ∨ ¬q ∨ r ∨ s, p, ¬r, q, ¬s }
. . . 節形式の別表現
でも OK
2. p → (q → r), ¬(q → r) ⊢ ¬p を resolution 法により証明せよ。
1) 問題を CNF（節形式）に変換
S = CN F (前提) ∪ CN F (¬帰結)
= CN F (p → (q → r)) ∪ CN F (¬(q → r)) ∪ CN F (¬¬p)
= { ¬p ∨ ¬q ∨ r } ∪ { q, ¬r } ∪ { p }
= { ¬p ∨ ¬q ∨ r, q, ¬r, p }
2) resolution の実行
1
2
3
4
5
6
7
¬p ∨ ¬q ∨ r
q
¬r
p
¬q ∨ r
r
2
裏に続く。
∈S
∈S
∈S
∈S
res. 1, 4
res. 2, 5
res. 3, 6
3. 以下の節集合 S = { 節 1, · · · , 節 43} が充足不能であることを示せ。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
p12 ∨ p13 ∨ p23
p12 ∨ p14 ∨ p24
p12 ∨ p15 ∨ p25
p12 ∨ p16 ∨ p26
p13 ∨ p14 ∨ p34
p13 ∨ p15 ∨ p35
p13 ∨ p16 ∨ p36
p14 ∨ p15 ∨ p45
p14 ∨ p16 ∨ p46
p15 ∨ p16 ∨ p56
p23 ∨ p24 ∨ p34
p23 ∨ p25 ∨ p35
p23 ∨ p26 ∨ p36
p24 ∨ p25 ∨ p45
p24 ∨ p26 ∨ p46
p25 ∨ p26 ∨ p56
p34 ∨ p35 ∨ p45
p34 ∨ p36 ∨ p46
p35 ∨ p36 ∨ p56
p45 ∨ p46 ∨ p56
¬p12 ∨ ¬p13 ∨ ¬p23
¬p12 ∨ ¬p14 ∨ ¬p24
¬p12 ∨ ¬p15 ∨ ¬p25
¬p12 ∨ ¬p16 ∨ ¬p26
¬p13 ∨ ¬p14 ∨ ¬p34
¬p13 ∨ ¬p15 ∨ ¬p35
¬p13 ∨ ¬p16 ∨ ¬p36
¬p14 ∨ ¬p15 ∨ ¬p45
¬p14 ∨ ¬p16 ∨ ¬p46
¬p15 ∨ ¬p16 ∨ ¬p56
¬p23 ∨ ¬p24 ∨ ¬p34
¬p23 ∨ ¬p25 ∨ ¬p35
¬p23 ∨ ¬p26 ∨ ¬p36
¬p24 ∨ ¬p25 ∨ ¬p45
¬p24 ∨ ¬p26 ∨ ¬p46
¬p25 ∨ ¬p26 ∨ ¬p56
¬p34 ∨ ¬p35 ∨ ¬p45
¬p34 ∨ ¬p36 ∨ ¬p46
¬p35 ∨ ¬p36 ∨ ¬p56
¬p45 ∨ ¬p46 ∨ ¬p56
p12
p13
p14
∈S
∈S
∈S
∈S
∈S
∈S
∈S
∈S
∈S
∈S
∈S
∈S
∈S
∈S
∈S
∈S
∈S
∈S
∈S
∈S
∈S
∈S
∈S
∈S
∈S
∈S
∈S
∈S
∈S
∈S
∈S
∈S
∈S
∈S
∈S
∈S
∈S
∈S
∈S
∈S
∈S
∈S
∈S
44
45
¬p13 ∨ ¬p23
¬p14 ∨ ¬p24
res. 41, 21
res. 41, 22
49
¬p14 ∨ ¬p34
res. 42, 25
56
¬p23
res. 44, 42
60
p24 ∨ p34
res. 56, 11
63
¬p24
res. 45, 43
67
p34
res. 63, 60
70
71
¬p14
2
res. 67, 49
res. 70, 43
2
© Copyright 2024 ExpyDoc
