情報実習II

数理論理学
第7回
論理式の性質とモデル
© 加藤，高田，新出
3.2.3項(p. 65)
述語論理の論理
式の性質
演習課題6 member 削除
リストから要素を取り除く確定節 del を定義せよ。
?  del( sumire, [ sumire, sakiko, maruko], X ).
X  [ sakiko, maruko]
?  del( sakiko, [ sumire, sakiko, maruko], X ).
X  [ sumire, maruko]
(1) List=[ ] ならばTgtとは無関係に答えは[ ]。
(2) Listの先頭要素がTgt，残りをTailとする。TailからTgtを除
いたリストがWならば、答えはWである。
(3)先頭要素HeadがTgtでなく、かつTailからTgtを除いたもの
がWならば、答えはWの先頭にHeadをつけたものである。
del( _ , [], []).
del(Tgt , [Tgt | Tail ], W ) : del(Tgt , Tail , W ).
del(Tgt,[ Head|Tail ], [ Head|W ]) : - Tgt \= Head ,
del(Tgt , Tail , W ).
3.2.3 述語論理の論理式の性質
解釈
I ( D ,A )
対象領域割り当て
Dの例
定義3.14
定義3.15
D  {tomozou , kotake, hiroshi, sumire,
sakiko, maruko}
さくら家における解釈を I ( D ,A )
sakura
sakura
とする。ただし
Dsakura  {tomozou, kotake, hiroshi, sumire, sakiko, maruko}
Asakura とは、さくら家における述語記号や関数記号の割り当て
Asakura ( parent ) 表
tomozou
kotake
hiroshi
…
maruko
tomozou
⊥
⊥
T
…
⊥
kotake
⊥
⊥
T
…
⊥
hiroshi
⊥
⊥
⊥
…
T
…
…
…
…
…
…
maruko
⊥
⊥
⊥
…
⊥
F  (x( human ( x)  mortal ( x)))
 human(c)  mortal (c) p.63
I ({nello , patrasche},A )
A ( human)(nello)  T
A ( human)( patrasche) 
A ( mortal )(nello)  T
A ( mortal )( patrasche)  T
A (c)  nello
D
I ( D ,A ) の用い方
(pp. 63-64)
F  (x( human ( x)  mortal ( x)))
 human(c)  mortal (c)
I ({nello , patrasche},A )
この解釈 I の元で、論理式Fが
真になること、つまり
I (F )  T
を示す。
F  (x( human ( x)  mortal ( x)))
 human(c)  mortal (c)
E1
⊃
E2
(p.62) 5.
 I ( E1 )  T かつ I ( E2 ) 
I (F )  
T その他の場合
E1  (x( human ( x)  mortal ( x)))
E11
 human(c)
E12
A ( human)(c) 
 A ( human)(A (c))
 A ( human)(nello)  T
(p.62) 3.
T I ( E11 )  T かつ I ( E12 )  T
I ( E1 )  
 その他の場合
I ((x( human ( x)  mortal ( x))))
の値は、 p.62 6. によると、
I (human (nello)  mortal (nello))と
I (human ( patrasche)  mortal ( patrasche))
の値に依存する。まずnelloの場合を調べる
I (human (nello)  mortal (nello))
 I (human (nello))  T


かつ I (mortal (nello)) 
T その他の場合
p.62 5.

F  (x( human ( x)  mortal ( x)))
 human(c)  mortal (c)
I ({nello , patrasche},A )
A ( human)(nello)  T
A ( human)( patrasche) 
A ( mortal )(nello)  T
A ( mortal )( patrasche)  T
A (c)  nello
D
I ((x( human ( x)  mortal ( x))))
の値は、 p.62 6. によると、
I (human (nello)  mortal (nello))と
I (human ( patrasche)  mortal ( patrasche))
の値に依存する。まずnelloの場合を調べる
I (human (nello)  mortal (nello))
 I (human (nello))  T


かつ I (mortal (nello)) 
T その他の場合
p.62 5.

I ((x( human ( x)  mortal ( x))))
T
の値は、 p.62 6. によると、
I (human (nello)  mortal (nello))と
I (human ( patrasche)  mortal ( patrasche))
の値に依存する。patrascheの場合
I (human ( patrasche)  mortal ( patrasche))
 I (human ( patrasche))  T


かつ I (mortal ( patrasche)) 
T その他の場合
p.62 5.

E1  (x( human ( x)  mortal ( x)))
E11
A ( E11 )  T
 human(c)
E12
A ( human)(c) 
 A ( human)(A (c))
 A ( human)(nello)  T
(p.62) 3.
T I ( E11 )  T かつ I ( E12 )  T
I ( E1 )  
 その他の場合
