命題論理

認知システム論 知識と推論(5)
知識と論理で問題を解決する
節集合
(set of clauses)
一階述語論理による知識表現の技法
節集合への変換
復習(1/3)
個体記号
オブジェクト(個体)を表現
A
A
オブジェクトの性質(property)を命題として表現
Mortal
A
A is mortal.
Mortal ( A)
オブジェクト間の関係(relation)を命題として表現
A is a friend of B.
A
B
オブジェクト間の関数(function)を表現
A
father of A
名前の
ない要素
述語記号
(1変数)
述語記号
(2変数)
Friend ( A, B)
関数記号
father ( A)
復習(2/3)
項
(1) 定数は項である.
20
(2) 変数は項である.
x
(3) f が n 変数の関数記号, t1, , tn が項ならば,
f ( 1t ,
n
, tは項である.
)
age( father ( John))
原子式
P が n 変数の述語記号, t1,
P(t1, , tn ) は原子式である.
, tn が項ならば,
GREATER(age( John),20)
復習(3/3)
限量子:
(x)
All
(x)
全称記号 「すべての x について」
(for all x , …)
存在記号「ある x が存在して」
(there exists x such that …)
Exist
s
述語論理による知識表現の技法
表現の技法(1/9) 定義域
定義域(オブジェクトの世界)を決定する
D = {Jack, Elizabeth,...} :いろいろな人の集合
D = {0, 2, π,1+2i, ...} : すべての数の集合
表現の技法(2/9) 個体記号(定数)
固有名詞,数詞は個体記号(定数)で表現
Jack, Mickey,Sapporo
2, π
点P,直線L,三角形ABC
表現の技法(3/9) 述語記号
普通名詞,形容詞,動詞は述語記号で表現
DOCTOR(x):
x is a doctor.
INT(x):
x is an integer.
RED(x):
x is red.
GREATER(x, y):
x is greater than y.
ON(x, y):
Point x lies on Line y.
LOVES(x, y):
x loves y.
PRODUCT(x, y, z): The product of x and y is z.
表現の技法(4/9) 関数記号
2変数以上の述語で1つの引数が他の引数から
一意に決定できる
MOTHER(x, y):
y is the mother of x.
SUCCESSOR(x, y): y is the successor of x (y=x+1).
MID(x, y, z):
z is the midpoint of x and y.
関数記号で表すことも可能
the 普通名詞 of は関数記号で表現
mother(x): the mother of x
s(x):
the successor of x (= x + 1)
mid(x, y): the midpoint of x and y
表現の技法(5/9) ∀と→の組合せ
「P は Q である」 という一般的な叙述は,
(∀x)( P(x) → Q(x) ) のパターン使う.
(1) 花は美しい.
Flower is beautiful.
(∀x)( FLOWER(x) → BEAUTIFUL(x) )
(2) 偶数は2で割り切れる.
Every even number is divided by 2.
(∀x)( EVEN(x) → DIVIDES(s(s(0)), x) )
表現の技法(6/9) ∃と∧の組合せ
「 a +普通名詞」 は,∃ と ∧ の組合せを使う.
ジャックはある女性を愛している.
Jack loves a woman.
(∃w)(WOMAN(w) ∧LOVES(Jack, w))
表現の技法(7/9) (∀x)(∃y)
全称記号と存在記号の出現順序が意味をもつ
(x)(y ) P( x, y )
任意のx に対し,あるy が存在し,P(x,y) が成り立つ
P(x,y)
y
a
b
c
a
T
F
F
b
F
T
F
c
T
T
F
x
表現の技法(8/9) (∃y)(∀x)
全称記号と存在記号の出現順序が意味をもつ
(y )(x) P( x, y )
あるy が存在し,任意のx に対し,P(x,y) が成り立つ
P(x,y)
y
a
b
c
a
T
T
F
b
F
T
F
c
F
T
F
x
表現の技法(9/9) 技法の組合せ
(1) すべての男性はある女性を愛している.
Every man loves a woman.
(∀m)( MAN(m) →
(∃w)(WOMAN(w) ∧LOVES(m, w))
各男性(m)ごとに,愛している女性(w)が異なる
(2) すべての男性が愛する女性がいる.
There exists a woman every man loves.
(∃w) (WOMAN(w) ∧
(∀m)( MAN(m) → LOVES(m, w)) )
全男性(m)が,特定の1人の女性(w)を愛している
節集合への変換
節形式への変換の概要
一階述語論理の論理式
等価
冠頭標準形
1.同値と含意を除去する
2.否定を原子論理式の直前に移す
3.変数名を付け替える
4.冠頭標準形にする
連言標準形
5.連言標準形にする
等価ではないが,充足可能性は保存
スコーレム標準形
節集合
6.スコーレム標準形にする
7.節集合にする
冠頭標準形への変換(1)
冠頭標準形
論理式は次の形をしているとき冠頭標準形であるという.
(Q1 x1 )
(Qn xn ) M
前置部
母式
ただし,各 (Qi xi )(i  1,, n) は,(xi ) か (xi ) であり,
M は限量子を含まない論理式である.
例
(x)(y)(z )( P( x, y)  Q( y, z ))
冠頭標準形への変換(2)
1.同値と含意を除去する
F  G  ( F  G)  (G  F )
F  G  F  G
2.否定を原子の直前まで移す
(F )  F
( F  G)  F  G
( F  G)  F  G
(x) F  (x)(F )
(x) F  (x)(F )
冠頭標準形への変換(3)
3.変数名を付け替える
各限量子に対応する変数が他の限量子に対応する
変数と同じ名前にならないように必要に応じて付
け替える
例
(x) F ( x)  (x)G( x)
(x) F ( x)  (y)G( y)
ステップ4
(x)(y)( F ( x)  G( y))
冠頭標準形への変換(4)
NOTE M(x): x is a man. W(x): x is a woman.
(x) M ( x)  (x)W ( x)  (x)[ M ( x)  W ( x)]
(x) M ( x)  (x)W ( x)  (x)[ M ( x)  W ( x)]
NOTE
下記のケースは付け替えなくても良い
(x) M ( x)  (x)W ( x)  (x)[ M ( x)  W ( x)]
(x) M ( x)  (x)W ( x)  (x)[ M ( x)  W ( x)]
冠頭標準形への変換(5)
4.冠頭標準形にする
限量子を外側(左側)に移動する
((Qx ) F[ x])  G  (Qx )( F[ x]  G)
((Qx ) F[ x])  G  (Qx )( F[ x]  G)
(x) F ( x)  (x) H ( x)  (x)[ F ( x)  H ( x)]
(x) F ( x)  (x) H ( x)  (x)[ F ( x)  H ( x)]
(Q1 x) F ( x)  (Q2 x) H ( x)  (Q1 x)(Q2 z)[ F ( x)  H ( z)]
(Q1 x) F ( x)  (Q2 x) H ( x)  (Q1 x)(Q2 z)[ F ( x)  H ( z)]
冠頭標準形への変換(5)
例
(x) P( x)  (x)Q( x)
 ((x) P( x))  (x)Q( x)
 (x)(P( x))  (x)Q( x)
 (x)(P( x)  Q( x))
連言標準形への変換(1)
リテラル
原子式 はリテラルである.

例 P( x, y) 正リテラル
原子式
Q( x, y) 負リテラル
p  q  rはリテラルである.
節
リテラルの選言(orで結合したもの)
例 P( x, y)  Q( x, y)
( p  q)  ( p  q)  r
連言標準形
節の連言(andで結合したもの)
例 ( P( x, y)  Q( x, y))  ( R( x)  Q( x, y))
連言標準形への変換(2)
5.連言標準形にする
冠頭標準形
(Q1 x1 ) (Qn xn )M
M を連言標準形にする
分配則を使って∨を入れ子の内側へ移動していき
,リテラル同士を直接接合するようにする
F  (G  H )  ( F  G)  ( F  H )
スコーレム標準形への変換(1)
6.スコーレム標準形にする
冠頭標準形
M が連言標準形
(Q1 x1 ) (Qn xn )M
存在記号をすべて除去する
・等価性は失われる
・充足可能性は変わらない
スコーレム標準形
スコーレム標準形への変換手順:
最も左にある存在記号に着目し,以下の処理(つぎの2つの
スライド)を存在記号がなくなるまで繰り返す
スコーレム標準形への変換(2)
(x )(Q x )
1
2
2
(Q x ) M
n
n
のとき
1.M に現れない新しい定数 a を任意に選び,M中
のすべての x1 を a で置き換える. a をスコーレム定
数という.
2.(x1 ) を前置部から除去する
例
(x)(y)(z )(w)[P( x, y)  Q( x, z, w)]
(y)(z )(w)[P(a, y)  Q(a, z, w)]
スコーレム標準形への変換(3)
(x )
1
(x )(x )(Q x )
k 1
k
k 1
k 1
(Q x ) M
n
n
のとき
1.M に現れない新しい関数記号 f を任意に選び,M中
のすべての xk を f ( x1 , x2 ,, xk 1 ) で置き換える.f をスコ
ーレム関数という.
2.(xk ) を前置部から除去する
例
(y)(z )(w)[P(a, y)  Q(a, z, w)]
(y)(z )[P(a, y)  Q(a, z, f ( y, z ))]
節集合への変換
7.節集合にする
スコーレム標準形
M が連言標準形
(x )
1
(x ) M
k
Mに含まれている節を集める
節集合
例
(x)(y)[(P(a, x)  Q( x))  Q( y)]
P(a, x)  Q( x)

Q( y )