Fil de navigation

Clause logique de HORN

Le VIsual Prolog (VIP) et d’autres langages Prolog sont basés sur la Clause logique de HORN. Cette clause de HORN est un système formel pour raisonner sur des objets et sur la manière dont ces objets ont des relations entre eux.

Un exemple : Dans notre monde du Bridge on exprime en langage naturel une exigence comme celle-ci :

Un critère pour ouvrir au palier de un à la couleur est d’avoir une main avec 12 points d’honneurs.

Le premier travail du concepteur va consister à reformuler le plus simplement possible cette affirmation en :

  • Supprimant les mots inutiles qui n’ajoutent rien à l’information, check
  • Choisissant une organisation de la phrase en y  groupant les informations relatives à chaque objet, seek
  • Isolant le verbe qui indique la relation entre les objets
  • Remplaçant chaque objet par un mot mnémonique qui le caractérise au mieux.

Reprenons notre exemple et reformulons : Ouverture possible palier de un à la couleur avec 12 points d’honneur.

On a fait disparaitre le mot « main », car le joueur de bridge ne peut pas faire de confusion et on a mis en tête le verbe d’action « ouvrir avec ». Les objets sont ainsi clairement identifiés ; on peut alors leur affecter un mnémonique (un mot unique t représentatif que le concepteur choisi) et qui pourra être aussi un nom d’identification de « variable » dans un langage informatique. Soit dans notre exemple:

  • Relation : ouvrir avec = ouvriravec
  • Objet 1 : Palier de un à la couleur = Palier1Coul
  • Objet 2 : 12 points d’honneur = 12_ptH

On peut reformuler cette relation en abrégé en étant plus concis : ouvriravec, ptH égal 12, au Palier1Coul.

Ou encore: ouvriravecptH égal 12, au Palier1Coul.

Ici nous avons deux objets : « Palier1Coul » et un nombre «12 », plus une relation entre ces objets. Explicitement, on produit une enchère au palier de un à la couleur avec 12 points Honneurs. Pour pouvoir travailler avec la clause de HORN on formalise cette relation (cette affirmation) par unFUNCTOR, de la manière suivante :

[ouvriravecptH ("12", "Palier1Coul").] ou encore [ouvriravecptH ("Palier1Coul", "12").]

Dans cette formalisation sous forme de FUNCTOR, on met le nom de la relation en tête et les deux objets entre des parenthèses séparés par des virgules. Le FUNCTOR, ou relation, se termine toujours par un point. Les noms des deux objets sont connus dans les ordinateurs comme étant des littéraux "strings" ou plus simplement des strings. Les doubles apostrophes sont utilisées pour délimiter les strings.

Pour ajouter un concept supplémentaire, nous dirons que «ouvriravecptH » est un prédicat, (ou une relation). Un prédicat décrit une relation entre deux objets, dans ce cas «"12"» et «"Palier1Coul"». Dans l’interprétation qui est donnée ici, le second argument «"Palier1Coul"» est ouvert«ouvriravecptH » si les points H, du premier argument sont de «"12"».

Vous noterez que l’on peut choisir un ordre arbitraire des objets dans la parenthèse. Nous retiendrons la première formulation qui est plus logique (au sens de la compréhension), mais nous aurions  aussi bien pu choisir l’autre. L’ordre des arguments est donc un choix du concepteur pour la formalisation. Néanmoins, une fois que ce choix est fait il faudra être respectueux de cet ordre, ainsi dans cette formalisation le nombre de point d’honneur devra toujours être le premier argument. Nous pouvons dire  que dans un programme nous créons un « monde » et que dans ce monde le premier membre du prédicat «ouvriravecptH » représente le nombre de points d’honneur qui rend la relation vraie.

Avec la formalisation ci-dessus on peut établir n’importe quelle relation entre tous les types d’ouvertures et les points d’honneur, mais aussi écrire pour un même palier tous les niveaux de points d’honneur ou on ouvre à ce palier. Plus généralement, avec un prédicat et des arguments on peut spécifier une relation entre des objets. Voyons d’autres exemples :

[ouvriravecptH ("15", "Palier1SA").]

[avecdistrib (“01“, “Palier1SA”).]

Ce sont des relations entre deux objets. N’importe quel nombre d’argument est possible, un argument, mais aussi trois sont possibles par exemple :

[ouvrir_de_2T_ si_pas_2SA(“22”, “01”, “palier2T”).]

Cette affirmation s’écrit en langage naturel : On ouvre de 2T si  on n’a pas ouvert de 2SA avec 22 points d’honneur et une distribution régulière n° 01, pour le palier de 2T.

Cette affirmation qui pourra paraître un peu curieuse à certain lecteur sera utilisée par la suite comme « discriminant » entre deux règles sur l’ouverture de 2T, mais ce n’est pas le sujet que l’on traite pour le moment. On s’intéresse  ici à la formalisation d’un fait , indiquant une relation entre trois objets.

Donnons encore un exemple de FAIT au bridge :

[ mainref("10","6,3,2,2","unicolore, semi-regulier","5,6425").]

Cette affirmation s’écrirait en langage naturel : On définit une main de référence qui porte le n°10, sa distribution est 6, 3, 2, 2, de typeunicolore semi-régulier, et sa probabilité d’apparition est de 5,6426 %.

On voit ici, que le nombre d’arguments (les objets) est quelconque et que la relation qui les réuni est un choix arbitraire du concepteur dont il devra ultérieurement respecter la structure.

De telles spécifications sont appelées des [facts], faits. Un fait consiste en un prédicat, un nombre d’arguments entre parenthèses séparés par des virgules et il est terminé par un point pour indiquer la fin de celui-ci. Un fait décrit une relation statique entre des objets.