A ( E1 )  T
F  (x( human ( x)  mortal ( x)))
 human(c)  mortal (c)
E1
A ( E1 )  T
⊃
E
2
A ( mortal )(c) 
 A ( mortal )(A (c))
 A ( mortal )(nello)  T
 I ( E1 )  T かつ I ( E2 ) 
I (F )  
T その他の場合
F  (x( human ( x)  mortal ( x)))
 human(c)  mortal (c) p.63
I ({nello , patrasche},A )
A ( human)(nello)  T
A ( human)( patrasche) 
A ( mortal )(nello)  T
A ( mortal )( patrasche)  T
A (c)  nello
D
F  (x( human ( x)  mortal ( x)))
 human(a )  mortal (a )
I1  I ({nello , patrasche},A )
1
A1 (human) A1 (mortal)
nello
T
T
patrashe
⊥
T
I1 ( F )  T
I 2  I ({katuo , patrasche},A2 )
A2 (human) A2 (mortal)
katuo
T
⊥
patrashe
⊥
T
I2 (F )  T
今回のまとめ
論理式の性質
• 恒真
どのような解釈 I の下でも T
• 充足可能ある解釈 I の下で T
• 充足不能どのような解釈 I の下でも ⊥
解釈の性質
• モデル
論理式 F に対して I(F) = Tとなるとき、
I は F のモデルである
3.2.3節
1. 論理式 F が恒真(valid)
F  (x( human ( x)  mortal ( x)))
 human(a )  mortal (a )
どんな解釈 I の下でも、I (F )  T
つまり値が真になること。
3.2.3節
2. 論理式 F が充足可能(satisfiable)
ある解釈の下でFが真となること。
F  x( human ( x)  mortal ( x))
I1  I ({nello , patrasche},A1 ) I ( F )  T
1
I 2  I ({katuo , patrasche},A2 ) I 2 ( F )  
I (F) =T となるような解釈が存在した
3.2.3節
3. 論理式 E が充足不能(unsatisfiable)
F  ((x( human ( x)  mortal ( x)))
 human(a )  mortal (a ))
どんな解釈 I の下でも、 I (F )  
つまり値が偽になること。
3.2.3節
充足不能(unsatisfiable) でないことは、
充足可能(satisfiable)であること。
注意: 「恒真」の否定が「充足不能」では
ない。「任意の～について・・・である」
の否定は、「ある～について・・・でない」
定義 3.18 モデル
F  x( human ( x)  mortal ( x))
I1  I ({nello , patrasche},A1 )
I 2  I ({katuo , patrasche},A2 )
I 2 ( F )   だが、 I1 ( F )  T
I1 は、論理式 F のモデルである。
今回のまとめ
論理式の性質
• 恒真
どのような解釈 I の下でも T
• 充足可能ある解釈 I の下で T
• 充足不能どのような解釈 I の下でも ⊥
解釈の性質
• モデル
論理式 F に対して I(F) = Tとなるとき、
I は F のモデルである
課題 7
F  x( bird ( x)  fly ( x))
この論理式 F のモデルをひとつ作成せよ。ただし
D={mikeneko, hibari} とし、Aによる割り当てを自分
で作る。
また、なぜそれが F のモデルになるか証明せよ。
I  I ({mikeneko , hibari},A )
A (bird)
A ( fly )
mikeneko
hibari
各ますにはT か ⊥ を入れる
証明:
ここで与えた解釈 I が論理式 F のモデル
となることを示す。
I (x( bird ( x)  fly ( x)))
 (1)
の値は、 p.62 規則 6. によると、
mikenekoに関する式)
(a)
I (bird ((mikeneko
)  fly (mikeneko
)) (2)
と
I (bird(hibari
(hibari
)  fly (hibari
に関する式)
(b) ))  (3)
を求め、ひとつでも⊥であれば⊥。
(2)式の値は、p. 62の規則 5. によると
I (bird (mikeneko
))  T かつ I ( fly (mikeneko
))  
(d)
(c)
ならば⊥、そうでなければ T。
A によると、
(e)
I (bird (mikeneko
)) 
, I ( fly (mikeneko
)) 
(c)
(d)
(f)
なので(2)式の値は(g)
T となる。同様に(3)式の値
は (g)
T となるので、(1)式の値は (h)
T となる。以上
T が示された。定義3.18より、
より I (F )  (h)
I (F )  (h)
T となる解釈I は、F のモデルなので、
(i)
ここで与えた I はF のモデルとなる。
(i)
課題 7
解釈を I ({mikeneko,hibari},A ) とする。ただし
割当A を下の表で与える。
A (bird)
A ( fly )
mikeneko
hibari
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)
……
……
……
……
……
……
……
……
……
今回の答案の書き方

Download Report