x - 京都大学

知能情報システム特論
論理式による集合の定義(1)
山本章博
京都大学情報学研究科知能情報学専攻
http://www.iip.ist.i.kyoto-u.ac.jp/member/akihiro/
[email protected]
帰納の例(数学的概念)



偶数とは 2 で割切れる自然数である
具体的な事実の観測(データの収集)
偶数である：22, 4, 16, 6, 184,…
偶数でない：7, 55, 13, 9, 1,…
法則の導出

一般的法則の探索・発想
S = { x | x は自然数かつ x mod 2 = 0 }

具体的事実を用いた検証
計算機科学における概念定義方法

述語論理

数学的推論の形式化・機械化
S = { x | x は自然数かつ x mod 2 = 0 }
"x (even(x)  nat(x)  (x mod 2 = 0))
"x (even(x)  nat(x) mod(x,2,0))
"x even(x) x = 0 y((x = y + 2)even(y))
対象と対象の表現


偶数: 0, 2, 4, 6,…
S = { x | x は自然数かつ x mod 2 = 0 }
偶数の表現 : 0, 10, 00, 100, 110, 000, 010, …
E=
{ x | x = 0で終わるような1と0からなる有限列}
1
0
0
1
対象と対象の表現(2)


3の倍数: 0, 3, 6, 9,…
S = { x | x は自然数かつ x mod 2 = 0 }
3の倍数の表現 : 0, 11, 00, 110, 000, 011, …
E:
1
0
1
0
0
1
対象と対象の表現(3)

対象を直接扱うのではなく，その表現を扱う
N
{0, 1}*
0
1
0
1
001
2
0010
10
3
11
表現の構成法

(1) Primitiveな記号を(有限種)用意する
(2) Primitiveな記号を組合せる方法を与える
{0, 1}*
例
Primitiveな記号: 0, 1
記号を組合せる方法: 一列に並べる
0, 1, 00, 01, 10, 11, 000, 001, …

{0, 1}*は述語論理では用いないが，述語論理と同
様の方法で集合を定義することができる(Smullyan)
述語論理で用いる表現(1)

数学で用いられる表現
0, 2, -56, 355674, 5+27, 4×8+2, 23,…
∠B, AB, △ABC,…



表記されない記号を明示する
前置き記法(prefix notation)で表す
-(56), +(*(4, 8), 2), ^(2, 3) ,…
∠(B), d(A, B), △(A,B,C),
(この講義では)アルファベット・数字などのISO文字
の列を用いることにする
agl(B), d(A, B), tri(A, B, C),…
述語論理で用いる表現(2)


(1) Primitiveな記号:
対象を表すための記号: 0, 2, 56, 355674,…
定数記号
A, B, C,…
関数を表すための記号: -, *, ^ , agl, d,…
関数記号
(2) 記号を組合せる方法:
対象に関数を繰り返し適用してゆく:
*(4, 8), +(*(4, 8), 2), ^(2, 3),
*(+(*(4, 8), 2), ^(2, 3)),…
このような表現を基礎項(ground term), 基礎項
全体の集合をHerbrand Universeとよぶ
述語論理で用いる表現(3)

項は以下のように再帰的に定義される:
(1) 定数記号は基礎項である.
(2) f を関数記号, t1, t2,…,tn を基礎項とするとき
f (t1, t2,…,tn ) は基礎項である.
(3) (1), (2) を有限回適用して得られる式だけが
基礎項である.
述語論理で用いる表現(4)

対象を直接扱うのではなく，その表現を扱う
U
N
0
1
2
1
0
+(0, 1)
2
+(1,1)
*(2,*(2,1))
述語論理で用いる表現(5)

(1) Primitiveな記号: 対象 0, 関数 s
(2) 記号を組合わせる方法: s(s(…s(0)…))
N
UN
0
0
1
s(0)
2
3
s(s(0))
s(s(s(0)))
論理式(1)
目標

基礎項の集合(Herbrand Universe Uの部分集
合)
S = { x | p(x) }
基礎項の組の集合
S = { (x1, x2,…,xn) | q(x1, x2,…,xn) }
を定義する方法を論理式を用いて与える．
基礎原子論理式(1)

基礎項 t や基礎項の組(t1, t2,…,tn )が S に属して
いることを表すための式 : p(t), q(t1, t2,…,tn)
基礎原子論理式(ground atomic formula)
p, q : 述語記号
例 Seven = {even(t) | t は偶数を表す基礎項}
even : 述語記号
even(0)Seven, even(s(s(0)))Seven ,
even(s(0))Seven , even(s(s(s(0))))Seven ,
...
基礎原子論理式(2)
例 Smod ={mod (t, s, u) | t (が表す自然数)を
s で割ったときの余りが u }
mod : 述語記号
mod(0, s(s(0)), 0)Smod,
mod(s(0), s(s(0)), s(0))Smod,
mod(s(s(s(0))), s(s(s(0))), 0))Smod ,
mod(s(0), s(s(0)), 0) Smod ,
...
 基礎原子論理式全体の集合をHerbrand baseと
