IAS / Logique Propositionnelle - TP 1: Syntaxe

Ce premier travail pratique sur la logique propositionnelle vise à :

  • représenter une formule de la logique propositionnelle par un arbre de syntaxe abstraite (Abstract Syntax Tree, AST) au moyen d'une hiérarchie de classes Java ;
  • manipuler cet arbre par récursion structurelle (calcul de sous-formules, de variables, de profondeur, etc.) ;
  • produire différentes représentations textuelles d'une même formule (notation infixe parenthésée au minimum, notation préfixe / polonaise) ;
  • écrire un analyseur lexical (ou lexer) puis un analyseur syntaxique par descente récursive (recursive-descent parser) transformant une chaîne de caractères en AST, en respectant la priorité et l'associativité des connecteurs.

Ce travail porte exclusivement sur la syntaxe : on ne cherche pas à évaluer la valeur de vérité d'une formule, mais à la représenter, la parcourir, l'afficher et l'analyser correctement.

Prérequis

Ce travail demande de bonnes connaissances des notions de programmation Java, en particulier celles de classes abstraites, interfaces, héritage, polymorphisme. Il demande aussi une connaissance des notions plus générales de structures et fonctions récursives ainsi que de structure arborescente.

Ce travail est l'illustration par l'exemple du cours Logique Propositionnelle: Syntaxe disponible dans la section Intelligence Artificielle Symbolique.

Il est recommandé pour ce travail d'utiliser un JDK 17 ou ultérieur. Le développement peut être réalisé au moyen d'un IDE si besoin. La bibliothèque JUnit 5 est recommandé pour les tests mais non obligatoire.

1. Syntaxe de la logique propositionnelle

La syntaxe de la logique propositionnelle est définie formellement par un vocabulaire sur lequel est exprimé une grammaire.

1.1 Vocabulaire

Une formule est construite à partir :

  • D'un ensemble fini \( \mathcal{P} \) de variables propositionnelles, par exemple: $$ \mathcal{P}=\{a, b, c\} $$
  • D'un ensemble \( \mathcal{C} \) des connecteurs logiques défini par: $$ \mathcal{C}=\{\neg, \wedge, \vee, \to, \leftrightarrow\} $$
  • D'un ensemble \( \mathcal{S} \) de symboles défini par: $$ \mathcal{S}=\{\top, \bot, (, )\} $$

Ces trois ensembles forment le vocabulaire \( \mathcal{V} \) défini par: $$ \mathcal{V}=\mathcal{P}\cup{}\mathcal{C}\cup{}\mathcal{S} $$

1.2. Grammaire

L'ensemble des formules propositionnelles, noté \( \mathcal{L}_{p0} \), est l'ensemble des mots sur le vocabulaire \( \mathcal{V} \) tel que:

  1. \( \top\in{}\mathcal{L}_{p0} \) et \( \bot\in{}\mathcal{L}_{p0} \)
  2. \(\forall{}x\in\mathcal{P}\ x\in\mathcal{L}_{p0}\)
  3. \( \forall{}A\in\mathcal{L}_{p0}\ \forall{}A\in\mathcal{L}_{p0}\ \ \{(A),(B),\neg{}A,\neg{}B,A\wedge{}B,A\vee{}B,A\to{}B,A\leftrightarrow{}B\}\in{}\mathcal{L}_{p0} \) 

Une formule propositionnelle pouvant être ambiguë suivant l'ordre d'application des connecteurs, ceux-ci sont munis de priorité (plus la valeur de priorité est grande, plus le connecteur est prioritaire):

Connecteur Priorité Associativité
\( \neg \) 4 Droite
\( \wedge \) 3 Gauche
\( \vee \) 2 Gauche
\( \to \) 1 Droite
\( \leftrightarrow \) 0 Gauche

 

Afin de lever toute ambiguïté sans utiliser les priorités sur les connecteurs, il est possible de définir l'ensemble des formules propositionnelles strictes, noté \( \mathcal{L}^{*}_{p0} \):

  1. \( \top\in{}\mathcal{L}_{p0} \) et \( \bot\in{}\mathcal{L}_{p0} \)
  2. \(\forall{}x\in\mathcal{P}\ x\in\mathcal{L}_{p0}\)
  3. \( \forall{}A\in\mathcal{L}_{p0}\ \forall{}A\in\mathcal{L}_{p0}\ \ \{(A),(B),\neg{}A,\neg{}B,(A\wedge{}B),(A\vee{}B),(A\to{}B),(A\leftrightarrow{}B)\}\in{}\mathcal{L}^{*}_{p0} \) 

2. Environnement Java

