x. father(john). father(John). father(x, y).Ga na of mother(abraham,isaac) een instantie is van
mother(X,isaac) mother(X,X) mother(Y,X) X(abraham, isaac)Ga ook na of mother(abraham,isaac) een gemeenschappelijke instantie is van
mother(X,isaac) en mother(Y,isaac) mother(X,isaac) en mother(abraham,X) mother(X,isaac) en mother(abraham,Y) mother(X,Y) en mother(abraham,X) mother(abraham,Z) en mother(Y,X)Uitwerkingen
kleur(rood).
kleur(blauw).
kleur(groen).
kleur(geel).
% kaart(Gr,Fr,Dr,Ov,Ge,Fl,Nb,Ut,Nh,Zh,Lb,Zl) :-
% de provincies Groningen,...,Zeeland, aangeduid door de variabelen
% Gr,...,Zl, krijgen een kleur toegewezen zodanig dat aangrenzende
% provincies verschillende kleuren krijgen.
kaart(Gr,Fr,Dr,Ov,Ge,Fl,Nb,Ut,Nh,Zh,Lb,Zl) :-
Gr \== Fr, Gr \== Dr,
Fr \== Dr, Fr \== Ov, Fr \== Fl,
Dr \== Ov,
Ov \== Fl, Ov \== Ge,
Ge \== Ut, Ge \== Fl, Ge \== Nb, Ge \== Lb, Ge \== Zh,
Fl \== Nh, Fl \== Ut,
Nb \== Zh, Nb \== Zl, Nb \== Lb,
Ut \== Nh, Ut \== Zh,
Nh \== Zh,
Zh \== Zl,
kleur(Gr), kleur(Fr), kleur(Dr), kleur(Ov),
kleur(Ge), kleur(Fl), kleur(Nb), kleur(Ut),
kleur(Nh), kleur(Zh), kleur(Lb), kleur(Zl).
Hoeveel kleuren zijn er eigenlijk minimaal nodig om deze kaart te kleuren?
Hoeveel verschillende oplossingen zijn er voor het minimale aantal kleuren?
% natural_number(N) :- N is een natuurlijk getal. natural_number(0). natural_number(s(X)) :- natural_number(X). % plus(X,Y,Z) :- % Z is de som van de natuurlijke getallen X en Y. plus(0,X,X) :- natural_number(X). plus(s(X),Y,s(Z)) :- plus(X,Y,Z). % times(X,Y,Z) :- % Z is het produkt van de natuurlijke getallen X en Y. times(0,X,0) :- natural_number(X). times(s(X),Y,Z) :- times(X,Y,XY), plus(XY,Y,Z). f(0,s(0)). f(s(N),F) :- f(N,F1), times(s(N),F1,F). % leq(X,Y) :- % X en Y zijn natuurlijke getallen % met X kleiner dan of gelijk aan Y. leq(0,X) :- natural_number(X). leq(s(X),s(Y)) :- leq(X,Y).Wat is de betekenis van f(N,X)?
% pos_nat(N) :- N is een positief natuurlijk getal. pos_nat(1). pos_nat(X+1) :- pos_nat(X).
% conv(T,N) :- conversie tussen termrepresentatie T en % standaardrepresentatie N van een getal. conv(0,0). conv(s(X),Y) :- conv(X,Z), Y is Z+1. % is/2 wordt later uitgelegdis het mogelijk om van die vermoeiende s(s(s(...-notatie af te komen. Definieer nu, met gebruikmaking van plus,times,fib , predikaten cplus/3, ctimes/3, cfib/2 die zich ongeveer zo gedragen als plus, times, fib maar dan met de gebruikelijke getalnotatie.
% list(X) :- X is een lijst. list([]). list([X|Xs]) :- list(Xs). % member(X,Ys) :- X is een element in lijst Ys. member(X,[X|Xs]). member(X,[Y|Ys]) :- member(X,Ys). % prefix(Xs,Ys) :- Xs is een prefix (beginstuk) van lijst Ys. prefix([],Ys). prefix([X|Xs],[X|Ys]) :- prefix(Xs,Ys). % suffix(Xs,Ys) :- Xs is een suffix (eindstuk) van lijst Ys. suffix(Xs,Xs). suffix(Xs,[Y|Ys]) :- suffix(Xs,Ys). % sublist(Xs,Ys) :- Xs is een aaneengesloten deellijst van Ys. sublist(Xs,Ys) :- prefix(Xs,Ys). sublist(Xs,[Y|Ys]) :- sublist(Xs,Ys). sublist2([],Ys). sublist2(Xs,[Y|Ys]) :- sublist2(Xs,Ys). sublist2([X|Xs],[X|Ys]) :- sublist2(Xs,Ys). % append(X,Ys,Zs) :- Zs ontstaat uit lijst Ys % door toevoeging van X aan het begin van Ys. append([],Ys,Ys). append([X|Xs],Ys,[X|Zs]) :- append(Xs,Ys,Zs).Hebben sublist en sublist2 dezelfde betekenis?
% adjacent(X,Y,Zs) :- X en Y komen naast elkaar in lijst Zs voor. % last(X,Zs) :- X is het laatste element van lijst Zs. % double(Xs,Ys) :- Ys ontstaat uit lijst Xs door elk element te herhalen, % dus bv. double([1,2,3,3],[1,1,2,2,3,3,3,3]).Maak hierbij geen gebruik van append.
% sum(N,Xs) :- N is de som van de elementen van de % lijst van natuurlijke getallen Xs.Doe dit op twee manieren: (i) mbv. plus/3; (ii) zonder hulppredikaat, met slechts drie axioma's.
% delete(L,X,LminX) :- LminX ontstaat uit lijst L door % alle voorkomens van X te verwijderen. % substitute(X,Y,LmetYipvX) :- LmetYipvX ontstaat uit lijst L % door alle voorkomens van X door Y te vervangen. % no_doubles(Xs,Ys) :- Ys ontstaat uit Xs % door van elk element met n+1 voorkomens % n voorkomens weg te laten. % swap(XaYbZ,XbYaZ) :- lijst XaYbZ ontstaat % uit lijst XbYaZ door verwisseling % van twee elementen. % even_permutation(L,M) :- M is een permutatie % van L die het resultaat is van een even % aantal verwisselingen. % odd_permutation(L,M) :- M is een permutatie % van L die het resultaat is van een oneven % aantal verwisselingen. % merge(Xs,Ys,Ms) :- Ms is de gesorteerde % samenvoeging van de gesorteerde % lijsten Xs en Ys.Definieer mergesort/2 met gebruikmaking van merge, op twee manieren: (i) nondeterministisch, met gebruikmaking van append; (ii) deterministisch, met gebruikmaking van split/3, gedefineerd door
% split(Xs,As,Bs) :- As bevat de elementen % van Xs die op oneven posities staan, % Bs de elementen van Xs op even posities.
% binary_tree(B) :- B is een gelabelde binaire boom, % opgebouwd mbv. de functor tree/3: % tree(X,L,R) denoteert en boom met label X, % linker subboom L en rechter subboom R. binary_tree(void). binary_tree(tree(X,L,R)) :- binary_tree(L), binary_tree(R).Definieer nu de volgende predikaten:
% subtree(S,T) :- S en T zijn binaire bomen % en S is een deelboom van T, dwz. de % wortel van S is een knoop van T. % sum_tree(T,S) :- T is een binaire boom met natuurlijke getallen als labels, % en S is de som van de getallen in de knopen van T. % path(X,T,L) :- lijst L is het pad dat loopt van de wortel % van binaire boom T naar de knoop met label X.
%% union(B,C,D) :- bag D ontstaat uit bag B %% en bag C door voor alle elementen als %% multipliciteit de som van de %% multipliciteiten in B en C te nemen.Aanwijziging: gebruik het hulppredikaat
%% elem_union(X,N,B,C) :- bag C ontstaat %% uit bag B door de multipliciteit %% van X met N te verhogen.Definieer op analoge wijze de doorsnede van twee bags:
%% intersect(B,C,D) :- bag D is de doorsnede %% van bag B en bag C.Definieer predikaten die een lijst resp. een binaire boom in een bag omzetten.
%% goodbag(B) :- B is een nette bag-structuur, %% waarin elk element hoogstens een keer %% voorkomt, met multipliciteit >= 1.Aanwijzing: gebruik het predikaat
%% not_in(X,B) :- X is not in bag B.Definieer vervolgens:
%% norm(B,Bn) :- Bn is een nette variant van bag B, %% ontstaan door verwijderen van elementen met %% multipliciteit 0 en wegwerken van meervoudige %% voorkomens van elementen.
?- verdeel([jan,anna,kees],[tol,pop,auto],X). X = [speelt_met(jan,tol), speelt_met(anna,auto), speelt_met(kees,pop)]); X = [speelt_met(jan,auto), speelt_met(anna,tol), speelt_met(kees,pop)]); etc...Een naieve aanpak zal redundante oplossingen opleveren: als lijst verschillend, maar als verzameling gelijk. Een methode om dit te voorkomen is: ga uit van de structuur (in dit geval de volgorde) van de representatie van de input, en hanteer die bij het samenstellen van de oplossingen. In dit geval: ga uit van de volgorde van de lijst van kinderen, en zorg ervoor dat de lijst termen van de vorm speelt_met(ki,sj) in die volgorde komt te staan. Het kan daarbij handig zijn gebruik te maken van het volgende hulppredikaat
% select(X,L,LzonderX) :- LzonderX ontstaat uit lijst L door een voorkomen van X weg te nemen.
Val is expris dat de aritmetische expressie expr uitgerekend wordt (dat betekent oa. dat alle variabelen een aritmetische waarde moeten hebben) en dat het resultaat geunificeerd wordt met Val. Met behulp hiervan kan de faculteitsfunctie als volgt gedefinieed worden:
% factorial(N,F) :- F equals N!. factorial(0,1). factorial(N,F) :- N > 0, N1 is N-1, factorial(N1,F1), F is N*F1.Definieer nu soortgelijke programma's voor
% triangle(N,T) :- T is het N-de driehoeksgetal, dwz. % de som van de getallen 1 t/m N. % power(X,N,P) :- P is X tot de macht N % (N een natuurlijk getal).Ter wille van de efficientie kan het handig zijn om recursie te vervangen door iteratie mbv. een accumulator. Voor de faculteitsfunctie ziet dat er als volgt uit:
% iterfac(N,F) :- F equals N!, berekend mbv. iteratie. iterfac(N,F) :- fac(N,1,F). % fac(N,M,F) :- F equals N! * M. fac(0,M,M). fac(N,M,F) :- N > 0, M1 is M*N, N1 is N-1, fac(N1,M1,F).Definieer nu soortgelijke programma's voor triangle, power.
Voeg cuts toe in de volgende programma's:
% partition(Xs,Y,Littles,Bigs) :- (Littles,Bigs) is een partitie % van Xs, alle elementen van Littles zijn kleiner dan of gelijk % aan Y, alle elementen van Bigs zijn groter dan Y. partition([X|Xs],Y,[X|L],B) :- X =< Y, partition(Xs,Y,L,B). partition([X|Xs],Y,L,[X|B]) :- X > Y, partition(Xs,Y,L,B). partition([],Y,[],[]). % inssort(Xs,Ys) :- Ys is een geordende permutatie van Xs, % verkregen dmv. insertion sort. inssort([X|Xs],Ys) :- inssort(Xs,Zs), insert(X,Zs,Ys). inssort([],[]). % insert(X,Ys,Zs) :- de gesorteerde lijst Zs ontstaat uit % de gesorteerde lijst Ys door X in te voegen. insert(X,[],[X]). insert(X,[Y|Ys],[Y|Zs]) :- X > Y, insert(X,Ys,Zs). insert(X,[Y|Ys],[X,Y|Ys]) :- X =< Y.Wat is er mis met het volgede programma?
% minimum(X,Y,Z) :- Z is het minimum van X en Y. minimum(X,Y,X) :- X =< Y, !. minimum(X,Y,Y).Aanwijzing: wat gebeurt er met bv. minimum(1,2,2)?.
% minimum(X,Y,Z) :- Z is het minimum van X en Y. minimum(X,Y,Z) :- X =< Y, !, Z = X.
% union_intersect(Xs,Ys,Us,Is) :- Us is de vereniging en % Is is de doorsnede van Xs en Ys. union_intersect([],Ys,Ys,[]). union_intersect([X|Xs],Ys,Us,[X|Is]) :- member(X,Ys), union_intersect(Xs,Ys,Us,Is). union_intersect([X|Xs],Ys,[X|Us],Is) :- not member(X,Ys), union_intersect(Xs,Ys,Us,Is).Breid dit programma uit met het verschil van Xs en Ys.
% binary_tree(B) :- B is een gelabelde binaire boom, % opgebouwd mbv. de functor tree/3: % tree(X,L,R) denoteert en boom met label X, % linker subboom L en rechter subboom R. binary_tree(void). binary_tree(tree(X,L,R)) :- binary_tree(L), binary_tree(R).De opdracht luidt nu: schrijf een programma dat in 1 pass het volgende oplevert:
% maxval(T,TM) :- TM ontstaat uit binaire boom T (met natuurlijke getallen als labels) % door alle labels te vervangen door de maximale in T voorkomende labelwaarde.In twee passes is dit niet moeilijk, maar in een (1) pass? Het te ontwikkelen programma moet, gegeven een binaire boom, twee dingen doen:(i) bepalen van Max, het maximum van de labels van de boom; (ii) vervangen van alle labels door Max. Dit kan iets algemener worden geformuleerd: (i) bepalen van Max; (ii) alle labels vervangen door een vaste waarde Val. Dit leidt tot twee programma's tmax/2, tval/3 met dezelfde structuur:
% tmax(T,M) :- M is de maximale waarde van labels in binaire boom T. % tval(T,X,TX) :- TX ontstaat uit binaire boom T door alle labels % door X te vervangen.Vervolgens kunnen tmax en tval in elkaar geschoven worden tot
% tmaxval(T,M,X,TX) :- M is de maximale waarde van labels in binaire boom T, % en TX ontstaat uit T door alle labels door X te vervangen.Ten slotte kunnen we maxval verkrijgen door, in de aanroep van tmaxval, op de posities 2 en 3 dezelfde variabele in te vullen.
oplossing(X) :- genereer(X), test(X).Het volgende programma kan gebruikt worden om de gehele getallen in een interval te genereren:
% between(I,J,K) :- I,J,K zijn gehele getallen met I =< J =< K. between(I,I,K) :- I =< K. between(I,J,K) :- I < J, I1 is I + 1, between(I1,J,K).Gebruik dit programma om, met de generate-and-test methode, de geheeltallige wortel van een getal te bepalen:
% wortel(N,W) :- W is een geheel getal met W^2 =< N < (W + 1)^2 % dus een benadering van de wortel uit N