人工知能概論
13章、14章の解答抜粋
2016年度春学期講義
白井英俊
演習13-1
• 下の真理値表を完成させよ．(T=1, F=0)
p
q
T
T
T
F
F
T
F
F
￢p∨q
p→q
￢(q→p)
p∧￢p
演習13-1
• 下の真理値表を完成させよ．(T=1, F=0)
p
q
￢p∨q
p→q
￢(q→p)
p∧￢p
T
T
T
T
F
F
T
F
F
F
F
F
F
T
T
T
T
F
F
F
T
T
F
F
演習13-2
先に挙げた例，
p1 すべての人は平和を好む
p2 太郎は人である．
p3 太郎は平和を好む．
をそれぞれ，述語論理式であらわしてみよう．
何をどのように変数と置くかは自分で考えてみよう．
演習13-2
• 先に挙げた例，
「(xが)人」を Human(x)
「(xがyを)好む」を Like(x,y)
「平和」を PEACE
「太郎」を 太郎 で表すとする
• p1 すべての人は平和を好む
• p2 太郎は人である．
• p3 太郎は平和を好む．
• をそれぞれ，述語論理式であらわしてみよう．
• 何をどのように変数とおくかは自分で考えてみよう．
1. ∀ ( → , )
2. Hum(太郎)
3. 太郎, )
演習問題 13-3
次の命題論理式を連言標準形の節形式に変換しなさい．
（p→q）∧（¬p→¬（q∨r））
ドモルガン則
解答
(¬p ∨ q) ∧(¬ ¬ p ∨ （ ¬ q∧ ¬ r））
(¬p ∨ q) ∧(p ∨ （ ¬ q∧ ¬ r））
分配律
(¬p ∨ q) ∧(p∨ ¬ q) ∧ （ p ∨ ¬ r）
演習13-4
次の述語論理式のスコーレム標準形を求め，節集合形式
で表しなさい．
∀x∃y[P(x)→Q(x,y)]∧¬(∀x∃y[P(x)∧∀zR(z)])
同値と含意の除去
∀x∃y[¬ P(x)∨Q(x,y)]∧¬(∀x∃y[P(x)∧∀zR(z)])
二重否定の除去とド・モルガンの法則による否定記号の移動
∀x∃y[¬ P(x)∨Q(x,y)]∧ (¬ ∀x∃y[P(x) ∧ ∀zR(z)])
∀x∃y[¬ P(x)∨Q(x,y)]∧ (∃ x ∀ y ¬ [P(x) ∧ ∀zR(z)])
∀x∃y[¬ P(x)∨Q(x,y)]∧ (∃ x ∀ y [¬ P(x) ∨ ¬ ∀zR(z)])
∀x∃y[¬ P(x)∨Q(x,y)]∧ (∃ x ∀ y [¬ P(x) ∨ ∃ z ¬ R(z)])
変数の標準化
∀x∃y[¬ P(x)∨Q(x,y)]∧ (∃ u [¬ P(u) ∨ ∃ w ¬ R(w)])
演習13-4(解答続き)
変数の標準化の結果
∀x∃y[¬ P(x)∨Q(x,y)]∧ (∃ u [¬ P(u) ∨ ∃ w ¬ R(w)])
スコーレム関数を用いた存在記号の除去（ｆ
スコーレム関数を用いた存在記号の除去（ は関数、a,bは定数)
∀x [¬ P(x)∨Q(x, f(x))]∧ ([¬ P(a) ∨ ¬ R(b)])
冠頭形への変形
∀x { [¬ P(x)∨Q(x, f(x))]∧ (¬ P(a) ∨ ¬ R(b)) }
分配律を用いて節形式へ変形 --- すでに節形式
各節の変数の独立化--各節の変数の独立化 すでに済んでいる
節集合
｛ (¬ P(x)∨Q(x, f(x)) ),
(¬ P(a) ∨ ¬ R(b)) }
演習14-1
前提(P∧Q)→R, P→Q, P から結論Q∧Rが導けることを，
導出原理を用いて証明せよ．
解答：
まず前提と、結論の否定とを節集合の形で表す
{ ¬P ∨¬Q ∨R , ¬P ∨Q , P , ¬Q ∨¬R }
これから導出節を次々に作り、空節（矛盾）を導く
その導出グラフは次の通り;
¬P ∨¬Q ∨R
¬P ∨Q
¬Q ∨R
P
¬P ∨¬R
Q
¬R
R
□
¬Q ∨¬R
演習14-2 一般疑問文 解答
前提と質問を論理式で表し、前提の論理式と「質問の論理式の否定」を節集合
で表す。
「ネズミは動物だ」
∀x(ネズミ(x)→動物(x))
「あらゆる動物は生き物だ」
∀x(動物(x)→生物(x))
「山田は人間だ」
人間（山田）
質問「ネズミは生き物か？」
∀x(ネズミ(x)→生物(x))
前提、および質問の否定の節集合: (aはスコーレム定数)
{ ¬ネズミ(x)∨動物(x), ¬動物(y)∨生物(y), 人間(山田),
ネズミ(a) , ¬生物(a) }
演習14-2 一般疑問文 解答(続)
導出グラフ
¬ネズミ(x)∨動物(x)
人間(山田)
¬動物(y)∨生物(y）
ネズミ(a)
s={y/a}
s={x/a}
動物(a)
¬動物(a)
□
¬生物(a)
演習14-3 特殊疑問文(解答)
まずは論理式で表し、前提および「質問の否定」の節集合
を求める
∀x(ネズミ(x)→動物(x))
「ネズミは動物だ」
「あらゆる動物は生き物だ」
∀x(動物(x)→生物(x))
人間（山田）
「山田は人間だ」
∀x(人間(x)→動物(x))
「あらゆる人間は動物だ」
∃x 動物（x）
質問「動物なのは誰か？」
前提、および質問の否定の節集合: (aはスコーレム定数)
{ ¬ネズミ(x)∨動物(x), ¬動物(y)∨生物(y), 人間(山田),
¬人間(ｚ)∨動物(z), ¬動物（w) }
演習14-3 特殊疑問文 解答(続)
導出グラフ
¬ネズミ(x)∨動物(x)
人間(山田)
¬人間(ｚ)∨動物(z)
¬動物（w)
¬動物(y)∨生物(y）
s={z/山田}
動物(山田)
s={ｗ/山田}
□