Les faits sont utiles pour  représenter le « savoir » mais ils sont insuffisants, comme quand vous regardez un quiz à la télévision qui reste totalement statique et figé.  Pour rendre les faits plus intéressants, nous avons besoin de relations plus générales entre des objets ou des groupes d’objets. Ces relations plus générales sont appelées des [rules] Règles.

Comme exemple nous pouvons bâtir une règle entre les points d’honneur et les distributions pour définir une ouverture particulière:

On ouvrira au palier de 1SA,  SI , les points H de la main autorisent le palier1SA, ET SI ,  la distribution est régulière donc compatible du palier 1SA.

[ ouvrirpalier1SA (PointH, Distribution) :-
ouvrirsiptH  (PointH, "palier1SA"), 
avecdistrib (Distribution, "palier1SA"). ]

Dans cette règle nous utilisons, avec les prédicats, ce que l’on nomme classiquement des opérateurs logiques: le mot [SI] et le mot [ET]. Dans cette formalisation le mot [SI] est remplacé par le symbole [:-] et le mot [ET] est remplacé par la virgule [,]. Ce sont les symboles qui sont utilisés en Prolog pour représenter les opérateurs logiques. Clairement dans [ouvrirpalier1SA (PointH, Distribution)], nous voulons indiquer que PointH etDistribution sont nécessaires pour choisir le palier  d’ouverture 1SA. Une telle formalisation est appelée règle.

Regardons de plus près la grammaire de cette règle. La première partie  [ouvrirpalier1SA (PointH, Distribution)] est appelée la conclusion. La conclusion est suivie par le signe [:-] SI. Après ce signe, SI, il y a un  ou plusieurs prédicats de fait, séparés par des virgules et terminés par un point. Dans cette règles ces prédicats de fait sont appelés les membres de la règle. Notez aussi que [ouvrirpalier1SA] commence par une minuscule. Les arguments comme PointH commencent par une majuscule. En Prolog ceci représente la notation d’une variable . Ceci indique que l’on peut utiliser n’importe quel objet du type [pointH]. Notons que pour cette règle les membres sont des faits. Il est aussi possible d’utiliser des conclusions d’autres règles comme membre.

Si vous connaissez la logique, alors vous reconnaîtrez la formulation connue sous le terme de déduction. La différence est qu’en logique on utilise une écriture telle que :

[IF p AND q THEN r ]                      (SI p ET q ALORS)

Tandis qu’en Prolog nous écrirons :

[r :- p,q.]

Quand les membres sont vrais, alors la conclusion est aussi vraie. Ceci est plus ou moins vrai en Prolog…..

La forme générale d’une règle est la suivante :

Conclusion :- membre1, membre2,…………membreN.

Dans notre règle explicative précédente nous avons utilisé des noms de variable à peu près explicites pour la compréhension humaine. Avec laclause de HORN on peut faire cela comme on le souhaite. Nous sommes libres de choisir presque tous les noms de variable que l’on souhaite.

 

Comprenez bien que cela est seulement pratique pour le lecteur humain de notre code. Les ordinateurs eux ne réalisent pas que la variable « Père » par exemple pourra avoir un « enfant ». Votre ordinateur sera satisfait avec une règle qui utilise des variables totalement non explicites, par exemple:

[g(X, Y) :- f(X, Z), f(Z, Y).]

Dans une règle nous utilisons des variables à la place des noms des objets. Une règle est une relation générale qui s’applique entre différents objets.

En résumé : quand vous lisez une règle vous devez interpréter le symbole [:-] comme un « SI » logique et la virgule [,] qui sépare les prédicats comme un « ET » logique. Dans les noms de variables PointH et Distribution, les premières lettres sont des majuscules. En Prolog un nom de variable débute toujours par une majuscule.

En choisissant des noms de variable qui aide mieux à la compréhension que X,Y,Z,  nous améliorons la lisibilité des règles pour l’homme. La lisibilité est aussi améliorée en écrivant les règles sur plusieurs lignes. Une ligne pour la conclusion et des lignes pour les membres.

 

En ajoutant cette règle nous avons introduit un prédicat pour la relation ouvrirpalier1SACette règle est plus efficace que d’écrire à chaque fois un nouveau fait spécifique de notre monde (notre théorie)nous spécifions une règle et nous utilisons implicitement les faits précédents. De plus nous avons choisi l’ordre des arguments. Il faudra rester homogène avec ce choix, c.à.d que les arguments des différents prédicats suivent le même principe.

En Prolog, faits et règles sont appelés des clauses. Avec des faits et des règles nous sommes capables de formuler des théories. En général unethéorie est une collection de faits et de règles, en Prolog nous pourrons dire qu’une théorie est un ensemble de clauses.

Nous allons par la suite définir dans une étude de faisabilité un maquettage de notre « Théorie » (au sens de PROLOG), qui comportera des faits et des règles. Nous expliquerons comment tester cette théorie avec P.I.E avant d’envisager de passer éventuellement à un code exécutable de ce maquettage sans P.I.E.

Note de Microperso: Le canevas du texte ci-dessus est repris d'un texte original en anglais duTutorial de T de BOER , auquel je me référerais souvent sur ce site, les lecteurs en registrés peuvent télécharger la version originale de T.de BOER ou ma traduction personnelle en français (pas totalement finalisée) ici:

xxxxxxxxxxxxxxxxxxxx en cours de restructuration

Nouveauté Joomla 3.7: Un nouveau champ de type quelconque par article