Ce travail sera réalisé sous la forme d'un projet Java.

 Exercice 1.
Créer un projet Java dans lequel les classes nécessaires à ce travail seront développées. Ce projet doit comporter au moins un package fr.utln.logic.propositional. Il est recommandé d'utiliser Maven pour gérer le projet.

 

2. Représentation de formules propositionnelles

Cette partie du travail vise à produire les classes et les interfaces permettant de représenter une formule propositionnelle.

2.1. Formule

Tout élément de la logique propositionnelle est une formule, il s'agit donc du premier objet à représenter. 

 Exercice 2.
Dans le package fr.utln.logic.propositional. ajouter une interface Formula qui permettra de caractériser une formule propositionnelle. Cette interface est vide pour l'instant.

 

2.2. Variable

Le composant le plus simple d'une formule est la variable propositionnelle.

 Exercice 3.
Dans le package fr.utln.logic.propositional. ajouter une interface Var qui étend l'interface Formula et qui représente une variable propositionnelle.

Une variable étant identifiée de façon unique par un nom, ajouter la méthode String getName() à l'interface Var.

 

Comme le défini la grammaire de la logique propositionnelle, l'ensemble des formules propositionnelles est défini par l'ensemble de variables sur lesquelles elles sont construites.

 Exercice 4.

Dans le package fr.utln.logic.propositional. ajouter une classe VariableSet qui permettra de représenter un ensemble de variables propositionnelles. Cette classe devra proposer au moins les 5 méthodes suivantes:

  1. public boolean addVariable(String name) qui ajoute la variable de nom name à l'ensemble.
    Cette méthode retourne     true si la variable est bien ajoutée et false sinon
    (    attention, une variable est identifiée par un nom unique))

  2. public Var removeVariable(String name) qui retire la variable de nom name de l'ensemble.
    Cette méthode retourne une référence vers la variable retirée (ou     null si la variable n'était pas dans l'ensemble).

  3. public Var getVariable(String name) qui retourne une référence vers la variable de nom name si celle-ci est bien dans l'ensemble ou null sinon.

  4. public void clearVariable() qui vide l'ensemble de variables.

  5. public Var getOrAddVariable(String name) qui retourne une référence vers la variable de nom name si celle-ci est présente dans l'ensemble ou qui l'ajoute er retourne une référence vers celle-ci si elle n'est pas encore présente dans l'ensemble.

 

Afin de pouvoir utiliser les variables propositionnelles dans le projet, il faut implanter une classe pouvant être instanciée.

 Exercice 5.
Dans le package fr.utln.logic.propositional. ajouter une classe VarImpl qui implante l'interface Var afin de pouvoir instancier une variable propositionnelle. Cette classe doit bénéficier au moins d'un constructeur public VarImpl(String name) qui permet d'instancier une variable de nom name.

 

2.3. Connecteurs

Une formule propositionnelle est composée en grande partie de variables ainsi que des 5 connecteurs \( \neg,\ \wedge,\ \vee,\ \to,\ \leftrightarrow \). Un connecteur peut être vu comme le lien entre un ou deux opérandes que sont les formules.

 Exercice 6.
Ajouter au projet le package fr.utln.logic.propositional.connector et y ajouter une interface Connector.
Cette interface doit posséder une méthode public Formula[] getOperands() qui permet de récupérer la ou les opérandes (formules) auxquelles ce connecteur est appliqué.

 

La logique propositionnelle repose sur deux types de connecteurs:

  • 1 connecteur unaire ( \( \neg \))
  • 4 connecteurs binaires (\( \wedge,\ \vee,\ \to,\ \leftrightarrow \))
 Exercice 7.
Dans le package fr.utln.logic.propositional.connector, ajouter une interface UnaryConnector qui étend Connector.  Cette interface doit posséder une méthode public Formula getOperand() qui permet de récupérer la formule à laquelle ce connecteur est appliqué.

 

 Exercice 8.

Dans le package fr.utln.logic.propositional.connector, ajouter une interface BinaryConnector qui étend Connector.  Cette interface doit posséder:

  • une méthode public Formula getOperandLeft() qui retourne une référence sur l'opérande (formule) de gauche;
  • une méthode public Formula getOperandRight() qui retourne une référence sur l'opérande (formule) de droite;
  • un champ statique public static final int LEFT = 0 qui fixe que l'opérande gauche est celui d'index 0;
  • un champ statique public static final int RIGHT = 1 qui fixe que l'opérande droit est celui d'index 1.

 

A partir des interfaces représentant un connecteur, les 5 connecteurs de la logique propositionnelle peuvent être implantés en gardant en tête que les connecteurs sont également des formules.

 Exercice 9.

