(I)   [P <-> Q] |- (P -> Q) & (P <- Q)
(II)  [P <- C v D] |- (P <- C) & (P <- D)
(III) [ ]|-  (x P(x) & x Q(x)) <-> x ( P(x) & Q(x) )

Dans le cas propositionnel les formules du complété d'un programme sont de la forme :

                            p '<->' q & r & s   v   t & q   v   r

i.e. une équivalence avec en partie gauche une proposition et en partie droite une union (opérateur 'v' ) de conjonctions (opérateur '&')

En Prolog si on déclare correctement les opérateurs '<->' (l'équivalence) , v (ou logique) et & (et logique) on peut écrire directement des formules de complété sans parenthèse qui sont des termes Prolog et qui peuvent donc apparaître en paramètres de prédicats Prolog.

exemple : p '<->' q & r & s   v   t & q   v   r    avec

:- op(900 , xfx , '<->').
:- op(600 , xfy , v).
:- op(400 , xfx , '<-').
:- op(300 , xfy , &).

On a défini une syntaxe abstraite pour ces formules :

1) Catégories syntaxiques :

f , f1 , ... : F (formule de complété)
d , d1 , ... : D (disjonction)
c , c1 , ... : C (conjonction)
p , p1 , .. : P (proposition) on se limitera aux symboles p , q , r , s , t
i,i1,… : I (implication inverse)
cl,cl1,… :Cl (clause)
ls,ls1,… :L (liste de clause)
q1,q2,.. : Q (queue de clause)

%% les deux valeurs logiques 'true' et 'false' sont directement introduites dans les définitions

2) Définitions :

f ::= p <-> d
d ::= c | c v d1
c ::= p | true | false | p & c1
i::= p '<-' d
cl ::= p :- q
q ::= p | p,q1

On veut maintenant retrouver les clauses Prolog correspondant à une (1) formule de complété. Alors, à partir de la syntaxe abstraite on définit des règles d'inférence de transformation d'une formule de complété en une liste de clauses (règles et/ou faits) Prolog.

Rappels : Les clauses Prolog correspondantes ont toutes en tête de clause, la partie gauche de l'équivalence et il y a autant de clauses que de conjonctions (séparées par des v) dans la partie droite de l'équivalence.

On définit les transformations suivantes :

F '-f->' L   : la transformation d'une formule de complété en une liste de clauses Prolog, (complete2Prolog/2 en Prolog)
I '-d->' L   : la transformation d'une implication inverse en une liste de clauses Prolog, (impl2Prolog/3 en Prolog)
C '-q->' Q : la transformation d'une conjonction en partie droite d'une clause, (conj2Prolog/2 en Prolog)

Et on a écrit : les règles Rf , Rd et Rq pour la transformation d'une formule et d'une disjonction

	p <- d '-d->' l
Rf :		% on délaisse le seulement-si ('->') de '<->'
	p <-> d '-f->' l

	p <- c '-d->' l1 p <- d '-d->' l2
Rd1 :		si l = conc(l1,l2)
	p <- c v d '-d->' l

	c '-q->' q
Rd2 :
	p <- c '-d->' [p :- q]

	c '-q->' q
Rq1 :		si p dans [p,q,r,s,t,false]
	p & c '-q->' p , q

Rq2 :		si p dans [p,q,r,s,t,false]
	p '-q->' p

Q2 : Donnez la version Prolog de ces règles (en respectant la terminologie proposée ci dessus)

1) Catégories syntaxiques :

f , f1 , ... : F (formule de complété)
d , d1 , ... : D (disjonction)
c , c1 , ... : C (conjonction)
p , p1 , .. : P (proposition) on se limitera aux symboles p , q , r , s , t
i,i1,… : I (implication inverse)
cl,cl1,… : Cl (clause)
l,l1,… : L (liste de clause)
q1,q2,.. : Q (queue de clause)

%% les deux valeurs logiques 'true' et 'false' sont directement introduites dans les définitions

2) Définitions :

f ::= equiv(p , d)
d ::= c | ou(c , d1)
c ::= p | true | false | et(p , c1)
i::= implInv(p , d )
cl ::= p :- q
q ::= p | p,q1

Et pour l'analyse syntaxique d'une formule de complété on s'est donné la grammaire suivante (DCG) :

