TP 8 : Prolog

Systèmes Logiques

Unification

Trouver un unificateur le plus général (mgu) pour les problèmes suivants s’il existe :

  1. f(h(x),g(y,h(x))) et f(h(g(y,z)),z).
  2. f(x,x) et f(x,h(x)).
  3. f(x,y,h(x,y)) et f(u,u,h(v,v)).
Correction
  1. On doit unifier h(x)=?h(g(y,z)) et g(y,h(x))=?z

On remplace z: h(x)=?h(g(y,g(y,h(x)))) et z=?g(y,h(x))

On déconstruit h : x=?g(y,g(y,h(x))) et z=?g(y,h(x))

On échoue car x est dans le terme de droite.

  1. On doit unifier x=?x et x=?h(x). On échoue pour la même raison.

  2. On doit unifier x = u, y = u, h(x,y) = h(v,v).

On remplace x: x = u, y = u, h(u,y) = h(v,v).

On remplace y: x = u, y = u, h(u,u) = h(v,v).

On déconstruit x = u, y = u, u = v.

On remplace u : x = v, y = v, u = v. On ne peut plus progresser, on a trouvé un mgu!

Prolog

On pourra utiliser https://swish.swi-prolog.org/ pour exécuter des programmes prolog.

Une affaire de famille

On considère les données suivantes :

Définir des prédicats binaires mere et pere et y ajouter les données précédentes.

Correction
 % Zeus est le père de : Apollon, Artemis, Hermès, Aphrodite et Dionysos.
pere(zeus, apollon).
pere(zeus, artemis).
pere(zeus, hermes).
pere(zeus, aphrodite).
pere(zeus, dionysos).
 %   Atlas est le père de Maïa.
pere(atlas, maia).
 %   Arès est le père d’Eros de d’Harmonia.
pere(ares, eros).
 %   Chronos est le père de Zeus.
pere(chronos, zeus).
pere(ares, harmonia).
%Léto est la mère d’Apollon et d’Artémis.
mere(leto, apollon).
mere(leto, artemis).
 %   Maïa est la mère d’Hermès.
mere(maia, hermes).
 %   Dione est la mère d’Aphrodite.
mere(dione, aphrodite).
 %   Aphrodite est la mère d’Harmonia et d’Eros.
mere(aphrodite, harmonia).
mere(aphrodite, eros).

 %   Sémélé est la mère de Dionysos.
mere(semele, dionysos).

 %   Rhéa est la mère de Zeus.
mere(rhea, zeus).

 %   Pléioné est la mère de Maïa.
mere(pleione, maia).

Définir un prédicat parent(X,Y) qui est vrai seulement si X est la mère ou le père de Y.

Correction
parent(X,Y) :- mere(X,Y).
parent(X,Y) :- pere(X,Y).

Définir un prédicat freresoeur(X,Y) qui est vrai seulement si X et Y ont la même mère et le même père. Lister les frères et soeurs de la base de connaissances. Que remarquez-vous ?

Correction
freresoeur(X,Y) :- pere(Z,X), pere(Z,Y), mere(Z,X), mere(Z,Y).

On liste les frères et soeurs avec ?- freresoeur(X,Y). On remarque que X et toujours le frère/soeur de X ce qui est assez contre-intuitif. On peut rajouter qu’on veut X ≠ Y :

freresoeur(X,Y) :- pere(Z,X), pere(Z,Y), mere(Z,X), mere(Z,Y), X\==Y.

Définir un prédicat demifreresoeur(X,Y) qui est vrai seulement si X et Y ont un parent commun. Lister les demis frères et soeurs de la base de connaissances. Que remarquez-vous ?

Correction
demifreresoeur(X,Y) :- parent(Z,X), parent(Z,Y).

On liste les demi frères et soeurs avec ?- demifreresoeur(X,Y). On remarque encore que X et toujours le demi frère/soeur de X ce qui est assez contre-intuitif. On peut rajouter qu’on veut X ≠ Y :

demifreresoeur(X,Y) :- parent(Z,X), parent(Z,Y), X\==Y.

Définir un prédicat oncletante(X,Y) qui est vrai seulement si X est le frère ou la soeur d’un parent de Y. Lister ce prédicat.

Correction
oncletante(X,Y) :- parent(Z,Y), freresoeur(X,Z).

Entiers de Peano

On définit les entiers de Peano en Prolog de la façon suivante (z pour zéro, s pour successeur) :

nat(z).
nat(s(x)):-nat(x).

Le représentant d’un entier n est donc sn(z), c’est-à-dire, la fonction s appliquée successivement n fois à partir de 0.

Définir un prédicat p(x,y) (p pour “précédent”) qui est vrai seulement si s(y) = x. En déduire une requête qui calcule le prédécesseur de 3.

Correction
p(s(X), X).
?- p(s(s(s(X))), R).

Définir un prédicat double(x,y) qui est vrai seulement si y représente le double de x. En déduire une requête Prolog qui calcule la moitié de s(s(s(s(s(s(z)))))).

Correction
double(z,z).
double(s(X), s(s(Y))) :- double(X,Y).
?- double(X,s(s(s(s(s(s(z))))))).

Définir un prédicat add(x,y,z) qui est vrai seulement si z est la représentation de a + bx est la représentation de a et y la représentation de b. En déduire une requête prolog qui calcule les solutions entières de l’équation X + 2 = Y + 3.

Correction
add(z,X,X).
add(s(X),Y,s(Z)) :- add(X,Y,Z).
?- add(X, s(s(z)), s(s(s(Y)))).