Dans le package fr.utln.logic.propositional.connector, ajouter les classe:

  • Not qui étend UnaryConnector et Formula;
  • And, Or, Imp et Equiv qui étendent BinaryConnector et Formula.

Ajouter les constructeurs nécessaires à l'utilisation de ces connecteurs.

 

2.4. Instanciation de Formule

Il doit être possible pour un développeur utilisant vos classes de créer n'importe quelle formule propositionnelle à partir de votre API de façon programmatique. Par exemple, l'instruction:

Formule f = equiv(and(or(not(var("a")), var("b")), imp(var("c"), var("d"))), or(var("a"), var("d")));

doit permettre de créer programmatiquement la formule $(((\neg{}a\vee{}b)\wedge{}(c\rightarrow{}d))\leftrightarrow{}(a\vee{}d))$.

 Exercice 10.

Ajouter un package fr.utln.logic.propositional.factory, au projet Java actuel et y ajouter une classe FormulaFactory permettant de créer des formules comme dans l'exemple précédent. La classe FormulaFactory peut contenir des méthodes statiques permettant d'instancier des formules spécifiques:

  • static Var var(String name) qui instancie une variable de nom name;
  • static Not not(Formula f) qui instancie \(  \neg{}f \);
  • static And and(Formula a, formula b) qui instancie \( a\wedge{}b \);
  • static Or or(Formula a, Formula b) qui instancie \( a\vee{}b \);
  • static Imp imp(Formula a, Formula b) qui instancie \( a\to{}b \);
  • static Equiv equiv(Formula a, Formula B) qui instancie \( a\leftrightarrow{}b \).

Indice: Il est possible d'appeler les méthodes statiques d'une classe sans avoir à nommer explicitement celle-ci (penser aux imports statiques)

 

2.5. Affichage d'une formule

La bibliothèque doit permettre d'afficher une instance de Formula sur la console en utilisant une notation textuelle des opérateurs tels que:

  • $\neg{}A$ sera affiché !A
  • $A\wedge{}B$ sera affiché A & B
  • $A\vee{}B$ sera affiché A | B
  • $A\rightarrow{}B$ sera affiché A -> B
  • $B\leftrightarrow{}B$ sera affiché A <-> B

Exemple

Les instructions:

Formula f = equiv(and(or(not(var("a")), var("b")), imp(var("c"), var("d"))), or(var("a"), var("d")));
System.out.println("F: "+f);

doivent afficher:

F: (((!a | b) & (c -> d)) <-> (a | d))

3. Entrées / sorties

Cette partie est dédiée aux entrées / sorties pour les formules propositionnelles.

3.1. Affichage en HTML

bibliothèque doit permettre de récupérer, à partir d'une instance f de Formula, une chaine de caractère de type String représentant f en HTML. Pour rappel:

  • $\neg{}$ correspond à l'entité HTML &not;
  • $\wedge{}$ correspond à l'entité HTML &wedge;
  • $\vee{}$ correspond à l'entité HTML &vee;
  • $\rightarrow{}$ correspond à l'entité HTML &rightarrow;
  • $\leftrightarrow{}$ correspond à l'entité HTML &leftrightarrow;

3.2. Lecture d'une formule en LaTeX

La bibliothèque doit permettre d'instancier une Formula à partir d'une notation LaTeX. Cela peut être réalisé par exemple à l'aide d'une méthode Formula readFromLatex(String latex) qui prend en paramètre une chaine de caractère représentant une formule écrite en LaTeX et retourne la formule correspondante comme une instance de Formula.

Les notations LaTeX pour les formules propositionnelles sont:

  • $\neg{}A$ correspond à la commande LaTeX \neg{}A ou \neg A
  • $A\wedge{}B$ correspond à la commande LaTeX A\wedge{}B ou A\wedge B
  • $A\vee{}B$ correspond à la commande LaTeX A\vee{}B ou A\vee B
  • $A\rightarrow{}B$ correspond à la commande LaTeX A\rightarrow{}B ou A\rightarrow B
  • $A\leftrightarrow{}B$ correspond à la commande LaTeX A\leftrightarrow{}B ou A\leftrightarrow B

Exemple

Les expressions latex:

(((\neg{}a\vee{}b)\wedge{}(c\rightarrow{}d))\leftrightarrow{}(a\vee{}d))

ou

(((\neg a\vee b)\wedge (c \rightarrow d))\leftrightarrow (a\vee d))

correspondent à la formule $(((\neg{}a\vee{}b)\wedge{}(c\rightarrow{}d))\leftrightarrow{}(a\vee{}d))$

 

Intelligence Artificielle Symbolique