Ř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, 5. března 2013
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 řezem se už další klauzule neuvažují
Hana Rudová, Logické programování I, 5. března 2013 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 řezem se už další klauzule neuvažují
Hana Rudová, Logické programování I, 5. března 2013 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ílů pred rezem se už další klauzule neuvažují
Hana Rudová, Logické programování I, 5. března 2013 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, 5. března 2013
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, 5. března 2013
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ílU
Hana Rudová, Logické programování I, 5. března 2013
Ř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, 5. března 2013
3
Rez, negace
Chování opeřátořu řezu
Předpoklá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 momentě, kdy je nalezen řez, existuje řešení cílů TI, ..., Tm
X=1,Y=1
Ořezání: při provádení řezu se už další možné splnení cílu 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, 5. b rezna 2013
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),  !, 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).
Hana Rudová, Logické programování I, 5. bŘrezna 2013
5
RŘez, negace
Řez: návrat na rodice
?- a(X).
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).
Hana Rudová, Logické programování I, 5. b rezna 2013
5
Rez, negace
Řez: návrat na rodice
?- a(X).
a(x)
(1) a(X) :- h(X,Y).
(2) a(X) :- d. h(X,Y)
(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).
Hana Rudová, Logické programování I, 5. b rezna 2013
5
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),  !, 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).
Hana Rudová, Logické programování I, 5. března 2013 5 Řez, negace
a(x)
h(X,Y)
X/1 t1(Y),!,e'(X')
Řez: návrat na rodice
?- a(X).
(1) a(X) h(X,Y).
(2) a(X) d.
(3) h(1,Y)       t1(Y),  !, 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).
a(x)
h(X,Y)
X/1 t1(Y),!,e'(X')
Y/1 b,!,e(X')
Hana Rudová, Logické programování I, 5. b rezna 2013
5
Rez, negace
Řez: návrat na rodice
?- a(X).
(1) a(X) h(X,Y).
(2) a(X) d.
(3) h(1,Y)       t1(Y),  !, 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).
a(x)
h(X,Y)
X/1 t1(Y),!,e'(X')
Y/1 b,!,e(X')
c,!,e(X')
Hana Rudová, Logické programování I, 5. bŘrezna 2013
5
RŘez, 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),
(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).
a(x)
h(X,Y)
X/1
I, e(X). t1(Y),!,e'(X')
Y/1
b,!,e(X') c,!,e(X')
no
Hana Rudová, Logické programování I, 5. b rezna 2013
5
Rez, negace
Rez: 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.
no
(8) b :- d.
(9) d.
(10) e(1) .
(11) e(2).
Hana Rudová, Logické programování I, 5. brezna 2013 5 Rez, negace
a(x)
h(X,Y)
X/1
t1(Y),!,e'(X') Y/1 / b,!,e(X')
c,!,e(X') d,!,e(X')
Řez: návrat na rodice
?- a(X).
(1) a(X) h(X,Y).
(2) a(X) d.
(3) h(1,Y)       t1(Y),  !, 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).
a(x)
h(X,Y)
X/1
t1(Y),!,e'(X') Y/1 /
b,!,e(X') c,!,e(X') d,!,e(X')
no
!,e(X')
Hana Rudová, Logické programování I, 5. b rezna 2013
5
Rez, negace
Rez: návrat na rodice
?- 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).
a(x)
h(X,Y)
X/1
t1(Y),!,e'(X') Y/1 /
b,!,e(X') c,!,e(X') d,!,e(X')
no
!,e(X')
e(X')
Hana Rudová, Logické programování I, 5. března 2013
5
Řez, negace
Řez: návrat na rodice
?- 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).
a(x)
h(X,Y)
X/1
t1(Y),!,e'(X') Y/1 / b,!,e(X')
c,!,e(X') d,!,e(X')
no
!,e(X')
e(X')
X'/1 □
Hana Rudová, Logické programování I, 5. b rezna 2013
5
Rez, negace
Rez: 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).
a(x)
h(X,Y)
X/1
t1(Y),!,e'(X') Y/1 /
b,!,e(X') c,!,e(X') d,!,e(X')
no
!,e(X')
e(X') X'/l y \ X'/2
Hana Rudová, Logické programování I, 5. b rezna 2013
5
Rez, negace
Rez: návřat na řodice
?- a(X).
(1) a(X) :- h(X,Y).
(2) a(X) :- d.
(3) h(1,Y)  :- t1(Y),  !, 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).
a(x)
híX/Y) X/1y \^
t1(Y),!,e(X') upnutí
Y/1 / \ b,!,e(X') ořezání
c,!,e(X') d,!,e(X')
no
!,e(X')
e(X') X'/l y \ X'/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, 5. b rezna 2013
5
Rez, negace
Řez: návrat na rodice
?- a(X).
(1) a(X) h(X,Y).
(2) a(X) d.
(3) h(1,Y)       t1(Y),  !, 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).
a(x)
h(X,Y)
x/iX \
t1(Y),!,e(Xl) upnutí
Y/1 / \ b,!,e(X') ořezání
c,!,e(X') d,!,e(X')
no
!,e(X')
e(X') X'/l y \ X'/2
d
Po zpracování klauzule s řezem se vracím až na rodiCe této klauzule, tj. a(X)
Hana Rudová, Logické programování I, 5. b rezna 2013
5
Rez, negace
Řez: návrat na rodice
?- 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).
a(x)
h(X/Y) X/1y \^
t1(Y),!,e(Xl) upnutí
Y/1 / \ b,!,e(X') ořezání
c,!,e(X') d,!,e(X')
no
!,e(X')
e(X') X'/l y \ X'/2
d
Po zpracování klauzule s řezem se vracím až na rodiCe této klauzule, tj. a(X)
Hana Rudová, Logické programování I, 5. b rezna 2013
5
Rez, negace
Rez: příklad
c(X) :- p(X). c(X) :- v(X).
p(1).   p(2). v(2).
?- c(2).
Hana Rudová, Logické programování I, 5. b rezna 2013
6
Rez, negace
c(X) :- p(X). cCX) :- v(X).
Řez: príklad
p(1). p(2).
v(2).
?- c(2).
true ? ; %p(2)
true ? ; %v(2)
no
?- c(X).
Hana Rudová, Logické programování I, 5. března 2013
Rez, negace
6
Rez: 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, 5. brezna 2013 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). ?- 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, 5. března 2013 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, 5. března 2013 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).
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, 5. března 2013
Rez, negace
6
Rez: 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),!. 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
2. Napište predikát pro výpocet maxima max( X, Y, Max )
Hana Rudová, Logické programování I, 5. bŘrezna 2013
7
RŘez, negace
Typy rezu
Zlepšení efektivity programu: urCíme, které alternativy nemá smysl zkoušet
Poznámka: na vstupu pro X oCekávám Císlo Zelený rez: odstraní pouze neúspešná odvození
f(X,1)       X >= 0,  !.    f(X,-1)       X < 0.
Hana Rudová, Logické programování I, 5. b rezna 2013
8
Rez, negace
Typy rezu
Zlepšení efektivity programu: urCíme, které alternativy nemá smysl zkoušet
Poznámka: na vstupu pro X oCekávám Císlo Zelený rez: 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, 5. b rezna 2013
8
Rez, negace
Typy rezu
Zlepšení efektivity programu: urCíme, které alternativy nemá smysl zkoušet
Poznámka: na vstupu pro X oCekávám Císlo Zelený rez: odstraní pouze neúspešná odvození
f(X,1)       X >= 0,  !.    f(X,-1)       X < 0.
bez rezu zkouším pro nezáporná Císla 2. klauzuli
Modrý rez: odstraní redundantní rešení
f(X,1)       X >= 0,  !.    f(0,1). f(X,-1)       X < 0.
Hana Rudová, LogiCké programování I, 5. brezna 2013
8
Rez, negaCe
Typy řezu
Zlepšení efektivity programu: urame, které alternativy nemá smysl zkoušet
Poznámka: na vstupu pro X ocekávám císlo 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. bez rezu vrací f(0,1) 2x
Hana Rudová, Logické programování I, 5. b rezna 2013
8
Rez, negace
Typy rezu
Zlepšení efektivity programu: urcíme, které alternativy nemá smysl zkoušet
Poznámka: na vstupu pro X ocekávám císlo Zelený rez: odstraní pouze neúspešná odvození
f(X,1)       X >= 0,  !.    f(X,-1)       X < 0.
bez rezu zkouším pro nezáporná císla 2. klauzuli
Modrý rez: odstraní redundantní r ešení
f(X,1)      X >= 0,  !.    f(0,1). f(X,-1)      X < 0. bez rezu vrací f(0,1) 2x
Červený rez: odstraní úspešná rešení
f(X,1)       X >= 0,   !. f(_X,-1).
Hana Rudová, Logické programování I, 5. b rezna 2013
8
Rez, negace
Typy rezu
Zlepšení efektivity programu: urCíme, které alternativy nemá smysl zkoušet
Poznámka: na vstupu pro X oCekávám Císlo Zelený rez: 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
Modrý rez: odstraní redundantní r ešení
f(X,1) :- X >= 0,  I.    f(0,1). f(X,-1) :- X < 0. bez rezu vrad f(0,1) 2x
Červený rez: odstraní úspešná rešení
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, 5. b rezna 2013
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, 5. března 2013
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 p rípade \+ P uspeje \+(_).
Hana Rudová, Logické programování I, 5. b rezna 2013
10
Rez, negace
Negace jako neúspech: opeřátoř \+
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 prí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, 5. b rezna 2013
10
Rez, negace
Negace a přomenné
\+(P)  :- P,  !, fail. % (I)
\+(_). % (II)
dobre( citroen ). % (1)
dobre( bmw ). % (2)
drahe( bmw ). % (3)
rozumne( Auto ) :- % (4)
\+ drahe( Auto ).
Hana Rudová, Logické programování I, 5. bŘrezna 2013
RŘez, negace
Negace a promenné
\+(P)       P,  !, 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, 5. b rezna 2013
Rez, negaCe
Negace a promenne
\+(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, 5. b rezna 2013
ii
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, 5. b rezna 2013
11
Rez, negace
Negace a přomenné
\+(P)  :- P,  !, 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, 5. b rezna 2013
11
Rez, negace
Negace a přomenné
\+(P)  :- P,  !, 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, 5. bŘrezna 2013
11
RŘez, 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, 5. b rezna 2013
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, 5. b rezna 2013
11
no
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 ).
Hana Rudová, Logické programování I, 5. b rezna 2013
12
Rez, negace
Negace a promenne
\+(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, 5. b rezna 2013
12
Rez, negace
Negace a promenné
rozumne(X), dobre(X)
\+(P)  :- P,  !, 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, 5. brezna 2013
12
Řez, negace
Negace
\+(P)  :- P,  !, 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)
Hana Rudová, Logické programování I, 5. b rezna 2013
12
Rez, negace
\+(P) :- P, I, fail. % (I) \+(_). % (II)
dobre( citroen ). dobre( bmw ).
Negace a promenne
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, 5. b rezna 2013
12
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 ).
promRenné
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, 5. bŘrezna 2013
12
RŘez, negace
Negace
\+(P)  :- P,  !, 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, 5. b rezna 2013 12
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)
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 ).
Hana Rudová, Logické programování I, 5. brezna 2013 12
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)
fail,dobre(bmw) no
Rez, negace
Bezpečný cíl
C ?- \+ drahe( citroen ). yes
?- \+ drahe( X ). no
JS> ?- rozumne( citroen ). yes
?- rozumne( 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, 5. b rezna 2013
13
Řez, negace
Chování negace
-í* ?- \+ drahe( citroen ). yes
?- \+ drahe( X ). no
C ?- 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 )
Hana Rudová, LogiCké programování I, 5. b rezna 2013
14
Rez, negaCe
Chování negace
-í* ?- \+ drahe( citroen ). yes
?- \+ drahe( X ). no
C ?- 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 )
& TEDY: pro Cíle s negad neplatí existuje X takové, že \+ drahe( X )
Hana Rudová, LogiCké programování I, 5. b rezna 2013
14
Rez, negaCe
Chování negace
-í* ?- \+ drahe( citroen ). yes
?- \+ drahe( X ). no
C ?- 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 )
& TEDY: pro cíle s negací neplatí existuje X takové, že \+ drahe( X )
=> negace jako neúspech není ekvivalentní negaci v matematické logice
& Negace jako neúspech používá predpoklad uzavřeného sveta
pravdivé je pouze to, co je dokazatelné
Hana Rudová, Logické programování I, 5. b rezna2013 14 Řez, negace
Prediká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.
Hana Rudová, Logické programování I, 5. b rezna 2013
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 rešení cíle P once(P) :- P, I.
Hana Rudová, Logické programování I, 5. brezna 2013
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,  !, fail; true.
once(P): vrátí pouze jedno rešení cíle P once(P) :- P, !.
Vyjádrení podmínky: P -> Q ; R
J* jestliže platí P tak Q        (P -> Q ; R) :- P,  !, Q. v opacném prípade R      (P -> Q ; R) :- R. príklad: min(X,Y,Z) :- X =< Y -> Z = X ; Z = Y.
Hana Rudová, Logické programování I, 5. b rezna 2013
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 reš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, 5. b rezna 2013
15
Rez, negace
Predikáty na r ízení behu programu I.
M rez „!"
& fail: cíl, který vždy neuspeje      true: cíl, který vždy uspeje -í* \+ P: negace jako neúspech
\+ P :- P,  !, fail; true.
& once(P): vrátí pouze jedno rešení cíle P once(P) :- P, !.
& Vyjád rení podmínky: P -> Q ; R
J* jestliže platí P tak Q        (P -> Q ; R) :- P,  !, Q. v opacném p r í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)
S> príklad: zaporne(X) :- number(X) -> X < 0.
Hana Rudová, Logické programování I, 5. b rezna 2013 15 Rez, negace
Predikáty na ŕízení běhu programu II.
call(P): zavolá cíl P a uspeje, pokud uspeje P nekonečná posloupnost backtrackovacích voleb: repeat repeat.
repeat :- repeat.
Hana Rudová, Logické programování I, 5. b rezna 2013
16
Rez, negace
Predikáty na řízení běhu programu II.
call(P): zavolá cíl P a uspeje, pokud uspeje P nekonečná 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, 5. března 2013
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, 5. b rezna 2013
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, 5. b rezna 2013
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]
p r ed T'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, 5. b rezna 2013
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]
p r ed T'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, 5. b rezna 2013
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]
Jt Seznam = [a,b,c|T], T = [d,e|S], Seznam = [a,b,c,d,e|S]
Hana Rudová, Logické programování I, 5. brezna 2013 18 Seznamy
Prvek 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, 5. b rezna 2013
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, 5. b rezna 2013
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, 5. brezna 2013
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, 5. b rezna 2013
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])
dle (2)
member(1,[1,4])
Hana Rudová, Logické programování I, 5. b rezna 2013
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])
Hana Rudová, Logické programování I, 5. b rezna 2013
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, 5. brezna 2013
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, 5. b rezna 2013
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)
Príklady použití:
± member(1,[2,1,3]). J* member(X,[1,2,3]).
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, 5. března 2013
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, 5. brezna 2013
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, 5. b rezna 2013
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( S1, S2, S3).
X
S1
S2
S3
Hana Rudová, Logické programování I, 5. b rezna 2013
20
Seznamy
CviCení: append/2
append( [], S, S ).        % (1)
append( [X|S1], S2, [X|S3] ) :- append( S1, S2, S3). % (2) :- append([1,2],[3,4],A).
Hana Rudová, Logické programování I, 5. b rezna 2013
21
Seznamy
CviCení: append/2
append( [], S, S ).        % (1)
append( [X|S1], S2,  [X|S3] ) :- append( S1, S2, S3).     % (2)
:- append([1,2],[3,4],A). I (2) I A=[1|B]
Hana Rudová, Logické programování I, 5. b rezna 2013
21
Seznamy
CviCení: append/2
append( [], S, S ).        % (1)
append( [X|S1], S2,  [X|S3] ) :- append( S1, S2, S3).     % (2)
:- append([1,2],[3,4],A). | (2) | A=[1|B]
|
:- append([2],[3,4],B).
Hana Rudová, Logické programování I, 5. brezna 2013
21
Seznamy
CviCení: append/2
append( [], S, S ).        % (1)
append( [X|S1], S2,  [X|S3] ) :- append( S1, S2, S3).     % (2)
:- append([1,2],[3,4],A). I (2) I A=[1|B]
I
:- append([2],[3,4],B). I (2)
| B=[2|C]    => A=[1,2|C]
Hana Rudová, Logické programování I, 5. b rezna 2013
21
Seznamy
Cvičení: append/2
append( [], S, S ).        % (1)
append( [X|S1], S2,  [X|S3] ) :- append( S1, S2, S3).     % (2)
:- append([1,2],[3,4],A). | (2) | A=[1|B]
|
:- append([2],[3,4],B). | (2)
| B=[2|C]    => A=[1,2|C] |
:- append([],[3,4],C).
Hana Rudová, Logické programování I, 5. b rezna 2013
21
Seznamy
Cvicení: append/2
append( [], S, S ).        % (1)
append( [X|S1], S2,  [X|S3] ) :- append( S1, S2, S3).     % (2)
:- append([1,2],[3,4],A). | (2) | A=[1|B]
|
:- append([2],[3,4],B). | (2)
| B=[2|C]    => A=[1,2|C] |
:- append([],[3,4],C). | (1)
| C=[3,4]    => A=[1,2,3,4], |
yes
Hana Rudová, Logické programování I, 5. b rezna 2013 21 Seznamy