よぶ.
目標’

基礎原子論理式の集合(Herbrand base) Bの部
分集合)
S = {p(t1, t2,…,tn) | F [p]}
を定義する方法を論理式を用いて与える．
量化子のない論理式(2)

項は以下のように再帰的に定義される:
(1) 論理定数 □(^), ■ (T)は論理式である.
(2) 基礎原子論理式は論理式である.
(3) j , z を論理式とするとき
j
j  zj  z j  z j  z j  z
(4) (1), (2) を有限回適用して得られる式だけが
論理式である.
量化子のない論理式(1)

基礎原子論理式から論理結合子

を用いて構成される式
even(s(0))
even(s(s(0))) mod(s(s(0)), s(s(0)), 0)
even(s(s(0))) even(0)
even(s(s(s(s(0))))) even(s(s(0)))

Cf. (–4 )×(6+5)
論理演算
論理演算



数学者 Boole により考案
2種類の値 1, 0 (真偽値)だけを用いる空間
1 は真，0 は偽を表す．
真偽値同士の演算は真理値表により定義


真偽値の和，積はそれぞれ，自然数や実数の和，
積と非常に似た性質を持つ
論理式の意味を{0, 1}を用いて表す

多項式がn内の曲線や曲面を表すように, 論理
式は{0,1}n内の“曲線”や“曲面”を表す
論理演算

一般に，n変数の論理演算は2^(2^n)) 種類しか
ない
真理値表で表現
x f(x)
0
1
x
y
0
0
0
1
1
1
0
1
f(x, y)
代表的な論理演算
論理積
論理和
x
y
xy
0
0
0
x y x+y
0 0
0
0
1
1
1
0
1
0
0
1
0 1
1 0
1 1
1
1
1
否定
x
y
0
1
1
0
単項(1引数)論理演算
単項（1引数）論理演算は22種類
x
0
1
f1(x) f2(x) f3(x)
0
0
1
0
1
0
否定 x
f4(x)
1
1
2項(2引数)論理演算
2項（2引数）論理演算は24種類
x y f1
f16
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
論理積 x y
論理和 x + y
同値 x  y
含意 x  y
否定, 論理和, 論理積の性質
交換律
結合律
分配律
冪等律
零元
単位元
補元
x+ y = y + x
xy = y x
(x + y) + z = x + (y + z)
(x y)z = x (y z)
(x + y) z = x z + y z
x y + z = (x + z)(y + z)
x+x=x
xx=x
x+ 0 = x
x・0 = 0
x ・1 = x
x +1=1
x+x=1
xx=0
1 = 0,
0=1
二重否定
x=x
ド・モルガン律 x + y = x y, x y = x + y
含意, 同値
x
0
0
1
1
y
0
1
0
1
xy
1
1
0
1
x
0
0
1
1
y
0
1
0
1
xy
1
0
0
1
x
0
0
1
1
x
0
0
1
1
y
0
1
0
1
y
0
1
0
1
x
1
1
0
0
x+y
1
1
0
1
x y y x (x y) (y x )
1
1
1
1
0
0
0
1
0
1
1
1
含意(2)

xw y+z = x+w +y+z
論理式の解釈(1)

解釈 I ： Herbrand base B から{0, 1}への関数



基礎原子論理式に真偽値を“代入”する
{0, 1}n 内の1点
解釈 I のもとでの論理式の解釈
1. 論理定数の解釈値
I (□) = 0, I (■) = 1
2. 論理演算子
I (j  z ) = I (j) ・ I (z )
I (j  z ) = I (j) + I (z )
I (j  z ) = I (j)  I (z )
I ( j ) = I (j)
論理式の解釈(2)
例解釈 I:
I(r) = 1, I(s) = 0, I(t) = 0, I(u) = 1, I(v) = 1
I (((r  s)  (t  u)) v)
= I ((r  s)  (t  u))  I (v)
= (I (r  s)・I(t  u))  I (v)
= ((I (r) ・ I (s)) ・ (I(t)・ I(u)))  I (v)
= ((1 ・ 0 )・ (0 ・ 1))  1
= (0 ・ 0 )  1
=01=1
論理的帰結

zが j1,...,jn の論理的帰結：
I(j1) =…= I(jn ) = 1 であるどのような解釈 I に
対しても I(z) = 1
j1,...,jn |=z
例
j1 =mod(s(s(0)), s(s(0)), 0)
j2 =mod(s(s(0)), s(s(0)), 0)  even(s(s(0)))
z =even(s(s(0)))
量化子のない論理式による集合の定義

解釈 I ： Herbrand base B から{0, 1}への関数
Herbrand base B の部分集合を指定している

論理的帰結 j1,...,jn |=z は
j1,...,jnが表す集合から zが表す集合の
構成法を与えている
情報の階層モデル[原島・森島 89]
伝えたい内容・意図
意図・動機
意味
概念
構造・記号
モデル
信号波形
意図・動機
意図・動機
意味情報
概念情報
構造・記号情報
意味
概念
構造・記号
モデル
パラメータ情報
信号波形情報
信号波形

Download Report