% une formule est une équivalence...
fcompl --> prop , ['<->'] , disj.
% la partie droite de l'équivalence est une simple conjonction et propositions 
% ou bien une disjonction de conjonctions
disj --> conj.
disj --> conj , [v] , disj.
% une conjonction est une simple proposition ou une valeur logique
% ou bien une conjonction de ces éléments
conj --> prop .
conj --> [true] .
conj --> [false] .
conj --> prop , [&] , conj.
conj --> [true] , [&] , conj.
conj --> [false] , [&] , conj.
% une proposition est une lettre choisie parmi : p,q,r,s,t
prop --> [X] , {member(X , [p,q,r,s,t])}.

Q3.1 : compléter cette DCG pour construire l'arbre de syntaxe abstraite d'une formule de complété pendant son analyse et selon la syntaxe abstraite nouvellement définie

Q3.2 : transformer le programme Prolog de la question 2 pour l'adapter à la nouvelle syntaxe abstraite

Q3.3 : donner le but et le résultat attendu pour l'analyse et la transformation de  p '<->' q & r & s v t & q v r

4-Java :  (5 points)

En java, on va représenter les arbres de syntaxe abstraite d'une formule de complété au moyen du système de classes suivant à l'aide duquel on veut implanter la même transformation qu'en Prolog i.e. obtenir une édition d'une formule de complété sous la forme d'un ensemble de clauses Prolog. Pour cela les classes implantent la méthode

public String toProlog(){ ... }

public class Fcompl{
    private Prop p;
    private Disj d;

    public Fcompl(Prop tete,Disj alter){
        p=tete;  d=alter;
    }
    public String getTete(){
        return p.getNom();
    }
    public String toString(){
        return p.getNom() + " <-> " + d.toString();
    }
    public String toProlog(){ //règle sémantique structurelle rf
        return new Impl(p,d).toProlog();
    }
}

public class Impl{
    private Prop p;
    private Disj d;
 
    public Impl(Prop tete,Disj alter){
        p=tete; d=alter;
    }
    public String getTete(){
        return p.getNom();
    }
    public String toString(){
        return p.getNom() + " <- " + d.toString();
    }
    public String toProlog(){
        if (d instanceof Ou){	// règle sémantique rd1
            return . . . /* à complèter */;           
        } 
        if (d instanceof Conj){ // règle sémantique rd2
             return . . . /* à complèter */;
        }
        return "erreur de syntaxe...";
    }
}

public abstract class Disj{
    public abstract String toString();
    public abstract String toProlog();
}

public class Ou extends Disj{
    public Conj c;
    public Disj d;
    public Ou(Conj mg , Disj md){
        c = mg; d = md;
    }
    public String toString(){
        return c.toString() + " v " + d.toString();
    }
    public String toProlog(){
        return "";
    }
}

public abstract class Conj extends Disj {}

public class Prop extends Conj{
    private String nom;
    public Prop(String n){
        nom=n;
    }
    public String getNom(){
        return nom;
    }
    public String toString(){
        return nom;
    }
    public String toProlog(){	// règle sémantique rq2
        return . . . /* à complèter */ ;
    }
}
 public class Et extends Conj {
    private Prop p;
    private Conj c;
    public Et(Prop mg,Conj md){
        p = mg; c = md;
    }
    public String toString(){
        return p.toString() + " & " + c.toString();
    }
    public String toProlog(){	// règle sémantique rq1
        return . . . /* à complèter */ ;
    }
}
public class False extends Conj{
    public String toString(){
        return "False";
    }
    public String toProlog(){
        return . . . /* à complèter */ ;
    }
public class True extends Conj{
    public String toString(){
        return "True";
    }
    public String toProlog(){
        return . . . /* à complèter */ ;
    }
}

Q4.1 : donner le diagramme UML de classes du programme

Q4.2 : compléter les méthodes   public String toProlog(){ ... }

Q4.3 : donner le corps du programme de test qui correspond à la transformation du but de la question Q3.3 :

p '<->' q & r & s v t & q v r

public class TestFCompl{
    public static void main(String [] args){
        Fcompl f=new Fcompl( . . . /* à complèter */ );
        System.out.println(f.toString());
        System.out.println(f.toProlog());
    }
}