人工知能の基礎知識

述語論理式の構文と意味

一階述語論理式の構文



述語，限量記号
自然言語文の述語論理式表現
一階述語論理式の意味



解釈
妥当，充足不能
閉式の充足不能性
©2008 Ikuo Tahara
1
述語論理

述語（predicate）の導入
命題論理による表現
「太郎は人間である」
「花子は人間である」
述語論理による表現
p
q
h(Taro)
述語
h( Hanako)
「・・・人間である」という共通する情報が欠落してしまう
©2008 Ikuo Tahara
2
述語論理

限量記号(quantifier)の導入

a は p である：
p(a)
全称記号

すべての

ある
x は p である： x. p( x)
x は p である：
x. p ( x )
存在記号
©2008 Ikuo Tahara
3
一階述語論理の構文

語彙







個体定数（constant）： a, b, c,
個体変数（variable）： x, y, z,
関数記号（function symbol）： f , g ,
述語記号（predicate symbol）： p, q,
論理記号（connective）： , , , 
限量記号（quantifier）： , 
補助記号（punctuation symbol）： (, )
©2008 Ikuo Tahara
4
一階述語論理の構文

項（term）の帰納的定義
（１）個体定数は項である．
（２）個体変数は項である．
（３） f が n 引数の関数記号，t1 , , tn が項
⇒ f (t1 , , tn ) は項である．
（４）項とは（１），（２），（３）を有限回繰り返し適用して得
られる記号列のみである．
©2008 Ikuo Tahara
5
一階述語論理の構文

整式（wff）の帰納的定義
（１） p が n 引数の述語記号， t1 , , tn が項
⇒ p(t1 , , tn ) は整式（素式）である．
（２）  ,  が整式
⇒  ,    ,    ,    は整式である．
（３）  が整式， x が個体変数
⇒ x. , x. は整式である．
（４）整式とは（１），（２），（３）を有限回繰り返し適用して
得られる記号列のみである．
©2008 Ikuo Tahara
6
限量記号の作用



作用域（scope）: Qx. の  （ただし Q  {, }）
束縛変数（bound variable）：Qx. の  に現れる x
自由変数（free variable）：束縛変数以外の変数
束縛変数
束縛変数
x.[ p( x, y)  x.q( x)]
自由変数
©2008 Ikuo Tahara
7
限量記号の作用

束縛関係： Qx. の x と部分式  の自由変数 x
は Q に束縛されるという．
p( x, y )  xq( x)
x.[ p( x, y)  x.q( x)]
自由変数
q( x)
自由変数

閉式（closed formula）: すべての変数が束縛され
ている整式で，文（sentence）ともいう．
©2008 Ikuo Tahara
8
自然言語文→述語論理式表現

翻訳の基本パターン




すべてのものが p である．（Everything is p.)
⇒ x. p( x)
p なものが存在する．(Something is p.)
⇒ x. p ( x )
すべての p は q である．（Every p is q.）
⇒ x.[ p( x)  q( x)]
ある p は q である．（Some p is q.）
⇒ x.[ p( x)  q( x)]
©2008 Ikuo Tahara
9
自然言語文→述語論理式表現

なぜ「ある p は q である」を「 x.[ p( x)  q( x)] 」
と表現すべきなのか？
「ある p は q である」
x.[ p( x)  q( x)]
否定
否定
「すべての p は q でない」
x.[ p( x)  q( x)]
 x.( p( x)  q( x))
 x.[ p( x)  q( x)]
©2008 Ikuo Tahara
10
表現の例
① 試験が難しい科目の受験者は皆喜ばない．
② 試験が難しくなければ喜ぶ受験者がいる．
③ 数学の受験者しか喜ばない．
p ( x)
q ( x, y )
r ( x)
m
：
：
：
：
x は試験が難しい.
x は y の受験者である.
x は喜ぶ.
数学.
① x.[ p( x)  y.[q( y, x)  r ( y)]]
② x.[p( x)  y.[q( y, x)  r ( y)]]
③ x.[r ( x)  q( x, m)]
©2008 Ikuo Tahara
11
一階述語論理式の意味

