Ř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í I, 3. března 2009 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í I, 3. března 2009 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í I, 3. března 2009 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í I, 3. března 2009 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í I, 3. března 2009 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í I, 3. března 2009 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í I, 3. března 2009 Ř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í I, 3. března 2009 Ř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í I, 3. března 2009 h(X,Y) X=l / \ X=2 tl(Y) a (vynechej: upnutí) Y=l / \ Y=2 b c (vynechej: ořezání) / Ř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í I, 3. března 2009 5 Ř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í I, 3. března 2009 5 Ř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í I, 3. března 2009 5 c(X) :- p(X). c(X) :- v(X). Rez: příklad cl(X) :- p(X), ! cl(X) :- v(X). P(l). p(2) v(2) ?- c(2). true ? ; %p(2) true ? ; %v(2) no ?- cl(2) ?_ c (X). x = 1 ? ; %p(D x = 2 ? ; %p(2) x = 2 ? ; %v(2) no Hana Rudová, Logické programování I, 3. března 2009 Ř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í I, 3. března 2009 Ř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í I, 3. března 2009 5 í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í I, 3. března 2009 6 Ř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í I, 3. března 2009 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í 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í I, 3. března 2009 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í 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í I, 3. března 2009 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í 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í I, 3. března 2009 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í 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í I, 3. března 2009 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í 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í I, 3. března 2009 7 Ř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í I, 3. března 2009 8 Ř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í I, 3. března 2009 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 -• 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í I, 3. března 2009 9 Ř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í I, 3. března 2009 10 Ř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í I, 3. března 2009 10 Ř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í I, 3. března 2009 proměnné dobre(X),rozumne(X) 10 Ř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í I, 3. března 2009 proměnné dobre(X),rozumne(X) dle (1), X/citroen rozumne(citroen) 10 Ř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í I, 3. března 2009 proměnné dobre(X),rozumne(X) dle (1), X/citroen rozumne(citroen) dle (4) \+ drahe(citroen) 10 Ř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í I, 3. března 2009 proměnné dobre(X),rozumne(X) dle (1), X/citroen rozumne(citroen) dle (4) \+ drahe(citroen) dle (I) drahe(citroen),!, fail 10 Ř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í I, 3. března 2009 proměnné dobre(X),rozumne(X) dle (1), X/citroen rozumne(citroen) dle (4) \+ drahe(citroen) dle (I) drahe(citroen),!, fail 10 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í I, 3. března 2009 proměnné dobre(X),rozumne(X) dle (1), X/citroen rozumne(citroen) dle (4) \+ drahe(citroen) dle (I) drahe(citroen),!, fail dle (II) yes 10 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í I, 3. března 2009 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 ) ?- rozumne( X ), dobre( X ). Hana Rudová, Logické programování I, 3. března 2009 1 1 Ř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í I, 3. března 2009 proměnné rozumne(X), dobre(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 ) ?- rozumne( X ), dobre( X ). Hana Rudová, Logické programování I, 3. března 2009 proměnné rozumne(X), dobre(X) dle (4) \+ drahe(X), dobre(X) 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 ) ?- rozumne( X ), dobre( X ). Hana Rudová, Logické programování I, 3. března 2009 proměnné rozumne(X), dobre(X) dle (4) \+ drahe(X), dobre(X) dle (I) drahe(X),!,fail,dobre(X) 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 ) ?- rozumne( X ), dobre( X ). Hana Rudová, Logické programování I, 3. března 2009 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) n Ř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í I, 3. března 2009 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) n Ř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í I, 3. března 2009 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) 11 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í I, 3. března 2009 12 Ř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í I, 3. března 2009 13 Ř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í I, 3. března 2009 13 Ř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í I, 3. března 2009 13 Ř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í I, 3. března 2009 :ení běhu programu I true: cíl, který vždy uspěje 14 Ř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í I, 3. března 2009 14 Ř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í I, 3. března 2009 14 Ř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í I, 3. března 2009 14 Ř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í I, 3. března 2009 14 Ř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í I, 3. března 2009 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. 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í I, 3. března 2009 15 Řez, negace Seznamy Reprezentace seznamu -• Seznam: [a, b, c], prázdný seznam [] -• Hlava (libovolný objekt), tělo (seznam): .(Hlava, Telo) M všechny strukturované objekty stromy - i seznamy M funktor".", dva argumenty * .(a, .(b, .(c, []))) = [a, b, c] «• notace: [ Hlava | Telo ] = [a | Tel o] Hana Rudová, Logické programování I, 3. března 2009 17 Seznamy Reprezentace seznamu -• Seznam: [a, b, c], prázdný seznam [] -• Hlava (libovolný objekt), tělo (seznam): .(Hlava, Telo) M všechny strukturované objekty stromy - i seznamy M funktor".", dva argumenty * .(a, .(b, .(c, []))) = [a, b, c] «• notace: [ Hlava | Telo ] = [a | Tel o] Telo je v [a | Tel o] seznam, tedy píšeme [ a, b, c ] = [ a | [ b, c ] ] Hana Rudová, Logické programování I, 3. března 2009 17 Seznamy Reprezentace seznamu -• Seznam: [a, b, c], prázdný seznam [] -• Hlava (libovolný objekt), tělo (seznam): .(Hlava, Telo) M všechny strukturované objekty stromy - i seznamy M funktor".", dva argumenty * .(a, .(b, .(c, []))) = [a, b, c] «• notace: [ Hlava | Telo ] = [a | Tel o] Telo je v [a | Tel o] seznam, tedy píšeme [ a, b, c ] = [ a | [ b, c ] ] -• Lze psát i: [a,b|Telo] M 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í I, 3. března 2009 17 Seznamy Reprezentace seznamu -• Seznam: [a, b, c], prázdný seznam [] -• Hlava (libovolný objekt), tělo (seznam): .(Hlava, Telo) M všechny strukturované objekty stromy - i seznamy M funktor".", dva argumenty * .(a, .(b, .(c, []))) = [a, b, c] «• notace: [ Hlava | Telo ] = [a | Tel o] Telo je v [a | Tel o] seznam, tedy píšeme [ a, b, c ] = [ a | [ b, c ] ] -• Lze psát i: [a,b|Telo] M 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|[]] M pozor: [ [a,b] | [c] ] + [ a,b | [c] ] Hana Rudová, Logické programování I, 3. března 2009 17 Seznamy Reprezentace seznamu -• Seznam: [a, b, c], prázdný seznam [] -• Hlava (libovolný objekt), tělo (seznam): .(Hlava, Telo) M všechny strukturované objekty stromy - i seznamy M funktor".", dva argumenty * .(a, .(b, .(c, []))) = [a, b, c] «• notace: [ Hlava | Telo ] = [a | Tel o] Telo je v [a | Tel o] seznam, tedy píšeme [ a, b, c ] = [ a | [ b, c ] ] -• Lze psát i: [a,b|Telo] M 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|[]] M pozor: [ [a,b] | [c] ] + [ a,b | [c] ] -• Seznam jako neúplná datová struktura: [a,b,c|T] M Seznam = [a,b,c|T], T = [d,e|S], Seznam = [a,b,c,d,e|S] Hana Rudová, Logické programování I, 3. března 2009 17 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í I, 3. března 2009 18 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, 3. března 2009 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í I, 3. března 2009 18 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, 3. března 2009 18 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, 3. března 2009 18 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, 3. března 2009 18 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, 3. března 2009 18 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, 3. března 2009 18 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, 3. března 2009 18 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í I, 3. března 2009 19 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í I, 3. března 2009 19 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, 3. března 2009 19 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, 3. března 2009 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] ] -• 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, 3. března 2009 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] ] -• 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, 3. března 2009 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] ] -• 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, 3. března 2009 20 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í I, 3. března 2009 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 ). -• delete smaže libovolný výskyt prvku pomocí backtrackingu ?- delete(a, [a,b,a,a], S). S = [b,a,a] ; S = [a,b,a]; S = [a,b,a] Hana Rudová, Logické programování I, 3. března 2009 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 ). -• 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, 3. března 2009 21 Seznamy