人工知能特論2007 No.7

人工知能特論2011
資料No.7
東京工科大学大学院
担当教員亀田弘之
前回までの確認から
はじめに論理式φありき
1. 論理式φを等価変形し、Prenex Conjunctive
Normal Form (PCNF)の形式ψにする。
例 xP( x)  xQ( x)
 ~ xP( x )  xQ( x )
 ~ xP( x )  yQ( y )
 x ~ P ( x )  yQ( y )
 x (~ P ( x )  yQ( y ))
 xy (~ P ( x )  Q ( y ))
Prenex Conjunctive Normal Form
q1x1 qn xn (C1  Cm )
qiはかであり、 x1, x2 ,, xnはすべて論理式に現れる変数
4
Prenex Conjunctive Normal Form
Clause
q1x1 qn xn (C1  Cm )
Prenex
Matrix
qiはかであり、 x1, x2 ,, xnはすべて論理式に現れる変数
イメージ：
∀x∃y∃z∀u．．．
イメージ：
(P(x)∨Q(y, f(z))) ∧P(u)∧(Q(x, u)∨P(z, f(f(y))))
5
PCNFをSSFに
2. PCNFをさらにSkolem Standard Form
(SSF) に変形する。
（注）この変形は真理値を保存しない
ことに注意。
Skolem Standard Form
Clause
q1x1 qn xn (C1  Cm )
Prenex
Matrix
qiはだけであり、 x1, x2 ,, xnはすべて論理式に現れる変数
7
Prenex Conjunctive Normal Form
Clause
q1x1 qn xn (C1  Cm )
Prenex
Matrix
qiはだけであり、 x1, x2 ,, xnはすべて論理式に現れる変数
イメージ：
∀x∀u．．．
イメージ：
(P(x)∨Q(g(x), f(z))) ∧P(u)∧(Q(x, u)∨P(h(x), f(f(g(x)))))
8
PCNF ＝＞ SSFへの書き換え
• 限量記号（存在記号）∃を除去しなければなら
ない。そのために、スコーレム定数やスコーレ
ム関数を導入する。
• 例：
xyP( x, y)  xP( x, f ( x))
yxP( x, y)  xP( x, a)
9
確認：大切な注意事項（その１）
• 任意の論理式はPCNFに変形可能
• 任意のPCNFはSSFに変形可能
• 任意の論理式とそれから導かれるSSFとは
論理的に等価であるとは限らない（真理値は
必ずしも保存されない！）。
10
真理値が保存されない例
  xP( x)
  P(a)
1.D  {1,2}
2.　a  2  D
3.　I p (1)  T　and　I p (2)  F ; I  {P(1)}
確認：大切な注意事項（その２）
• BUT
• 充足不可能な論理式は充足不可能なSSF
に変形される。
• 元の論理式がモデルを持つための必要十
分条件は、SSFがモデルを持つことである。
（これは重要な定理の１つ）
12
定理
• 任意の論理式φに対して、そのSSFをψとする。
このとき、以下の関係が成り立つ。
Ψ |= φ
つまり、
・φはψの論理的帰結である。
・ψが真となる解釈はどれも
φを真とする解釈にになっている。
・ψのモデルはφのモデルでもある。

定理
• 任意の論理式φに対して、そのSSFをψとする。
このとき、以下のことが成り立つ。
・ψが充足不可能ならばφも充足不可能である。
・ψがモデルを持たなければ
φもモデルを持たない。
定理
• 任意の論理式φに対して、そのSSFをψとする。
このとき、以下のことが成り立つ。
・ψが充足不可能ならばφも充足不可能であり、
かつ、その逆も成り立つ・。
・ψがモデルを持たないことと、
φもモデルを持たないこととは等価である。
Herbrand Models（復習）
• フランスの論理学者Jacques Herbrand が考
案したとある解釈(interpretation)のこと。
この解釈を特に、Herbrand interpretation とよ
び、この解釈に基づくモデルを Herbrand
model と呼ぶ。
その実態は．．．
16
HMの構造をもう一度見てみよう！
•
•
•
•
•
Herbrand universe U
Herbrand base B
Herbrand pre-interpretation J
Herbrand interpretation I
Herbrand model M
以下、例で説明する。
17
HMの構造をもう一度見てみよう！
• Herbrand universe U ＜＝解釈の領域
• Herbrand base B ＜＝アトムの集合
• Herbrand pre-interpretation J
＜＝項と領域要素との対応を定義
• Herbrand interpretation I
＜＝アトムの真理値を定義
• Herbrand model M
以下、例で説明する。
18
例：
{P(a), Q(a, f (b)),x( P( x)  Q( x, x))}
まず、このような論理式
の集合を考える。
19
Herbrand Universe
U  {a, b, f (a), f (b), f ( f (a)), f ( f (b)),}
元の論理式に含まれていた定数と関数に着目し、
これからか得られるすべての項を集めたもの。
20
Herbrand Base
B  {P(a), P(b), Q(a, a),Q(b, b), P( f (a)), P( f (b)),}
元の論理式に含まれていた述語を、先ほどのUの
要素に適用して得られる述語すべてからなる集合。
21
Herbrand pre-interpretation
• 解釈の領域D：Hebrand Universe U
• 定数記号の解釈: 自分自身に対応させる。
• 関数記号の解釈：自分自身に対応させる。
22
Herbrand pre-interpretation
• 解釈の領域D：Hebrand Universe U
• 定数記号の解釈: 自分自身に対応させる。
• 関数記号の解釈：自分自身に対応させる。
ここがポイント！
23
Herbrand interpretation
• Herbrand pre-interpretation に基づく
Interpretation をHerbrand Interpretation
(HI) と呼ぶ。
• なおHIの内、所与の論理式（群）を充足する
ものを Herbrand Model (HM) と呼ぶ。
24
例:  {P(a),Q(a, f (b)),x( P( x)  Q( x, x))}
• H Pre-I J:
1. 領域 U ＝ Herbrand Universe
2. 定数記号 a in φ  個体 a ∈ U,
定数記号 b in φ  個体 b ∈ U.
3. 関数記号f in φ  関数f(t) ∈ U.
4. 真理値割り当て：
•
•
•
•
I1 ={P(a), P(b), Q(a, b), Q(b,b) }
I2 ={P(a), Q(a, a), Q(a, f(b)) }
I3 ={P(f(f(a))), P(b), Q(a, a), Q(a, f(b)) }
I4 ={P(a), P(b), Q(a, a), Q(b, b), Q(a, f(b)) }
注意事項
• HMの意義
1.Σがモデルを持つ  ΣがHMを持つ。
2.Σ ｜＝ φ  SはHMを持たない。
ただし、Sは Σ∪{～φ} のSSF。
述語論理における推論
•
•
•
•
Resolution
代入
論理プログラミング（Prologなど）
帰納論理プログラミング(Progolなど)
＝＞知識分類・知識獲得・知識発見
以降は、Prologを使って説明します。

Download Report