解釈（interpretation）： M  ( D,  )


領域（domain）： D
割り当て: 
（１）個体定数 c ：
（２）関数記号 f ：
（３）述語記号 p ：

c  D
f  : Dn  D
p : Dn  {T, F}
変数割り当て： 
個体変数 x に対して x  D
 [ x / d ] : x に d  D を割り当て，x 以外には
 による割り当てをする変数割り当て．
©2008 Ikuo Tahara
12
一階述語論理式の意味

( M ,  ) による意味評価






c M ,  c 
x M ,  x
( f (t1, , tn ))M ,  f  (t1M , , , tnM , )
( p(t1, , tn ))M ,  p (t1M , , , tnM , )
( )M ,   M ,
(  )M ,   M ,  M ,

(x. )

(x. ) M ,
M ,


M , [ x / d ]
T:

 T for d  D

F: otherwise
M , [ x / d ]
T:

 T for d  D

F: otherwise
©2008 Ikuo Tahara
13
述語論理式を解釈してみよう
x[p( y)  q( f ( x), a)]
(M , )
M : D  {1, 2}
a  1
p  (1)  T
f  (1)  2
f  (2)  1
p  (2)  F
q  (1,1)  T q  (1, 2)  F q  (2,1)  F q  (2, 2)  T
 : x  1 y  2
T
©2008 Ikuo Tahara
14
充足可能性
 ：論理式 M ：解釈  ：変数割り当て


( M ,  ) は  を充足する（ ‘ M ,  ）．
 を充足する ( M ,  ) が存在する（しない）．
 は充足可能（不能）である．
 M ,  T
任意の  について  M ,  T
M は  を充足する（ ‘ M  ）．
 M が閉式  （またはその集合  ）を充足す
るとき， M を  （または  ）のモデルという．

©2008 Ikuo Tahara
15
妥当性
任意の解釈と任意の変数割り当てが論理式 
を充足するとき， は妥当であるという（ ‘  ）．

 は妥当である．

‘ 
  は充足不能である．
任意の ( M ,  ) について ‘ M , 
任意の ( M ,  )，d  D について ‘ M , [ x / d ] 
任意の ( M ,  ) について ‘ M , x.
‘ x.
閉式
©2008 Ikuo Tahara
16
論理的帰結
 ：論理式の集合
 ：論理式
 を充足する任意の解釈と任意の変数割り当
てが必ず  を充足するとき，  は  の論理的
帰結であるという（  ‘  ）．

{1 ,, n } ‘ 
‘ (1 
 n )  
‘ x.[(1 
 n )   ]
閉式 x.[(1   n )   ]
は充足不能である.
©2008 Ikuo Tahara
17
閉式の充足不能性

閉式 x.[ x] の充足不能性を考える．
M : D  {1, 2, }
一般には決定できない
x.[ x]  T
[1]  [2] 
 [i] 
T
x.[ x]  F
[1]  [2] 
 [i] 
F
ある[i] がFであれば決定できる
命題論理式
[i]が恒偽な命題論理式であれば
任意の解釈 M  で [i]  F
©2008 Ikuo Tahara
18
閉式の充足不能性
x.[ p( x)  p(a)]
M 2 : D2  {
, , , }
M 1 : D1  {1, 2, }
a 1  2
a 2 
p 1 (1)  F
p 2 ()  T
( p1 (1)  p1 (2))  ( p1 (2)  p1 (2)) 
( p2 ()  p2 ())  ( p2 ()  p2 ()) 
恒偽
恒偽
M : D  {a}
a  a
標準的解釈
p  (a)  T, F
p (a)  p (a)  F
©2008 Ikuo Tahara
19
まとめると…


一階述語論理式の充足不能性
閉式の充足不能性
x.[ x] の充足不能性
充足不能であれば決定可能
標準的な解釈の存在
©2008 Ikuo Tahara
20

Download Report