Les règles PROLOG avec exercices

Cours les règles PROLOG avec exercices, tutoriel & guide de travaux pratiques en pdf.

Les données

Si on se réfère à la Logique Computationnelle, toutes les données en Prolog sont des termes. Les différents types de termes que nous avons déjà vus en Logique Computationnelle on les retrouve tout naturellement en Prolog, saupoudrés en plus avec des épices propres à ce langage. Ainsi une distinction fondamentale pour les données enProlog s’opère entre les données simples et les données structurées.

Les données simples

Prolog est un langage absolument, ou mieux, viscéralement non typé. L’avantage de ce fait est que nul part on ne déclare qu’un élément est un tableau ou un réel ou une chaîne de caractères. On écrit un programme comme on construit un discours sans avoir à établir d’avance quels seront les adjectifs, les verbes ou les noms communs que nous utiliserons. Mais malgré tout, il faut au moins pouvoir faire la distinction entre constantes et variables. En Prolog cette distinction se fait de manière implicite. Le nom d’une variable doit toujours commencer par une lettre majuscule, par exemple Variable, tandis que celui d’une constante par une lettre minuscule, par exemple cONSTANTE.
On distingue les constantes en nombres et atomes. Les nombres peuvent être des entiers ou des réels. Tout ce qui n’est pas nombre et qui commence par une lettre miniscule, peut être considéré comme un atome. Par exemple toto ou av_du_Parc_95000_Cergy sont des atomes. De même une chaîne de caractères alphanumériques entourée de simple quote « ’ » est aussi un atome, e.g. ’Toto’, ’1,av. du Parc, 95000 Cergy’ ou ’3a’ sont des atomes.
Les variables commencent toujours par une lettre majuscule ou par le caractère « _ ». Il y a aussi la variable anonyme, représentée par « _ » et qui peut être unifiée à n’importe quelle variable ou constante pour laquelle il n’y aura pas dans le programme un usage explicite. Par exemple considérons l’ensemble de règles :
nomFait(objet1, objet2, objet3) ← nomFait1(objet1, objet2), nomFait2(objet1)
nomFait(objet1, objet2, objet3) ← nomFait3(objet1), nomFait4(objet3)
dont la première ne fait pas appel à objet3 et la seconde n’utilise pas objet2. On peut donc les écrire sous la forme :
nomRelation(objet1, objet2, _ ) ← nomFait1(objet1, objet2), nomFait2(objet1)
nomFait(objet1, _, objet3) ← nomFait3(objet1), nomFait4(objet3)

Les données structurées

Les constantes et les variables sont des données brutes, sans aucune structuration. On peut aussi envisager des données structurées, e.g. des données contenues dans des bases de données. Ainsi on peut envisager une base de données contenant des adresses des personnes selon l’exemple sui-ant : adresse(’Toto’, 1, av, ’du Parc’, 95000, ’Cergy’) et dont l’explication est évidente. En se référant au cours de la Logique Computationnelle, on constate que adresse représente un foncteur. Bien évidemment, dans la mesure où Prolog est un langage de logique d’ordre 1, nous pouvons envisager d’avoir comme arguments d’un foncteur d’autres foncteurs. Ainsi on peut aussi écrire adresse(nom(’Toto’), numero(1), rue(av, ’du Parc’), ville(95000, ’Cergy’)) à la place du foncteur précédent et où nom, numero, rue, ville sont aussi des foncteurs.
Un autre type des données structurées, sont les prédicats qui, comme nous le savons, expriment des valeurs de vérité concernant des relations. Par exemple le prédicat couleur Rouge (titre Livre, rouge) est un prédicat qui a la valeur 1 si la couleur du livre titre Livre est rouge. Il est possible aussi, selon la remarque précédente, que les arguments d’un prédicat soient des foncteurs. Ainsi la valeur du prédicat couleur Rouge(titre(Titre Livre), couleur(Couleur)) est égale à 1 si la variable Couleur est unifiée à la couleur rouge et à 0 sinon. Ici titre et couleur sont des foncteurs.
La distinction, en programmation Prolog, entre foncteurs et prédicats est parfois assez subtile et, de toute façon, elle est toujours laissée à la charge du programmeur, i.e. en clair Prolog n’est pas capable de distinguer entre prédicats et foncteurs et, pour s’en sortir, il applique à la lettre les règles établies par la logique des prédicats. Ainsi, si on écrit enProlog, la règle
couleurRouge(X) :- livre(titreLivre(X),couleur(rouge)).
accompagnée des faits :
livre(titreLivre(petitLivre), couleur(rouge)).
livre(titreLivre(vert), couleur(verte)).
on obtient pour la question couleurRouge(petitLivre). la réponseoui et pour la question couleurRouge(vert). la réponsenon. Mais, grâce à la particularité deProlog de pouvoir répondre à des questions symétriques, on peut aussi poser la question couleurRouge(X). et avoir comme réponse non pas une réponse affirmative, à laquelle il fallait s’attendre du fait que dans la base de données il y a un livre de couleur rouge, mais carrément son titre, à savoir X=petitLivre, comme si le prédicatcouleurRouge était un foncteur. Ainsi si on écrit dans le programme, la ligne supplémentaire : bibliothequeRouge(couleurRouge(X)).
le compilateur (ou l’interpréteur) deProlog ne s’aperçoît pas que couleurRouge(X)
soit un prédicat et en tant que tel ne doit pas apparaître comme un argument.
La surprise viendra si on veut connaître tous les livres rouges d’une biblio-
thèque et, tout naturellement, on pose la question : bibliothequeRouge(couleurRouge(X)). Dans ce cas la seule réponse qu’on reçoit est X égale au nom de la variable interne avec laquelle Prolog a unifié X.

