Řez a upnutí
Rez, negace
Rez a ořezání
f(X,Y) s(X,Y) s(X,Y)
s(X,Y).
Y i s X + 1.
Y i s X + 2.
f(X,Y) s(X,Y) s(X,Y)
s(X,Y), !.
Y i s X + 1.
Y i s X + 2.
?- fCl.Z).
Z = 2 ? ; Z = 3 ? ; no
Z = no
fCl.Z). 2 ? ;
Ořezání: po splnění podcílů před řezem se už neuvažuje další možné splnění těchto podcílů
Smazání řezu změní chování programu
Hana Rudová, Logické programování I, 5. března 2013
f(X,0) f(X,2) f(X,4)
X < 3,   ! .
3 =< X, X < 6, !
6 =< X.
přidání operátoru řezu
6
?- f(l,Y), Y>2.
f(X,0) :- X < 3, !. %(1) f(X,2) :- X < 6, !. %(2) f(X,4).
?- fCl.Y).
1 Smazání řezu v (1) a (2) změní chování programu
1 Upnutí: po splnění podcílů před řezem se už další klauzule neuvažují
Hana Rudová, Logické programování I, 5. března 2013 2
Řez, negace
Chování operátoru řezu
Předpokládejme, že klauzule H :- TI, T2, Tm, !
aktivována voláním cíle C, který je unifikovatelný s H.
V momentě, kdy je nalezen řez, existuje řešení cílů TI, ..., Tm
...Tn.je
G=h(X,Y)
X=1,Y=1
Ořezání: při provádění řezu se už další možné splnění cílů TI, .. nehledá a všechny ostatní alternativy jsou odstraněny
Upnutí: dále už nevyvolávám další klauzule, jejichž hlava je také unifikovatelná s C
Tm
Y=2 X=2
?- h(X,Y).
h(l,Y) h(2,Y)
tl(Y), !. a.
tl(l) tl(2)
b.
c.
h(X,Y) X=l   /     \ X=2
tl(Y) a (vynechej: upnutí) Y=l /     \ Y=2
b c   (vynechej: ořezání)
/
Hana Rudová, Logické programování I, 5. března 2013
Rez: návrat na rodiče
■ Po zpracování klauzule s řezem se vracím až na rodiče této klauzule, tj. a(X)
Hana Rudová, Logické programování I, 5. března 2013 5 Řez, negace
Řez: příklad
?- a(X).		a(x)	c(X) :-c(X) :-	p (X), v (X).	clCX) :-d(X) :-	P(X), ! v(X).
Cl) a(X)  :- h(X,Y). (2) a(X) :- d.		h(X,Y) d Sk l tl(Y),!,e(X')   upnutí □		p(D. p(2).	v(2)	
(3) h(l,Y)  :- tl(Y), !	, e(X).	Y/1 / X				
(4) h(2,Y)  :- a.		b,!,e(X') ořezání	?- c(2)		?- cl(2)	
(5) tl(l)  :- b.		c,!,e(X') d,!,e(X')	true ?	%p(2)	true ?	; %p(2)
(6) tl(2) :- c.		1 1	true ?	%v(2)	no	
(7) b :- c.		no !,e(X') j i	no			
(8) b :- d.						
(9) d. (10) e(l) ■ (11) e(2).		/^'\ 2 □ □	?- c(X) X = 1 ? X = 2 ? X = 2 ?	; %p(D ; %p(2) ; %v(2)	?- cl(X) X = 1 ? no	; %p(D
Hana Rudová, Logické programování I, 5. března 2013
Řez: cvičení
1. Porovnejte chování uvedených programů pro zadané dotazy.
Typy řezu
a(X,X)  :- b(X). a(X,X)  :- b(X),!.
a(X,Y)  :- Y i s X+l. a(X,Y)  :- Y i s X+l.
b(X)  :- X > 10. b(X) :- X > 10.
?- a(X,Y). ?- a(l,Y). ?- a(ll,Y).
2. Napište predikát pro výpočet maxima max( X, Y, Max )
a(X,X)  :- b(X),c. a(X,Y)  :- Y is X+l. b(X)  :- X > 10. c :- ! .
Zlepšení efektivity programu: určíme, které alternativy nemá smysl zkoušet
Poznámka: na vstupu pro X očekávám číslo Zelený řez: odstraní pouze neúspěšná odvození
■ f(X,l)  :- X >= 0,   !.    f(X,-l)  :- X < 0.
bez řezu zkouším pro nezáporná čísla 2. klauzuli
Modrý řez: odstraní redundantní řešení
■ f(X,l) :- X >= 0, !. f(0,l). f(X,-l) :- X < 0. bez řezu vrací f(0,l) 2x Červený řez: odstraní úspěšná řešení
■ f(X,l) :- X >= 0,  !.   f(_X,-l).      bez řezu uspěje 2. klauzule pro nezáporná čísla
Hana Rudová, Logické programování I, 5. března 2013 7 Řez, negace Hana Rudová, Logické programování I, 5. března 2013
Negace jako neúspěch
Negace jako neúspěch: operátor \+
Speciální cíl pro nepravdu (neúspěch) fail a pravdu true
Xa Y nejsou unifikovatelné: different(X, Y)
differentC X, Y )  :- X = Y,  !, fail. differentC _X, _Y ).
Xje muž: muz(X)
muz( X ) :- zena( X ),  !, fail. muz( _X ).
different(X,Y) :- X different(_X,_Y).
Y,  !, fail.       muz(X)  :- zena(X),  !, fail muz(_X).
Unární operátor \+ P
■ jestliže P uspěje, potom \+ P neuspěje \+(P) :- P,  !, fail.
■ v opačném případě \+ P uspěje \+(_)■
differentC X, Y ) :- \+ X=Y. muz( X ) :- \+ zena( X ).
Pozor: takto definovaná negace \+P vyžaduje konečné odvození P
Hana Rudová, Logické programování I, 5. března 2013
Negace a proměnné
\+(P) :- P, !, fail. % (I) \+(_). % (ID
dobre( citroen ). dobre( bmw ).
drahe( bmw ).
rozumne( Auto ) :-\+ drahe( Auto ).
% (D
% (2)
% (3)
% (4)
?- dobre( X ), rozumne( X ).
d ob re (X), rozum n e (X)
dle (1), X/citroen
rozumne(citroen) dle (4)
\+ drahe(citroen) \ dle (II) dle (I)
drahe(citroen),!, fail
□ yes
no
Hana Rudová, Logické programování I, 5. března 2013
Hana Rudová, Logické programování I, 5. března 2013
Negace a proměn
\+(P) :- P, !, fail. % (I) \+(_). % (ID
dobre( citroen ). dob re( bmw ).
drahe( bmw ).
rozumne( Auto ) :-\+ drahe( Auto ) .
% (D
% (2)
% (3)
% (4)
?- rozumne( X ), dobre( X ).
b'žumne(X), dobre(X) dle (4)
\+ drahe(X), dobre(X) dle (I)
drahe(X),!,fail,dobre(X) dle (3), X/bmw
!, fail, dobre(bmw)
fail,dobre(bmw)
no
Hana Rudová, Logické programování I, 5. března 201 3 1 2
Bezpečný cíl
?- \+ drahe( citroen ). yes ?- \+ drahe( X ). no ?- rozumne( citroen ). yes ?- rozumne( X ). no \+ Pje bezpečný: proměnné Pjsou v okamžiku volání P instanciovány ■ negaci používáme pouze pro bezpečný cíl P
Hana Rudová, Logické programování I, 5. března 2013
Predikáty na řízení běhu programu I.
řez „!"
fai 1: cíl, který vždy neuspěje      true: cíl, který vždy uspěje \+ P: negace jako neúspěch
\+ P :- P,  !, fail ; true. once(P): vrátí pouze jedno řešení cíle P
once(P) :- P,  !. Vyjádření podmínky: P -> Q ; R
■ jestliže platí P tak Q        (P -> Q ; R) : - P,  ! , Q.
■ v opačném prípade R      (P -> Q ; R) :- R.
■ príklad: min(X,Y,Z) : - X =< Y -> Z = X ; Z = Y. P -> Q
■ odpovídá: (P -> Q; fail)
■ príklad: zaporne(X) :- number(X) -> X < 0.
Hana Rudová, Logické programování I, 5. března 201 3 15
Chování negace
1 ?- \+ drahe( citroen ). yes ?- \+ drahe( X ). no
■ ?- drahe( X ).
PTÁME SE: existuje X takové, že drahe( X ) platí?
■ ?- \+ drahe( X ). \+ drahe( X) :- drahe(X),!,fail. \+drahe(X).
z definice \+ plyne: není dokazatelné, že existuje X takové, že drahe( X ) platí tj. pro všechna X platí \+ drahe( X )
1 TEDY: pro cíle s negací neplatí existuje X takové, že \+ drahe( X )
p negace jako neúspěch není ekvivalentní negaci v matematické logice
1 Negace jako neúspěch používá předpoklad uzavřeného světa pravdivé je pouze to, co je dokazatelné
Hana Rudová, Logické programování I, 5. března 2013 14 Řez, negace
Predikáty na řízení běhu programu II.
1 cal 1 (P): zavolá cíl P a uspěje, pokud uspěje P 1 nekonečná posloupnost backtrackovacích voleb: repeat repeat.
repeat :- repeat.
klasické použití: generuj akci X, proveď ji a otestuj, zda neskončit Hlava :- ...
u"loz_stav( StaryStav ),
repeat,
generuje X ), % deterministické: generuj, prováděj, testuj
prováděj( X ), testuj( X ),
i
obnov_stav( StaryStav ),
Hana Rudová, Logické programování I, 5. března 2013
Reprezentace seznamu
Seznamy
1 Seznam: [a, b, c], prázdný seznam []
1 Hlava (libovolný objekt), tělo (seznam): .(Hlava, Telo)
■ všechny strukturované objekty stromy - i seznamy
■ funktordva argumenty
■ .(a,  .(b,  .(c,  []))) = [a, b, c]
■ notace: [ Hlava | Telo ] = [a | Tel o]
Telo je v [a | Tel o] seznam, tedy píšeme [ a, b, c ] = [ a | [ b, c ] ] ' Lze psát i: [a, b | Tel o]
■ před " |" je libovolný počet prvků seznamu , za " | "je seznam zbývajících prvků
■ [a.b.c] = [a|[b,c]] = [a,b|[c]] = [a,b,c|[]]
■ pozor: [ [a,b]  |  [c]]r[a,b|  [c] ]
1 Seznam jako neúplná datová struktura: [a,b,c|T]
■ Seznam = [a,b,c|T], T = [d,e|S], Seznam = [a,b,c,d,e|S]
Hana Rudová, Logické programování 1,5. března 2013 18
Prvek seznamu
■ member( X, S )
■ platí: member( b,  [a,b,c] ).
■ neplatí: member( b,  [[a,b]|[c]] ).
■ Xje prvek seznamu S, když
■ Xje hlava seznamu S nebo member( X,  [ X | _ ] ). %(1)
■ Xje prvek těla seznamu S
member( X,  [ _ | Telo ] ) :-
member( X, Telo ). %(2)
■ Příklady použití:
■ memberCl,[2,1,3]).
■ memberCX,[1,2,3]) .
Hana Rudová, Logické programování I, 5. března 201 3 19
dle (1).
□ yes
dle(1).
□ yes
member(1,[2,1,3,1,4])
dle (2) member(1,[1,3,1,4])
dle (2) member(1,[3,1,4])
dle (2) member(1 ,[1,4])
dle (2) member(1 ,[4])
|  dle (2) member(1,[]) dle (2)
no
Spojení seznamů
append( LI, L2, L3 )
Platí: append( [a,b],  [c,d],  [a,b,c,d] )
Neplatí: append( [b,a],  [c,d],  [a,b,c,d] ), append( [a,[b]],  [c,d],  [a,b,c,d] )
Definice:
■ pokud je 1. argument prázdný seznam, pak 2. a 3. argument jsou stejné seznamy: append( [], S, S ).
■ pokud je 1. argument neprázdný seznam, pak má 3. argument stejnou hlavu jako 1.: append( [X|S1], S2,  [X|S3] )  :- append( SI, S2, S3).
X
S1
S2
S3
Hana Rudová, Logické programování I, 5. března 2013
Cvičení: append/2
appendC [], S, S ).        % (1)
appendC [X|S1], S2,  [X|S3] ) :- appendC SI, S2, S3).     % (2)
:- append([l,2],[3,4],A). I (2) I A=[1|B]
I
:- append([2],[3,4],B). I (2)
I B=[2|C]   => A=[1,2|C]
I
:- append([],[3,4],Q.
I CD
| C=[3,4]   => A=[l,2,3,4],
I
yes
Hana Rudová, Logické programování I, 5. března 2013
21
Seznamy