Cours Prolog résolution en logique propositionnelle

Substitutions

On applique une substitution = fXi =ti gi=1::n a une formule F en remplacant simultanement chaque occurrence libre de Xi par le terme ti , pour 1 i n.
Soient p(X ; Y ; f (a)) et = fX =b; Y =X g, p(X ; Y ; f (a)) = p(b; X ; f (a))
Si = fX1=s1; : : : ; Xn=smg et = fY1=t1; : : : ; Yn=tng sont deux substitutions, est une substitution.
= fX1=s1 ; : : : ; Xn=sm ; Y1=t1; : : : ; Yn=tng, ou on supprime tous les element de la forme X =X et Yj =tj tel que Yj 2 dom( ).
Soient = fX =f (Y ); Y =Z g et = fX =a; Y =b; Z =Y g. = fX =f (b); Z =Y g.
Instance : Soient deux termes t1 et t2. S’il existe une substitution telle que t1: = t2, alors t2 est une instance de t1 et t1 est une generalisation de t2. Ex : t1 = X , t2 = s(0)
Soient E et F deux expressions. E et F sont des variantes s’il existe deux substitutions et telles que E = F et F = E . Ex : E = p(X ; Y ) , F = p(A; B). Attention, E = p(X ; X ) n’est pas une variante de F = p(A; B).
Soit E une expression et V l’ensemble des variables de E . Une substitution de renommage est une substitution a variables pures fXi =Yi g telle que les Yi 6= Yj pour i 6= j et (V f Xi g) \ fYi g = ;.

Unication

Soit un ensemble ni de termes P = fti = si g. Un uni cateur pour P est une substitution telle que pour tout 1 i n et avec i 6= j, ti = si . Si une telle substitution existe, on dit que les termes ti et si sont uni ables. On note U(P) l’ensemble des uni cateurs de P.
Un uni cateur pour deux atomes p(s1; : : : ; sm) et p(t1; : : : ; tm) est un uni cateur pour P = fsi = ti g. Si U(P) 6= ;, on dit que P est uni able.
L’uni cateur principal ou plus general (upg) de n expressions Ei est une substitution telle que pour tout uni cateur j de Ei , il existe une substitution j telle que j = j .
Ex : t1 = p(s(X )), t2 = p(s(s(Y ))), = fX =s(Y 0 ); Y =Y 0 g, 1 = fX =s(0); Y =0g

Algorithme d’unication

