人工知能特論2007 No.

人工知能特論2009
No.6(前半部分は前回と同じ)
東京工科大学大学院
亀田弘之
まずは、復習から。
2
論理体系構築の手順（復習）
字母の決定
（論理式を記述するための記号群を決める）
 Syntax
（記号の意味ある並びを決める。論理式であ
るための条件、論理式の表現規則を決める）
 Semantics
（論理式の意味の取り扱いを決める）
 その後、推論へと話を進める。

3
確認

字母
定数：
 変数:
 関数記号:
 述語記号:
 結合子:
 限量記号:
 補助記号:

a, b, c, d, …
x, y, z, w, …
f, g, h, …
P, Q, R,
~, ∧, ∨, →, ↔
∃, ∀
( ) ,
4
定義４．２項(Term)
1.
2.
3.
定数は項である。
変数は項である。
もし f が arity n （n変数）の関数記号であ
り、t1, t2,… tn が項であるならば、
f( t1, t2, … , tn )
は項である。
5
定義４．３ ( well-formed ) 論理式
1.
2.
3.
4.
Pはn変数の述語記号であり、 t1, t2,… tn
が項であるならば、P(t1, t2,… tn ) は論理式
である。アトムあるいは原始式と呼ぶ。
φが論理式ならば、~φは論理式。
φとψが論理式ならば、
(φ∧ψ), (φ∨ψ), (φ→ψ), (φ↔ψ)
は論理式。
φが論理式、xが変数ならば、
∃x φ , ∀x φ
は論理式。
6
定義４．８ pre-interpretation J
1.
2.
3.
集合D:解釈のための領域（非空集合）
定数記号に対して、Dの要素を割り当てる。
関数記号f (n変数関数)に対して、Dnから
Dへの写像を割り当てる。
つまり、集合Dに基づいて、定数記号や
関数記号の意味（実体）を決める。これが、
pre-interpretation。
7
定義４．９変数割り当てV

変数記号に領域Dの要素を割り当てる。
（variable assignment）
V: 変数記号の集合∋x → d∈D
8
定義４．１０項割り当て
定数記号に対して、pre-interpretation Jに
基づいてDの要素を割り当てる。
 変数記号に対して、変数割り当てVに基づ
いてDの要素を割り当てる。
 t1, t2, …,tn がd1, d2, … ,dn に割り当てられ
るとき、f(t1, t2, …,tn ）は、
Jf(d1, d2, … ,dn ）に割り当てられる。

9
定義４．１１解釈I

Pre-interpretation J が定められているとき、
述語記号Pに対して、Dnから{ T, F } への
写像を割り当てることを解釈という。
10
11
述語論理言語L1

字母
定数：
 変数:
 関数記号:
 述語記号:
 結合子:
 限量記号:
 補助記号:

a, b, c, d, …
x, y, z, w, …
f, g, h, …
P(arity=2), Q, R,
~, ∧, ∨, →, ↔
∃, ∀
( ) ,
論理式を表記する記号群
12
論理式を表記するための記号群
 記号の並べ方の規則（Syntactic Rules）
 Well-formed な論理式
 Pre-interpretation


定数記号と関数記号に意味を与える。
項の割り当て、変数の割り当て
 解釈


述語に意味を与える。
論理式の真偽が決まる
13
例：

論理式
P( x, a ) → Q( x )
これの真偽は？
（解釈Iを決めれば決まる）
・定数 a
・変数 x
・述語PとQ
14
解釈の例
P( x, a ) → Q( x )
解釈の領域
D = { 赤い箱R, 白い箱W, 青い円錐B }
 Pre-interpretation




定数 a = R
関数記号なし
変数の割り当て

V(x) = W
解釈I P(x,y): x が y の上に載っている。
Q(x): x は青い円錐である。
 真偽： P( x, a ) → Q( x ) は＿＿

15
Prenex Conjunctive Normal Form
Literal
 Clause
 PCNF

16
Leteral

Literalの定義：
1.
2.

アトムはリテラル (例： P(x), Q(3,5,8) )
アトムの否定もリテラル (例： ~P(x), ~Q(3,5,8))
上記の１を正リテラル(positive literal)、
２を負リテラル(negative literal) という。
（例： P(f(x)) は正リテラル, ~P(f(x)) は
負リテラル)
17
Clause

Clauseの定義：

ゼロ個以上かつ有限個のリテラルからなる選
言のこと。
例：
1.
2.
P(a) v Q(x,b,f(s))
~Q(x,y) ＜＝１個のリテラルの選言！
18
Clauseの集合による表記法
1.
2.
P(a) v Q(x,b,f(s))
 {P(a) , Q(x,b,f(s))}
~Q(x,y)  {~Q(x,y) }
19
Prenex Conjunctive Normal Form
q1x1 qn xn (C1  Cm )
qiはかであり、 x1, x2 ,, xnはすべて論理式に現れる変数
20
Prenex Conjunctive Normal Form
Clause
q1x1 qn xn (C1  Cm )
Prenex
Matrix
qiはかであり、 x1, x2 ,, xnはすべて論理式に現れる変数
21
PCNFの例
 xy ((P ( x) ~ Q ( x, y ))  (~ R (a, b) ~ P (a )))
 xyz ( S ( x, y, z )  P ( y, z ))
 x((P (a )  P (b)) ~ Q (a, x)  P ( x)  (~ P (b)  Q ( x, x)))
 x ~ y ( P ( y )  Q ( y, a ))
 x( P ( x)  Q ( x, a ))
 ~ y (Q ( y, a ))
22
PCNFへの変形
任意の述語論理式は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 ))
23
定理

