融合原理

認知システム論知識と推論（３）
知識と論理で問題を解決する
融合原理による推論
(resolution)
推論規則
融合原理
推論規則
(Inference rules)
命題論理の推論規則（1/5）：推論規則とは？
推論規則
P1
P2
前提
Pn
Q
結論
前提がすべて知識ベース（ＫＢ）に入っていたら，
結論をＫＢに追加してよい．
P1
P1 P2 Pn
R
S
P2
Pn
Q
状態遷移
P1 P2 Pn
R Q S
命題論理の推論規則（2/5）：モーダス・ポネンス
モーダス・ポネンス
P
P Q
Q
P, Q はKB内の論理式（命題）そのものではなく，それらを
値としてとる変数（命題変数）を表している．
Glitter→Gold
Glitter
P P Q
Q
Glitter→Gold
Glitter
Gold
輝くものは黄金である．
それは輝いている．
それは黄金である．
命題論理の推論規則（3/5）：健全性
推論規則
P1
P2
Pn
Q
P1, P2 ,
, Pn
は，
Q
を満たすとき，健全であるという．
Q
は
P1, P2 ,
P1, P2 ,
, Pn
, Pn
の論理的帰結
のすべてを真とする
どんな解釈のもとでも
Q
が真
命題論理の推論規則（4/5）：健全な推論規則
例
モーダス・ポネンス
P
P Q
Q
は，健全な推論規則である．
（４通りの解釈について確認せよ）
例
逆は真なり
PQ
QP
は，健全ではない．
（逆は真とは限らぬ．P =F，Q =T のときを考えよ）
命題論理の推論規則（5/5）：その他の推論規則
以下の推論規則は，いずれも健全である
三段論法
対偶
P Q
Q  P
PQ Q R
PR
∧導入
∧除去
∨導入
∨除去
P Q
PQ
PQ
P
P
PQ
P  Q P
Q
例題魔宮の世界
背景知識
(1,2) にモンスターがいるなら，(1,1) で異臭を感じる
M 12  S11
(1)
(1,2) に落とし穴があるなら，(1,1) で風を感じる
P12  B11
(2)
(1,2) にモンスターも落とし穴もないなら，(1,2) はOK
M12  P12  OK12
事実
(1,1) で異臭を感じない
S11
(4)
(1,1) で風を感じない
B11
(5)
(3)
質問
(1,2) はOKか？
OK12
(6)
と仮定し，充足不能
であれば OK
例題魔宮の世界：推論規則による判定
M 12  S11
P12  B11
(1)
M12  P12  OK12
S11
(4)
B11
(5)
OK12
(2)
(3)
対偶：(1)より
(6)
ＭＰ：(4),(7)より
対偶：(2)より
MPは
モーダス・ポネンス
の略
証明
S11  M 12
(7)
M 12
(8)
B11  P12
(9)
P12
(10)
∧導入：(8),(10)より M 12  P12
(11)
ＭＰ：(5),(9)より
ＭＰ： (11),(3)より
∨除去： (6),(12)より
ゆえに，充足不能
OK12
□
(12)
(13)
空節（矛盾）
疑問点と問題点
推論規則は，あれだけで十分か？
もっと多く必要か？もっと少なくてよいか？
適用可能な推論が多すぎて，探索効率が悪い
∨導入
P
PQ
融合というただ１つの推論規則だけ
あれば十分である．
融合原理
(Resolution principle)
融合原理（1）
融合 (resolution)
節に対して適用する推論規則
PC
CとDは節
P  D
CD
融合節
符号の異なるリテラルを１個ずつキャンセルし，
残りのリテラルを∨で結合する．
キャンセルするリテラルの節の中の場所はどこでもよい．
（左端である必要はない）
重複したリテラルは１個を残して削除する．
融合原理（2）：例
例
P  Q Q  R
P R
例
P  Q P  Q
P P
重複したリテラルは削除する
ダメな例
P  Q P   Q  R
R
まとめて２個キャンセルするのは，ダメ！
融合原理（3）：例
例
モーダス・ポネンス
P P  Q
Q
P PQ
Q
例三段論法
P  Q Q  R
P  R
例
矛盾
P
P
空節
PQ Q R
PR
融合原理（4）：導出と導出可能性
導出と導出可能性
節集合 {P1, P2 ,
, Pn }に次々と融合を適用し，
節の系列
P1, P2 ,
, Pn , R1, R2 ,
, Rk , Q
が得られるとき，
という．
P1, P2 ,
また， P1, P2 ,
とかく．
, Pn から Q が導き出される
, Pn から Q へ導出可能といい，
P1, P2 ,
, Pn
Q
融合原理（5）：健全性
定理
任意の２つの節Ｃ１，Ｃ２の融合節Ｃは
Ｃ１，Ｃ２の論理的帰結になっている．
証明
C1  P  C1 C2  P  C2 C  C1  C2
Ｃ１，Ｃ２を T とする解釈を考える．
C1  T
P = T の場合： C2  T
P = F の場合：
C1  C2  T
健全性：導出したものは論理的帰結になっている．
P1, P2 , , Pn
Q ならば P1, P2 , , Pn
Q
融合原理（6）：完全性
健全性の別な言い方：
節集合 S から空節 □ が導き出されれば，
S は充足不能である．
定理
逆
完全性
節集合 S が充足不能ならば
S から空節 □ を導き出すことができる．
融合原理（7）：融合原理を用いた証明
Q
は
P1, P2 ,
, Pn
の論理的帰結
同値
P1  P2 
P1, P2 ,
, Pn
 Pn  Q
は充足不能
同値
節集合
S  C1,
, Ck 
は充足不能
同値
S  C1,
, Ck 
から空節を導出可能
融合原理（8）：例題魔宮の世界
M12  S11
S11
(1)
P12  B11
(2)
M12  P12  OK12
(4)
B11
(5)
OK12
知識ベース
(3)
(6) 結論の否定
(1),(4)より
M12
(7)
(2),(5)より
P12
(8)
(3),(6)より
(8),(9)より
(7),(10)より
M12  P12
M12
(9)
(10)
(11) 矛盾
融合原理（9）：例題魔宮の世界：証明の探索
(1)
(2)
(3)
(4)
(5)
(6)
M 12  S11 P12  B11 M 12  P12  OK12 S11 B11 OK12
S11  P12  OK12 B11  M 12  OK12 M 12 P12 M 12  P12
(9)
(7) (8)
B11  S11  OK12
B11  OK12
M 12
(10)
(11)
証明に不必要な節もたくさん導出されている
効率向上のための工夫が必要
融合原理（10）：証明の探索の制御
初期状態 CLOSEDは空リスト．すべての節を OPENに．
CLOSED LIST
OPEN LIST
一般の状態 CLOSEDリスト内のどの２つの節も融合済み
C
C
C
C
parent
各Ｃと融合
child
導出節をOPENに追加
融合原理（11）：証明アルゴリズム
boolean Prove (KB, Q) { // KB: 知識ベース（公理）， Q: 質問（定理）
OPEN ← KB∧¬Q を節集合に変換したもの．
CLOSED ← { }
while ( OPEN≠{ } ) {
parent ← OPEN に含まれる任意の１つの節．
OPENから parent を削除する．
for each clause C in CLOSED do {
children ← parent と Cからのすべての導出節の集合．
if ( □∈children ) return true
KB∧¬Q は充足不能
childrenに含まれる節のうち，OPENにもCLOSEDにも
含まれないものをOPENに追加する．
}
}
return false
}
KB∧¬Q は充足可能

Download Report