Algorithme de Montelli-Montanari
1: Procedure Unification(P) . Un ensemble d’equations ti = si
2: X=X[E!E . Tautologie
3: X = t [ E (ou X appara^t dans E mais pas dans t) !
4: fX = tg [ E [X =t] . Application
5: t = X [ E (t n’est pas une variable) ! X = t [ E . Orientation
6: f (s1; : : : ; sn) = f (t1; : : : ; tn) [ E !
7: fs1 = t1; : : : ; sn = tng [ E . Decomposition
8: g (s1; : : : ; sm) = f (t1; : : : ; tn) [ E ! echec . Clash
9: X = t [ E (ou X appara^t dans t) ! echec . Test d’occurrence
10: Fin Procedure
Exemples
fp(f (X ); a); p(Y ; f (W ))g n’est pas uni able fp(f (X ); Z ); p(Y ; a)g est uni able
fp(f (X ); h(Y ); a); p(f (X ); Z ; a); p(f (X ); h(Y ); b)g uni able ?
fp(f (a); g (X )); p(Y ; Y )g
fp(a; X ; h(g (Z ))); p(Z ; h(Y ); h(Y ))g fp(X ; X ); p(Y ; f (Y ))g

Proprieté de l’algorithme d’unication

L’algorithme precedent termine
Chaque application preserve l’ensemble des solutions
Si P est uni able, l’algorithme termine avec un upg pour P S’il existe, l’upg d’un ensemble d’expressions est unique a un renommage de variable pres.

L’ interprete PROLOG

Mecanisme de base : Resolution SLD (reduction de buts). Soit Ai un litteral (negatif) dans une requ^ete PROLOG. La reduction de Ai etant donne un programme P est le remplacement de Ai par le corps d’une instance d’une clause A : B1; : : : Bi ; : : : Bm de P telle que A et Ai aient une instance commune.
Resolvante : Etat intermediaire de la requ^ete PROLOG.

L’interprete PROLOG (simpli e)

1: Fonction InterpreteProlog(P; Q) . Q requ^ete et P programme logique . La reponse sera Q si Q est consequence logique de P, echec sinon
2: Resolvante Q
3: Tant que Resolvante : A1; ::Ai ; ::An 6= et qu’il existe un but Ai et une clause de P (renommee) A : B1; ::Bi ; ::Bm, telle que A = Ai Faire
4: Resolvante (: (A1; ::; Ai 1; B1; :::; Bm; Ai+1; ::; An) )
5: Q Q
6: Fin Tant que
7: Si Resolvante = Alors
8: Retourner Q
9: Sinon
10: Retourner ECHEC
11: Fin Si
12: Fin Fonction

L’ interprete PROLOG, remarques

Trace du programme PROLOG : Suite des resolvantes pendant le deroulement du programme PROLOG.
Arbre de preuve PROLOG : Arbre des buts reduits pendant le deroulement du programme PROLOG.
Points de choix
Choix du sous but a resoudre Ai : le plus a gauche dans la resolvante
Choix de la clause de P a utiliser dans la reduction : la premiere par ordre d’apparition dans P satisfaisant A = Ai

Mecanisme de retour arriere integr dans PROLOG

Si echec, remise en cause du choix immediatement precedent de la clause de P utilisee pour resoudre le sous-but courant. On peut egalement forcer le retour arriere ( 😉 : PROLOG enumere alors toutes les solutions.

Representation des listes

Une liste est une structure de donnees de nie comme une sequence d’elements de longueur n
– Exemple : la liste contenant les constantes demain, ce, sont,
les, vacances s’ecrira en Prolog : [demain, ce, sont, les, vacances]
Comment est representee une liste en Prolog ?
– comme tous les objets en Prolog, sous la forme d’un arbre. Par exemple, la liste [a, b, c] est representee, a l’aide de l’operateur . (cons) comme l’arbre
Il est souvent necessaire de manipuler la totalite de la queue d’une liste
– Exemple : soit L = [a,b,c].
?- L = [Head|Tail] reussit avec Head = a et Tail = [b,c] et L = .(a, Tail)
Il est possible de lister n’importe quel nombre d’elements de la liste suivi de « | » et le reste de la liste : – [a,b,c] = [a|[b,c]] = [a,b|[c]] = [a,b,c|[]]

Operations sur les listes

Les principales operations sur les listes sont les suivantes
– veri er si un eleement est present dans une liste
– concatener deux listes, i.e., obtenir une troisieme liste qui correspond a l’union des deux listes
– ajouter ou supprimer un element a une liste
– compter le nombre d’elements d’une liste
– …
En Prolog, la liste permet egalement de modeliser les ensembles
Le programme permettant de determiner si la relation member(X,L) est vrai s’appuie sur les observations suivantes : X est un membre de L si
– X est la t^ete de L, ou
– X est membre de la queue de L
Le programme s’ecrit en Prolog
member(X, [X| Tail]).
member(X, [ |Tail]) :- member(X, Tail).
Soit la relation member(X,L)qui est vrai X est element d’une liste L
?- member(b,[a,b,c]) reussit ?- member(b,[a,[b,c]]) echoue
?- member([b,c],[a,[b,c]]) reussit ?- member(X,[a,b,c]) ?
?- member(a,L) ?
L’operateur de concatenation : pour ecrire le programme permettant de concatener deux listes, deux cas doivent ^etre consideres en fonction du premier argument L1 :
Le premier argument est la liste vide, la seconde liste et le resultats sont identiques
Le premier argument est une liste non vide, qui peut donc ^etre decompos en une t^ete et une queue
conc ( [ ] , L,L ) .
conc ( [X|L1] , L2 , [X|L3] ) :- conc (L1 , L2 , L3).
L’operateur de concatenation peut servir a veri er qu’une liste respecte une certaine forme
Exemple : il est possible de trouver un element qui precede un element donne de la liste :
?- conc (Before , [may| After] , [jan, feb, mar, apr, may, jun, jul, aug, sep, oct, nov, dec]). Before = [jan, feb, mar , apr]
After = [jun, jul, aug, sep, oct, nov, dec]
Autre exemple :
?- conc ( , [Month1,may,Month2| ] , [jan, feb, mar, apr, may, jun, jul, aug, sep, oct, nov, dec]) .
Month1 = apr
Month2 = jun
L’operateur de concatenation peut ^etre utile pour decomposer une liste en deux listes
Utilisation inversee de l’operateur conc
?- conc (L1, L2, [a, b, c]).
conc (L1, L2, [a, b, c]).
L1=[]
L2 = [a b, c] ;
L1 = [a]
L2 = [b, c] ;
L1 = [a, b]
L2 = [c] ;
L1 = [a, b, c]
L2=[];
L’operateur de concatenation peut permettre de supprimer les elements d’une liste apres un element ou une une sequence d’elements
Exemple :
?- L1 = [a, b, z, z, c, z, z, z, d, e] , conc (L2, [z, z, z| ] , L1).
L1 = [a , b, z, z, c, z, z, z, d, e]
L2 = [a , b, z, z, c]
L’operateur de concatenation peut permettre de tester si un element est present dans une liste ou non member1(X,L) :- conc ( , [X| ],L)

Logique clausale propositionnelle

Connecteurs
:- si
; ou , et
clause : tete [ :- corps ].
tete : [ litteral[ ; litteral ] ]
corps : litteral [ , litteral ]
Exemple :
marie ; celibataire :- homme, adulte. Un homme adulte est soit marie, soit celibataire

Logique clausale propositionnelle

Un programme est un ensemble ni de clauses, toutes terminees par un point ; un ensemble de clauses doit s’interpreter comme une conjonction de clauses.
En notation PROLOG homme ;femme :- humain. humain :- homme. humain :- femme.
En notation logique classique (humain ! (homme _ femme))^ (homme ! humain)^ ((femme ! humain)
ou encore
(:humain _ homme _ femme)^
(:homme _ humain)^
(:femme _ humain)

Chapitre 0 : Généralités
Ch. 1 : Résolution en logique propositionnelle
Rappels logique propositionnelle
Résolution en logique propositionnelle
Sémantique logique des prédicats
Introduction à PROLOG
L’interpréte PROLOG
Structures récursives : les listes
Logique des prédicats
Aspects avancés de PROLOG