人工知能特論2007 No.4

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

Download Report