資料No.4

人工知能特論2007
No.4
東京工科大学大学院
担当教員：亀田弘之
命題論理から述語論理へ
命題論理も有用なものであることは、組合
せ回路論などでも実証済み。
 でも、…

命題論理の限界
命題論理で扱えないものがある。
 例：
「AはBより大きく、BはCより大きい。した
がって、AはCより大きい。」

P= AはBより大きい。
Q= BはCより大きい。
R=AはCより大きい。
「PかつQならばR」
これが証明できない！
真であることが証明できｊない！

これを克服するためには、文単位の論理体
系では駄目で、文の内部構造も明示的に
取り扱う必要がある。
＝＝＞述語論理へ
論理体系構築の手順（復習）
字母の決定（論理式を記述するための記号
群を決める）
 Syntax（記号の意味ある並びを決める。論
理式であるための条件、論理式の表現規
則を決める）
 Semantics（論理式の意味の取り扱いを決
める）
 その後、推論へと話を進める。

定義４．１述語論理の字母
1.
2.
定数： a, b, c, …
必要に応じて添え字も許す。
変数： x, y, z, w, …
必要に応じて添え字も許す。
3.
4.
関数記号： f, g, h, …
必要に応じて添え字も許す。
関数ごとに変数の個数(arity)
が決まっている。
述語記号： P,Q, R, …
必要に応じて添え字も許す。
関数ごとに変数の個数(arity)
が決まっている。
5.
6.
7.
結合子: ~, ∧, ∨, →, ↔ （４種類）
限量記号: ∃, ∀
(読み方)∃：存在記号
∀：全称記号
補助記号： “(“ , “)”, “,”
左括弧、右括弧、コンマ（３種類）
ここまでで何ができたか？

例：
太郎は花子のことが好きである。
＝＞好き（太郎，花子）
＝＞ love(taro, hanako)
＝＞ P(a,b)
このような文を、記号化することができるよ
うになった。
（具体例の練習は後でやりましょう。）
もう少し話を進めましょう！
確認

字母
定数
 変数
 関数記号
 述語記号
 結合子
 限量記号
 補助記号

確認

字母
定数：
 変数:
 関数記号:
 述語記号:
 結合子:
 限量記号:
 補助記号:

a, b, c, d, …
x, y, z, w, …
f, g, h, …
P, Q, R,
~, ∧, ∨, →, ↔
∃, ∀
( ) ,
定義４．２項(Term)
1.
2.
3.
定数は項である。
変数は項である。
もし f が arity n （n変数）の関数記号であ
り、t1, t2,… tn が項であるならば、
f( t1, t2, … , tn )
は項である。
例

設定：
定数： a, b, c
変数： x1, x2, y
関数記号： f, g
( ｆは1変数関数、ｇは3変数関数)
述語記号: P, Q, R, S
( それぞれ、2, 1, 2,
例（続き）

項の例：
a
x2
f( b )
f( f( f( x1 ) ) )
g(x2, x1, f( f( f( a ) ) ) )
述語論理式の構成要素
例（続き）

項でないものの例：
f( a, b )
P( a, c )
(a∨b)
これらはなぜ項では
ないのでしょうか？
説明してみましょう。
定義４．３ ( well-formed ) 論理式
1.
2.
3.
4.
Pはn変数の述語記号であり、 t1, t2,… tn
が項であるならば、P(t1, t2,… tn ) は論理式
である。アトムあるいは原始式と呼ぶ。
Φが論理式ならば、~φは論理式。
Φとψが論理式ならば、
(φ∧ψ), (φ∨ψ), (φ→ψ), (φ↔ψ)
は論理式。
Φが論理式、xが変数ならば、
∃x φ , ∀x φ
は論理式。
補足

アトムでない論理式のことを、複合論理式
(composite formula)と呼ぶことがある。
論理式の例

論理式の例
Q(a)
P( f( f( x1 ) ), g( a, c, f( b ) ) )
P( f( f( x1 ) ), g( a, c, f( b ) ) ) → Q(a)
~∀x Q(x)
∃x1 ~∀x2 (∃yR(x2,x1) ∧ Q(b) )
論理式の例（続き）

論理式でない例
( P(a,b) ∨ f( y ) )
P( a )
Q( P(a, b ) )
∀a Q(a)
補足

命題論理のときと同様に、字母と論理式定
義規則から得られる記号列（論理式）の集
合を（1階述語論理）言語 (first-order
language) と呼ぶ。
定義４．４スコープ（参照範囲）

論理式 ∀x φ における∀xのスコープは、φ
であり、論理式 ∃x φ における∃xのスコー
プは、φである。
∃x のスコープ

例：
∃x (P(x,y)→Q(x))
∃x (∀y P(x,y)∧Q(x))
∀y のスコープ
定義４．５変数の束縛
定義４．６閉じた論理式

自由変数を１つも含まない論理式のこと。
例：
~∀y P(a,y)
定義４．７基礎項(ground term)と
基礎論理式(groung formula)
基礎項：変数を１つも含まない項のこと。
 基礎論理式：変数を１つも含まない
論理式のこと。
例：
f(a), g(b, f(a), c)
P(a, f(b) )
∀x P(x,a) ＜＝これは基礎論理式
ではない！

Semantics
定義４．８ pre-interpretation J
1.
2.
3.
集合D:解釈のための領域（非空集合）
定数記号に対して、Dの要素を割り当てる。
関数記号f (n変数関数)に対して、Dnから
Dへの写像を割り当てる。
つまり、集合Dに基づいて、定数記号や関
数記号の意味（実体）を決める。これが、
pre-interpretation。
例
定義４．９変数割り当てV

変数記号に領域Dの要素を割り当てる。
（variable assignment）
V: 変数記号の集合∋x → d∈D
定義４．１０項割り当て
定数記号に対して、pre-interpretation Jに
基づいてDの要素を割り当てる。
 変数記号に対して、変数割り当てVに基づ
いてDの要素を割り当てる。
 t1, t2, …,tn がd1, d2, … ,dn に割り当てら
れるとき、f(t1, t2, …,tn ）は、 Jf(d1, d2,
… ,dn ）に割り当てられる。

定義４．１１解釈I

Pre-interpretation J が定められているとき、
述語記号Pに対して、Dnから{ T, F } への写
像を割り当てることを解釈という。

Download Report