Exécution

Pour exécuter un programmeProlog il faut d’abord le charger dans le fenêtre de travail à l’aide de la commande?-consult (’nomProgramme.pl’).. Ensuite il faut poser la question.
Afin de répondre à une question posée, Prolog est toujours capable de construire, à partir de sa base de données, une arborescence dont la racine est la question posée. Ensuite Prolog parcourt cette arborescence en appliquant l’algorithme de résolution SLD, que nous avons vu en Logique Computationnelle, sans toutefois faire la vérification des occurrences. Si, en appliquant cet algorithme, il arrive à « filtrer » la question, alors il affiche le message yes et, en fonction de la question posée, le contenu des variables de la question exemplifiées (instanciées) à des constantes. Prolog est en mesure de fournir toutes les réponses contenues dans la base de données. Pour les avoir, il suffit, après chaque réponse affichée, de taper la touche «; » qui, rappelons-le, en Prolog signifie « ou ». Si, par contre on veut s’arrêter, alors il faut taper la touche « Retour ».
Programme 1.5.1
gr(a,b,2).
gr(a,g,6).
gr(b,e,2).
gr(b,c,7).
gr(g,e,1).
gr(g,h,4).
gr(e,f,2).
gr(f,c,3).
gr(f,h,2).
gr(c,d,3).
gr(h,d,2).
Chacune de ces clauses représente une proposition qui a une valeur de vérité – vrai ou faux. Si on pose la question ?-gr(b,c,7) alors la réponse estoui, c’est-à-dire vrai, tandis que la réponse à la question ?-gr(b,f,10) est bien évidemment non, c’est-à-dire faux. Si donc on représente par E l’ensemble de clauses : E = {gr(a, b, 2), gr(a, g, 6), . . . , gr(h, d, 2)}, alors on obtient une réponse positive à une question composée de la clauseq si et seulement si E |= q. Il est évident que cette condition est remplie siq ∈ IeE qui est le modèle minimal d’Herbrand du programme E. Dans la mesure où le programme E est, dans notre cas, composé des clauses filtrées, nous avons comme modèle minimal d’Herbrand, les prédicats qui font partie des clauses du programme, ce qui en absence des règles donne: IeE = E. Par conséquent les seules fbf qui peuvent être satisfiables parE sont les clauses du programme. On voit ainsi que la logique des propositions est une logique
« pauvre » qui ne permet pas d’exprimer toute la richesse du raisonnement humain.

Exercices

Exercice 1.1 Examiner la base de données de l’exemple??. Établir la no-tion d’un sommet successeur d’un autre. Par exemple le sommet d est suc-cesseur du sommet a.
Exercice 1.2 Considérons le texte suivant :
Si Cyclope est un personnage mythologique, alors il est immortel mais s’il n’est pas un personnage mythologique, alors il est mortel. Si Cyclope est soit immortel, soit mortel, alors il a un seul œil. Cyclope est magique s’il a un seul œil.
(1) Représenter ce texte à l’aide d’une base de connaissances avec des propositions de la logique propsitionnelle.
(2) Donner les modèles pour que Cyclope soit magique si nous faisons l’hypothèse qu’il soit un personnage mythologique.
(3) Écrire en Prolog un programme qui permet de répondre aux questions suivantes :
(a) Cyclope est-il mythique?
(b) Cyclope est-il magique?
(c) Cyclope a-t-il un œil?
Exercice 1.3 Soit le problème suivant :
Trois coureurs Toto, Koko et Lolo portent des maillots de couleur différente et courent ensemble lors d’une course. Nous allons essayer d’établir l’ordre de l’arrivée de ces coureurs. Pour cela nous disposons des informations suivantes :
Toto dit qu’il est arrivé avant le coureur qui porte le maillot rouge. Koko, qui porte le maillot jaune, dit qu’il est arrivé avant le coureur au maillot vert.
Utiliser Prolog pour trouver l’ordre d’arrivée des coureurs.

1.2 Les règles
1.2.1 Les questions
1.3 Les données
1.3.1 Les données simples
1.3.2 Les données structurées
1.4 Exécution
1.5 Un exemple
1.6 Exercices