情報実習II

数理論理学
第8回
様々な再帰処理
© 加藤，高田，新出
7.6節 (p. 190)
リスト処理
(応用問題)
前回のまとめ
論理式の性質
• 恒真
どのような解釈 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 )
⊥
⊥
hibari
T
T
各ますにはT か ⊥ を入れる
mikeneko
証明:
ここで与えた解釈 I が論理式 F のモデル
となることを示す。
I (x( bird ( x)  fly ( x)))
 (1)
の値は、 p.62 規則 6. によると、
I (bird (mikeneko)  fly (mikeneko)) (2)
(a)
と
I (bird (hibari )  fly (hibari ))  (3)
(b)
を求め、ひとつでも⊥であれば⊥。
(2)式の値は、p. 62の規則 5. によると
I (bird (mikeneko))  T かつ I ( fly (mikeneko))  
(c)
(d)
ならば⊥、そうでなければ T。
A によると、
I (bird (mikeneko)) ,
(e)
I ( fly (mikeneko)) 
(f)
なので(2)式の値は T となる。同様に(3)式の値
(g)
は T となるので、(1)式の値は T となる。以上
より
I (F )  T
(h)
I (F ) が示された。定義3.18より、
T
となる解釈I は、F のモデルなので、
(i)
ここで与えた I はF のモデルとなる。
演習課題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 ).
練習問題 member 追加
リストとリストを結合する確定節 add を定義せよ。
?- add([tomozou],[sumire, sakiko, maruko], X).
X = [tomozou, sumire, sakiko, maruko]
?- add([tomozou, hiroshi],[sumire, sakiko, maruko], X).
X = [tomozou, hiroshi, sumire, sakiko, maruko]
(add は組み込み述語 append と同じもの)
追加リストを List1=[Head|Tail], 元のリストを List2 とする。
(1) List1=[]のとき、答えはList2
(2) Tail を List2に追加したものがWならば、答えはWの前に
Headをつけてできるリストである。
追加リストを List1=[Head|Tail], 元のリストを List2 とする。
(1) List1=[]のとき、答えはList2
(2) Tail を List2に追加したものがWならば、答えはWの前に
Headをつけてできるリストである。
add([],List2,List2).
add([Head| T ail],List2,[Head| W])
: - add(T ail,List2,W).
追加リストを List1=[Head|Tail], 元のリストを List2 とする。
(1) List1=[]のとき、答えはList2
(2) Tail を List2に追加したものがWならば、答えはWの前に
Headをつけてできるリストである。
add([],List2,List2).
add([Head| T ail],List2,[Head| W])
: - add(T ail,List2,W).
演習課題 8 List を用いた和集合
リスト同士の和集合を求める cup (∪) を定義せよ。
? cup([kotake, hiroshi, maruko], [tomozou, hiroshi, maruko], X ).
X  [kotake, tomozou, hiroshi, maruko]
二つのリストをそれぞれ List1=[Head|Tail], List2 とする。
(1) List1=[]のとき、答えは List2
(2) Head がList2のmemberかつ、TailとList2の和集合がW
ならば、List1とList2の和集合はWである。
(3) Head がList2のmemberではなく、かつ、TailとList2の
和集合がWならば、List1とList2の和集合はWの前に
Headをつけてできるリストである。
memberが単独で動くことを、事前に
必ず確認しておくこと。
?- member(sumire,[sumire, sakiko, maruko]).
true
? cup([kotake, hiroshi, maruko], [tomozou, hiroshi, maruko], X ).
X  [kotake, tomozou, hiroshi, maruko]
(1) List1=[]のとき、答えは List2
(2) Head がList2のmemberかつ、TailとList2の和集合がW
ならば、List1とList2の和集合はWである。
(3) Head がList2のmemberではなく、かつ、TailとList2の
和集合がWならば、List1とList2の和集合はWの前に
Headをつけてできるリストである。
cup([],List2,List2).
cup([Head| T ail],List2,W): - member(Head, List2),
cup(T ail,List2,W).
cup([Head| T ail],List2,[Head| W]): - \  member(Head, List2),
cup(T ail,List2,W).

Download Report