任意の論理式φに対して、φと真理値が等
価な論理式ψでかつPCNFのものが１つ
存在する。
24
変形の手順（その１）
1.
論理式φの中の→と↔を次の規則を用いて
取り除く。
1.
2.
2.
（A→B）を (~A v B) に置き換える。
(A↔B) を (~A v B)^(A v ~B) に置き換える。
分離された変数がそれぞれ異なるように変
数名を書き換える。
25
変形の手順（その２）
3.
すべての～がアトムの直前に来るように次
の規則を用いて変形する。
1.
2.
3.
4.
5.
～∀x ψ を ∃ｘ～ψ に置き換える。
～∃ x ψ を ∀ｘ～ψ に置き換える。
～( φ ∨ ψ ) を ( ~φ ∧ ~ψ ) に置き換える。
～( φ ∧ ψ ) を ( ~φ ∨ ~ψ ) に置き換える。
～～φ を φ に置き換える。
26
変形の手順（その３）
4.
すべての限量子∀と∃を論理式の先頭部分
へ移動させる。
1.
2.
3.
4.
5.
6.
7.
8.
∃ｘ φ∨ψ
φ∨∃x ψ
∀ｘ φ∨ψ
φ∨ ∀x ψ
∃ｘ φ∧ψ
φ∧∃x ψ
∀ｘ φ∧ψ
φ∧∀x ψ
＝＞
＝＞
＝＞
＝＞
＝＞
＝＞
＝＞
＝＞
∃ｘ (φ∨ψ)
∃ｘ (φ∨ψ)
∀ｘ (φ∨ψ)
∀ｘ (φ∨ψ)
∃ｘ (φ∧ψ)
∃ｘ (φ∧ψ)
∀ｘ (φ∧ψ)
∀ｘ (φ∧ψ)
27
変形の手順（その4）
5.
Matrix部分をCNF形式に変形する。
1.
2.
((A∧B)∨C) を ((A∨C) ∧(B ∨C)) に
((A∨B)∧C) を ((A∧C) ∨(B ∧C)) に
28
PCNF導出の例（練習問題）
x( P( x)  P( f ( x))) ~ x(Q( x)  R( x, a))
 x(~ P( x)  P( f ( x))) ~ x(Q( x)  R( x, a ))
 x(~ P( x)  P( f ( x))) ~ y (Q( y )  R( y, a))
 x(~ P( x)  P( f ( x)))  y ~ (Q( y )  R( y, a))
 x(~ P( x)  P( f ( x)))  y (~ Q( y ) ~ R( y, a ))
 x((~ P( x)  P( f ( x)))  y (~ Q( y ) ~ R( y, a )))
 xy ((~ P( x)  P( f ( x)))  (~ Q( y ) ~ R( y, a)))
 xy ((~ P( x)  P( f ( x)) ~ Q( y ))  ((~ P( x)  P( f ( x)) ~ R( y, a )))
29
PCNFの曖昧性
１つの論理式から得られるPCNFは１つと
は限らない。
 例：   xyP( x, y )  xQ(a, x)

  xyz ( P( x, y)  Q(a, z ))
  xy( P( x, y)  Q(a, x))
（注）ΑとβはともにΦのPCNF!
30
確認問題

次の置き換えは、真理値を保存することを
確かめよ。
D  {a, b, c}
I  {P(a, c), P(c, b), Q(a, a), Q(a, c), Q(b, a)}
  xyP( x, y )  xQ(a, x)
  xyz ( P( x, y )  Q(a, z ))
  xy ( P( x, y )  Q(a, x))
31
確認問題

次の置き換えは、真理値を保存することを
確かめよ。
D  {a, b, c}
I  {P(a), P(c), P(c)}
  xP( x)  yP( y)
  xy( P( x)  P( y ))
32
Skolem Standard Form
33
Skolem Standard Form
Clause
q1x1 qn xn (C1  Cm )
Prenex
Matrix
qiはだけであり、 x1, x2 ,, xnはすべて論理式に現れる変数
34
PCNF ＝＞ SSF への書き換え
限量記号（存在記号）∃を除去しなければな
らない。そのために、スコーレム定数やス
コーレム関数を導入する。
 例：

xyP( x, y)  xP( x, f ( x))
yxP( x, y)  xP( x, a)
35
大切な注意事項（その１）
任意の論理式はPCNFに変形可能
 任意のPCNFはSSFに変形可能
 任意の論理式とそれから導かれるSSFとは
論理的に等価であるとは限らない（真理値
は必ずしも保存されない！）。

36
大切な注意事項（その２）
BUT
 充足不可能な論理式は充足不可能なSSF
に変形される。
 元の論理式がモデルを持つための必要十
分条件は、SSFがモデルを持つことである。
（これは重要な定理の１つ）

37
Herbrand Models

次に、フランスの論理学者Jacques Herbrand
が考案した解釈(interpretation)を導入する。
この解釈を特に、Herbrand interpretation とよ
び、この解釈に基づくモデルを Herbrand
model と呼ぶ。
38
Herbrand universe U
 Herbrand base B
 Herbrand pre-interpretation J
 Herbrand interpretation I
 Herbrand model M

以下、例で説明する。
39
例：
{P(a), Q(a, f (b)),x( P( x)  Q( x, x))}
40
Herbrand Universe
U  {a, b, f (a), f (b), f ( f (a)), f ( f (b)),}
41
Herbrand Base
B  {P(a), P(b), Q(a, a),Q(b, b), P( f (a)), P( f (b)),}
42
Herbrand pre-interpretation
43
Herbrand interpretation
44

Download Report