IB013 Logické programovanie: zbierka príkladov 7. mája 2012 Zadania úloh pre prednášky 1 Unifikácia 1. Pre každú z nasledujúcich unifikácií rozhodnite, či uspeje. Ak áno, zapíšte výslednú substitúciu (a) pondelok = pondelok (b) 'Pondelok' = pondelok (c) 'pondelok' = pondelok (d) Pondelok = pondelok (e) pondelok = utorok (f) den(pondelok) = pondelok (g) den(pondelok) = X (h) den(X) = den(pondelok) (i) den(pondelok,X) = den(Y,utorok) (j) den(pondelok,X,streda) = den(Y,utorok,X) (k) den(pondelok,X,streda) = den(Y,štvrtok) (1) den(D) = D (m) vikend(den(sobota),den(nedela)) = vikend(X,Y) (n) vikend(den(sobota),X) = vikend(X,den(nedela)) 2 Backtracking, rez Fibonacciho postupnosti je postupnost čísel, ktorej prvé dva členy sú rovné 1 a každý další člen je súčtom dvoch predchádzajúcich (fíb(í) — 1, fib(2) — 1, fib(n) — fib(n — 1) + fib(n — 2), n > 2). 1. Nižšie uvedený logický program obsahuje predikát f ib/2, ktorý vypočíta n-tý člen Fibonacciho postupnosti. Program však nie je úplne korektný. Správnu hodnotu síce vypočíta, no ak si po jej nájdení vyžiadame pomocou ; dalšie riešenia, program sa zacyklí (správne by mal skončit s odpovedou no). Pridajte do programu na správne miesta operátory rezu tak, aby program v takýchto prípadoch necyklil. fib(N,l) :- N =< 2. fib(N,X) :- Nl is N-2, fib(Nl,1,1,X). fib(0,_A,X,X). fib(N,A,B,X) :- Nl is N-l, C is A+B, fib(Nl,B,C,X). 2. Zamyslite sa a zdôvodnite, prečo nasledujúci logický program, ktorý počíta n-tý člen Fibonacciho postupnosti priamo podlá definície, nie je vhodný (napriek tomu, že výsledok vypočíta vždy korektne) fib(l,l). fib(2,l). fib(N,X) :- N>2, Nl is N-l, N2 is N-2, fib(Nl,Y),fib(N2,Z),X is Y+Z. 1 IB013 Logické programovanie: zbierka príkladov 7. mája 2012 3 Rezolúcia 1. Nájdite (ak existuje) najobecnejší uniŕikátor a nasledujúcich literálov: (a) p(X) ap(/(y)) (b) p(X,f(X)) &p(f(X),Y) (c) p(X,Y)&p(Z,Z) (d) p(X,8) &p(Y,Y) (e) p(f(X)) &p(Z,Y) (f) p(f(Z),g(X))ap(Y,g(Y)) (g) p(X,g(Z),X) ap(f(Y),Y,W) 2. Na literáloch C\, C*2 vykonajte rezolúciu a nájdite rezolventu, jednotlivé kroky (premenovanie premenných, nájdenie naj obecnejšieho uniŕikátora, rezolučný princíp) rozpíšte: (a) Ci = {q(X),MY),P(f(Z)J(Z))} a C2 = {n(Y),^r(W),^p(f(W), f(W))} (b) d = {gpo,-r(y),p(x,y)} a c2 = {n(y),-r(iy),^(/(Ty),/(Ty))} 3. Pomocou lineárnej rezolúcie vyvrátte S = {{-tpQ}, {,(1)}, {c(l), c(2), ^(1)}, {t(0 ),-c(l)}, {í(l), -c(l)}, {í(0),^c(2)}, {í(2),^c(2)}} 4. Prepíšte nasledujúci program v prologovskej notácii ako množinu klauzulí. Následne na cieli ?- a. demonštrujte lineárnu rezolúciu. a :- b,c,d. b :- f. c. d. f. 5. Pomocou rezolučného princípu vyvrátte S — {{a, b}, {c, ~^b}, {^c}, {^a, d}, {^e}, {e, ^d}}. Existuje viacero možných riešení, skúste nájst čo najviac z nich. 6. Uvážme nasledujúci Prologovský program a dotaz ?- a. Nakreslite zodpovedajúci SLD strom. a :- b,c. a :- d. b. b :- d. c. d :- e. d. 7. Uvážme nasledujúci Prologovský program a dotaz ?- p (X, X). Nakreslite zodpovedajúci SLD strom. p(X,Y) :- q(X,Z), r(Z,Y). p(X,X) :- s(X). q(X,b). q(b,a). q(X,a) :- r(a,X). r (b,a) . 2 IB013 Logické programovanie: zbierka príkladov 7. mája 2012 s(X) :- t(X,a). s(X) :- t(X,b). s(X) :- t(X,X). t(a,b). t(b,a). 8. Do programu z predchádzajúcej úlohy pridajte 1 operátor rezu, tak aby výsledný program uspel práve dvakrát (pomôžte si nakresleným stromom z predchádzajúcej úlohy). Zadania úloh pre cvičenia 1 Backtracking, počítanie pomocou následníkov 1. Napíšte predikát convert/2, ktorý prevedie svoj prvý argument (prirodzené číslo) na reprezentáciu daného čísla pomocou následníkov. Napr.: ?-convert(3,X). X = s(s(s(0))) 2. Napíšte predikát geq/2, ktorý ako argumenty dostane 2 čísla zadané pomocou následníkov a uspeje, ak prvé číslo je väčšie alebo rovné druhému. Napr.: ?-geq(s(0),s(s(0))). no 3. Napíšte predikát sucet/3, ktorý vypočíta súčet dvoch čísel zadaných pomocou následníkov. Napr.: ?- sucet(s(0),s(s(0)),X). X = s(s(s(0))) 4. Napíšte predikát sucin/3, ktorý vypočíta súčin dvoch čísel zadaných pomocou následníkov. Napr.: ?- sucin(s(s(0)),s(s(0)),X) . X = s(s(s(s(0)))) 5. Zadaná je databáza faktov v tvare priamacesta(a,b), ktoré hovoria o tom, že existuje priama (jednosmerná) cesta z miesta a do miesta b. Napíšte predikát cesta/2 tak, že cesta(a,b) uspeje, ak existuje nejaká cesta (ktorá môže prechádzat cez lubovolný počet miest) z miesta a do miesta b. Môžete předpokládat, že cesty netvoria cykly (tzn. ak raz odídete z nejakého miesta, už sa tam nedá vrátit) Rozšírenie 1: Upravte vaše riešenie tak, že cesta(a,b,S). uspeje, ak existuje nejaká cesta a S je zoznam miest, cez ktoré táto cesta prechádza (ideálne v poradí, v akom ich prechádzame) Rozšírenie 2: Upravte vaše riešenie tak, aby fungovalo aj v prípade, že cesty tvoria cykly. 2 Aritmetika 1. Napíšte predikát mocnina/l, ktorý uspeje ak číslo zadané ako argument je mocninou dvojky (využite fakt, že mocniny dvojky je možné opakovane bez zvyšku delit dvomi až kým nedostaneme jednotku) 2. Napíšte predikát sucet/2, ktorý spočíta súčet prvých N prirodzených čísel. Napr.: ?- sucet(5,X). X = 15 3 IB013 Logické programovanie: zbierka príkladov 7. mája 2012 3. Napíšte predikát nsd/3, ktorý vypočíta najväčšieho spoločného delitela dvoch čísel. Napr.: ?- nsd(21,49,X). X = 7 Využite Euklidov algoritmus, ktorý je založený na pozorovaní, že najväčší spoločný dělitel čísel a, b kde a > b je rovnaký ako najväčší spoločný dělitel čísel (a — b), b 4. Napíšte predikát cif sucet/2, ktorý spočíta ciferný súčet zadaného čísla. Napr.: ?- cifsucet(12345,X). X = 15 3 Zoznamy 1. Napíšte predikát dvojnasobok/2, ktorý uspeje ak prvky v druhom zozname sú dvojnásobkami prvkov prvého zoznamu. napr. dvojnasobok( [5,3,2] , [10,6,4] ) uspeje, ale dvojnasobok( [1,2,3] , [2,4,5] ) neuspeje 2. Napíšte predikát f ilter/2, ktorý zo zoznamu odstráni všetky nečíselné hodnoty, napr.: ?- filter([5,s(0),3,a,2,A,7] ,X). X = [5,3,2,7] 3. Napíšte predikát cifry/2, ktorý zo zoznamu cifier vybuduje číslo, napr.: ?- cifry([2,8,0,7],X). X = 2807 4. Napíšte predikát nty/3, ktorý vráti n-tý prvok zoznamu, napr.: ?- nty(4,[5,2,7,8,0],N). N = 8 5. Napšte predikát rovnaju_sa/2, ktorý uspeje, ak sa dva zadané zoznamy rovnajú. V prípade, že sa zoznamy nerovnajú, vypíšte dôvod, prečo je to tak (jeden zoznam je kratší ako druhý, výpis prvých 2 prvkov, ktoré sa nerovnajú...) Môžete předpokládat, že zoznamy neobsahujú premenné. Napríklad: ?- rovnaju_sa([5,3,7],[5,3,7]). yes ?- rovnaju_sa([5,3,7],[5,3,7,2]). 1. zoznam je kratsi no ?- rovnaju_sa([5,3,7],[5,2,3,7]). 3 sa nerovná 2 no 6. Napíšte predikát priemer/2, ktorý vypočíta aritmetický priemer zadaného zoznamu. Napr.: ?- priemer([1,2,3,4,5,6],X). X = 3.5 7. Napíšte predikát insert/3, ktorý do usporiadaného zoznamu čísel vloží dalšie číslo tak, aby aj výsledný zoznam bol usporiadaný. Napr.: ?- insert(7,[1,2,3,10,12],X). X = [1,2,3,7,10,12] 4 IB013 Logické programovanie: zbierka príkladov 7. mája 2012 4 D C gramatiky 1. Napíšte DCG pre rozpoznávanie párnych (=sudých) binárnych čísel. 2. Napíšte DCG rozpoznávajúcu palindrómy pozostávajúce z písmen a, b (palindróm je slovo, ktoré sa číta rovnako od začiatku aj od konca. Napr. [] , [a,b,a] , [a,b,b,a] sú palindrómy, ale [a,b,b] palindróm nie je) 3. Napíšte DCG pre jazyk, ktorý obsahuje slová v tvare anbm kde m > n (pomôcka: vyskúšajte najprv jazyk slov v tvare anbn) 4. Napíšte DCG pre jazyk slov v tvare anb2n. 5. Napíšte DCG pre jazyk slov v tvare a™6™+1c™+2. 6. Prevedte nasledujúcu gramatiku na predikáty s rozdielovými klauzulami: s —> np, vp. np —> det, n. vp —> tv, np. vp —> v. det — > [the] . det — > [a] . det —> [every]. n —> [man] . n —> [woman]. n —> [park] . tv —> [loves]. tv —> [likes]. v —> [walks]. 7. Nakreslite derivačný strom pre nejakú vetu rozpoznávanú gramatikou z predchádzajúcej úlohy. 8. Napíšte, aké termy zodpovedajú nasledujúcim derivačným stromom: 5 IB013 Logické programovanie: zbierka príkladov 7. mája 2012 Exp S Sub Yesterday NP VP Add Num John V NP Exp Exp 4 saw Det NP Num Mul a Adj NP 5 Exp Exp good N Num Num movie 7 2 9. Pre prvý strom z predchádzajúcej úlohy zostrojte zodpovedajúcu gramatiku s vytváraním derivačného stromu (tzn. tak aby derivačný strom vety "Yesterday John saw a good movie" zodpovedal znázornenému - overte si to v Prologu). Nevadí, ak vaša gramatika bude generovat aj iné, nezmyselné vety. 6 IB013 Logické programovanie: zbierka príkladov 7. mája 2012 5 Logické programovanie s obmedzujúcimi podmienkami 1. Vyriešte pomocou Prologu nasledujúci algebrogram: KC + I = OK + + + A + A = KM OL + KO = LI 2. Vyriešte pomocou Prologu nasledujúcu variáciu (jednu z mnoha) známej Einsteinovej hádanky: Je rada piatich domov, pričom každý má inú farbu. V týchto domoch žije pät ludí rôznych národností. Každý z nich chová iné zviera, rád pije iný nápoj a fajčí iné cigarety. I. Brit býva v červenom dome. II. Švéd chová psa. III. Dán pije čaj. IV. Zelený dom stojí hneď vlavo od bieleho. V. Majitel zeleného domu pije kávu. VI. Ten, kto fajčí Pall Mail, chová vtáka. VIL Majitel žltého domu fajčí Dunhill. VIII. Človek z prostredného domu pije mlieko. IX. Nór býva v prvom dome. X. Ten, kto fajčí Blend, býva vedia toho, kto chová mačku. XI. Ten, kto chová kone, býva vedia toho, kto fajčí Dunhill. XII. Ten, kto fajčí Blue Master, pije pivo. XIII. Nemec fajčí Prince. XIV. Nór býva vedia modrého domu. XV. Ten, kto fajčí Blend, má suseda, ktorý pije vodu. Kto chová rybičky? Úloha má jediné riešenie, je možné jednoznačne určit všetky informácie, nielen informáciu o tom, kto chová rybičky. Najzložitejšou častou úlohy teda je zvolit si správnu reprezentáciu zadaných faktov, následne je zvyšok relatívne jednoduchý. Ak sa vám to nedarí, pri riešení v závere zbierky nájdete nápovědu. Riešenia úloh pre prednášky 1 Unifikácia 1. výsledky si lahko overíte v prologu 2 Backtracking, rez 1. fib(N,l) :- N =< 2, ! . fib(N,X) :- Nl is N-2, fib(Nl,1,1,X). fib(0,_A,X,X) :- !. fib(N,A,B,X) :- Nl is N-l, C is A+B, fib(Nl,B,C,X). 7 IB013 Logické programovanie: zbierka príkladov 7. mája 2012 2. Program je velmi neefektívny (až exponenciálna zložitosť), pretože hodnoty predchádzajúcich členov postupnosti sa počítajú opakovane. Najlepšie to uvidíte, ak si nakreslíte strom výpočtu pre nejaké malé N, napr. 6. Takto zapísaný program navyše neumožňuje optimalizáciu posledného volania. 3 Rezolúcia 1. (a) o = [X/f (Y)] (b) neexistuje (c) a — [X/Z, Y/Z] (d) B, Al is A-B, nsd(Al,B,X). nsd(A,B,X) :- B>A, BI is B-A, nsd(A,Bl,X). Dodajme, že existuje efektívnejšia verzia využívajúca zvyšky po delení. 4. cifsucet(N,CS) :- cifsucet(N,0,CS). cifsucet(0,CS,CS) :- !. cifsucet(N,X,CS) :- XI is X + N mod 10, Nl is N //10, cifsucet(Nl,Xl,CS). 3 Zoznamy 1. dvoj násobok ([],[]) . dvojnasobok([Xl|Tl],[X2IT2]) :- X2 is 2*X1, dvojnasobok(Tl,T2). 2. filter([],[]). filter([X|Tl],[X|T2]) :- number(X), !, filter(Tl,T2). filter([_X|Tl],T2) :- filter(Tl,T2). 3. cifry(S,X) :- cifry(S,0,X). cifry([] ,X,X) . cifry( [AlT],P,X) :- PI is 10*P + A, cifry(T,Pl,X). 4. nty(N,[X|_T],Y) :- N =< 1, !, X = Y. nty(N,[_X|T],Nty) :- Nl is N-l, nty(Nl,T,Nty). 5. rovnaju_sa( [],[]). rovnaju_sa([XlTl] ,[X|T2]) :- !, rovnaju_sa(Tl,T2). rovnaju_sa([],_S) :- write('l. zoznam je kratsi'), !, fail. rovnaju_sa(_S,[]) :- write('2. zoznam je kratsi'), !, fail. rovnaju_sa([X|_T1],[Y|_T2]) :- write(X), write(' sa nerovná '), write(Y), !, fail. Pre úplnost dodajme, že ak by sme nepožadovali výpis dôvodu nerovnosti, vystačili by sme si s faktom rovnaju_sa(S,S). (ak S neobsahuje premenné) 6. priemer(S,X) :- priemer(S,0,0,X). priemer([],Sum,Count,X) :- X is Sum/Count. priemer([H|T],Sum,Count,X) :- Suml is Sum+H, Countl is Count+1, priemer(T,Suml,Countl,X). 7. insert (X, [] , [X] ) . insert (X, [H I T] , [X, HI T] ) :-X= [0] . parne —> [1], parne. parne —> [0], parne. 2. Výsledná gramatika môže vyzerat takto: palindrom —> [] . palindrom —> [a] . palindrom —> [b] . palindrom —> [X],palindrom,[X], {member(X,[a,b])}. (posledný riadok je možné nahradit dvoma rozpísaním možných hodnôt X) 3. Pre jazyk anbn napíšeme gramatiku an_bn —> [] . an_bn —> [a],an_bn,[b]. Gramatiku pre jazyk anbm kde m > n potom môžeme zadeŕinovat nasledujúcim spôsobom: an_bm —> an_bn, same(b). Pričom same definujeme ako same(_X) — > [] . same(X) —> [X],same(X). (teda trochu inak ako bol definovaný na cvičeniach) 4. an_b2n — > [] . an_b2n —> [a],an_bn,[b],[b]. 5. Jedno z možných riešení je velmi podobné riešeniu pre jazyk anbncn, ktoré bolo uvedené na cvičeniach. Nižšie uvedené riešenie je založené na rovnakej myšlienke (tzn. pomocou následníkov), avšak je zapísané stručnejším spôsobom pomocou pomocného neterminálu repeat: abc —> repeat(a,X), repeat(b,s(X)), repeat(c,s(s(X))). repeat(_,0) —> [] . repeat(A,s(X)) —> [A],repeat(A,X). 6. s(S0,S) :- np(S0,Sl), vp(Sl,S). np(S0,S) :- det(S0,Sl), n(Sl,S). vp(S0,S) :- tv(S0,Sl), np(Sl,S). vp(S0,S) :- v(S0,S). det([the|S],S). det([a|S],S). det([everyI S],S). n([man|S],S). n([womanlS] ,S) . n([park|S],S). tv([lovesI S] , S) . tv([likes|S],S) . v([walks|S],S) . 12 IB013 Logické programovanie: zbierka príkladov 7. mája 2012 7. závisí od vybranej vety 8. S (Ad (Yesterday), SI (NP ( N (John) ), VP (V (saw), NP (Det (a), NP (Adj (good), NP (N (movie))))))) Exp( Sub(Exp( Add(Expr(Num(5)),Exp( Mul(Expr(Num(7)),Exp( Num(2))))))),Exp( Num(4))) 9. sentence(s(Ad,S)) —> adverb(Ad), sentencel(S). adverb(ad(yesterday)) —> [yesterday]. sentencel(sl(NP,VP)) —> noun_phrase(NP), verb_phrase(VP). noun_phrase(np(N)) —> noun(N). noun_phrase(np(Det,NP)) —> determiner(Det), noun_phrase(NP). noun_phrase(np(Adj,NP)) —> adjective(Adj), noun_phrase(NP). determiner(det(a)) —> [a], adjective(adj(good)) —> [good], noun(n(john)) —> [john]. noun(n(movie)) —> [movie]. verb_phrase(vp(V,NP)) —> verb(V), noun_phrase(NP). verb(v(saw)) —> [saw]. 5 Logické programovanie s obmedzujúcimi podmienkami 1. alg([K,C,I,0,A,M,L]) :- domain([K,1,0,A,L],1,9), domain([C,M],0,9), all_distinct([K,C,I,0,A,M,L]), 10*K + C + I #= 10*0 + K, A + A #= 10*K + M, 10*0 + L + 10*K + 0 #= 10*L + I, 10*K + C + A #= 10*0 + L, I + A #= 10*K + 0, 10*0 + K + 10*K + M #= 10*L + I, labeling([],[K,C,1,0,A,M,L]). 2. Nápověda: Domy si môžeme očíslovat zlava doprava číslami 1 až 5. Pre každú národnost, farbu, zviera, nápoj a cigarety si vytvoríme premennú, ktorá bude nadobúdat hodnoty 1 až 5 podlá príslušného domu. Následne môžeme napríklad obmedzenie "človek z prostredného domu pije mlieko" zapísat ako Mlieko #= 3 a obmedzenie "Brit býva v červenom dome" ako Brit #= Červeny. Kompletné riešenie: einstein([Nor,Brit,Sved,Dan,Nemec, Červeny,Zeleny,Zity,Modry,Biely, Caj,Kava,Mlieko,Pivo,Voda, Pes,Vták,Macka,Kon,Ryba, Pallmall,Dunhill,Blend,Bluemaster,Prince]):-Vals = [Nor,Brit,Sved,Dan,Nemec, Červeny,Zeleny,Zity,Modry,Biely, Caj,Kava,Mlieko,Pivo,Voda, Pe s,Vtak,Macka,Kon,Ryba, Pallmall,Dunhill,Blend,Bluemaster,Prince], domain(Vals,1,5), 13 IB013 Logické programovanie: zbierka príkladov 7. mája 2012 all_distinct([Nor,Brit,Sved,Dan,Nemec]), all_distinct([Červeny,Zeleny,Zity,Modry,Biely] ) , all_distinct([Caj,Kava,Mlieko,Pivo,Voda] ), all_distinct([Pes,Vták,Macka,Kon,Ryba] ), all_distinct([Pallmall,Dunhill,Blend,Bluemaster,Prince]), 7«Brit byva v červenom dome. Brit #= Červeny, 7«Sved chova psa. Sved #= Pes, 7«Dan pije caj . Dan #= Caj, 7«Zeleny dom stoji hned vlavo od bieleho. Zeleny #= Biely - 1, 7«Majitel zeleného domu pije kavu. Zeleny #= Kava, °/«Ten, kto fajči Pall Mail, chova vtáka. Pallmall #= Vták, 7«Majitel zlteho domu fajči Dunhill. Zity #= Dunhill, Vdovek z prostredného domu pije mlieko. Mlieko #= 3, 7«Nor byva v prvom dome. Nor #= 1, °/«Ten, kto fajči Blend, byva vedia toho, kto chova macku. (Blend #= Macka+1 ; Blend #=Macka-l), 7«Ten, kto chova kone, byva vedia toho, kto fajči Dunhill. (Kon #= Dunhill+1 ; Kon#=Dunhill-l), 7«Ten, kto fajči Blue Master, pije pivo. Bluemaster #= Pivo, "/oNemec fajči Prince. Nemec #= Prince, y«Nor byva vedia modrého domu. (Nor #= Modry + 1 ; Nor #= Modry-1 ), y«Ten, kto fajči Blend, ma suseda, ktorý pije vodu. (Blend #= Voda + 1; Blend#= Voda-1), labeling([],Vals). 14