Comment définir une relation d'équivalence ?

Bonjour à tous !

Je souhaiterait implémenter une relation d'équivalence dans un programme ProLog, mais étant encore débutant dans ce langage l'une de mes règles génère systématiquement des erreurs.

Définition d'une relation d'équivalence (en mathématique) :
R est une relation d'équivalence si et seulement si :

• R est réflexive (pour tout x on a xRx)
• R est transitive (si on a xRy et yRz alors on a xRz)
• R est symétrique (si on a xRy alors on a yRx)

Je sais coder les deux premières propriétés :

Code:

---

1 2 3 4 5 6

% réflexivité : r(X,X).   % transitivité : r(X,Z) :- r(X,_) , r(_,Z).

---

Mais je ne sais pas coder la propriété de symétrie, j'ai naïvement essayé ceci :

Code:

---

1 2 3

% symétrie : r(X,Y) :- r(Y,X).

---

Mais cette ligne de code provoque un dépassement systématique de la pile...

Pouvez-vous m'aidez svp ?

Il suffit juste de coder ce qui est écrit dans l'énoncé... ;) Voici dans le vrai langage ProLog (à adapter avec la version Edimbourg):

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

% Définition d'une relation d'équivalence (en mathématique) : % R est une relation d'équivalence si et seulement si : % * R est réflexive (pour tout x on a xRx) % * R est transitive (si on a xRy et yRz alors on a xRz) % * R est symétrique (si on a xRy alors on a yRx) rel(x,y)-> eq(x,y); % Voici ze relation. A modifier pour les tests!! equivalence-> reflexive transitive symetrie; reflexive-> rel(x,x); transitive-> rel(x,y) rel(y,z) rel(x,z); symetrie-> rel(x,y) rel(y,x);

---

eq(x,y) est une fonction prédéfinie pour interpreter l'égalité. Le but equivalence me rend vrai.
dif(x,y) est une fonction prédéfinie pour interpreter l'inégalité. Le but equivalence me rend faux.


Cordialement,


Billy

Citation:

---

Envoyé par billynirvana

Il suffit juste de coder ce qui est écrit dans l'énoncé... ;) Voici dans le vrai langage ProLog (à adapter avec la version Edimbourg):

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

% Définition d'une relation d'équivalence (en mathématique) : % R est une relation d'équivalence si et seulement si : % * R est réflexive (pour tout x on a xRx) % * R est transitive (si on a xRy et yRz alors on a xRz) % * R est symétrique (si on a xRy alors on a yRx) rel(x,y)-> eq(x,y); % Voici ze relation. A modifier pour les tests!! equivalence-> reflexive transitive symetrie; reflexive-> rel(x,x); transitive-> rel(x,y) rel(y,z) rel(x,z); symetrie-> rel(x,y) rel(y,x);

---

eq(x,y) est une fonction prédéfinie pour interpreter l'égalité. Le but equivalence me rend vrai.
dif(x,y) est une fonction prédéfinie pour interpreter l'inégalité. Le but equivalence me rend faux.


Cordialement,


Billy

---

C'est du prolog "standard" ça ? Je suis pas un spécialiste, mais ça a une drôle de tête quand même... Sans doute des tas de trucs que je connais pas...

Citation:

---

Envoyé par Eusebius

C'est du prolog "standard" ça ?

---

C'est du Prolog avec la syntaxe de Marseille (celle utilisée par Alain Colmerauer, l'inventeur de Prolog, et que billynirvana utilise), par opposition à la syntaxe d'Edimburgh, qu'on est nombreux à utiliser ici.

Citation:

---

Envoyé par pcaboche

C'est du Prolog avec la syntaxe de Marseille (celle utilisée par Alain Colmerauer, l'inventeur de Prolog, et que billynirvana utilise), par opposition à la syntaxe d'Edimburgh, qu'on est nombreux à utiliser ici.

---

OK, merci de la précision.

Maintenant, si on a;

• r : E |-> E
• E est un ensemble dénombrable

On peut prouver que r est une relation d'équivalence de la façon suivante:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

rel_equiv :- reflexive, transitive, symetrique.       reflexive :- forall( r(X, _) , r(X, X) ).       transitive :- forall( ( r(X, Y), r(Y, Z) ) , r(X, Z) ).           symetrique :- forall( r(X, Y) , r(Y, X) ).

---

Maintenant, si E n'est pas dénombrable, c'est plus difficile...

Je vous remercie pour vos réponses rapides qui sont très intéressantes, mais j'ai du mal poser ma question : ce que je voulais savoir, ce n'était pas comment prouver qu'une relation est une relation d'équivalence (bien que cela me servira surement), mais sachant qu'une relation est d'équivalence, fabriquer des règles pour que ProLog puisse trouver de nouveaux faits à partir de faits connus.

exemple des colocataires :
Julie, Solange et Sophie sont colocataires et habite donc sous le même toit.

Soit la base de fait suivante :

Code:

---

1 2 3 4 5 6

meme_toit(julie,solange). meme_toit(solange,sophie).   meme_toit(romain,jeff). meme_toit(romain,grégoire).

---

Je souhaite programmer des règles pour que ProLog soit capable de déduire les faits suivants :
Julie habite sous le même toit que Julie (propriété de réflexivité)
Julie habite sous le même toit que Sophie (propriété de transitivité)
Solange habite sous le même toit que Julie (propriété de symétrie)

ce qui en code donne :

Code:

---

1 2 3

meme_toit(julie,julie). meme_toit(julie,sophie). meme_toit(solange,julie).

---

