命題論理

認知システム論 知識と推論(4)
知識と論理でを組み合わせて問題を解決する
一階述語論理
(first-order predicate logic)
一階述語論理入門
構文論(論理式の文法)
意味論(論理式の解釈)
一階述語論理入門(1/9):命題論理の世界
命題論理の世界
true
P
true
Q
(原始命題の世界)
false
原始命題より細かな情報は表現されない
原始命題の真偽しか表現されない
原始命題を論理記号(¬∧∨→)で
つないで複雑な命題を表現
一階述語論理入門(2/9)命題論理の表現力の限界
これはOK
P
PQ
Q
雨が降っている
雨が降っているならば道路が濡れている
論理的帰結
道路が濡れている
一階述語論理入門(3/9)命題論理の表現力の限界
これは?
P
ソクラテスは人間である
(Socrates is a human.)
Q
すべての人間は死ぬ運命にある
(Every human is mortal.)
論理的帰結
R
ソクラテスは死ぬ運命にある
(Socrates is mortal.)
一階述語論理入門(4/9)
一階述語論理の世界
Aibo
Human
Mortal
(オブジェクトの世界)
名前のない
要素もOK
Mickey
Human
Mortal
Jack
Socrates
Human
Will
Elizabeth
オブジェクト(個体)を表現できる
オブジェクトの性質(property)を命題として表現できる
オブジェクト間の関係(relation)を命題として表現できる
オブジェクト間の関数(function)を表現できる
一階述語論理入門(5/9)
個体記号
オブジェクト(個体)を表現
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)
一階述語論理入門(6/9)
原始命題は,1つの述語記号とその
引数(項)から構成される
A is a friend of the father of B.
A
Friend ( A, father ( B))
B
原子式 (atom)
項 (term)
一階述語論理では,原子式が原始命題を表現する.
一階述語論理入門(7/9)
すべての人間は死ぬ運命にある
(Every human is mortal.)
全称記号
変数記号
x Human( x)  Mortal ( x)
Every human is mortal.
= Everything is mortal if it is human.
= For all object,
if it is human, then it is mortal.
∀ と → の組合せは,相性が良い.
一階述語論理入門(8/9)
すべての人間は死ぬ運命にある
(Every human is mortal.)
x Human( x)  Mortal ( x)
ソクラテスは人間である
(Socrates is a human.)
Human( Socrates)
論理的帰結
ソクラテスは死ぬ運命にある
(Socrates is mortal.)
Mortal ( Socrates)
これは機械的に導出可能!
( x = Socrates )
一階述語論理入門(9/9)
存在記号
ミッキーは,人間の友達をもっている
(Mickey has a human friend.)
x Human( x)  Friend ( x, Mickey)
Mickey has a human friend.
= Mickey has something which is human and
his friend.
= There exists something which is human and
which is a friend of Mickey.
∃ と ∧ の組合せは,相性が良い.
述語論理の構文論
論理式の文法
構文論(1/6) 一階述語論理の構成要素
一階述語論理の構文要素
個体記号(定数):
a, b, c, John,30, Socrates
変数:
x, y, z, u, v
関数記号:
f , g , h, father, age, plus
述語記号:
P, Q, R, HUMAN , MORTAL , GREATER
DOCTOR ( father( John))  GREATER(age( father( John)), plus (a,30))
ジョンの父は医師であり,かつ,その年齢は a+30 より大きい
構文論(2/6) 項
定数:特定のオブジェクト
John
変数:不特定のオブジェクト
x
項:定数や,変数,関数記号を用いて
別のオブジェクトを表現
(項に,述語記号は用いない)
father ( John)
age( father ( John))
plus(a,30)
構文論(3/6) 項
項
(1) 定数は項である.
(2) 変数は項である.
(3) f が n 変数の関数記号, t1, , tn が項ならば,
f ( 1t ,
n
, tは項である.
)
構文論(4/6) 原子式
原子式:それ以上分解すると命題ではなくなる命題
DOCTOR( John)
GREATER(age( John),20)
原子式
P が n 変数の述語記号, t1,
P(t1, , tn ) は原子式である.
, tn が項ならば,
構文論(5/6) 限量子
限量子:
(x)
All
(x)
全称記号 「すべての x について」
(for all x , …)
存在記号「ある x が存在して」
(there exists x such that …)
Exist
s
構文論(6/6) 論理式
論理式:原子式を論理結合子および
限量子と組合せて作る命題
論理式
原子式 は論理式である.
P, Q が論理式ならば,以下の5つも
論理式である.
(P ) ( P  Q) ( P  Q)
( P  Q) ( P  Q)
P
が論理式ならば,以下の2つも論理式である.
(x) P
(x) P
述語論理の意味論
解釈に基づく論理式の真理値の計算
意味論(1/7) 解釈
命題論理:
命題記号への真理値の割り当てを解釈と呼ぶ
P, Q
一階述語論理:
DOCTOR (John)
GREATER(age( John),20)
定数,変数,関数記号,述語記号がそもそも何を意味
するかを決定しなければならない
意味論(2/7) 解釈
解釈
論理式 G の解釈は,次の4つのことを具体的に
決定することで定義される.
空でない集合 D (定義域という)
G 中の各個体記号(定数)の意味として,
D の要素を一つ割当てる.
n 変数の各関数記号の意味として,
D n から D への写像を割当てる.
n 変数の各述語記号の意味として,
D n から {T, F} への写像を割当てる.
意味論(3/7) 解釈
解釈の例
解釈1
GREATER(One, Nine)
定義域
D={0, 1, 2, …. }
定数への割当て
One
Nine
1
9
述語への割当て
GREATER
>
GREATER(One, Nine)  (1  9)  F
意味論(4/7) 解釈
解釈2
定義域
D={尾根さん,仁根さん}
定数への割当て
One
Nine
尾根さん
仁根さん
述語記号への割当て
GREATER(x,y): 「xはyよりも偉大である」
x
y
GREATER(x,y)
尾根さん
尾根さん
F
尾根さん
仁根さん
T
仁根さん
尾根さん
F
仁根さん
仁根さん
F
GREATER(One, Nine) 「 尾根さ んは, 仁根さ んよ り 偉大である 」  T
意味論(5/7) 解釈
関数記号を含む場合の解釈
LOVES ( John, father ( John))  T
定義域
D={人物1, 人物2, 人物3, …} 実世界のDBを用
いても可
定数への割当て
John
関数への割当て
father(人物 i) = 人物(i+1)
人物5
述語記号への割当て
LOVES(人物 i, 人物(i+1)) = T
LOVES(人物 i, 人物(i+2)) = T
それ以外は,LOVES(人物 i, 人物 j) = F
意味論(6/7) 論理式の真理値の計算
論理式の真理値
原子式の真理値は解釈によって直接定まる.
P, Q の真理値が定まっていれば,
以下の論理式の真理値も計算できる.
(P ) ( P  Q) ( P  Q) ( P  Q) ( P  Q)
(x) P は,P の真理値がD のすべての要素
x についてT ならばT,さもなくば F .
(x) P は,P の真理値がD の少なくとも1つの
要素x についてT ならばT,さもなくば F .
意味論(7/7) 充足不能,充足可能
恒真 どんな解釈のもとでも真
充足不能 どんな解釈のもとでも偽
充足可能 ある解釈のもとで真
論理的帰結
P1, P2 , , Pn
Q が真
P1  P2 
のすべてを真とするどんな解釈のもとでも
 Pn  Q
が充足不能