情報実習II

数理論理学
第11回
• 節集合
• prologによるソーティングプログラム
© 加藤，高田，新出
4.1.4節(p. 87)
節集合
7.7節(p. 197)
Prologによる
Quicksort
プログラム
演習課題 10
xv(r ( x, v))  zw(q( z, w))
をスコーレム標準形に変換せよ。
スコーレム関数記号は、x に影響を受けるもの
はf (x)を、x と z に影響を受けるものはg(x,z)
を使用すること。
途中の経過式、および使った規則も全て記入すること。
これらが一つでも欠けていれば０点。
レポート用紙には、以下のヒントも含め、全て記述すること
xv(r ( x, v))  zw(q( z, w))
⊃ 除去(p. 74 10.)
 (xv(r ( x, v)))  zw(q( z, w))
￢移動 (p. 74 12,11)
 xv(r ( x, v))  zw(q( z, w))
∀,∃移動
 xvzw(r ( x, v)  q( z, w))
∃削除(スコーレム化)
 xz(r ( x, f ( x))  q( z, g ( x, z)))
スコーレム標準形へ変換
y ( ( A( f ( y ))  B  )
C1
 ( E  F  )

C2
 ( P  Q  )Cm)
y( C1  C2  Cm )
4.1.4 節集合
p. 87
Fsk  x1x2 (C1  C2   Cm )
とする。このとき、
prologプログラム
に対応
S  {C1, C2 ,, Cm}
をFsk に対応する節集合という。また、
Fsk を S に対応するスコーレム標準形という。
定義 4.5 S の解釈は、 Fsk の解釈と同じ。
I(S) = I(Fsk)
parent(tomozou, hiroshi).
parent(kotake, hiroshi).
parent(hiroshi, sakiko).
parent(sumire, sakiko).
parent(hiroshi, maruko).
parent(sumire, maruko).
事実節
male(tomozou).
male(hiroshi).
female(kotake).
female(sumire).
female(sakiko).
female(maruko).
child(X, Y) :- parent(Y, X).
mother(X, Y) :- parent(X, Y), female(X).
確
定
節
parent(tomozou, hiroshi).
parent(kotake, hiroshi).
parent(hiroshi, sakiko).
parent(sumire, sakiko).
parent(hiroshi, maruko).
parent(sumire, maruko).
male(tomozou).
male(hiroshi).
female(kotake).
female(sumire).
female(sakiko).
female(maruko).
child(X, Y) :- parent(Y, X).
mother(X, Y) :- parent(X, Y), female(X).
例 4.8
(p. 88)
female(sumire).
parent(sumire, maruko).
mother(X, Y) :- parent(X, Y), female(X).
例 4.8
(p. 88)
female(sumire).
parent(sumire, maruko).
mother(X, Y) :- parent(X, Y), female(X).
?- mother(sumire, maruko).
:  と ? は  に相当(向きは逆 )
female(sumire)
Ù parent(sumire, maruko)
Ù (parent(x,y)Ù female(x) É mother(x,y))
Ù mother(sumire, maruko) É
例 4.8
(p. 88)
female(sumire).
parent(sumire, maruko).
mother(X, Y) :- parent(X, Y), female(X).
?- mother(sumire, maruko).
:  と ? は  に相当(向きは逆 )
"x"y
( female(sumire)
Ù parent(sumire, maruko)
Ù (parent(x,y)Ù female(x) É mother(x,y))
Ù mother(sumire, maruko) É )
"x"y
例 4.8
( female(sumire)
Ù parent(sumire, maruko)
Ù (parent(x,y)Ù female(x) É mother(x,y))
Ù mother(sumire, maruko) É )
⊃ 除去（p. 74 10.) E  F  E  F
"x"y
( female(sumire)
Ù parent(sumire, maruko)
Ù (Ø(parent(x,y)Ùfemale(x))Ú mother(x,y))
ÙØmother(sumire, maruko))
"x"y
例 4.8
( female(sumire)
Ù parent(sumire, maruko)
Ù (Ø(parent(x,y)Ùfemale(x))Ú mother(x,y))
ÙØmother(sumire, maruko))
ド・モルガン (p. 74
8.)
( E  F )  E  F
"x"y
( female(sumire)
Ù parent(sumire, maruko)
Ù (Øparent(x,y)ÚØfemale(x)Ú mother(x,y))
ÙØmother(sumire, maruko)) = Fsk
"x"y
例 4.8
( female(sumire)
Ù parent(sumire, maruko)
Ù (Ø(parent(x,y)ÚØfemale(x)Ú mother(x,y))
ÙØmother(sumire, maruko)) = Fsk
{female(sumire),
parent(sumire, maruko),
mother(x,y)ÚØ(parent(x,y)ÚØfemale(x),
Ømother(sumire, maruko)} = S
クイックソート (p. 197)
[3, 8, 0, 5, 2, 1] → [0, 1, 2, 3, 5, 8]
クイックソート (p. 197)
[3, 8, 0, 5, 2, 1]
クイックソート (p. 197)
[3, 8, 0, 5, 2, 1]
[0, 2,1]
[8, 5]
クイックソート (p. 197)
[3, 8, 0, 5, 2, 1]
[0, 2,1]→[0, 1, 2]
[8, 5]→[5, 8]
クイックソート (p. 197)
[3, 8, 0, 5, 2, 1]
[0, 2,1]→[0, 1, 2]
[0, 1, 2, 3, 5, 8]
[8, 5]→[5, 8]
プログラム7.8
quick_sort([], []).
quick_sort([Head | Tail], List2)
:- partition(Tail, Head, Small, Large),
quick_sort(Small, ListS),
quick_sort(Large, ListL),
append(ListS, [Head | ListL], List2).
(p. 199)
quick.pl とし
て作成し、
教科書通りの
実行例を確認
partition([Head | Tail], Pibot, [Head | ListS], ListL)
:- Head =< Pibot, partition(Tail, Pibot, ListS, ListL).
partition([Head | Tail], Pibot, ListS, [Head | ListL])
:- Head > Pibot, partition(Tail, Pibot, ListS, ListL).
partition([], _, [], []).
quick_sort([], []).
quick_sort([Head | Tail], List2)
:- partition(Tail, Head, Small, Large),
quick_sort(Small, ListS),
quick_sort(Large, ListL),
append(ListS, [Head | ListL], List2).
partition([Head | Tail], Pibot, [Head | ListS], ListL)
:- Head =< Pibot, partition(Tail, Pibot, ListS, ListL).
partition([Head | Tail], Pibot, ListS, [Head | ListL])
:- Head > Pibot, partition(Tail, Pibot, ListS, ListL).
partition([], _, [], []).
append は、リストとリストの接着剤
append(ListS, [Head | ListL], List2).
append([1,2], [3,4], [1,2,3,4]).
append([ ], [3,4], [3,4]).
append([1,2], [ ], [1,2]).
append([ ], [ ], [ ]).
append が、並べ替えの要
quick_sort([Head | Tail], List2)
:- partition(Tail, Head, Small, Large),
quick_sort(Small, ListS ),
quick_sort(Large, ListL),
append(ListS, [Head | ListL], List2).
quick_sort([], []).
partition([Head | Tail], Pibot, [Head | ListS], ListL)
:- Head =< Pibot, partition(Tail, Pibot, ListS, ListL).
partition([Head | Tail], Pibot, ListS, [Head | ListL])
:- Head > Pibot, partition(Tail, Pibot, ListS, ListL).
partition([], _, [], []).
?- quick_sort ([3, 8, 5, 2],List2).
quick_sort([Head | Tail], List2)
:- partition(Tail, Head, Small, Large),
quick_sort([3 | 8,5,2], List2)
:- partition([8,5,2], 3, Small, Large),
partition([Head | Tail], Pibot, [Head | ListS], ListL)
:- Head =< Pibot, partition(Tail, Pibot, ListS, ListL).
partition([Head | Tail], Pibot, ListS, [Head | ListL])
:- Head > Pibot, partition(Tail, Pibot, ListS, ListL).
partition([], _, [], []).
?- partition([8,5,2], 3, Small, Large)
partition([Head | Tail], Pibot, ListS, [Head | ListL]) :Head > Pibot, partition(Tail, Pibot, ListS, ListL).
partition([8 | 5,2], 3, ListS, [8 | ListL]) :8 > 3, partition([5,2], 3, ListS, ListL).
[2]
[5]
partition([8 | 5,2], 3, [2], [8 | 5]) :8 > 3, partition([5,2], 3, [2], [5]).
quick_sort([Head | Tail], List2)
:- partition(Tail, Head, Small, Large),
quick_sort(Small, ListS ),
quick_sort(Large, ListL),
append(ListS, [Head | ListL], List2).
quick_sort([], []).
partition([Head | Tail], Pibot, [Head | ListS], ListL)
:- Head =< Pibot, partition(Tail, Pibot, ListS, ListL).
partition([Head | Tail], Pibot, ListS, [Head | ListL])
:- Head > Pibot, partition(Tail, Pibot, ListS, ListL).
partition([], _, [], []).
?- quick_sort([3, 8, 5, 2], List2)
quick_sort([Head | Tail], List2)
:- partition(Tail, Head, Small, Large),
quick_sort(Small, ListS ),
quick_sort(Large, ListL),
append(ListS, [Head | ListL], List2).
quick_sort([], []).
?- quick_sort([3, 8, 5, 2], List2)
3 [8,5,2]
quick_sort([Head | Tail], List2)
[8, 5]
[2]
:- partition(Tail, Head, Small, Large),
quick_sort(Small, ListS ), [2]
quick_sort(Large, ListL), [5, 8]
append(ListS, [Head | ListL], List2).
[2, 3, 5, 8]
quick_sort([], []).
?- quick_sort ([2],ListS).
quick_sort([Head | Tail], List2)
:- partition(Tail, Head, Small, Large),
quick_sort([2 | ], ListS )
:- partition([ ], 2, Small, Large),
=[] =[]
partition([Head | Tail], Pibot, [Head | ListS], ListL)
:- Head =< Pibot, partition(Tail, Pibot, ListS, ListL).
partition([Head | Tail], Pibot, ListS, [Head | ListL])
:- Head > Pibot, partition(Tail, Pibot, ListS, ListL).
partition([], _, [], []).
?- quick_sort ([2],ListS).
quick_sort([Head | Tail], List2)
:- partition(Tail, Head, Small, Large),
quick_sort([2 | ], ListS )
:- partition([ ], 2, Small, Large),
=[] =[]
quick_sort([2 | ], ListS )
:- partition([] , 2, [], []),
quick_sort([], []),
quick_sort([], []),
append([], [2 | ], [2]).
?- quick_sort([2], List2).
[2] [ ]
[2]
quick_sort([Head | Tail], List2)
:- partition(Tail, Head, Small, Large),
[] []
quick_sort(Small, ListS ),
[]
[]
quick_sort(Large, ListL),
[]
[]
append(ListS, [Head | ListL], List2).
[]
[]
[2]
quick_sort([], []).
?- quick_sort([3, 8, 5, 2], List2).
3 [8,5,2]
quick_sort([Head | Tail], List2)
[2] [8, 5]
:- partition(Tail, Head, Small, Large),
quick_sort(Small, ListS ),[2]
quick_sort(Large, ListL),[5, 8]
append(ListS, [Head | ListL], List2).
[2, 3, 5, 8]
quick_sort([], []).
課題11(教科書 p. 205 [6])
• quick_sort を参考に、大きいもの順
に数字のリストを並べ替えるプログ
ラム、quick_reverseを定義せよ。
?- quick_reverse([3, 8, 0, 5, 2, 1], List2).
List2 = [8, 5, 3, 2, 1, 0]
?- quick_reverse([ ], List2).
List2 = [ ]
課題11
?- quick_reverse([3, 8, 0, 5, 2, 1], List2).
List2 = [8, 5, 3, 2, 1, 0]
quick_reverse([Head | Tail], List2)
:- partition(Tail, Head, Small, Large),
quick_reverse(Small, ListS ),
quick_reverse(Large, ListL),
append( ListL, [Head | ListS], List2).
quick_reverse([], []).

Download Report