Bien que j'arrive à programmer la relation de reflexivité :

Code:

---

meme_toit(X,X).

---

Les relations de transitivité et de symétrie génèrent des erreurs lors de l'éxécution :

programme :

Code:

---

1 2 3 4 5

% transitivité : meme_toit(X,Z) :- meme_toit(X,Y) , meme_toit(Y,Z). % symétrie : meme_toit(X,Y) :- meme_toit(Y,X).

---

Lors de l'exécution voici les erreurs générés :
pour la transitivité :

Code:

---

1 2 3

5 ?- meme_toit(julie,sophie). ERROR: Out of local stack Exception: (14,514) meme_toit(julie, sophie) ?

---

pour la symétrie :

Code:

---

1 2 3

6 ?- meme_toit(solange,sophie). ERROR: Out of local stack Exception: (59,743) meme_toit(solange, sophie) ?

---

J'imagine qu'il manque un certain nombre de choses importantes dans mes règles, mais je n'arrive pas à trouver quoi. Pouvez me mettre sur la piste svp ?

Citation:

---

Envoyé par Amon-Râ

mais sachant qu'une relation est d'équivalence, fabriquer des règles pour que ProLog puisse trouver de nouveaux faits à partir de faits connus.

---

Dans ce cas là, le plus simple est de définir un prédicat meme_toit1/2 qui définit tes faits et d'écrire le prédicat meme_toit/2 à partir de cette relation.

Après, ça demande un peu de réflexion pour avoir toutes les relations 1 et 1 seule fois (et sans boucle).

Voici le programme qui retournera les relations d'équivalence que l'ont peut déduire à partir du prédicat meme_toit1/2. En plus, les relations d'équivalence n'apparaissent qu'une fois chacune et sont triées dans l'ordre alphabétique :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77

:- dynamic( meme_toit1/2 ).   meme_toit1(julie,solange). meme_toit1(solange,sophie).   meme_toit1(romain,jeff). meme_toit1(romain,grégoire).       ensemble(E) :- findall( X , (meme_toit1(X,_) ; meme_toit1(_,X)) , L ),   sort(L, E).         trans(L1, [], L2) :- !, sort(L1, L2).     trans(L1, L2, R) :-   findall(Y , ( member(X, L2), (meme_toit1(X,Y) ; meme_toit1(Y,X)), \+memberchk(Y,L1), \+memberchk(Y,L2) ) , L3 ),   append(L1, L2, L4), trans(L4, L3, R).         combi(L, X, Y) :- member(X, L), member(Y, L).         meme_toit(X,Y) :- ensemble(E), meme_toit(E, [], X, Y).     meme_toit([Elem|Q], Visited, X, Y) :- \+memberchk(Elem, Visited), !, trans([], [Elem], L), ( combi(L, X, Y) ; ( union(Visited, L, S), meme_toit(Q, S, X, Y) ) ).     meme_toit([_|Q], Visited, X, Y) :- meme_toit(Q, Visited, X, Y).

---

Génial !Cà correspond tout à fait à ce que je voulais.

En fait si j'ai bien compris le fonctionnement de ton programme :

On donne une liste composé d'un élément en deuxième argumant à la fonction trans, et celle-ci renvoie la liste de tous les éléments de sa classe d'équivalence (c'est à dire tous les colocataires vivant sous le même toit), puis on regarde si les deux objets X et Y appartiennent à la même classe. Si oui, alors on a fini, sinon on recommence avec le terme suivant dans la liste (si il n'appartient pas déjà à une classe d'équivalence déjà écrite : c'est le rôle de la liste Visited) jusqu'à ce qu'on ait regardé tous les éléments.

Merci beaucoup !

Citation:

---

Envoyé par Amon-Râ

On donne une liste composé d'un élément en deuxième argumant à la fonction trans, et celle-ci renvoie la liste de tous les éléments de sa classe d'équivalence (c'est à dire tous les colocataires vivant sous le même toit),

---

Tout à fait. En théorie des graphes, on appelle ça une "clique" (un sous-graphe complet).

Il m'a semblé, de prime abord, logique de procéder ainsi:
- 1er argument: les points déjà visités
- 2ème argument: les points à visiter
- 3ème argument: le résultat (l'ensemble des gens habitant sous le même toit, trié)

Mais on peut changer l'ordre des arguments (ce que j'ai fait pour meme_toit/4).

Citation:

---

Envoyé par Amon-Râ

puis on regarde si les deux objets X et Y appartiennent à la même classe.

---

Pas tout à fait. En fait, le prédicat member/2 permet d'énumérer les éléments d'une liste (pour vérifier l'appartenance, on utilise plutôt memberchk/2). Le prédicat combi/3 énumère tous les couples X,Y possibles avec X et Y appartenant tous deux à L. C'est ainsi qu'on énumère les relations d'équivalence.

Citation:

---

Envoyé par Amon-Râ

Si oui, alors on a fini, sinon on recommence avec le terme suivant dans la liste (si il n'appartient pas déjà à une classe d'équivalence déjà écrite : c'est le rôle de la liste Visited) jusqu'à ce qu'on ait regardé tous les éléments.

---

Quand on a fini d'énumérer toutes les relations possibles à partir d'un terme donné (grâce à combi/3) on essaye d'en trouver d'autres à partir d'un autre terme, en prennant gare à ne pas énumérer 2 fois la même solution (d'où l'utilisation de la liste Visited, en effet).

Citation:

---

Envoyé par Amon-Râ

Merci beaucoup !

---

De rien. C'était un exercice vraiment sympa, je trouve.