Correction de la question II du TP3
ensemble ([]).
ensemble ([T|Q]) :- hors (T,Q) , ensemble (Q).
supprimer (_ ,[] ,[]).
supprimer (X ,[X|L1],L2) :- supprimer (X,L1 ,L2 ).
supprimer (X ,[T|L1 ],[T|L2 ]) :- supprimer (X,L1 ,L2), X \= T.
listeEnsemble ([] ,[]).
listeEnsemble ([T|Q1 ],[T|Q2 ]) :- supprimer (T,Q1 ,Q), listeEnsemble (Q,Q2 ).
intersection ([] ,_ ,[]).
intersection ([T|Q],L ,[T|Q1 ]) :- appartient (T,L), supprimer (T,L,QL), intersection (Q,QL ,Q1 ).
intersection ([T|Q],L,Q1) :- hors (T,L), intersection (Q,L,Q1 ).
union ([] ,L,L).
union ([T|Q],L ,[T|Q1 ]) :- supprimer (T,L,QL), union (Q,QL ,Q1 ).
Implantation de hors(T,L), deux solutions :
Solution1 :
hors(T,L) :- not(appartient(T,L)).
Solution2 :
hors(T,L) :- appartient(T,L), !, fail.hors(_,_).
I- Soit le puzzle logique suivant :
TP Prolog 3
Trois personnes, de nationalités différentes (anglaise, espagnole et française) et pratiquant des sports différents (football, natation et tennis), habitent dans trois maisons de couleurs distinctes (blanc, bleu, vert). Ces trois maisons sont situées dans la même rue ; une des maisons est située au début de la rue, une autre au milieu, et la troisième au bout de la rue.
On caractérise chacune des 3 maisons par un triplet m(C, N, S), où C est la couleur de la maison, N et S la nationalité et le sport pratiqué par son occupant.
-
1- Définir le prédicat tableau(Rue) où Rue est la liste des maisons qui satisfont à la
description précédente. L’ordre des éléments dans la liste correspond à l’ordre des
maisons dans la rue. Il y a a priori 216 combinaisons possibles.
Exemple :
?- tableau(R).
R = [m(blanc, anglais, football), m(bleu, espagnol, natation), m(vert, français, tennis)] ;
…
R = [m(bleu, espagnol, natation), m(blanc, anglais, football), m(vert, français, tennis)] ;
…
R = [m(vert, français, tennis), m(bleu, espagnol, natation), m(blanc, anglais, football)] ; false. - 2- On dispose des 5 indices suivants :
– Dans la maison verte on pratique la natation.
– La maison verte est située avant la maison de l’espagnol.
– L’anglais habite la maison blanche.
– La maison blanche est située avant la maison où on pratique le football.
– Le tennisman habite au début de la rue.
Définir le prédicat puzzle(Rue) où Rue est la liste des maisons qui vérifient les indices
précédents. L’ordre des éléments dans la liste correspond à l’ordre des maisons dans la rue.
Chaque indice doit trouver sa traduction Prolog dans la définition du prédicat puzzle/1.
Exemple :
?- puzzle(R).
R = [m(blanc, anglais, tennis),
m(vert, francais, natation),
m(bleu, espagnol, football)] ;
false.
Indications : On utilisera le prédicat appartient (X, L) et on écrira le prédicat precede (T, T1, L) qui est vrai si T précède T1 dans la liste L.
II- Un ensemble est représenté ici par une liste Prolog dont les éléments sont tous différents les uns des autres. Définir les prédicats suivants :
1. ensemble(L) : la liste L représente un ensemble. ?- ensemble([a,b,c]).
true ;
false.
?- ensemble([a,b,a,c]).
false.
2. listeEnsemble(L,E) : la liste L est transformée en un ensemble E. ?- listeEnsemble([a,b,a,c,a,a],
[a,b,c]).
true ;
false.
?- listeEnsemble([a,b,a,c,a,a],E).
E = [a, b, c] ;
false.
3. intersection(E1,E2,E3) : E3 contient l’intersection de 2 ensembles.
?- intersection([a,b,c],[b,d,a],
[a,b]
).
true ;
false.
?- intersection([a,b,c],[b,d,a],E3).
E3 = [a, b] ;
false.
4. union(E1,E2,E3) : E3 contient l’union de 2 ensembles. ?- union([a,b,c],[b,d,a],
[a,b,c,d]).
true ;
false.
?- union([a,b,c],[b,d,a],E3).
E3 = [a, b, c, d] ;
false.
Indications : On aura besoin du prédicat appartient (X, L) qui est vrai si X appartient à la liste L etdu prédicat supprime (X, L, QL) qui renvoie dans QL la liste L dont a supprimé les occurrences deX.
Licence d’Informatique 2011/2012 Logique et Programmation Logique Universit ́e de Strasbourg
Travaux Pratiques en Logique : Prolog (2)
1 Automate
Le but est d’ ́ecrire un automate capable de reconnaˆıtre un mot d’un langage donn ́e. L’automate constituera la base de fait du programme
ex :
entr(et1).
sort(et3).
existe(et1, a, et2).
existe(et2, b, et3).
existe(et3, a, et3).
Compl`eter ce programme et d ́efinir le pr ́edicat reconnaˆıtre(l) ou` l est une liste de lettres correspondant au mot `a reconnaˆıtre.
2 Listes
Une liste en Prolog est construite r ́ecursivement `a l’aide d’un foncteur de la forme : [ | ] la premi`ere place (premier underscore) indiquant le premier ́el ́ement de la liste et la deuxi`eme place la liste des ́el ́ements restants : c’est une liste. La liste vide est not ́ee []. En typant ces op ́erations, on aurait :
[] : -> liste
[_ | _] : element liste ->liste
Cette ́ecriture peut ˆetre all ́eg ́ee en prolog. Ainsi la liste [1 | [2 | [ 3 | []]]] peut aussi s’ ́ecrire :
[1,2,3].
a) D ́efinissez un pr ́edicat donnant la longueur d’une liste.
b) D ́efinissez un pr ́edicat de la forme estdans(Elem, Liste) r ́eussissant si l’ ́el ́ement est dans la liste.
Donnez des clauses d ́efinissant un pr ́edicat permettant de trouver le n`eme ́el ́ement d’une liste (et qui
́echoue si la liste est trop petite).
c) E ́crivez un programme prolog permettant de concat ́ener deux listes.
d) D ́efinir le pr ́edicat Prolog Somele(P,n) qui pour toute liste d’entiers l, renvoie dans n la somme des
́el ́ements de l.
ex : Somele([1,2,3,4,5], N).
renvoie N=15
e) D ́efinir le pr ́edicat Prolog compte-aa(l,n) qui pour toute liste d’identificateurs l renvoie dans N le
nombre d’occurences de aa dans l.
ex : compte-aa([bb,aa,bb,aa,cc,aa], N).
renvoie N=3
Correction exercices sur les listes Prolog
-
1- longueur([],0).
longueur([_|R],X) :- longueur(R,Y), X is Y+1. -
2- nieme([X|_],0,X).
nieme([_|R], Y, X) :- nieme(R,Z,X), Y is Z+1. -
3- monconcat([],X,X).
monconcat([X|Q1], Y, [X|Q2]) :- monconcat(Q1, Y, Q2). -
4- someleb([],N,N).
someleb([X|L], N, N0) :- N1 is X+N, somele(L, N1,N0). somele(L,N) :- someleb(L,0,N). -
5- compte-aa([],0).
compte-aa([aa|L], N) :- compte-aa(L,N1), N is N1+1, !. compte-aa([_|L], N) :- compte-aa(L,N).