Řez, negace Rez f(X.O) :- X < 3 f(X,2) :- 3 =< X, X < 6 f(X,4) :- 6 =< X. Hana Rudová, Logické programování 1,11. března 201 0 a upnutí přidáni operátoru řezu ?- f(l,Y), Y>2. 2 Řez, negace Rez a upnutí f(X.O) f(X,2) f(X,4) - X < 3, !. - 3 =< X, X < 6 - 6 =< X. v ■ | * * pndam operátoru rezu , , > j ?- f(l,Y), Y>2 -• Upnutí: po splnění podcílů před řezem se už další klauzule neuvažují Hana Rudová, Logické programování 1,11. března 2010 2 Řez, negace Rez a upnutí f(X.O) :- X < 3, !. f(X,2) :- 3 =< X, X < 6 f(X,4) :- 6 =< X. V ■ I * * pndam operátoru rezu , , > j ?- f(l,Y), Y>2. f(X,0) :- X < 3, !. %(1) f(X,2) :- X < 6, !. %(2) f(X,4). -• Upnutí: po splnění podcílů před řezem se už další klauzule neuvažují Hana Rudová, Logické programování 1,11. března 2010 2 Řez, negace Rez a upnutí f(X.O) :- X < 3, !. f(X,2) :- 3 =< X, X < 6 f(X,4) :- 6 =< X. V ■ I * * pridaní operátoru rezu > j i j ?- f(l,Y), Y>2. f(X,0) :- X < 3, !. %(1) f(X,2) :- X < 6, !. %(2) f(X,4). ?- f(l,Y). -• Smazání řezu v (1) a (2) změní chování programu -• Upnutí: po splnění podcílů před řezem se už další klauzule neuvažují Hana Rudová, Logické programování 1,11. března 2010 2 Ř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(l,Z). Hana Rudová, Logické programování 1,11. března 201 0 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(l,Z). Z = 2 ? ; Z = 3 ? ; no Hana Rudová, Logické programování 1,11. března 201 0 3 Řez, negace Rez 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(i,z) ■ Z = 2 ? ; Z = 3 ? ; no fCX,Y) :- s(X,Y), !. s(X,Y) :- Y is X + 1 s(X,Y) :- Y is X + 2 ?_ f(i,z) Ořezání: po splnění podcílů před řezem se už neuvažuje další možné splnění těchto podcílů Hana Rudová, Logické programování 1,11. března 201 0 Řez, negace Rez a ořezání f (X, Y) s(X,Y) s(X,Y) - s(X,Y). - Y is X + 1 - Y is X + 2 f (X, Y) s(X,Y) s(X,Y) - s(X,Y), !. - Y is X + 1 - Y is X + 2 ?- f(l,Z) Z = 2 ? ; Z = 3 ? ; no ?- f(l,Z) Z = 2 ? ; no Ořezání: po splnění podcílů před řezem se už neuvažuje další možné splnění těchto podcílů Smazání řezu změní chování programu Hana Rudová, Logické programování 1,11. března 201 0 Řez, negace Chování operátoru řezu Předpokládejme, že klauzule H :- TI, T2, ..., Trn, !, ...Tn.je aktivována voláním cíle G, který je u n ifi kováte Iný s H. G=h(X,Y) V momentě, kdy je nalezen řez, existuje řešení cílů TI, ..., Trn X=1,Y=1 Ořezání: při provádění řezu se už další možné splnění cílů TI, ..., Trn nehledá a všechny ostatní alternativy jsou odstraněny Upnutí: dále už nevyvolávám další klauzule, jejichž hlava je také u n ifi kováte Iná s G Y=2 X=2 ?- h(X,Y). h(l,Y) :- tl(Y), ! h(2,Y) :- a. tl(l) :- b. tl(2) :- c. Hana Rudová, Logické programování 1,11. března 201 0 h(X,Y) X=l / \ X=2 tl(Y) a (vynechej: upnutí) Y=l / \ Y=2 b c (vynechej: ořezání) / Řez, negace Rez: návrat na rodiče ?- a(X). (1) a(X) :- h(X,Y). (2) a(X) :- d. (3) h(l,Y) :- tl(Y), !, e(X). (4) h(2,Y) :- a. (5) tl(l) :- b. (6) tl(2) :- c. (7) b :- c. (8) b :- d. (9) d. (10) e(l) . (11) e(2). -• Po zpracování klauzule s řezem se vracím až na rodiče této klauzule, tj. a(X) Hana Rudová, Logické programování 1,11. března 2010 5 Řez, negace Řez: příklad c(X) :- p(X). c(X) :- v(X). p(l). p(2). v(2). ?- c(2). Hana Rudová, Logické programování 1,11. března 201 0 6 Řez, negace Řez: příklad c(X) :- p(X). c(X) :- v(X). p(l). p(2). v(2). ?- c(2). true ? ; %p(2) true ? ; %v(2) no ?- c(X). Hana Rudová, Logické programování 1,11. března 201 0 6 Řez: příklad c(X) :- p(X). c(X) :- v(X). p(l). p(2). v(2). ?- c(2). true ? ; %p(2) true ? ; %v(2) no ?- c(X). X = 1 ? ; %p(l) X = 2 ? ; %p(2) X = 2 ? ; %v(2) no Hana Rudová, Logické programování 1,11. března 201 0 6 Rez: c(X) :- PCX). clCX) c(X) :- vCX). clCX) PCD. PC2). v ?- c(2) ■ ?- cl true ? ; %pC2) true ? ; %vC2) vC2) no ?- c(X). X = 1 ? ; %p(D X = 2 ? ; %p(2) X = 2 ? ; %v(2) no Hana Rudová, Logické programování 1,11. března 201 0 6 íklad PCX), ! vCX). Řez, negace c(X) :- p(X), c(X) :- v(X). Rez: příklad cl(X) :- p(X), ! cl(X) :- v(X). P(D. P(2) v(2). ?- c(2). true ? ; %p(2) true ? ; %v(2) no ?- cl(2). true ? ; %p(2) no ?- c(X). ?- cl(X) X = 1 ? ; %p(D X = 2 ? ; %p(2) X = 2 ? ; %v(2) no Hana Rudová, Logické programování 1,11. března 201 0 Řez, negace c(X) :- p(X). c(X) :- v(X). Rez: cl(X) cl(X) P(l). P(2) v(2) ?- c(2). true ? ; %p(2) true ? ; %v(2) no ?- cl(2) true ? no ?- c(X). ?- cl(X) X = 1 ? ; %p(D X = 1 ? X = 2 ? ; %p(2) no X = 2 ? ; %v(2) no Hana Rudová, Logické programování 1,11. března 201 0 6 íklad P(X), ! v (X). ; %p(2) ; %p(D Řez, negace Řez: cvičení 1. Porovnejte chování uvedených programů pro zadané dotazy. a(X,X) :- b(X). a(X,X) :- b(X),!. a(X,X) :- b(X),c. a(X,Y) :- Y is X+l. a(X,Y) :- Y is X+l. a(X,Y) :- Y is X+l. b(X) :- X > 10. b(X) :- X > 10. b(X) :- X > 10. c ■- ' ?- a(X,Y). ?- a(l,Y). ?- a(ll,Y). 2. Napište predikát pro výpočet maxima max( X, Y, Max ) Hana Rudová, Logické programování 1,11. března 201 0 7 Řez, negace Typy řezu -• Zlepšení efektivity programu: určíme, které alternativy nemá smysl zkoušet -• Zelený řez: odstraní pouze neúspěšná odvození 3 f(X,l) :- X >= 0, !. f(X,-l) :- X < 0. Hana Rudová, Logické programování 1,11. března 201 0 8 Řez, negace Typy řezu -• Zlepšení efektivity programu: určíme, které alternativy nemá smysl zkoušet -• Zelený řez: odstraní pouze neúspěšná odvození M f(X,l) :- X >= 0, !. f(X,-l) :- X < 0. bez řezu zkouším pro nezáporná čísla 2. klauzuli Hana Rudová, Logické programování 1,11. března 201 0 8 Řez, negace Typy řezu -• Zlepšení efektivity programu: určíme, které alternativy nemá smysl zkoušet -• Zelený řez: odstraní pouze neúspěšná odvození M f(X,l) :- X >= 0, !. f(X,-l) :- X < 0. bez řezu zkouším pro nezáporná čísla 2. klauzuli -• Modrý řez: odstraní redundantní řešení -• f(X,l) :- X >= 0, !. f(0,l). f(X,-l) :- X < 0. Hana Rudová, Logické programování 1,11. března 201 0 8 Řez, negace Typy řezu -• Zlepšení efektivity programu: určíme, které alternativy nemá smysl zkoušet -• Zelený řez: odstraní pouze neúspěšná odvození M f(X,l) :- X >= 0, !. f(X,-l) :- X < 0. bez řezu zkouším pro nezáporná čísla 2. klauzuli -• Modrý řez: odstraní redundantní řešení -• f(X,l) :- X >= 0, !. f(0,l). f(X,-l) :- X < 0. bez řezu vrací f(0,l) 2x Hana Rudová, Logické programování 1,11. března 201 0 8 Řez, negace Typy řezu -• Zlepšení efektivity programu: určíme, které alternativy nemá smysl zkoušet -• Zelený řez: odstraní pouze neúspěšná odvození M f(X,l) :- X >= 0, !. f(X,-l) :- X < 0. bez řezu zkouším pro nezáporná čísla 2. klauzuli -• Modrý řez: odstraní redundantní řešení -• f(X,l) :- X >= 0, !. f(0,l). f(X,-l) :- X < 0. bez řezu vrací f(0,l) 2x 3 Červený řez: odstraní úspěšná řešení M f(X,l) :- X >= 0, !. f(_X,-l). Hana Rudová, Logické programování 1,11. března 201 0 8 Řez, negace Typy řezu -• Zlepšení efektivity programu: určíme, které alternativy nemá smysl zkoušet -• Zelený řez: odstraní pouze neúspěšná odvození M f(X,l) :- X >= 0, !. f(X,-l) :- X < 0. bez řezu zkouším pro nezáporná čísla 2. klauzuli -• Modrý řez: odstraní redundantní řešení -• f(X,l) :- X >= 0, !. f(0,l). f(X,-l) :- X < 0. bez řezu vrací f(0,l) 2x 3 Červený řez: odstraní úspěšná řešení M f(X,l) :- X >= 0, !. f(_X,-l). bez řezu uspěje 2. klauzule pro nezáporná čísla Hana Rudová, Logické programování 1,11. března 201 0 8 Řez, 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) M different C X, Y ) :- X = Y, !, fail. differentC _X, _Y ). -• Xje muž: muz(X) muz( X ) :- zena( X ), !, fail. muz( _X ) . Hana Rudová, Logické programování 1,11. března 201 0 9 Řez, negace Negace jako neúspěch: operátor \+ M different(X,Y) :- X = Y, !, fail. muz(X) :- zena(X), !, fail. different(_X,_Y). muz(_X). -• Unární operátor \+ P 3 jestliže P uspěje, potom \+ P neuspěje \+(P) :- P, !, fail. 3 v opačném případě \+ P uspěje Hana Rudová, Logické programování 1,11. března 201 0 1 0 Řez, negace Negace jako neúspěch: operátor \+ M different(X,Y) :- X = Y, !, fail. muz(X) :- zena(X), !, fail. different(_X,_Y). muz(_X). -• Unární operátor \+ P 3 jestliže P uspěje, potom \+ P neuspěje \+(P) :- P, !, fail. 3 v opačném případě \+ P uspěje -• differentC X, Y ) :- \+ X=Y. M muz( X ) :- \+ zena( X ). M Pozor: takto definovaná negace \+P vyžaduje konečné odvození P Hana Rudová, Logické programování 1,11. března 201 0 1 0 Řez, negace Negace a proměnné \+(P) :- P, !, fail. % (I) \+(_). % (ID dobre( citroen ). % (1) dobre( bmw ). % (2) drahe( bmw ). % (3) rozumne( Auto ) :- % (4) \+ drahe( Auto ). Hana Rudová, Logické programování 1,11. března 201 0 1 1 Řez, negace Negace a proměnné \+(P) :- P, !, fail. % (I) \+(_). % (II) dobre( citroen ). % CD dobre( bmw ). % (2) drane( bmw ). % (3) rozumneC Auto ) :- % (4) \+ drahe( Auto ) ?- dobre( X ), rozumne( X ). Hana Rudová, Logické programování 1,11. března 2010 1 1 Řez, negace Negace a \+(P) :- P, !, fail. % (I) \+(_). % (II) dobre( citroen ). % CD dobre( bmw ). % (2) drane( bmw ). % (3) rozumneC Auto ) :- % (4) \+ drahe( Auto ) ?- dobre( X ), rozumne( X ). Hana Rudová, Logické programování 1,11. března 201 0 proměnné dobre(X),rozumne(X) 11 Řez, negace Negace a \+(P) :- P, !, fail. % (I) \+(_). % (II) dobre( citroen ). % CD dobre( bmw ). % (2) drane( bmw ). % (3) rozumneC Auto ) :- % (4) \+ drahe( Auto ) ?- dobre( X ), rozumne( X ). Hana Rudová, Logické programování 1,11. března 201 0 proměnné dobre(X),rozumne(X) dle (1), X/citroen rozumne(citroen) 11 Řez, negace Negace a \+(P) :- P, !, fail. % (I) \+(_). % (II) dobre( citroen ). % CD dobre( bmw ). % (2) drane( bmw ). % (3) rozumneC Auto ) :- % (4) \+ drahe( Auto ) ?- dobre( X ), rozumne( X ). Hana Rudová, Logické programování 1,11. března 201 0 proměnné dobre(X),rozumne(X) dle (1), X/citroen rozumne(citroen) dle (4) \+ drahe(citroen) 11 Řez, negace Negace a \+(P) :- P, !, fail. % (I) \+(_). % (II) dobre( citroen ). % CD dobre( bmw ). % (2) drane( bmw ). % (3) rozumneC Auto ) :- % (4) \+ drahe( Auto ) ?- dobre( X ), rozumne( X ). Hana Rudová, Logické programování 1,11. března 201 0 proměnné dobre(X),rozumne(X) dle (1), X/citroen rozumne(citroen) dle (4) \+ drahe(citroen) dle (I) drahe(citroen),!, fail 11 Řez, negace Negace a \+(P) :- P, !, fail. % (I) \+(_). % (II) dobre( citroen ). % CD dobre( bmw ). % (2) drane( bmw ). % (3) rozumneC Auto ) :- % (4) \+ drahe( Auto ) ?- dobre( X ), rozumne( X ). Hana Rudová, Logické programování 1,11. března 201 0 proměnné dobre(X),rozumne(X) dle (1), X/citroen rozumne(citroen) dle (4) \+ drahe(citroen) dle (I) drahe(citroen),!, fail 11 no Řez, negace Negace a \+(P) :- P, !, fail. % (I) \+(_). % (II) dobre( citroen ). % CD dobre( bmw ). % (2) drane( bmw ). % (3) rozumneC Auto ) :- % (4) \+ drahe( Auto ) ?- dobre( X ), rozumne( X ). Hana Rudová, Logické programování 1,11. března 201 0 proměnné dobre(X),rozumne(X) dle (1), X/citroen rozumne(citroen) dle (4) \+ drahe(citroen) dle (I) drahe(citroen),!, fail dle (II) yes 11 no Řez, negace Negace a proměnné \+(P) :- P, !, fail. % (I) \+(_). % (ID dobre( citroen ). % (1) dobre( bmw ). % (2) drahe( bmw ). % (3) rozumne( Auto ) :- % (4) \+ drahe( Auto ). Hana Rudová, Logické programování 1,11. března 201 0 1 2 Řez, negace Negace a proměnné \+(P) :- P, !, fail. % (I) \+(_). % (II) dobre( citroen ). % CD dobre( bmw ). % (2) drane( bmw ). % (3) rozumneC Auto ) :- % (4) \+ drahe( Auto ) ?- rozumne( X ), dobre( X ). Hana Rudová, Logické programování 1,11. března 2010 12 Řez, negace Negace a \+(P) :- P, !, fail. % (I) \+(_). % (ID dobre( citroen ). % (1) dobre( bmw ). % (2) drahe( bmw ). % (3) rozumne( Auto ) :- % (4) \+ drahe( Auto ). ?- rozumne( X ), dobre( X ). Hana Rudová, Logické programování 1,11. března 201 0 proměnné rozumne(X), dobre(X) 12 Řez, negace Negace a \+(P) :- P, !, fail. % (I) \+(_). % (II) dobre( citroen ). % CD dobre( bmw ). % (2) drane( bmw ). % (3) rozumneC Auto ) :- % (4) \+ drahe( Auto ) ?- rozumne( X ), dobre( X ). Hana Rudová, Logické programování 1,11. března 201 0 proměnné rozumne(X), dobre(X) dle (4) \+ drahe(X), dobre(X) 12 Řez, negace Negace a \+(P) :- P, !, fail. % (I) \+(_). % (II) dobre( citroen ). % CD dobre( bmw ). % (2) drane( bmw ). % (3) rozumneC Auto ) :- % (4) \+ drahe( Auto ) ?- rozumne( X ), dobre( X ). Hana Rudová, Logické programování 1,11. března 201 0 proměnné rozumne(X), dobre(X) dle (4) \+ drahe(X), dobre(X) dle (I) drahe(X),!,fail,dobre(X) 12 Řez, negace Negace a \+(P) :- P, !, fail. % (I) \+(_). % (II) dobre( citroen ). % CD dobre( bmw ). % (2) drane( bmw ). % (3) rozumneC Auto ) :- % (4) \+ drahe( Auto ) ?- rozumne( X ), dobre( X ). Hana Rudová, Logické programování 1,11. března 201 0 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) 12 Řez, negace Negace a \+(P) :- P, !, fail. % (I) \+(_). % (II) dobre( citroen ). % CD dobre( bmw ). % (2) drane( bmw ). % (3) rozumneC Auto ) :- % (4) \+ drahe( Auto ) ?- rozumne( X ), dobre( X ). Hana Rudová, Logické programování 1,11. března 201 0 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) 12 Řez, negace Negace a \+(P) :- P, !, fail. % (I) \+(_). % (II) dobre( citroen ). % CD dobre( bmw ). % (2) drane( bmw ). % (3) rozumneC Auto ) :- % (4) \+ drahe( Auto ) ?- rozumne( X ), dobre( X ). Hana Rudová, Logické programování 1,11. března 201 0 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) 12 no Řez, negace Bezpečný cíl -• ?- rozumneC citroen ). yes ?- rozumneC X ). no -• ?- \+ draheC citroen ). yes ?- \+ draheC X ). no ^ \+ P je bezpečný: proměnné P jsou v okamžiku volání P instanciovany M negaci používáme pouze pro bezpečný cíl P Hana Rudová, Logické programování 1,11. března 201 0 1 3 Řez, negace Chování negace M ?- \+ drahe( citroen ). yes ?- \+ drahe( X ). no M Negace jako neúspěch používá předpoklad uzavřeného světa 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í 1,11. března 201 0 1 4 Řez, negace Chování negace M ?- \+ drahe( citroen ). yes ?- \+ drahe( X ). no M Negace jako neúspěch používá předpoklad uzavřeného světa 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 ) -• ?- drahe( X ). VÍME: existuje X takové, že drahe( X ) platí -• ALE: pro cíle s negací neplatí existuje X takové, že \+ drahe( X ) Hana Rudová, Logické programování 1,11. března 201 0 1 4 Řez, negace Chování negace M ?- \+ drahe( citroen ). yes ?- \+ drahe( X ). no M Negace jako neúspěch používá předpoklad uzavřeného světa 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 ) -• ?- drahe( X ). VÍME: existuje X takové, že drahe( X ) platí -• ALE: pro cíle s negací neplatí existuje X takové, že \+ drahe( X ) => negace jako neúspěch není ekvivalentní negaci v matematické logice Hana Rudová, Logické programování 1,11. března 201 0 1 4 Řez, negace Predikáty na ří -• řez „!" -• fail: cíl, který vždy neuspěje «• \+ P: negace jako neúspěch \+ P :- P, !, fail; true. Hana Rudová, Logické programování 1,11. března 201 0 :ení běhu programu I true: cíl, který vždy uspěje 15 Řez, negace Predikáty na řízení běhu programu I. -• řez „!" -• fail: cíl, který vždy neuspěje true: cíl, který vždy uspěje «• \+ P: negace jako neúspěch \+ P :- P, !, fail; true. -• once(P): vrátí pouze jedno řešení cíle P once(P) :- P, !. Hana Rudová, Logické programování 1,11. března 201 0 1 5 Řez, negace Predikáty na řízení běhu programu I. -• řez „!" -• fail: cíl, který vždy neuspěje true: cíl, který vždy uspěje «• \+ P: negace jako neúspěch \+ P :- P, !, fail; true. -• once(P): vrátí pouze jedno řešení cíle P once(P) :- P, !. -• Vyjádření podmínky: P -> Q ; R -• jestliže platí P tak Q (P -> Q ; R) :- P, ! , Q. -• v opačném případě R (P -> Q ; R) :- R. -• príklad: min(X,Y,Z) : - X =< Y -> Z = X ; Z = Y. Hana Rudová, Logické programování 1,11. března 201 0 1 5 Řez, negace Predikáty na řízení běhu programu I. -• řez „!" -• fail: cíl, který vždy neuspěje true: cíl, který vždy uspěje «• \+ P: negace jako neúspěch \+ P :- P, !, fail; true. -• once(P): vrátí pouze jedno řešení cíle P once(P) :- P, !. -• Vyjádření podmínky: P -> Q ; R -• jestliže platí P tak Q (P -> Q ; R) :- P, ! , Q. -• v opačném případě R (P -> Q ; R) :- R. -• príklad: min(X,Y,Z) : - X =< Y -> Z = X ; Z = Y. M P -> Q Hana Rudová, Logické programování 1,11. března 201 0 1 5 Řez, negace Predikáty na řízení běhu programu I. -• řez „!" -• fail: cíl, který vždy neuspěje true: cíl, který vždy uspěje «• \+ P: negace jako neúspěch \+ P :- P, !, fail; true. -• once(P): vrátí pouze jedno řešení cíle P once(P) :- P, !. -• Vyjádření podmínky: P -> Q ; R -• jestliže platí P tak Q (P -> Q ; R) :- P, ! , Q. -• v opačném případě R (P -> Q ; R) :- R. -• príklad: min(X,Y,Z) : - X =< Y -> Z = X ; Z = Y. M P -> Q M odpovídá: (P -> Q; fail) M příklad: zaporne(X) :- number(X) -> X < 0. Hana Rudová, Logické programování 1,11. března 2010 15 Řez, negace Predikáty na řízení běhu programu IL -• call (P): zavolá cíl P a uspěje, pokud uspěje P -• nekonečná posloupnost backtrackovacích voleb: repeat repeat. repeat :- repeat. Hana Rudová, Logické programování 1,11. března 201 0 1 6 Řez, negace Predikáty na řízení běhu programu IL -• call (P): zavolá cíl P a uspěje, pokud uspěje P -• nekonečná posloupnost backtrackovacích voleb: repeat repeat. repeat :- repeat. klasické použití: generuj akci X, proveď ji a otestuj, zda neskončit Hlava :- ... uloz_stav( StaryStav ), repeat, generujC X ), % deterministické: generuj, prováděj, testuj provadejC X ), testujC X ), i ■ > obnov_stav( StaryStav ), Hana Rudová, Logické programování 1,11. března 2010 16 Řez, negace Seznamy Reprezentace seznamu -• Seznam: [a, b, c], prázdný seznam [] -• Hlava (libovolný objekt), tělo (seznam): .(Hlava, Telo) -• všechny strukturované objekty stromy - i seznamy 3 funktor".", dva argumenty 3 .(a, .(b, .(c, []))) = [a, b, c] -• notace: [ Hlava | Telo ] = [a | Tel o] Hana Rudová, Logické programování 1,11. března 201 0 1 8 Seznamy Reprezentace seznamu -• Seznam: [a, b, c], prázdný seznam [] -• Hlava (libovolný objekt), tělo (seznam): .(Hlava, Telo) -• všechny strukturované objekty stromy - i seznamy 3 funktor".", dva argumenty 3 .(a, .(b, .(c, []))) = [a, b, c] -• notace: [ Hlava | Telo ] = [a | Tel o] Telo je v [a | Tel o] seznam, tedy píšeme [ a, b, c ] = [ a | [ b, c ] ] Hana Rudová, Logické programování 1,11. března 201 0 1 8 Seznamy Reprezentace seznamu -• Seznam: [a, b, c], prázdný seznam [] -• Hlava (libovolný objekt), tělo (seznam): .(Hlava, Telo) -• všechny strukturované objekty stromy - i seznamy 3 funktor".", dva argumenty 3 .(a, .(b, .(c, []))) = [a, b, c] -• notace: [ Hlava | Telo ] = [a | Tel o] Telo je v [a | Tel o] seznam, tedy píšeme [ a, b, c ] = [ a | [ b, c ] ] -• Lze psát i: [a,b|Telo] -• před "|"je libovolný počet prvků seznamu , za "I"je seznam zbývajících prvků * [a,b,c] = [a|[b,c]] = [a,b|[c]] = [a,b,c|[]] Hana Rudová, Logické programování 1,11. března 201 0 1 8 Seznamy Reprezentace seznamu -• Seznam: [a, b, c], prázdný seznam [] -• Hlava (libovolný objekt), tělo (seznam): .(Hlava, Telo) -• všechny strukturované objekty stromy - i seznamy 3 funktor".", dva argumenty 3 .(a, .(b, .(c, []))) = [a, b, c] -• notace: [ Hlava | Telo ] = [a | Tel o] Telo je v [a | Tel o] seznam, tedy píšeme [ a, b, c ] = [ a | [ b, c ] ] -• Lze psát i: [a,b|Telo] -• před "|"je libovolný počet prvků seznamu , za "I"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, 11. března 2010 18 Seznamy Reprezentace seznamu -• Seznam: [a, b, c], prázdný seznam [] -• Hlava (libovolný objekt), tělo (seznam): .(Hlava, Telo) -• všechny strukturované objekty stromy - i seznamy 3 funktor".", dva argumenty 3 .(a, .(b, .(c, []))) = [a, b, c] -• notace: [ Hlava | Telo ] = [a | Tel o] Telo je v [a | Tel o] seznam, tedy píšeme [ a, b, c ] = [ a | [ b, c ] ] -• Lze psát i: [a,b|Telo] -• před "|"je libovolný počet prvků seznamu , za "I"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] ] M Seznam jako neúplná datová struktura: [a,b,c|T] 3 Seznam = [a,b,c|T], T = [d,e|S], Seznam = [a,b,c,d,e|S] Hana Rudová, Logické programování I, 11. března 2010 18 Seznamy Prvek seznamu -• memberC X, S ) -• platí: memberC b, [a,b,c] ). M neplatí: memberC b, [[a,b]|[c]] ). -• X je prvek seznamu S, když 3 X je hlava seznamu S nebo memberC X, [ X | _ ] ). %CD M X je prvek těla seznamu S memberC X, [ _ | Telo ] ) :- memberC X, Telo ). %C2) Hana Rudová, Logické programování 1,11. března 201 0 1 9 Prvek seznamu member(1,[2,1,3,1,4]) M memberC X, S ) -• platí: memberC b, [a,b,c] ). M neplatí: memberC b, [[a,b]|[c]] ). -• X je prvek seznamu S, když 3 X je hlava seznamu S nebo memberC X, [ X | _ ] ). %CD M X je prvek těla seznamu S memberC X, [ _ | Telo ] ) :- memberC X, Telo ). %C2) Hana Rudová, Logické programování I, 11. března 201 0 1 9 Seznamy Prvek seznamu -• memberC X, S ) -• platí: memberC b, [a,b,c] ). M neplatí: memberC b, [[a,b]|[c]] ). -• X je prvek seznamu S, když 3 X je hlava seznamu S nebo memberC X, [ X | _ ] ). %CD M X je prvek těla seznamu S memberC X, [ _ | Telo ] ) :- memberC X, Telo ). %C2) Hana Rudová, Logické programování 1,11. března 201 0 1 9 member(1,[2,1,3,1,4]) dle (2) member(1,[1,3,1,4]) Seznamy Prvek seznamu memberC X, S ) platí: memberC b, [a,b,c] ). neplatí: memberC b, [[a,b]|[c]] ). X je prvek seznamu S, když 3 X je hlava seznamu S nebo memberC X, [ X | _ ] ). %(1) M X je prvek těla seznamu S memberC X, [ _ | Telo ] ) :- memberC X, Telo ). %C2) dle (1 D yes member(1,[2,1,3,1,4]) dle (2) member(1,[1,3,1,4]) dle (2) member(1,[3,154]) Hana Rudová, Logické programování I, 11. března 201 0 1 9 Seznamy Prvek seznamu memberC X, S ) platí: memberC b, [a,b,c] ). neplatí: memberC b, [[a,b]|[c]] ). X je prvek seznamu S, když 3 X je hlava seznamu S nebo memberC X, [ X | _ ] ). %(1) M X je prvek těla seznamu S memberC X, [ _ | Telo ] ) :- memberC X, Telo ). %C2) dle (1 D yes member(1,[2,1,3,1,4]) dle (2) member(1,[1,3,1,4]) dle (2) member(1,[3,154]) dle (2) member(1,[1,4]) Hana Rudová, Logické programování I, 11. března 201 0 1 9 Seznamy Prvek seznamu memberC X, S ) platí: memberC b, [a,b,c] ). neplatí: memberC b, [[a,b]|[c]] ). X je prvek seznamu S, když 3 X je hlava seznamu S nebo memberC X, [ X | _ ] ). %(1) M X je prvek těla seznamu S memberC X, [ _ | Telo ] ) :- memberC X, Telo ). %C2) dle (1 D yes dle (1 D 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, 11. března 201 0 1 9 Seznamy Prvek seznamu memberC X, S ) platí: memberC b, [a,b,c] ). neplatí: memberC b, [[a,b]|[c]] ). X je prvek seznamu S, když 3 X je hlava seznamu S nebo memberC X, [ X | _ ] ). %(1) M X je prvek těla seznamu S memberC X, [ _ | Telo ] ) :- memberC X, Telo ). %C2) dle (1 D yes dle (1 D 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, 11. března 201 0 1 9 Seznamy Prvek seznamu memberC X, S ) platí: memberC b, [a,b,c] ). neplatí: memberC b, [[a,b]|[c]] ). X je prvek seznamu S, když 3 X je hlava seznamu S nebo memberC X, [ X | _ ] ). %(1) M X je prvek těla seznamu S memberC X, [ _ | Telo ] ) :- memberC X, Telo ). %C2) dle (1 D yes dle (1 D 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, 11. března 201 0 19 no Seznamy Prvek seznamu memberC X, S ) platí: memberC b, [a,b,c] ). neplatí: memberC b, [[a,b]|[c]] ). X je prvek seznamu S, když 3 X je hlava seznamu S nebo memberC X, [ X | _ ] ). %(1) M X je prvek těla seznamu S memberC X, [ _ | Telo ] ) :- memberC X, Telo ). %C2) Další příklady použití: 3 member(X,[1,2,3]). 3 member(l,[2,1,3,1]). dle (1 D yes dle (1 D yes member(1,[2,1,3,1,4]) dle (2) member(1,[1,3,1,4]) dle (2) member(1,[3,154]) dle (2) member(1,[1,4]) dle (2) member(1,[4]) dle (2) member(1,[]) dle (2) Hana Rudová, Logické programování I, 11. března 201 0 19 no Seznamy Spojení seznamů -• appendC LI, L2, L3 ) M Platí: appendC [a,b], [c,d], [a,b,c,d] ) M Neplatí: appendC [b,a], [c,d], [a,b,c,d] ), appendC [a,[b]], [c,d], [a,b,c,d] ) Hana Rudová, Logické programování 1,11. března 201 0 20 Seznamy Spojení seznamů -• appendC LI, L2, L3 ) M Platí: appendC [a,b], [c,d], [a,b,c,d] ) M Neplatí: appendC [b,a], [c,d], [a,b,c,d] ), appendC [a,[b]], [c,d], [a,b,c,d] ) -• Definice: 3 pokud je 1. argument prázdný seznam, pak 2. a 3. argument jsou stejné seznamy: appendC [], S, S ). Hana Rudová, Logické programování 1,11. března 201 0 20 Seznamy Spojení seznamů appendC LI, L2, L3 ) Platí: append( [a,b], [c,d], [a,b,c,d] ) Neplatí: append( [b,a], [c,d], [a,b,c,d] ), appendC [a,[b]], [c,d], [a,b,c,d] ) Definice: 3 pokud je 1. argument prázdný seznam, pak 2. a 3. argument jsou stejné seznamy: append( [], S, S ). M pokud je 1. argument neprázdný seznam, pak má 3. argument stejnou hlavu jako 1 appendC [X|S1], S2, [X|S3] ) :- append( SI, S2, S3). X S1 S2 S3 Hana Rudová, Logické programování I, 11. března 201 0 20 Seznamy Příklady použití append -• appendC [], S, S ). appendC [X|S1], S2, [X|S3] ) :- appendC SI, S2, S3). M Spojení seznamů: appendC [a,b,c], [1,2,3], S ). S = [a,b,c,1,2,3] appendC [a, [b,c], d], [a, [], b], S ). S = [a, [b,c] , d, a, [] , b] ] Hana Rudová, Logické programování I, 11. března 201 0 21 Seznamy Příklady použití append -• appendC [], S, S ). appendC [X|S1], S2, [X|S3] ) :- appendC SI, S2, S3). M Spojení seznamů: appendC [a,b,c], [1,2,3], S ). S = [a,b,c,1,2,3] appendC [a, [b,c], d], [a, [], b], S ). S = [a, [b,c] , d, a, [] , b] ] -• Dekompozice seznamu na dva seznamy: appendC SI, S2 , [a, b ]). SI = [], S2 = [a,b] ; SI = [a] , S2 = [b] ? ; SI = [a,b], S2 = [] Hana Rudová, Logické programování I, 11. března 201 0 21 Seznamy Příklady použití append -• appendC [], S, S ). appendC [X|S1], S2, [X|S3] ) :- appendC SI, S2, S3). M Spojení seznamů: appendC [a,b,c], [1,2,3], S ). S = [a,b,c,1,2,3] appendC [a, [b,c], d], [a, [], b], S ). S = [a, [b,c] , d, a, [] , b] ] -• Dekompozice seznamu na dva seznamy: appendC SI, S2 , [a, b ]). SI = [], S2 = [a,b] ; SI = [a] , S2 = [b] ? ; SI = [a,b], S2 = [] -• Vyhledávání v seznamu: appendC Pred, [c | Za ] , [a,b,c,d,e] ). Pred = [a,b], Za = [d,e] Hana Rudová, Logické programování I, 11. března 201 0 21 Seznamy Příklady použití append -• appendC [], S, S ). appendC [X|S1], S2, [X|S3] ) :- appendC SI, S2, S3). M Spojení seznamů: appendC [a,b,c], [1,2,3], S ). S = [a,b,c,1,2,3] appendC [a, [b,c], d], [a, [], b], S ). S = [a, [b,c] , d, a, [] , b] ] -• Dekompozice seznamu na dva seznamy: appendC SI, S2 , [a, b ]). SI = [], S2 = [a,b] ; SI = [a] , S2 = [b] ? ; SI = [a,b], S2 = [] -• Vyhledávání v seznamu: appendC Pred, [c | Za ] , [a,b,c,d,e] ). Pred = [a,b], Za = [d,e] M Předchůdce a následník: appendC _, [Pred,c,Za|_] , [a,b,c,d,e] ). Pred = b, Za = d Hana Rudová, Logické programování I, 11. března 2010 21 Seznamy Smazání prvku seznamu delete( X, S, SI ) M Seznam SI odpovídá seznamu S, ve kterém je smazán prvek X 3 jestliže X je hlava seznamu S, pak výsledkem je tělo S deleteC X, [X|Telo], Telo). M jestliže X je v těle seznamu, pak X je smazán až v těle deleteC X, [Y|Telo], [Y|Telol] ) :- deleteC X, Telo, Telol ). Hana Rudová, Logické programování 1,11. března 201 0 22 Seznamy Smazání prvku seznamu delete( X, S, SI ) M Seznam SI odpovídá seznamu S, ve kterém je smazán prvek X 3 jestliže X je hlava seznamu S, pak výsledkem je tělo S deleteC X, [X|Telo], Telo). M jestliže X je v těle seznamu, pak X je smazán až v těle deleteC X, [Y|Telo], [Y|Telol] ) :- deleteC 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] Hana Rudová, Logické programování 1,11. března 201 0 22 Seznamy Smazání prvku seznamu delete( X, S, SI ) M Seznam SI odpovídá seznamu S, ve kterém je smazán prvek X 3 jestliže X je hlava seznamu S, pak výsledkem je tělo S deleteC X, [X|Telo], Telo). M jestliže X je v těle seznamu, pak X je smazán až v těle deleteC X, [Y|Telo], [Y|Telol] ) :- deleteC 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 M deleteC X, [X|Telo], Telo) :- !. deleteC X, [Y|Telo], [Y|Telol] ) :- deleteC X, Telo, Telol). Hana Rudová, Logické programování I, 11. března 2010 22 Seznamy