Řez, negace
Řez a upnutí
f(X,0)       X < 3 .
f(X,2)       3 =< X, X < 6 .
f(X,4)       6 =< X.
přidání operátoru rezu ,,!''
y ?- f(i,y), y>2.
4 •-
2 ~ m 0
__i_1      ó_i_i_i_i_i_
3 6 x
Hana Rudová, Logické programování I, 28. února 2011
2
Řez, negace
Řez a upnutí
f(X,0)       X < 3, !.
f(X,2)       3 =< X, X < 6, !.
f(X,4)       6 =< X.
přidání operátoru rezu
y ?- f(i,y), y>2.
4 •-
2 ~ m 0
__i_1      ó_i_i_i_i_i_
3 6 x
& Upnutí: po splnění podcílů pred rezem se už další klauzule neuvažují
Hana Rudová, Logické programování I, 28. února 2011 2 Řez, negace
Řez a upnutí
f(X,0)  :- X < 3, I.
f(X,2)  :- 3 =< X, X < 6, I.
f(X,4)  :- 6 =< X.
přidání operátoru rezu ,,!''
y
4
2
j-l__é—1-L
-e
?- f(1,Y), Y>2.
f(X,0)  :- X < 3, I. f(X,2)  :- X < 6,   I. %(2) f(X,4).
J_L
3
6
x
& Upnutí: po splnění podcílů pred rezem se už další klauzule neuvažují
Hana Rudová, Logické programování I, 28. února 2011 2 Řez, negace
Řez a upnutí
f(X,0)  :- X < 3, I.
f(X,2)  :- 3 =< X, X < 6, I.
f(X,4)  :- 6 =< X.
přidání operátoru rezu ,,!''
y
4
2
j-l__é—1-L
-e
J_L
3
6
x
?- f(1,Y), Y>2.
f(X,0)  :- X < 3, I. f(X,2)  :- X < 6,   I. %(2) f(X,4).
?- f(1,Y).
Smazání rezu v (1) a (2) zmení chování programu
& Upnutí: po splnení podcílU pred rezem se už další klauzule neuvažují
Hana Rudová, Logické programování I, 28. února 2011 2 Rez, negace
Řez a ořezání
f(X,Y) :- s(X,Y). s(X,Y)  :- Y is X + 1. s(X,Y)  :- Y is X + 2.
?- f(1,Z).
Hana Rudová, Logické programování I, 28. února 2011
3
Řez, negace
Řez a ořezání
f(X,Y)  :- s(X,Y). s(X,Y)  :- Y is X + 1. s(X,Y)  :- Y is X + 2.
?- f(1,Z). Z = 2 ? ; Z = 3 ? ; no
Hana Rudová, Logické programování I, 28. února 2011
3
Řez, negace
Řez a ořezání
f(X,Y)  :- s(X,Y). s(X,Y)  :- Y is X + 1. s(X,Y)  :- Y is X + 2.
f(X,Y)  :- s(X,Y), I. s(X,Y)  :- Y is X + 1. s(X,Y)  :- Y is X + 2.
?- f(1,Z).
?- f(1,Z).
Z = 2 ? ; Z = 3 ? ; no
Ořezání: po splnění podcílů pred rezem se už neuvažuje další možné splnění těchto podcílů
Hana Rudová, Logické programování I, 28. února 2011
Řez, negace
Řez a ořezání
f(X,Y)  :- s(X,Y). s(X,Y)  :- Y is X + 1. s(X,Y)  :- Y is X + 2.
f(X,Y)  :- s(X,Y), I. s(X,Y)  :- Y is X + 1. s(X,Y)  :- Y is X + 2.
?- f(1,Z). Z = 2 ? ; Z = 3 ? ; no
?- f(1,Z). Z = 2 ? ; no
Ořezání: po splnění podcílů pred rezem se už neuvažuje další možné splnění těchto podcílů
Smazání rezu zmení chování programu
Hana Rudová, Logické programování I, 28. února 2011
3
Rez, negace
Chování opeřátořu řezu
Predpokládejme, že klauzule H :- T1, T2, Tm,  I,  ...Tn. je
aktivována voláním cíle G, který je unifikovatelný s H. G=h(X,Y)
V momente, kdy je nalezen rez, existuje rešení cílu T1, ..., Tm
X=1,Y=1
Ořezání: p r i provádení r ezu se už další možné splnení cílů T1, ..., Tm nehledá a všechny ostatní alternativy jsou odstraneny
Upnutí: dále už nevyvolávám další klauzule, jejichž hlava je také unifikovatelná s G
Y=2
X=2
?- h(X,Y).
h(1,Y) :- t1(Y), I. h(2,Y) :- a.
t1(1) :- b. t1(2)  :- c.
h(X,Y) X=1   /     \ X=2
t1(Y) a (vynechej: upnutí) Y=1 /     \ Y=2
b c   (vynechej: o rezání)
/
Hana Rudová, Logické programování I, 28. února 2011
4
Rez, negace
Řez: návřat na řodice
?- a(X).
(1) a(X) :- h(X,Y).
(2) a(X) :- d.
(3) h(1,Y) :- t1(Y),  I, e(X).
(4) h(2,Y)  :- a.
(5) t1(1) :- b.
(6) t1(2) :- c.
(7) b :- c.
(8) b :- d.
(9) d.
(10) e(1) .
(11) e(2).
-í* Po zpracování klauzule s řezem se vracím až na rodice této klauzule, tj. a(X)
Hana Rudová, Logické programování I, 28. února 2011
5
Rez, negace
Řez: příklad
c(X) :- p(X). c(X) :- v(X).
p(1).   p(2). v(2).
?- c(2).
Hana Rudová, Logické programování I, 28. února 2011
6
RŘez, negace
c(X) :- p(X). c(X) :- v(X).
Řez: příklad
p(1). p(2).
v(2).
?- c(2).
true ? ; %p(2)
true ? ; %v(2)
no
?- c(X).
Hana  udová, Logické programování I, 28. února 2011
Řez, negace
6
Řez: příklad
c(X) :- p(X). c(X) :- v(X).
p(1).    p(2). v(2).
?- c(2).
true ? ; %p(2)
true ? ; %v(2)
no
?- c(X).
X = 1 ? ; %p(1) X = 2 ? ; %p(2) X = 2 ? ; %v(2) no
Hana Rudová, Logické programování I, 28. února 2011 6 Řez, negace
Řez: příklad
c(X) :- p(X). c1(X) :- p(X), I.
c(X) :- v(X). c1(X) :- v(X).
p(1).    p(2). v(2).
?- c(2). ?- c1(2).
true ? ; %p(2)
true ? ; %v(2) no
?- c(X).
X = 1 ? ; %p(1) X = 2 ? ; %p(2) X = 2 ? ; %v(2) no
Hana Rudová, Logické programování I, 28. února 2011 6 Řez, negace
Řez: příklad
c(X) :- p(X). c1(X) :- p(X), I.
c(X) :- v(X). c1(X) :- v(X).
p(1).    p(2). v(2).
?- c(2).
true ? ; %p(2)
true ? ; %v(2)
no
?- c1(2).
true ?   ; %p(2)
no
?- c(X). ?- c1(X).
X = 1 ? ; %p(1)
X = 2 ? ; %p(2)
X = 2 ? ; %v(2)
no
Hana Rudová, Logické programování I, 28. února 2011 6 Rez, negace
Řez: příklad
c(X) :- p(X). c1(X) :- p(X), I.
c(X) :- v(X). c1(X) :- v(X).
p(1).    p(2). v(2).
?- c(2).
true ? ; %p(2)
true ? ; %v(2)
no
?- c1(2).
true ?   ; %p(2)
no
?- c(X).
X = 1 ? ; %p(1) X = 2 ? ; %p(2) X = 2 ? ; %v(2) no
?- c1(X).
X = 1 ?    ; %p(1)
no
Hana Rudová, Logické programování I, 28. února 2011
Rez, negace
6
Řez: cvičení
1. Porovnejte chování uvedených programu pro zadané dotazy.
a(X,X) :- b(X). a(X,Y) :- Y is X+1. b(X)  :- X > 10.
?- a(X,Y). ?- a(1,Y). ?- a(11,Y).
a(X,X) :- b(X),I. a(X,Y) :- Y is X+1. b(X) :- X > 10.
a(X,X) :- b(X),c. a(X,Y) :- Y is X+1.
b(X) :- X > 10
c ■- I
2. Napište predikát pro výpocet maxima max( X, Y, Max )
Hana Rudová, Logické programování I, 28. února 2011
7
RŘez, negace
Typy řezu
Zlepšení efektivity programu: urame, které alternativy nemá smysl zkoušet Zelený řez: odstraní pouze neúspešná odvození
f(X,1)  :- X >= 0,  I.    f(X,-1)  :- X < 0.
Hana Rudová, Logické programování I, 28. února 2011
8
Rez, negace
Typy řezu
Zlepšení efektivity programu: urcíme, které alternativy nemá smysl zkoušet Zelený řez: odstraní pouze neúspešná odvození
f(X,1)  :- X >= 0,  I.    f(X,-1)  :- X < 0.
bez rezu zkouším pro nezáporná císla 2. klauzuli
Hana Rudová, Logické programování I, 28. února 2011
8
Rez, negace
Typy řezu
Zlepšení efektivity programu: urcíme, které alternativy nemá smysl zkoušet Zelený řez: odstraní pouze neúspešná odvození
f(X,1)  :- X >= 0,  I.    f(X,-1)  :- X < 0.
bez rezu zkouším pro nezáporná císla 2. klauzuli
Modřý řez: odstraní redundantní r ešení
f(X,1)  :- X >= 0,  I.    f(0,1). f(X,-1)  :- X < 0.
Hana Rudová, Logické programování I, 28. února 2011
8
Rez, negace
Typy řezu
Zlepšení efektivity programu: urcíme, které alternativy nemá smysl zkoušet Zelený řez: odstraní pouze neúspešná odvození
f(X,1)  :- X >= 0,  I.    f(X,-1)  :- X < 0.
bez rezu zkouším pro nezáporná císla 2. klauzuli
Modřý řez: odstraní redundantní r ešení
a f(X,1) :- X >= 0,  I.    f(0,1). f(X,-1) :- X < 0. bez r ezu vrací f(0,1) 2x
Hana Rudová, Logické programování I, 28. února 2011
8
Rez, negace
Typy řezu
Zlepšení efektivity programu: urame, které alternativy nemá smysl zkoušet Zelený řez: odstraní pouze neúspešná odvození
f(X,1)  :- X >= 0,  I.    f(X,-1)  :- X < 0.
bez rezu zkouším pro nezáporná císla 2. klauzuli
Modřý řez: odstraní redundantní r ešení
a f(X,1) :- X >= 0,  I.    f(0,1). f(X,-1) :- X < 0. bez r ezu vrací f(0,1) 2x
Ceřvený řez: odstraní úspešná rešení
f(X,1)  :- X >= 0,  I. f(_X,-1).
Hana Rudová, Logické programování I, 28. února 2011
8
Rez, negace
Typy řezu
Zlepšení efektivity programu: urcíme, které alternativy nemá smysl zkoušet Zelený řez: odstraní pouze neúspešná odvození
f(X,1)  :- X >= 0,  I.    f(X,-1)  :- X < 0.
bez rezu zkouším pro nezáporná císla 2. klauzuli
Modřý řez: odstraní redundantní r ešení
a f(X,1) :- X >= 0,  I.    f(0,1). f(X,-1) :- X < 0. bez r ezu vrací f(0,1) 2x
Ceřvený řez: odstraní úspešná rešení
Jť f(X,1) :- X >= 0,  I.   f(_X,-1).     bez r ezu uspeje 2. klauzule pro nezáporná císla
Hana Rudová, Logické programování I, 28. února 2011
8
Rez, negace
Negace jako neúspěch
Speciální cíl pro nepravdu (neúspěch) fail a pravdu true
-í* X a Y nejsou unifikovatelné: different(X, Y)
C different( X, Y ) :- X = Y,  I, fail. different( _X, _Y ).
-í* Xje muž: muz(X)
muz( X ) :- zena( X ),  I, fail. muz( _X ).
Hana Rudová, Logické programování I, 28. února 2011
9
Řez, negace
Negace jako neúspěch: operátor \+
ďifferent(XfY) :-X=Y, I, fail. muz(X) :-zena(X), I, fail. different(_X,_Y). muz(_X).
Unární operátor \+ P
& jestliže P uspeje, potom \+ P neuspeje \+(P) :- P,  I, fail.
it v opačném prípade \+ P uspeje \+(_).
Hana Rudová, Logické programování I, 28. února 2011
10
Rez, negace
Negace jako neúspěch: operátor \+
M different(X,Y) :- X = Y,  I, fail.       muz(X) :- zena(X),  I, fail. different(_X,_Y). muz(_X).
& Unární operátor \+ P
& jestliže P uspeje, potom \+ P neuspeje \+(P) :- P,  I, fail.
it v opaCném p rípade \+ P uspeje \+(_).
C different( X, Y ) :- \+ X=Y. & muz( X ) :- \+ zena( X ).
& Pozor: takto definovaná negace \+P vyžaduje koneCné odvození P
Hana Rudová, Logické programování I, 28. února 2011
10
Rez, negace
Negace a přomenné
\+(P) :- P,  I, fail. % (I)
\+(_). % (II)
dobre( citroen ). % (1)
dobre( bmw ). % (2)
drahe( bmw ). % (3)
rozumne( Auto ) :- % (4)
\+ drahe( Auto ).
Hana Rudová, Logické programování I, 28. února 2011
11
Rez, negace
Negace a přomenné
\+(P) :- P,  I, fail. % (I)
\+(_). % (II)
dobre( citroen ). % (1)
dobre( bmw ). % (2)
drahe( bmw ). % (3)
rozumne( Auto ) :- % (4)
\+ drahe( Auto ). ?- dobre( X ), rozumne( X ).
Hana Rudová, Logické programování I, 28. února 2011
Rez, negace
Negace a přomenné
\+(p) :- p, Ij fail. % (I) dobre(X),rozumne(X)
\ +(_) % (II)
dobre( citroen ) % (1)
dobre( bmw ) % (2)
drahe( bmw ) % (3)
rozumne( Auto ) :- % (4)
\ + drahe( Auto ) ?- dobre( X ), rozumne( X ).
Hana Rudová, Logické programování I, 28. února 2011
11
Rez, negace
Negace a proměnné
\+(P) :- P,  I, fail. % (I)
\+(_). % (II)
dobre( citroen ). % (1)
dobre( bmw ). % (2)
drahe( bmw ). % (3)
rozumne( Auto ) :- % (4)
\+ drahe( Auto ). ?- dobre( X ), rozumne( X ).
dobre(X),rozumne(X)
dle (1), X/citroen rozumne(citroen)
Hana Rudová, Logické programování I, 28. února 2011
Rez, negace
Negace a přomenné
\+(P) :- P,  I, fail. % (I)
\+(_). % (II)
dobre( citroen ). % (1)
dobre( bmw ). % (2)
drahe( bmw ). % (3)
rozumne( Auto ) :- % (4)
\+ drahe( Auto ). ?- dobre( X ), rozumne( X ).
dobre(X),rozumne(X)
dle (1), X/citroen rozumne(citroen)
dle (4) \+ drahe(citroen)
Hana Rudová, Logické programování I, 28. února 2011
Rez, negace
Negace a přomenné
\+(P) :- P,  I, fail. % (I)
\+(_). % (II)
dobre( citroen ). % (1)
dobre( bmw ). % (2)
drahe( bmw ). % (3)
rozumne( Auto ) :- % (4)
\+ drahe( Auto ). ?- dobre( X ), rozumne( X ).
dobre(X),rozumne(X)
dle (1), X/citroen rozumne(citroen)
dle (4) \+ drahe(citroen)
dle (I) drahe(citroen),!, fail
Hana Rudová, Logické programování I, 28. února 2011
11
Rez, negace
Negace a promenné
\+(P) :- P,  I, fail. % (I)
\+(_). % (II)
dobre( citroen ). % (1)
dobre( bmw ). % (2)
drahe( bmw ). % (3)
rozumne( Auto ) :- % (4)
\+ drahe( Auto ). ?- dobre( X ), rozumne( X ).
dobre(X),rozumne(X)
dle (1), X/citroen rozumne(citroen)
dle (4) \+ drahe(citroen)
dle (I) drahe(citroen),!, fail
Hana Rudová, Logické programování I, 28. února 2011
no
Rez, negace
Negace a proměnné
\+(P) :- P, I, fail. % (I) \+(_). % (II)
dobre( citroen ). dobre( bmw ).
drahe( bmw ).
rozumne( Auto ) :-\+ drahe( Auto ).
% (1)
% (2)
% (3)
% (4)
?- dobre( X ), rozumne( X ).
dobre(X),rozumne(X)
dle (1), X/citroen
rozumne(citroen)
dle (4)
\+ drahe(citroen)
dle (I)
drahe(citroen),!, fail
dle (II)
yes
Hana Rudová, Logické programování I, 28. února 2011
11
no
Rez, negace
Negace a promenné
\+(P) :- P,  I, fail. % (I)
\+(_). % (II)
dobre( citroen ). % (1)
dobre( bmw ). % (2)
drahe( bmw ). % (3)
rozumne( Auto ) :- % (4)
\+ drahe( Auto ).
Hana Rudová, Logické programování I, 28. února 2011
12
Rez, negace
Negace a přomenné
\+(P) :- P,  I, fail. % (I)
\+(_). % (II)
dobre( citroen ). % (1)
dobre( bmw ). % (2)
drahe( bmw ). % (3)
rozumne( Auto ) :- % (4)
\+ drahe( Auto ). ?- rozumne( X ), dobre( X ).
Hana Rudová, Logické programování I, 28. února 2011
12
Rez, negace
Negace a přomenné
rozumne(X), dobre(X)
\+(P) :- P,  I, fail. % (I)
\+(_). % (II)
dobre( citroen ). % (1)
dobre( bmw ). % (2)
drahe( bmw ). % (3)
rozumne( Auto ) :- % (4)
\+ drahe( Auto ). ?- rozumne( X ), dobre( X ).
Hana Rudová, Logické programování I, 28. února 2011
12
Rez, negace
Negace
\+(P) :- P,  I, fail. % (I)
\+(_). % (II)
dobre( citroen ). % (1)
dobre( bmw ). % (2)
drahe( bmw ). % (3)
rozumne( Auto ) :- % (4)
\+ drahe( Auto ). ?- rozumne( X ), dobre( X ).
promenné
rozumne(X), dobre(X)
dle (4) \+ drahe(X), dobre(X)
Hana Rudová, Logické programování I, 28. února 2011
12
Rez, negace
\+(P) :- P, I, fail. % (I) \+(_). % (II)
dobre( citroen ). dobre( bmw ).
Negace a promenné
rozumne(X), dobre(X)
drahe( bmw ).
rozumne( Auto ) :-\+ drahe( Auto ).
% (1)
% (2)
% (3)
% (4)
dle (4)
\+ drahe(X), dobre(X)
dle (I)
drahe(X),!,fail,dobre(X)
?- rozumne( X ), dobre( X ).
Hana Rudová, Logické programování I, 28. února 2011
12
Rez, negace
Negace a
\+(P) :- P,  I, fail. % (I)
\ +(_) % (II)
dobre( citroen ). % (1)
dobre( bmw ) % (2)
drahe( bmw ) % (3)
rozumne( Auto ) :- % (4)
\ + drahe( Auto ) ?- rozumne( X ), dobre( X ).
přomenné
rozumne(X), dobre(X)
dle (4) \+ drahe(X), dobre(X)
dle (I)
drahe(X),!,fail,dobre(X)
dle (3), X/bmw !, fail, dobre(bmw)
Hana Rudová, Logické programování I, 28. února 2011
12
Rez, negace
Negace a
\+(P) :- P,  I, fail. % (I)
\+(_). % (II)
dobre( citroen ). % (1)
dobre( bmw ). % (2)
drahe( bmw ). % (3)
rozumne( Auto ) :- % (4)
\+ drahe( Auto ). ?- rozumne( X ), dobre( X ).
Hana Rudová, Logické programování I, 28. února 2011
promenné
rozumne(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)
2 Rez, negace
Negace a
\+(P)       P,  !, fail. % (I)
\+(_). % (II)
dobre( citroen ). % (1)
dobre( bmw ). % (2)
drahe( bmw ). % (3)
rozumne( Auto ) % (4)
\+ drahe( Auto ). ?- rozumne( X ), dobre( X ).
Hana  udová, Logické programování I, 28. února 2011
promenne
rozumne(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
2 Řez, negace
Bezpečný cíl
C ?- rozumne( citroen ). yes
?- rozumne( X ). no
JS> ?- \+ drahe( citroen ). yes
?- \+ drahe( X ). no JS> \+ P je bezpečný: proměnné P jsou 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, 28. února 2011
13
Řez, negace
Chování negace
-í* ?- \+ drahe( citroen ). yes ?- \+ drahe( X ). no
& Negace jako neúspěch používá předpoklad uzavřeného sveta
pravdivé je pouze to, co je dokazatelné
?- \+ 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 )
Hana Rudová, Logické programování I, 28. února 2011
14
Řez, negace
Chování negace
-í* ?- \+ drahe( citroen ). yes ?- \+ drahe( X ). no
& Negace jako neúspech používá předpoklad uzavřeného sveta
pravdivé je pouze to, co je dokazatelné
?- \+ drahe( X ). \+ drahe(X) :-drahe(X),!,fail.      \+ drahe(X).
z definice \+ plyne: není dokazatelné, že existuje X takové, že drahe( X ) platí tj. přo všechna X platí \+ drahe( X )
M ?- drahe( X ).
VÍME: existuje X takové, že drahe( X ) platí
JS> ALE: pro cíle s negací neplatí existuje X takové, že \+ drahe( X )
Hana Rudová, Logické programování I, 28. února 2011
14
Rez, negace
Chování negace
-í* ?- \+ drahe( citroen ). yes ?- \+ drahe( X ). no
& Negace jako neúspech používá predpoklad uzavřeného sveta
pravdivé je pouze to, co je dokazatelné
?- \+ 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 )
M ?- drahe( X ).
VÍME: existuje X takové, že drahe( X ) platí
JS> ALE: pro cíle s negací neplatí existuje X takové, že \+ drahe( X )
=> negace jako neúspech není ekvivalentní negaci v matematické logice
Hana Rudová, Logické programování I, 28. února 2011
14
Rez, negace
Predikáty na r ízení behu programu I.
rez „!"
fail: cíl, který vždy neuspeje      true: cíl, který vždy uspeje \+ P: negace jako neúspech
\+ P :- P,  I, fail; true.
Hana Rudová, Logické programování I, 28. února 2011
15
Rez, negace
Predikáty na řízení běhu programu I.
řez „!"
fail: cíl, který vždy neuspěje      true: cíl, který vždy uspeje \+ P: negace jako neúspech
\+ P :- P,  1, fail; true.
once(P): vrátí pouze jedno rešení cíle P once(P) :- P, 1.
Hana Rudová, Logické programování I, 28. února 2011
15
Rez, negace
Předikáty na ř ízení behu přogřamu I.
řez „!"
fail: cíl, který vždy neuspeje      true: cíl, který vždy uspeje \+ P: negace jako neúspech
\+ P :- P,  I, fail; true.
once(P): vrátí pouze jedno rešení cíle P once(P) :- P, I.
Vyjád rení podmínky: P -> Q ; R
J* jestliže platí P tak Q        (P -> Q ; R) :- P,  I, Q. v opacném p r ípade R      (P -> Q ; R) :- R. príklad: min(X,Y,Z) :- X =< Y -> Z = X ; Z = Y.
Hana Rudová, Logické programování I, 28. února 2011
15
Rez, negace
Predikáty na rízení behu programu I.
rez „!"
fail: cíl, který vždy neuspeje      true: cíl, který vždy uspeje \+ P: negace jako neúspech
\+ P :- P,  I, fail; true.
once(P): vrátí pouze jedno řešení cíle P once(P) :- P, I.
Vyjádrení podmínky: P -> Q ; R
J* jestliže platí P tak Q        (P -> Q ; R) :- P,  I, Q. v opacném prípade R      (P -> Q ; R) :- R. príklad: min(X,Y,Z) :- X =< Y -> Z = X ; Z = Y.
P -> Q
Hana Rudová, Logické programování I, 28. února 2011
15
Rez, negace
Predikáty na řízení běhu programu I.
M řez „!"
& fail: cíl, který vždy neuspeje      true: cíl, který vždy uspeje JS> \+ P: negace jako neúspech
\+ P :- P,  1, fail; true.
& once(P): vrátí pouze jedno rešení cíle P once(P) :- P, 1.
& Vyjádření podmínky: P -> Q ; R
J* jestliže platí P tak Q        (P -> Q ; R) :- P,  1, Q. v opacném prípade R      (P -> Q ; R) :- R. príklad: min(X,Y,Z) :- X =< Y -> Z = X ; Z = Y.
M P -> Q
-i- odpovídá: (P -> Q; fail)
-fc príklad: zaporne(X) :- number(X) -> X < 0.
Hana Rudová, Logické programování I, 28. února 2011 15 Rez, negace
Predikáty na r ízení behu programu II.
call(P): zavolá cíl P a uspeje, pokud uspeje P nekoneCná posloupnost backtrackovacích voleb: repeat repeat.
repeat :- repeat.
Hana Rudová, Logické programování I, 28. února 2011
16
Rez, negace
Predikáty na r ízení behu programu II.
call(P): zavolá cíl P a uspeje, pokud uspeje P nekonecná posloupnost backtrackovacích voleb: repeat repeat.
repeat :- repeat.
klasické použití: generuj akci X, proved'ji a otestuj, zda neskončit Hlava :- ...
uloz_stav( StaryStav ),
repeat,
generuj( X ), % deterministické: generuj, provadej, testuj
provadej( X ), testuj( X ),
I
■ >
obnov_stav( StaryStav ),
Hana Rudová, Logické programování I, 28. února 2011
16
Rez, negace
Seznamy
Reprezentace seznamu
-i* Seznam: [a, b, c], prázdný seznam []
& Hlava (libovolný objekt), telo (seznam): .(Hlava, Telo)
a všechny strukturované objekty stromy - i seznamy ± funktordva argumenty
.(a,  .(b,  .(c, []))) = [a, b, c] i> notace: [ Hlava | Telo ] = [ajTelo]
Hana Rudová, Logické programování I, 28. února 2011
18
Seznamy
Reprezentace seznamu
-i* Seznam: [a, b, c], prázdný seznam []
& Hlava (libovolný objekt), telo (seznam): .(Hlava, Telo)
a všechny strukturované objekty stromy - i seznamy ± funktordva argumenty
.(a,  .(b,  .(c, []))) = [a, b, c] i> notace: [ Hlava | Telo ] = [a|Te1o]
Telo je v [a|Te1o] seznam, tedy píšeme [ a, b, c ] = [ a | [ b, c ] ]
Hana Rudová, Logické programování I, 28. února 2011
18
Seznamy
Reprezentace seznamu
-i* Seznam: [a, b, c], prázdný seznam []
& Hlava (libovolný objekt), telo (seznam): .(Hlava, Telo)
a všechny strukturované objekty stromy - i seznamy ± funktordva argumenty
.(a,  .(b,  .(c, []))) = [a, b, c] i> notace: [ Hlava | Telo ] = [a|Te1o]
Telo je v [a|Te1o] seznam, tedy píšeme [ a, b, c ] = [ a | [ b, c ] ]
& Lze psát i: [a,b|Te1o]
pred "|"je libovolný pocet prvků seznamu , za "|"je seznam zbývajících prvků [a,b,c] = [a|[b,c]] = [a,b|[c]] = [a,b,c|[]]
Hana Rudová, Logické programování I, 28. února 2011
18
Seznamy
Reprezentace seznamu
-i* Seznam: [a, b, c], prázdný seznam []
& Hlava (libovolný objekt), telo (seznam): .(Hlava, Telo)
a všechny strukturované objekty stromy - i seznamy ± funktordva argumenty
.(a,  .(b,  .(c, []))) = [a, b, c] i> notace: [ Hlava | Telo ] = [a|Te1o]
Telo je v [a|Te1o] seznam, tedy píšeme [ a, b, c ] = [ a | [ b, c ] ]
& Lze psát i: [a,b|Te1o]
pred "|"je libovolný pocet 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] ] = [ a,b |  [c] ]
Hana Rudová, Logické programování I, 28. února 2011
18
Seznamy
Reprezentace seznamu
-i* Seznam: [a, b, c], prázdný seznam []
& Hlava (libovolný objekt), telo (seznam): .(Hlava, Telo)
a všechny strukturované objekty stromy - i seznamy ± funktordva argumenty
.(a,  .(b,  .(c, []))) = [a, b, c] i> notace: [ Hlava | Telo ] = [a|Te1o]
Telo je v [a|Te1o] seznam, tedy píšeme [ a, b, c ] = [ a | [ b, c ] ]
& Lze psát i: [a,b|Te1o]
pred "|"je libovolný pocet 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] ] = [ a,b |  [c] ]
& Seznam jako neúplná datová struktura: [a,b,c|T]
a Seznam = [a,b,c|T], T = [d,e|S], Seznam = [a,b,c,d,e|S]
Hana Rudová, Logické programování I, 28. února 2011 18 Seznamy
Přvek seznamu
-í* member( X, S )
C platí: member( b,  [a,b,c] ).
& neplatí: member( b,  [[a,b]|[c]] ).
JS> X je prvek seznamu S, když
& X je hlava seznamu S nebo
member( X,  [ X | _ ] ).
a X je prvek tela seznamu S
member( X,  [ _ | Telo ] ) :-
member( X, Telo ). %(2)
Hana Rudová, Logické programování I, 28. února 2011
19
Seznamy
Prvek seznamu
member(1,[2,1,3,1,4])
-í* member( X, S )
C platí: member( b,  [a,b,c] ).
& neplatí: member( b,  [[a,b]|[c]] ).
JS> X je prvek seznamu S, když
& X je hlava seznamu S nebo
member( X,  [ X | _ ] ).
a X je prvek tela seznamu S
member( X,  [ _ | Telo ] ) :-
member( X, Telo ). %(2)
Hana Rudová, Logické programování I, 28. února 2011
19
Seznamy
Prvek seznamu
member(1,[2,1,3,1,4])
-í* member( X, S )
dle (2)
C platí: member( b,  [a,b,c] ).
-í* neplatí: member( b, [[a,b]|[c]] ). JS> X je prvek seznamu S, když
& X je hlava seznamu S nebo member( X,  [ X | _ ] ).
a X je prvek tela seznamu S
member( X,  [ _    Telo ] ) :-
member(1,[1,3,1,4])
member( X, Telo
%(2)
Hana Rudová, Logické programování I, 28. února 2011
19
Seznamy
Prvek seznamu
member( X, S )
platí: member( b,  [a,b,c] ). neplatí: member( b,  [[a,b]|[c]] ). X je prvek seznamu S, když
& X je hlava seznamu S nebo
member( X,  [ X | _ ] ).
a X je prvek tela seznamu S
member( X,  [ _ | Telo ] ) :-
member( X, Telo ). %(2)
dle (1)
4
□
yes
member(1,[2,1,3,1,4])
dle (2)
member(1,[1,3,1,4])
dle (2)
member(1,[3,1,4])
Hana Rudová, Logické programování I, 28. února 2011
19
Seznamy
Přvek seznamu
member( X, S )
platí: member( b,  [a,b,c] ). neplatí: member( b,  [[a,b]|[c]] ). X je prvek seznamu S, když
& X je hlava seznamu S nebo
member( X,  [ X | _ ] ).
a X je prvek tela seznamu S
member( X,  [ _ | Telo ] ) :-
member( X, Telo ). %(2)
dle (1)
4
□
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])
Hana Rudová, Logické programování I, 28. února 2011
19
Seznamy
Přvek seznamu
member( X, S )
platí: member( b,  [a,b,c] ). neplatí: member( b,  [[a,b]|[c]] ). X je prvek seznamu S, když
& X je hlava seznamu S nebo
member( X,  [ X | _ ] ).
a X je prvek tela seznamu S
member( X,  [ _ | Telo ] ) :-
member( X, Telo ). %(2)
dle (1)
4
□
yes
dle (1)
4
□
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])
Hana Rudová, Logické programování I, 28. února 2011
19
Seznamy
Prvek seznamu
member( X, S )
platí: member( b,  [a,b,c] ). neplatí: member( b,  [[a,b]|[c]] ). X je prvek seznamu S, když
& X je hlava seznamu S nebo
member( X,  [ X | _ ] ).
a X je prvek tela seznamu S
member( X,  [ _ | Telo ] ) :-
member( X, Telo ). %(2)
dle (1)
4
□
yes
dle (1)
4
□
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,[ ])
Hana Rudová, Logické programování I, 28. února 2011
19
Seznamy
Prvek seznamu
member( X, S )
platí: member( b,  [a,b,c] ). neplatí: member( b,  [[a,b]|[c]] ). X je prvek seznamu S, když
& X je hlava seznamu S nebo
member( X,  [ X | _ ] ).
a X je prvek tela seznamu S
member( X,  [ _ | Telo ] ) :-
member( X, Telo ). %(2)
dle (1)
4
□
yes
dle (1)
4
□
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)
Hana Rudová, Logické programování I, 28. února 2011
19
no
Seznamy
Prvek seznamu
member( X, S )
platí: member( b,  [a,b,c] ). neplatí: member( b,  [[a,b]|[c]] ). X je prvek seznamu S, když
& X je hlava seznamu S nebo
member( X,  [ X | _ ] ).
a X je prvek tela seznamu S
member( X,  [ _ | Telo ] ) :-
member( X, Telo ). %(2)
Další príklady použití:
± member(X,[1,2,3]). J* member(1,[2,1,3,1]).
dle (1)
4
□
yes
dle (1)
4
□
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)
Hana Rudová, Logické programování I, 28. února 2011
19
no
Seznamy
Spojení seznamů
C append( L1, L2, L3 )
& Platí: append( [a,b],  [c,d],  [a,b,c,d] )
JS> Neplatí: append( [b,a],  [c,d],  [a,b,c,d] ), append( [a,[b]],  [c,d],  [a,b,c,d] )
Hana Rudová, Logické programování I, 28. února 2011
20
Seznamy
Spojení seznamů
C append( li, l2, l3 )
& Platí: append( [a,b],  [c,d],  [a,b,c,d] )
JS> Neplatí: append( [b,a],  [c,d],  [a,b,c,d] ), append( [a,[b]],  [c,d],  [a,b,c,d] )
-í* Definice:
-i- pokud je 1. argument prázdný seznam, pak 2. a 3. argument jsou stejné seznamy: append( [], S, S ).
Hana Rudová, Logické programování I, 28. února 2011
20
Seznamy
Spojení seznamů
append( L1, 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:
-i- pokud je 1. argument prázdný seznam, pak 2. a 3. argument jsou stejné seznamy: append( [], S, S ).
J* 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, 28. února 2011
20
Seznamy
Příklady použití append
append( [], S, S ).
append( [X|S1], S2,  [X|S3] ) :- append( S1, S2, S3).
Spojení seznamů: append( [a,b,c],  [1,2,3], S ). S = [a,b,c,1,2,3]
append( [a,  [b,c], d],  [a,  [], b], S ). S = [a,  [b,c], d, a,  [], b] ]
Hana Rudová, Logické programování I, 28. února 2011
21
Seznamy
P ř íklady použití append
append( [], S, S ).
append( [X|S1], S2,  [X|S3] ) :- append( S1, S2, S3).
& Spojení seznamů: append( [a,b,c],  [1,2,3], S ). S = [a,b,c,1,2,3]
append( [a,  [b,c], d],  [a,  [], b], S ). S = [a,  [b,c], d, a,  [], b] ]
& Dekompozice seznamu na dva seznamy: append( S1, S2,  [a, b ]).
S1 = [], S2 = [a,b] ; S1 = [a], S2 = [b] ? ; S1 = [a,b], S2 = []
Hana Rudová, Logické programování I, 28. února 2011
21
Seznamy
Příklady použití append
append( [], S, S ).
append( [X|S1], S2,  [X|S3] ) :- append( S1, S2, S3).
& Spojení seznamů: append( [a,b,c],  [1,2,3], S ). S = [a,b,c,1,2,3]
append( [a,  [b,c], d],  [a,  [], b], S ). S = [a,  [b,c], d, a,  [], b] ]
& Dekompozice seznamu na dva seznamy: append( S1, S2,  [a, b ]).
S1 = [], S2 = [a,b] ; S1 = [a], S2 = [b] ? ; S1 = [a,b], S2 = []
& Vyhledávání v seznamu: append( Před,  [ c | Za ],  [a,b,c,d,e] ). Pred = [a,b], Za = [d,e]
Hana Rudová, Logické programování I, 28. února 2011
21
Seznamy
Príklady použití append
append( [], S, S ).
append( [X|S1], S2,  [X|S3] ) :- append( S1, S2, S3).
& Spojení seznamů: append( [a,b,c],  [1,2,3], S ). S = [a,b,c,1,2,3]
append( [a,  [b,c], d],  [a,  [], b], S ). S = [a,  [b,c], d, a,  [], b] ]
& Dekompozice seznamu na dva seznamy: append( S1, S2,  [a, b ]).
S1 = [], S2 = [a,b] ; S1 = [a], S2 = [b] ? ; S1 = [a,b], S2 = []
& Vyhledávání v seznamu: append( Pred,  [c | Za ],  [a,b,c,d,e] ). Pred = [a,b], Za = [d,e]
-í* Predchůdce a následník: append( _,  [Pred,c,Za|_],  [a,b,c,d,e] ). Pred = b, Za = d
Hana Rudová, Logické programování I, 28. února 2011 21 Seznamy
Smazání prvku seznamu de1ete( X, S, S1 )
& Seznam S1 odpovídá seznamu S, ve kterém je smazán prvek X
a jestliže X je hlava seznamu S, pak výsledkem je telo S de1ete( X,  [X|Te1o], Telo).
& jestliže X je v tele seznamu, pak X je smazán až v tele
de1ete( X,  [Y|Te1o],  [Y|Te1o1] ) :- de1ete( X, Telo, Te1o1 ).
Hana Rudová, Logické programování I, 28. února 2011
22
Seznamy
Smazání prvku seznamu delete( X, S, Si )
& Seznam Si odpovídá seznamu S, ve kterém je smazán prvek X
a jestliže X je hlava seznamu S, pak výsledkem je telo S delete( X,  [X|Telo], Telo).
& jestliže X je v tele seznamu, pak X je smazán až v tele
delete( X,  [Y|Telo],  [Y|Telo1] ) :- delete( X, Telo, Teloi ).
-í* delete smaže libovolný výskyt prvku pomocí backtrackingu ?- delete(a,  [a,b,a,a], S). S = [b,a,a]; S = [a,b,a]; S = [a,b,a]
Hana Rudová, Logické programování I, 28. února 2011
22
Seznamy
Smazání prvku seznamu delete( X, S, S1 )
& Seznam S1 odpovídá seznamu S, ve kterém je smazán prvek X
a jestliže X je hlava seznamu S, pak výsledkem je telo S delete( X,  [X|Telo], Telo).
& jestliže X je v tele seznamu, pak X je smazán až v tele
delete( X,  [Y|Telo],  [Y|Telo1] ) :- delete( X, Telo, Telol ).
& delete smaže libovolný výskyt prvku pomocí backtrackingu ?- delete(a,  [a,b,a,a], S). S = [b,a,a]; S = [a,b,a]; S = [a,b,a]
delete, který smaže pouze první výskyt prvku X
^   delete( X,  [X|Telo], Telo) :- I.
delete( X,  [Y|Telo],  [Y|Telo1] ) :- delete( X, Telo, Telo1).
Hana Rudová, Logické programování I, 28. února 2011 22 Seznamy