Operátory, aritmetika
Operátory
C Infixová notace: 2*a + b*c
& Prefixová notace: +( *(2,a), *(b,c) ) priorita +: 500, priorita *: 400
-i- prefixovou notaci lze získat predikátem display/1
:- display((a:-s(0),b,c)). :-(a,  ,Cs(0), ,(b,c)))
& Priorita operátorů: operátor s nejvyšší prioritou je hlavní funktor
Hana Rudová, Logické programování I, 1. března 2012
2
Operátory, aritmetika
Operátory
C Infixová notace: 2*a + b*c
& Prefixová notace: +( *(2,a), *(b,c) ) priorita +: 500, priorita *: 400
-i- prefixovou notaci lze získat predikátem display/1
:- display((a:-s(0),b,c)). :-(a,  ,Cs(0), ,(b,c)))
& Priorita operátorů: operátor s nejvyšší prioritou je hlavní funktor
C Uživatelsky definované operátory: zna
petr zna alese.      zna( petr, alese).
& Definice operátoru: :- op( 600, xfx, zna ). priorita: 1..1200
Hana Rudová, Logické programování I, 1. března 2012
2
Operátory, aritmetika
Operátory
C Infixová notace: 2*a + b*c
& Prefixová notace: +( *(2,a), *(b,c) ) priorita +: 500, priorita *: 400
-i- prefixovou notaci lze získat predikátem display/1
display((a:-s(0),b,c)). :-(a,  ,(s(0), ,(b,c)))
& Priorita operátorů: operátor s nejvyšší prioritou je hlavní funktor
C Uživatelsky definované operátory: zna
petr zna alese.      zna( petr, alese).
& Definice operátoru:      op( 600, xfx, zna ). priorita: 1..1200
A :- op( 1100, xfy, ; ). nestrukturované objekty: 0
:- op( 1000, xfy, , ).
p :- q,r; s,t. p :- (q,r) ; (s,t).      ; má vyšší prioritu než ,
:- op( 1200, xfx, :- ).       :- má nejvyšší prioritu
Hana Rudová, Logické programování I, 1. března 2012
2
Operátory, aritmetika
Operátory
C Infixová notace: 2*a + b*c
& Prefixová notace: +( *(2,a), *(b,c) ) priorita +: 500, priorita *: 400
-i- prefixovou notaci lze získat predikátem display/1
display((a:-s(0),b,c)). :-(a,  ,(s(0), ,(b,c)))
& Priorita operátorů: operátor s nejvyšší prioritou je hlavní funktor
C Uživatelsky definované operátory: zna
petr zna alese.      zna( petr, alese).
& Definice operátoru:      op( 600, xfx, zna ). priorita: 1..1200
A :- op( 1100, xfy, ; ). nestrukturované objekty: 0
:- op( 1000, xfy, , ).
p :- q,r; s,t. p :- (q,r) ; (s,t).      ; má vyšší prioritu než ,
:- op( 1200, xfx, :- ).       :- má nejvyšší prioritu
C Definice operátoru není spojena s datovými manipulacemi   (krome spec. prípadu)
Hana Rudová, Logické programování I, 1. března 2012 2 Operátory, aritmetika
Typy operátorů
Typy operátorů
pr.   xfx = yfx pr.   fx ?- fy
-i- infixové operátory: xfx, xfy, yfx A prefixové operátory: fx, fy A postfixové operátory: xf, yf
x a y ůrcůjí prioritu argumentu
x reprezentuje argument, jehož priorita můsí být striktne menší než ů operátorů y reprezentůje argůment, jehož priorita je menší nebo rovna operátorů a-b-c odpovídá (a-b)-c a ne a-(b-c): „-" odpovídá yfx
chybně
správně
priorita: 0 priorita: 0
priorita: 500
priorita: 500
Hana Rudová, Logické programování I, 1. března 2012
Operátory, aritmetika
3
Aritmetika
JS> Předdefinované operátory
+ , -i *i A ** mocnina, // celočíselné dělení, mod zbytek po delení
J* ?- X = 1 + 2. X = 1 + 2      = odpovídá unifikaci
M ?- X is 1 + 2.
X = 3      „is" je speciální preddefinovaný operátor, který vynutí evaluaci
Hana Rudová, Logické programování I, 1. března 2012
4
Operátory, aritmetika
Aritmetika
JS> Předdefinované operátory
+ , -i *i A ** mocnina, // celočíselné dělení, mod zbytek po delení
J* ?- X = 1 + 2. X = 1 + 2      = odpovídá unifikaci
M ?- X is 1 + 2.
X = 3      „is" je speciální preddefinovaný operátor, který vynutí evaluaci
porovnej:      N = (1+1+1+1+1) N is (1+1+1+1+1)
Hana Rudová, Logické programování I, 1. března 2012
4
Operátory, aritmetika
Aritmetika
JS> Preddefinované operátory
+ , -i *i A ** mocnina, // celocíselné dělení, mod zbytek po delení
J* ?- X = 1 + 2. X = 1 + 2      = odpovídá unifikaci
M ?- X is 1 + 2.
X = 3      „is" je speciální preddefinovaný operátor, který vynutí evaluaci
porovnej:      N = (1+1+1+1+1) N is (1+1+1+1+1)
pravá strana musí být vyhodnotitelný výraz (bez promenné) A výraz na pravé strane je nejdríve aritmeticky vyhodnocen a pak unifikován s levou stranou volání ?- X is Y + 1. způsobí chybu
Hana Rudová, Logické programování I, 1. brezna 2012
4
Operátory, aritmetika
Aritmetika
JS> Preddefinované operátory
+ , -i *i A ** mocnina, // celočíselné dělení, mod zbytek po delení
J* ?- X = 1 + 2. X = 1 + 2      = odpovídá unifikaci
M ?- X is 1 + 2.
X = 3      „is" je speciální preddefinovaný operátor, který vynutí evaluaci
porovnej:      N = (1+1+1+1+1) N is (1+1+1+1+1)
pravá strana musí být vyhodnotitelný výraz (bez promenné) A výraz na pravé strane je nejdríve aritmeticky vyhodnocen a pak unifikován s levou stranou volání ?- X is Y + 1. zpusobí chybu
JS> Další speciální preddefinované operátory
>, <, >=, =<, =:= aritmetická rovnost, =\= aritmetická nerovnost
-i- porovnej:      1+2 =:= 2+1 1+2 = 2+1
Hana Rudová, Logické programování I, 1. brezna 2012
4
Operátory, aritmetika
Aritmetika
JS> Preddefinované operátory
+ , -i *i A ** mocnina, // celoCíselné dělení, mod zbytek po delení
J* ?- X = 1 + 2. X = 1 + 2      = odpovídá unifikaci
M ?- X is 1 + 2.
X = 3      „is" je speciální preddefinovaný operátor, který vynutí evaluaci
porovnej:      N = (1+1+1+1+1) N is (1+1+1+1+1)
pravá strana musí být vyhodnotitelný výraz (bez promenné) A výraz na pravé strane je nejdríve aritmeticky vyhodnocen a pak unifikován s levou stranou volání ?- X is Y + 1. způsobí chybu
JS> Další speciální preddefinované operátory
>, <, >=, =<, =:= aritmetická rovnost, =\= aritmetická nerovnost
-i- porovnej:      1+2 =:= 2+1 1+2 = 2+1
-fc obe strany musí být vyhodnotitelný výraz: volání ?- 1 < A + 2. způsobí chybu
Hana Rudová, Logické programování I, 1. brezna 2012 4 Operátory, aritmetika
Různé typy rovností a porovnání
X = Y      Xa Y jsou unifikovatelné
X \= Y     Xa Y nejsou unifikovatelné, (také \+ X = Y)
Hana Rudová, Logické programování I, 1. března 2012
5
Operátory, aritmetika
Různé typy rovností a porovnání
X = Y      Xa Y jsou unifikovatelné
X \= Y     Xa Y nejsou unifikovatelné, (také \+ X = Y)
X == Y     Xa Y jsou identické
porovnej:   ?-A == B. ... no      ?-A=B, A==B.
Hana Rudová, Logické programování I, 1. brezna 2012
5
Operátory, aritmetika
Různé typy rovností a porovnání
X = Y X \= Y X == Y
X \== Y
X a Y jsou unifikovatelné
X a Y nejsou unifikovatelné, (také \+ X = Y)
X a Y jsou identické
porovnej: ?- A == B. ... no ?- A=B, A==B. ... B = A yes X a Y nejsou identické
porovnej:   ?- A \== B. ... yes      ?- A=B, A \== B. ... A no
Hana Rudová, Logické programování I, 1. brezna 2012
5
Operátory, aritmetika
Různé typy rovností a porovnání
X = Y X \= Y
X == Y
X \== Y
X is Y X =:= Y
X =\= Y
X < Y
X a Y jsou unifikovatelné
X a Y nejsou unifikovatelné, (také \+ X = Y)
X a Y jsou identické
porovnej: ?- A == B. ... no ?- A=B, A==B. ... B = A yes X a Y nejsou identické
porovnej:   ?- A \== B. ... yes      ?- A=B, A \== B. ... A no
Y je aritmeticky vyhodnoceno a výsledek je prirazen X
X a Y jsou si aritmeticky rovny
X a Y si aritmeticky nejsou rovny
aritmetická hodnota X je menší než Y (=<, >, >=)
Hana Rudová, Logické programování I, 1. brezna 2012
5
Operátory, aritmetika
Různé typy rovností a porovnání
X = Y X \= Y
X == Y
X \== Y
X is Y
X =:= Y X =\= Y
X < Y
X @< Y
X a Y jsou unifikovatelné
X a Y nejsou unifikovatelné, (také \+ X = Y)
X a Y jsou identické
porovnej:   ?- A == B. ... no      ?- A=B, A==B. ... B = A yes X a Y nejsou identické
porovnej:   ?- A \== B. ... yes      ?- A=B, A \== B. ... A no
Y je aritmeticky vyhodnoceno a výsledek je prirazen X
X a Y jsou si aritmeticky rovny
X a Y si aritmeticky nejsou rovny
aritmetická hodnota X je menší než Y (=<, >, >=)
term X predchází term Y (@=<, @>, @>=)
1. porovnání termů: podle alfabetického n. aritmetického usporádání
2. porovnání struktur: podle arity, pak hlavního funktoru a pak
zleva podle argumentu
Hana Rudová, Logické programování I, 1. brezna 2012
5
Operátory, aritmetika
Různé typy rovností a porovnání
X = Y X \= Y
X == Y X \== Y
X is Y
X =:= Y X =\= Y
X < Y
X @< Y
X a Y jsou unifikovatelné
X a Y nejsou unifikovatelné, (také \+ X = Y)
X a Y jsou identické
porovnej:   ?- A == B. ... no      ?- A=B, A==B. ... B = A yes X a Y nejsou identické
porovnej:   ?- A \== B. ... yes      ?- A=B, A \== B. ... A no
Y je aritmeticky vyhodnoceno a výsledek je prirazen X
X a Y jsou si aritmeticky rovny
X a Y si aritmeticky nejsou rovny
aritmetická hodnota X je menší než Y (=<, >, >=)
term X predchází term Y (@=<, @>, @>=)
1. porovnání termu: podle alfabetického n. aritmetického usporádání
2. porovnání struktur: podle arity, pak hlavního funktoru a pak
zleva podle argumentu ?- f( pavel, g(b)) @< f( pavel, h(a)). ... yes
Hana Rudová, Logické programování I, 1. brezna 2012
Operátory, aritmetika
5
Ř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
4
2
?- f(1,Y), Y>2.
j—
J_L
-©
J_L
3
6
x
Hana Růdová, Logické programování I, 1. března 2012
7
Ř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-
J_L
-©
J_L
3
6
x
?- f(1,Y), Y>2.
& Upnutí: po splnení podcílu pred rezem se už další klauzule neuvažují
Hana Rudová, Logické programování I, 1. brezna 2012 7 Rez, negace
Rez 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-
J_L
-©
?- 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 splnení podcílu pred rezem se už další klauzule neuvažují
Hana Rudová, Logické programování I, 1. brezna 2012 7 Rez, negace
Rez 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-
J_L
-©
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, 1. brezna 2012 7 Rez, negace
Řez a orezá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, 1. brezna 2012
8
Řez, negace
Rez a orezá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, 1. brezna 2012
8
Řez, negace
Řez a orezá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), !. 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
& Orezání: po splnení podcílů pred rezem se ůž neůvažůje další možné splnení techto podcílů
Hana Růdová, Logické programování I, 1. bŘrezna 2012
8
RŘez, negace
Řez a orezá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
Orezání: po splnení podcílu pred rezem se už neuvažuje další možné splnení techto podcílů
Smazání rezu zmení chování programu
Hana Rudová, Logické programování I, 1. b rezna 2012
8
Rez, negace
Chování operátoru rezu
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
Orezání: pri provádení rezu 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.
Hana Rudová, Logické programování I, 1. b rezna 2012
h(X,Y)
X=1 /   \ X=2
t1(Y)     a   (vynechej: upnutí)
Y=1 /   \ Y=2
b c   (vynechej: o rezání)
/
Rez, negace
9
Rez: 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).
Hana Rudová, Logické programování I, 1. brezna 2012
10
Řez, negace
Rez: 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, 1. b rezna 2012
10
Rez, negace
Rez: 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),  !, 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, 1. brezna 2012
10
Řez, negace
Rez: 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).
Hana Rudová, Logické programování I, 1. brezna 2012 10 Řez, negace
a(x)
h(X,Y)
X/1 t1(Y),!,e'(X')
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')
Hana Rudová, Logické programování I, 1. b rezna 2012
10
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 Růdová, Logické programování I, 1. bŘrezna 2012
10
RŘ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),
(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, 1. b rezna 2012
10
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),  !, 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, 1. brezna 2012 10 Řez, negace
a(x)
h(X,Y)
X/1
t1(Y),!,e'(X') Y/1 /
b,!,e(X') c,!,e(X') d,!,e(X')
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')
Hana Rudová, Logické programování I, 1. b rezna 2012
10
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),  !, 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, 1. bŘrezna 2012
10
RŘ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, 1. b rezna 2012
10
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') d,!,e(X')
no
!,e(X')
e(X') X'/l y \ X'/2
Hana Růdová, Logické programování I, 1. brezna 2012
10
Řez, negace
Rez: 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/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
Po zpracování klauzule s rezem se vracím až na rodice této klauzule, tj. a(X)
Hana Rudová, Logické programování I, 1. b rezna 2012
10
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/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 rezem se vracím až na rodice této klauzule, tj. a(X)
Hana Rudová, Logické programování I, 1. b rezna 2012
10
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/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 rezem se vracím až na rodice této klauzule, tj. a(X)
Hana Rudová, Logické programování I, 1. b rezna 2012
10
Rez, negace
Řez: príklad
c(X) :- p(X). c(X) :- v(X).
p(1).   p(2). v(2).
?- c(2).
Hana Růdová, Logické programování I, 1. bŘrezna 2012
11
RŘez, negace
c(X) :- p(X). c(X) :- v(X).
Rez: 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, 1. brezna 2012
11
Rez, negace
Rez: prí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, 1. brezna 2012 11 Ř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, 1. brezna 2012 11 Řez, negace
Rez: prí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, 1. brezna 2012 11 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, 1. března 2012
11
Rez, negace
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
c ■- !
2. Napište predikát pro výpocet maxima max( X, Y, Max )
Hana Rudová, Logické programování I, 1. bŘrezna 2012
12
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, 1. b rezna 2012
13
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, 1. b rezna 2012
13
Rez, negace
Typy rezu
Zlepšení efektivity programů: ůrcíme, které alternativy nemá smysl zkoůšet
Poznámka: na vstůpů pro X ocekávám císlo Zelený rez: odstraní poůze neúspešná odvození
f(X,1)  :- X >= 0,  !.    f(X,-1)  :- X < 0.
bez rezů zkoůším pro nezáporná císla 2. klaůzůli
Modrý rez: odstraní redůndantní rešení
f(X,1)  :- X >= 0,  !.    f(0,1). f(X,-1)  :- X < 0.
Hana Růdová, Logické programování I, 1. b rezna 2012
13
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
Hana Rudová, Logické programování I, 1. b rezna 2012
13
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 vrací f(0,1) 2x
Červený rez: odstraní úspešná rešení
f(X,1)  :- X >= 0,  I. f(_X,-1).
Hana Rudová, Logické programování I, 1. b rezna 2012
13
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).     bez r ezu uspeje 2. klauzule pro nezáporná císla
Hana Rudová, Logické programování I, 1. b rezna 2012
13
Rez, negace
Negace jako neúspěch
Speciální cíl pro nepravdu (neúspěch) fail a pravdu true
ii> X a Y nejsou unifikovatelné: different(X, Y)
C different( X, Y ) :- X = Y,  I, fail. different( _X, _Y ).
-í* X je muž: muz(X)
muz( X ) :- zena( X ),  I, fail. muz( _X ).
Hana Rudová, Logické programování I, 1. března 2012
14
Řez, negace
Negace jako neúspech: opeřátoř \+
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 \+(_).
Hana Rudová, Logické programování I, 1. b rezna 2012
15
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 opačné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, 1. brezna 2012
15
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, 1. b rezna 2012
16
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 ).
Hana Rudová, Logické programování I, 1. b rezna 2012
16
Rez, negace
Negace a promenne
\+(P) :- P' Ij fai1- % (I) dobre(X),rozumne(X)
\+(_). % (II)
dobre( citroen ). % (1)
dobře( bmw ). % (2)
dřahe( bmw ). % (3)
řozumne( Auto ) :- % (4)
\+ dřahe( Auto ). ?- dobre( X ), rozumne( X ).
Hana Rudová, Logické programování I, 1. b rezna 2012
16
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, 1. b rezna 2012
16
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)
dle (4) \+ drahe(citroen)
Hana Rudová, Logické programování I, 1. b rezna 2012
16
Rez, 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 ).
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, 1. bŘrezna 2012
16
RŘez, 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, 1. b rezna 2012
16
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, 1. b rezna 2012
16
no
Rez, negace
Negace a promenné
\+(P) :- P,  I, fail. % (I)
\+(_). % (II)
dobre( citroen ). % (1)
dobře( bmw ). % (2)
dřahe( bmw ). % (3)
řozumne( Auto ) :- % (4)
\+ dřahe( Auto ).
Hana Rudová, Logické programování I, 1. b rezna 2012
17
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, 1. brezna 2012
17
Rez, negace
Negace a promenné
rozumne(X), dobre(X)
\+(P) :- P,  I, fail. % (I)
\+(_). % (II)
dobre( citroen ). % (1)
dobře( bmw ). % (2)
dřahe( bmw ). % (3)
řozumne( Auto ) :- % (4)
\+ dřahe( Auto ). ?- rozumne( X ), dobre( X ).
Hana Rudová, Logické programování I, 1. b rezna 2012
17
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, 1. b rezna 2012
17
Rez, negace
\+(P) :- P, I, fail. % (I) \+(_). % (II)
dobre( citroen ). dobre( bmw ).
Negace a proměnné
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, 1. b rezna 2012
17
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 ).
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)
Hana Rudová, Logické programování I, 1. b rezna 2012
17
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, 1. března 2012 17
proměnné
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)
Ř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, 1. b rezna 2012 17
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
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 Růdová, Logické programování I, 1. b rezna 2012
18
Řez, negace
Chování negace
-í* ?- \+ drahe( citroen ). yes ?- \+ drahe( X ). no
& Negace jako neúspech používá predpoklad uzavrené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, 1. b rezna 2012
19
Rez, negace
Chování negace
-í* ?- \+ drahe( citroen ). yes ?- \+ drahe( X ). no
& Negace jako neúspech používá p redpoklad uzav rené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 ).
PTÁME SE: 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, 1. b rezna 2012
19
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 ).
PTÁME SE: 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, 1. b rezna 2012
19
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, 1. brezna 2012
20
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, 1. b rezna 2012
20
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, 1. b rezna 2012
20
Rez, negace
Predikáty na ŕízení běhu programu I.
řez „!"
fail: cíl, který vždy neuspeje      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.
Vyjád rení podmínky: P -> Q ; R
J* jestliže platí P tak Q        (P -> Q ; R) :- P,  1, Q. v opacném p r í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, 1. b rezna 2012
20
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,  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.
M P -> Q
-i- odpovídá: (P -> Q; fail)
S> príklad: zaporne(X) :- number(X) -> X < 0.
Hana Rudová, Logické programování I, 1. brezna 2012 20 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, 1. b rezna 2012
21
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 neskonCit 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, 1. b rezna 2012
21
Rez, negace