1 of 34

数理論理学

第11回

​

  • 節集合
  • prologによるソーティングプログラム

​

© 加藤，高田，新出

2 of 34

4.1.4節(p. 87)

節集合

7.7節(p. 197)

Prologによる

Quicksort

プログラム

3 of 34

演習課題 10

​

​

​

をスコーレム標準形に変換せよ。

スコーレム関数記号は、x に影響を受けるもの

はf (x)を、x と z に影響を受けるものはg(x,z)

を使用すること。　

途中の経過式、および使った規則も全て記入すること。

これらが一つでも欠けていれば０点。

4 of 34

⊃ 除去(p. 74 10.)

￢移動 (p. 74 12,11)

∀,∃移動

∃削除(スコーレム化)

レポート用紙には、以下のヒントも含め、全て記述すること

5 of 34

スコーレム標準形へ変換

C1

C2

Cm

6 of 34

4.1.4 節集合

とする。このとき、

​

​

をFsk に対応する節集合という。また、

Fsk を S に対応するスコーレム標準形という。　

prologプログラム

に対応

定義 4.5 S の解釈は、 Fsk の解釈と同じ。

　　　 I(S) = I(Fsk)

p. 87

7 of 34

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).

事実節

確定節

8 of 34

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).

9 of 34

female(sumire).

parent(sumire, maruko).

mother(X, Y) :- parent(X, Y), female(X).

例 4.8 (p. 88)

10 of 34

female(sumire).

parent(sumire, maruko).

mother(X, Y) :- parent(X, Y), female(X).

?- mother(sumire, maruko).

例 4.8 (p. 88)

11 of 34

female(sumire).

parent(sumire, maruko).

mother(X, Y) :- parent(X, Y), female(X).

?- mother(sumire, maruko).

例 4.8 (p. 88)

12 of 34

例 4.8

⊃ 除去（p. 74 10.)

13 of 34

ド・モルガン (p. 74 8.)

例 4.8

14 of 34

例 4.8

15 of 34

クイックソート (p. 197)

[3, 8, 0, 5, 2, 1]

→ [0, 1, 2, 3, 5, 8]

16 of 34

クイックソート (p. 197)

[3, 8, 0, 5, 2, 1]

17 of 34

クイックソート (p. 197)

[0, 2,1]

[8, 5]

[3, 8, 0, 5, 2, 1]

18 of 34

クイックソート (p. 197)

[0, 2,1]→[0, 1, 2]

[8, 5]→[5, 8]

​

[3, 8, 0, 5, 2, 1]

19 of 34

クイックソート (p. 197)

[0, 2,1]→[0, 1, 2]

[8, 5]→[5, 8]

​

[0, 1, 2, 3, 5, 8]

[3, 8, 0, 5, 2, 1]

20 of 34

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([], _, [], []).

プログラム7.8 (p. 199)

quick.pl とし

て作成し、

教科書通りの

実行例を確認

21 of 34

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([], _, [], []).

22 of 34

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([ ], [ ], [ ]).

append が、並べ替えの要

23 of 34

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([], _, [], []).

24 of 34

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([3 | 8,5,2], List2)

:- partition([8,5,2], 3, Small, Large),

quick_sort([Head | Tail], List2)

:- partition(Tail, Head, Small, Large),

25 of 34

?- partition([8,5,2], 3, Small, Large)

partition([8 | 5,2], 3, ListS, [8 | ListL]) :-

8 > 3, partition([5,2], 3, ListS, ListL).

partition([Head | Tail], Pibot, ListS, [Head | ListL]) :-

Head > Pibot, partition(Tail, Pibot, ListS, ListL).

[2]

[5]

partition([8 | 5,2], 3, [2], [8 | 5]) :-

8 > 3, partition([5,2], 3, [2], [5]).

26 of 34

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([], _, [], []).

27 of 34

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)

28 of 34

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([], []).

3

[8,5,2]

[2]

[8, 5]

[2]

[5, 8]

?- quick_sort([3, 8, 5, 2], List2)

[2, 3, 5, 8]

29 of 34

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([2 | ], ListS )

:- partition([ ], 2, Small, Large),

quick_sort([Head | Tail], List2)

:- partition(Tail, Head, Small, Large),

=[]

=[]

30 of 34

quick_sort([2 | ], ListS )

:- partition([] , 2, [], []),

quick_sort([], []),

quick_sort([], []),

append([], [2 | ], [2]).

?- quick_sort ([2],ListS).

quick_sort([2 | ], ListS )

:- partition([ ], 2, Small, Large),

quick_sort([Head | Tail], List2)

:- partition(Tail, Head, Small, Large),

=[]

=[]

31 of 34

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([2], List2).

[2]

[ ]

[2]

[ ]

[ ]

[ ]

[ ]

[ ]

[2]

32 of 34

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([], []).

3

[8,5,2]

[2]

[8, 5]

[2]

[5, 8]

?- quick_sort([3, 8, 5, 2], List2).

[2, 3, 5, 8]

33 of 34

課題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 = [ ]

34 of 34

課題11

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([], []).

?- quick_reverse([3, 8, 0, 5, 2, 1], List2).

List2 = [8, 5, 3, 2, 1, 0]