LISP PROLOG . . , " ".
8.1. PROLOG
PROLOG (logic programming language). . PROLOG . Programming in Logic ( ). . PROLOG , .
PROLOG , , , . , (resolution), PROLOG. . 2.2.3.
PROLOG , , . PROLOG, , () , . . , " ", " ". , " ".
PROLOG- 1970 [49]. . [49, 50]. PROLOG 19751979 , . PROLOG. PROLOG LISP . [62]. . . [38]. 1987 [18].
|
|
1986 Turbo-Prolog, MS DOS, VISUAL-PROLOG WINDOWS.
8.2. PROLOG
PROLOG . 8.1.
- PROLOG, , , () . - . , .
. 8.1. PROLOG
. , . . :
- , (), ;
- , , .
. .
, , , , :
"alpha","Alpha","4beta",anna,x5
:
1b,#d,a-b
. :
(,;, <, >
PROLOG , .
:
- [] ;
- [AB] , B .
, PROLOG, , :
(,)
8.3. PROLOG
PROLOG :
- (domains);
- (predicates);
- (clauses).
:
Domains
< >=< >.
:
Domains
X=integer.
Z=real.
U=symbol*.
X, Z, U .
:
Predicates
< >(< >).
:
Predicates
vvod(X).
dlina(U,X).
vvod , dlina , , .
.
8.3.1.
PROLOG :
< >(< >),
.
:
(,).
(,).
([1,2,3,4]).
PROLOG :
< >(< >),
|
|
.
PROLOG:
<> if <1>, <2>,...,<N>.
PROLOG :
Clauses
<>.
<>.
:
Clauses
(,). /* */
(,). /* */
(,).
(,).
(X,Y) if (Z,Y),(X,Z).
/*X Y, Y Z,
Z */
8.3.2. PROLOG
PROLOG . GOAL, Clauses.
:
GOAL
(,) /* ?*/
.
< Run > < goal >
goal:(,).
.
8.1. : . .
: ? ? ? ?
:
domains
X,Y,Z=symbol.
predicates
(X,X,X).
clauses
(,,).
(,,).
/* :*/
goal:(,,Y)
:= Y=
goal (,,Y).
:= Y=
goal (,,Y)
:= Y=
goal (X,Y,Z)
:= Y= Z=
= Y= Z=
8.1. : : , , .
8.2. : , , , , ,
.
8.3. : , 1, 2 "" : , .
8.4. : : , , , .
8.5. : , , .
8.6. ( , ) : , .
8.7. : (), (), (, ) : (, Y), (, Y).
8.8. , (, ) "" (X, Y, Z, T).
8.9. : (, ), (, ) " " ().
8.10. : (, , ), "" (X, Y).
8.11. : ; ; ; , , ; , , ; , .
8.4. - PROLOG
readint(X), readreal(X), readchar(X), , , , .
: write(X) nl - .
8.2. .
domains
X,Y,Z=integer.
predicates
vvod(X,X).
sum(X,X,X).
clauses
vvod(X,Y) if write( , Y),
readint(X),readint (Y).
sum(X,Y,Z) if vvod(X,Y),Z=X+Y.
goal:sum(X,Y,Z).
, Z.
8.5. PROLOG
|
|
, . . , . .
if < >.
if < >.
- - - - - - - - - - - - - - - - - - - - - -
if < >
8.3. , .
Domains
X,Y=symbol.
Predicates
(X).
(X).
(X,X)
.
Clauses
(X) if write( ),readint(X),nl.
(Y) if write( ),write(Y).
(X,Y) if X<3,Y=.
(X,Y)if X>=3,X<=6,Y=...
(X,Y) if X>6,Y=..
if (X),(X,Y),().
8.12. .
8.13. .
8.14. (, , , ).
8.15. . ?
8.16. .
8.17. .
8.18. .
8.19. .
8.20. max(a,c)+max(b,c,d) a,b,c,d.
8.21. |x+xy+1| ,y.
8.22. max(a,b,c)min(b,c) a,b,c.
8.23. min(a,b)+min(b,c,d) a,b,c,d.
8.24. |2x + y| ,y.
8.25. max (a, b) max (a, c, d) a, b, c, d.
8.26. |3a b| a, b.
8.27. max (a, c) + max (b, c, d) a, b, c, d.
8.28. | x + xy + 1| , y.
8.29. max (a, b, c) min (b, c) a, b, c.
8.30. |ab 1| a, b.
8.31. min (a, b) + min (b, c, d) a, b, c, d.
8.32. |x y2| , y.
8.33. max (a, b) min (a, b, c) a, b, c.
8.34. |x2 y| , y.
8.35. min (a, c) min (b, c) a, b, c.
8.36. |x2 y2| , y.
8.37. min (a, b) × min (a, c) a, b, c.
8.38. |3x + y| , y.
8.39. max (a, b) + min (a, c) a, b, c.
8.40. |6x y| , y.
8.41. min (a, b) + min (d, c) a, b, c, d.
8.42. |x 8y2| , y.
8.43. max (a, c) × min (d, l) a, c, d.
8.44. |2x 3y| , y.
8.45. 2 min (a, b, c) a, b, c.
8.46. |ab + c| a, b, c.
8.47. max (a, c) min (a, c) a, c.
8.48. |ac b| a, b, c.
8.49. min (a, c) × min (d, e) a, c, d, e.
|
|
8.50. |a2 ac| a, c.
8.51. max (a, b) + min (b, c) a, b, c.
8.52. |x y2| , y.
8.53. min (a, b, c) × max (a, b) a, b.
8.6.
8.6.1.
PROLOG . , , . . .
8.4. :
("",).
("",).
("",).
("",).
("",).
(X)if (,).
(X)if (,).
(X)if (,).
(X)if (,).
: ?:
(X).
(X) , (). , "". (). (,). . (,), , (,) "", () "". "" "!!".
8.6.2. PROLOG
. , , . , , . :
if 1,2, n
:
1. 1 . , - - . , 1 = , 2.
2. 2 , 1. , 3. , PROLOG - , 1 1, . , 2 , 1. , 2. 1 , . 1, 2 = , 3 .
8.54. "" (, , ). : , , .
8.55. "" ( , , , ). : , , , .
8.56. "" (, , , ) : , , , .
8.57. "-" "-". : , .
8.58. "" (, , ) " , , , .
8.59. "-", "-" : , .
8.60. "" (, 1, 2) "" (, ).
8.61. "" ( 1, 2) 4 . "" ( 1, 2).
|
|
8.62. "" ( 1, 2) 5 " " (A, B).
8.63. "-" "".
8.64. "-". : , .
8.65. "" (, , ) " (X) 3".
8.66. "-" "-". : (X, Y) (X, Y).
8.67. "-" "-" "" (X, Y).
8.68. : (, ), (X), (X) " (X)".
8.6.3.
8.5. , . , , . ?
Clauses
(,).
(,).
(,).
(X,Y,Z) if (X,Y),(Y,Z).
Goal
(X,Y,Z).
8.69. . , . : ?
8.70. 4 X, Y, Z, T. , Y ; Y Z ; Z . ?
8.71. 6 : , , , , . , , , , , , .
8.72. , , , . , , ; ; , , . ?
8.73. , , 4 : , , , . - - . . ?
8.74. , , : , , . , , , ; , , ; .
8.75. : , , . :
) , ;
) , .
8.76. . , . :
) ;
) ;
) 4 ?
8.77. , . , :
) , ;
) ;
) , .
8.78. , . : . ?
8.79. , ,
) , ;
) , .
8.80. X, Y, Z, T , Y , Z T, Z Y T. .
8.7. PROLOG
8.7.1. PROLOG
PROLOG. . PROLOG- , - .
. , . :
) , ;
) , .
, . . .
8.7.2.
n! (n - 1)! , . , : n! = (n 1)! × n
PROLOG :
fact(0,1)if!.
fact(N,X)if M=N-1,fact(M,Y),X=Y+N.
:
fact(3,X).
. 8.1.
. 8.1.
() , - . "!", "" ( "cut"). . PROLOG- , , , , = -1, -2, . , "!".
.
8.6. 4 :
, , ,
fib(1,.,1) if!./* 1- ,0-- */
fib(2,1,1) if!./* =1, =1*/
fib(N,X,Y) if M=N-1,fib(M,L,X),Y=L+X.
/*N- =Y, N-1=X,
M=N- 1, M =, -1- =L,
Y=L+X*/.
8.7. NOD(M, N).
Clauses
Nod(X,X,X) if!.
Nod(X,Y,K) if X>Y,R=X-Y,nod(R,Y,K).
Nod(X,Y,K) if Y>X,R=Y-X,nod(X,Y,K).
/* X Y , nod=X, , */.
8.8. , xn :
xn=xn-1+2xn-2, x1=x2=1, x5=?
predicates
xn(integer,integer)
writeresult(integer)
query
clauses
xn(X,1) if X<=2,!.
xn(X,Y) if X1=X-1, xn(X1,Y1),X2=X-2, xn(X2,Y2),Y=Y1+2*Y2
writeresult(X) if
X<=0,
write("no solutions because N<=0"),
nl,!
writeresult(X) if
xn(X,Y),
write(Y),nl.
query if
write("input N: "), readint(N),
writeresult(N).
goal
query.
, xn.
8.81. xn = 2xn-1 1, x1=1, x5 =?
8.82. xn = n/xn-1, x1 = 2, x5 =?
8.83. xn = 3xn-1 + 1, x1 = 2, x5 =?
8.84. xn+1 = 2xn xn-1, x1 = 3, x2 = 1, x6 =?
8.85. xn = 1+xn-1 + xn-2, x1 = x2 = 2, x6 =?
8.86. xn+1 = xn + xn-1 + 3, x1 = 1, x2 = 2, x5 =?
8.87. xn+2 = xn + 2xn+1, x1 = 2, x2 = 1, x6 =?
8.88. xn = xn-1 + xn-2 + 2, x1 = x2 = 1, x6 =?
8.89. xn+2 = xn + 1/xn+1, x1 = x2 = 1, x5 =?
8.90. xn+1 = xn × xn-1, x1 = 1, x2 = 1/2, x6 =?
8.91. xn+2 = 2xn+1 + 3xn, x1 = 0, x2 = 1, x5 =?
8.92. xn = xn-1 + 2xn-2, x1 = x2 = 1, x5 =?
8.93. xn+2 = 2xn+1 + xn, x1 = 2, x2 = 1, x5 =?
8.94. xn+2 = xn+1 + xn/2, x1 = 1, x2 = 2, x5 =?
8.95. xn+1 = xn + 2xn-1, x1 = x2 = 1, x6 =?
8.7.3.
PROLOG- GRAPH, . N :
: N , N - 1 , N- .
: , .
8.9. 20 , 10 . (50, 50). - .
clauses
init if initgraph(0,0,_,_, ).
ris(1) if putpixel(50,50,15),!.
ris(N) if M=N-1,ris(M),X=50+20+M,putpixel (X, 50, 15).
rez if init,ris(20),readln(_),closegraph.
goal
rez.
8.10. 15 (300, 200) , 10 . R = 10.
clauses
konz(1) if circle(300,200,10)!.
konz(N) if M=N-1,konz(M),R=10+M*10,
circle(300,200,R).
goal
initgraph(0,0,_,_,),konz(15),readln(_),
closegraph.
8.11. .
clauses
zwet(c) if c=random(15),setcolor(c).
konz(1) if zwet(c),circle(300,200,10),!.
konz(N,c) if M=N-1,konz(M),zwet(c),k=10+M *10,circle(300,200,R).
goal
initgraph (0,0,_,_,),konc(15,c).
8.12. 4 .
predicates
image_item (integer)
query
clauses
image_item (0) if!.
image_item (N) if
Y = N * 100 50,
circle (50, Y, 40),
M = N 1,
image_item (M).
query if
initgraph (0, 0, _, _, ""),
cleardevice,
setcolor (15),
image_item (4),
readln (_),
closegraph.
goal
query.
, , , :
8.96.
8.97.
8.98.
8.99.
8.100.
8.101.
8.102.
8.103.
8.104.
8.105.
8.106.
8.107.
8.108.
8.109.
8.110.
8.8. PROLOG.
8.8.1.
8.2. :
) [ ] - ;
) [AB] - , - , - . .
:
) [1 [2, 3, 4]] 1 - , [2, 3, 4] - , . (. 8.2).
. 8.2. [1 [2, 3, 4]]
) [1, 2, 3, 4]. . PROLOG- 1, [1, 2]. [[1, 2]; [3, 4]]. (. 8.3).
. 8.3. [1, 2, 3, 4]
. , . , , , .. , , LISP, . PROLOG - .
8.8.2.
: " , ". , , 1 , . , . :
) , , ;
) , .
.
8.13. .
([ ], 0).
([A | B], N) if (B,M), N,M+1.
? ([, , ], ).
: =3.
8.14.
(X,[X _]).
(X, [A Y]) if (X,Y).
? (4, [1,3,4,9]).
: .
: , .
8.15. .
:
) , [ ] P, P;
) , P [XY], P Y X ( [XT]).
([ ], P, P).
([XY], P, [XT]) if (Y, P, T).
, :
? (L, [ R], [, , , , , ]).
:
L = [, ].
R = [, , ].
L = [, , , ].
R = [].
"append" (. "").
(!), , :
Append ([ ], L, L).
Append ([AB], C, [AD])if append (B, C, D).
? append (X, Y, [1, 2]).
:
X = [ ]
Y = [1,2]
X = [1]
Y = [2]
X = [1, 2]
Y = [ ].
append ([ ], l, l) if!. , :
X = [ ]
Y = [1, 2].
8.16. .
, , , -:
(X, [X Y], Y): !.
(X, [Z Y], [Z│W]): (X, Y, W).
: , , .
, X. "!" .
X :
(X, [ ], [ ]) if!.
(X, [X Y], W): (X, Y, W).
(X, [Z Y], [Z W]): (X, Y, W).
: , , , , .
8.17. .
, N X:
([X _ ], 1, X).
([W Y], N, X)if N is M+1, (Y, M, X).
.
8.18. .
max ([X], X).
max ([X Y], X): max (Y, W), X >W,!.
max ([X Y], W): max (Y, W).
: , , , , , .
8.19. .
. , . , :
([X], [X]).
([X Y], Z): (Y, W), (W, [X], Z).
, .
8.20. , .
Domains
X, Y, Z = symbol*.
A,B=symbol.
Predicates
Dan1 (X).
Dan2 (X).
Soed (X,X,X).
Udal (A,X,X).
Clauses
Dan1 ([1,2,3,4]).
Dan2 ([4,3,4,2]).
Soed ([ ], X, X) if!.
Soed ([X Y],Z, [ X T ]) if soed (Y, Z, T).
Udal (A, [ ], [ ]) if!.
Udal (A, [A Y], Z) if udal (A, Y, Z)
Udal (A, [ B Y], [B Z]) if udal (A, Y, Z).
Rezult (X, Y, Z) if dan1 (X), dan2 ([A Y]), soed (X, [A Y], T), udal (A, T, Z).
Rezult :
1. dan1 dan2 , X [1, 2, 3, 4], 4, Y [3, 4, 2].
1. [1,2,3,4] [4,3,4,2], T [1, 2, 3, 4, 4, 3, 4, 2].
2. 4, , T. Z=[1,2,3,3,2].
8.111. , max .
8.112. , .
8.113. , .
8.114. , , min.
8.115. , .
8.116. , , max.
8.117. , .
8.118. . min, max.
8.119. 5, .
8.120. , 6, min.
8.121. , 2, 3 . , max?
8.122. , . , .
8.123. ? , .
8.124. . . , .
8.125. , .
8.126. , , , .
8.127. , max .
8.128. , .
8.129. , min .
8.130. max , . .
8.131. .
8.132. max min . Min , max .
8.133. , , .
8.134. max .
8.135. , . . .
8.136. . .
8.137. . , , .
8.138. . , .
8.139. , .
8.140. . . .
8.141. min. , . , min 999.
8.9. PROLOG
8.9.1.
PROLOG. , PROLOG-. , , PROLOG , "". "", . , "modus ponens".
8.21.
: .
8.22. , -> ,
: ( ) = ( ) ( ).
8.23. .
, N . . , . , .
"" :
1) ;
2) ;
3) ;
4) .
, (,,,) , , .
: , (0,-,-,-) if!
:
(N,A,B,C) if M=N-1, (,,,), (,), (,,,).
(X,Y) if write ([, , , X, , Y]),nl.
: N , N-1 , , N-1 , .
8.24. .
: , , . : ", , , , ". ?
("").
("").
("").
("").
("").
("").
(X,Y) if (X), (Y), X= "", not (Y= ""), not(Y= "").
/* , , */
(X,Y) if (X), (Y), X= "", not (Y= ""), not(("",)).
/* , */
(X,Y) if (X), (Y), X= "", not (("",)), not(("",)).
/* , , , , */
, - . , .
8.142. , . , 2 3 , 3.
8.143. . , .
8.144. , . , , . . .
8.145. 3 : , . , . , . . , , . , .
8.146. , , , , . , , , . . ?
8.147. , , , , , ( ), . , .
8.148. 1, 2, 3 . - . . . 1- . ? ?
8.149. 5 , , , . , , , . , , . , , . , .
8.150. , , 4 , , , , . , , ; ; ; . ?
8.151. , , . . ?
8.152. A, B, C, D : , , . : , , . ,
) , , -;
) B , , :
) A , ;
) D -, .
?
8.153. , -. , , , . , . - , , :
) ;
) ;
) ;
) .
8.10. ,
, (. 8.4).
. 8.4.
, 6 1,,6 5
a, b, c, d, e. 6 . ( ) ( ).
8.25. .
6 b, c, d, e, f, g, , , : (b,e), (b,c), (d,e), (c,d), (e,f), (g,e). g . (. 8.5):
. 8.5. 8.25
, , , , .
: , , .
(X,Y,T), , Y, . :
(,,) if!.
/* , */
: Z Z . :
(X,Y,T) if (X,Z), not ( (Z,T)), (Z,Y, [Z T]).
(X,Z) (Z,X). :
(X,Y,T) if (Z,X), not ((Z,T)), (Z, Y, [Z T]).
, , : g; .. (g) , :
(a,X,[ ]), _().
.
8.154. (. 8.6), 2 . .
. 8.6. 8.154
8.155. 5- . , .
8.156. (X,Y,). .
8.157. , , . , .
8.158. , "" (X,Y) , .
8.159. , (. 8.7).
. 8.7. 8.159
8.160. . , . , ? , ?
. 8.8. 8.160
8.161. 6 :
(X,Y, 1- ).
, 12 14 1 , .
8.162. 4 , . , . .
8.163. , ≤500.
8.164. N1, N2, N3, . , .
N1 N2, N3, N4, N2 N3. , . , .