Programmation Logique

Prolog : Calcul des prédicats, Résolution et Unification

Khaled Barbaria
[Link]@[Link]

Faculté des Sciences de Bizerte

Cycle Ingénieur, première année

2023-2024

Prolog : Calcul des prédicats, Résolution et Unification 1 - 39 Khaled Barbaria

Calcul des prédicats I

Syntaxe
Ensemble de variables (notées souvent x,y,z,...)
Ensemble de constantes (notées souvent a,b,c,...)
Ensemble de fonctions d’arités strictement positives (les
constantes = s fonctions d’arité 0)
termes : toute variable ou constante est un terme, si f est un
symbole de fonction d’arité n, et t1 , .., tn sont des termes, alors
f (t1 , .., tn ) est un terme
Ensemble de prédicats (relations) d’arités positives ou nulles
atomes :expressions de la forme p(t1 , .., tn ) où p est un symbole
de prédicat n-aire et t1 , .., tn sont des termes
Remarque : les parenthèses sont parfois considérées comme
faisant partie du vocabulaire logique
Foncteur : terme construit à l’aide d’un symbole fonctionnel ou
prédicatif. Ses arguments sont eux-même des termes.

Prolog : Calcul des prédicats, Résolution et Unification 2 - 39 Khaled Barbaria

Calcul des prédicats II

Exemple : Socrate est mortel

(homme( socrate) ∧ (∀x homme(x) ⇒ mortel(x))) ⇒
mortel(socrate)
variables : x
fonctions :
constantes : socrate
prédicats : homme, mortel
atomes : homme(socrate), homme(x), mortel(x), mortel(socrate)

Prolog : Calcul des prédicats, Résolution et Unification 3 - 39 Khaled Barbaria

Calcul des prédicats III

Logique des prédicats

La logique des prédicats (ou logique du premier ordre) porte sur
les formules bien formées
les atomes sont des formules bien formées.
si f et g sont des formules bien formées et x est une variable, alors
¬ f, f∨ g, f∧ g, f ⇒ g,∀ x f et ∃ x f sont des formules bien formées
La logique des propositions (logique d’ordre 0) ne prend en
compte que les variables et les connecteurs usuels
La logique du second ordre (d’ordre 2) autorise la quantification
des fonctions et des prédicats.

Prolog : Calcul des prédicats, Résolution et Unification 4 - 39 Khaled Barbaria

Clauses de Horn I

Clauses de Horn
Une clause de Horn est une clause comportant au plus un littéral
positif. Une clause de Horn a donc pour forme générale
∀x1 , .., xn a ∧ ¬b1 ... ∧ ¬bq où les bi sont des atomes.
Une clause de Horn peut également s’écrire :
∀x1 , .., xn , b1 ... ∧ bq ⇒ a
Exemple : ∀x, y , z : pere(x, y ) ∧ pere(y , z) ⇒ grand_pere(x, z)
Les seules formules pouvant être écrites en Prolog sont des
clauses de Horn

Prolog : Calcul des prédicats, Résolution et Unification 5 - 39 Khaled Barbaria

Clauses de Horn II

Règles Prolog
Ce sont des clauses de Horn avec un littéral positif et au moins un
littéral négatif.
Exemple : la clause
(∀x, y , z enfant(x, y ) ∧ enfant(y , z) ⇒ petit_enfant(x, z)) est
équivalente à
(∀x, y , z ¬enfant(x, y ) ∨ ¬enfant(y , z) ∨ petit_enfant(x, z))
... s’écrit en Prolog :
petit_enfant_de(X,Z) :- enfant_de(X,Y),enfant_de(Y,Z).

Faits Prolog
Ce sont des clauses de Horn sans littéral négatif (clauses de Horn
positives)
Exemple : enfant_de(samir,ali).

Prolog : Calcul des prédicats, Résolution et Unification 6 - 39 Khaled Barbaria

Clauses de Horn III

Buts Prolog
Ce sont des clauses de Horn sans littéral positif (clauses de Horn
négatives)
Exemple : homme(X),pere_de(X,ali).
Même si les buts s’écrivent comme littéraux positifs a1 ∧ · · · ∧ ai ,
l’interpréteur va manipuler la conjonction de littéraux positifs
comme disjonction de littéraux négatifs : a1 ∨ · · · ∨ ai
Pour utiliser le mécanisme de résolution, les buts sont introduits
sous forme négative, et le but est de chercher une contradiction
(Résolution par réfutation)

Prolog : Calcul des prédicats, Résolution et Unification 7 - 39 Khaled Barbaria

Clauses de Horn IV

Algorithme de résolution d’un ensemble de clauses de Horn

Soit S l’ensemble de clauses
Tant que ⊥ ∈/S
Choisir p : clause unitaire positive et c : clause de contenant ¬p ;
Calculer la résolvante r de p et c ;
Remplacer S par (S − c) ∪ r
Si ⊥ ∈
/ S alors l’ensemble S est consistent
S’applique aux propositions (variables booléennes)
Complexité O(n2 ) mais Il y a des algorithmes linéaires

Prolog : Calcul des prédicats, Résolution et Unification 8 - 39 Khaled Barbaria

Clauses de Horn V

Resolution des clauses de Horn dans Prolog

Dans le format Prolog, le litéral positif est la tête de la clause
Alors la résolution consiste à unifier un litéral négatif avec la tête
d’une clause
Les litéraux négatifs sont vus comme nouveaux buts
Ainsi les corps des clauses devienent des nouveaux buts lorsque
les têtes sont unifiées.

Prolog : Calcul des prédicats, Résolution et Unification 9 - 39 Khaled Barbaria

Clauses de Horn VI

Programme Prolog
Une séquence (l’ordre est important) de faits et de règles. Il est
conseillé de regrouper les faits concernant et les règles
commençant par le même prédicat.
Portée des constantes et variables : les constantes : portent sur
tout le programme (tout le code chargé dans l’interpréteur) alors
que les variables ont une portée limitée à la règle dans laquelle ils
se trouvent.
On charge du code Prolog dans l’interpréteur en utilisant le
prédicat unaire consult consult(fichier’) ou en utilisant [].
Il est possible de charger plusieurs fichiers
Une fois les programmes chargés et donc la base de faits et de
règles constituée, on peut poser des questions
L’interpréteur effectue une démonstration logique pour répondre à
la question.

Prolog : Calcul des prédicats, Résolution et Unification 10 - 39 Khaled Barbaria

Sémantique déclarative et procédurale I

Sémantique déclarative
Prolog s’utilise avec une approche relationnelle.
Prolog permet d’établir des relations entre des entités.
Si dans la question on utilise des variables, alors Prolog va fournir
la substitution (ensemble de valeurs des variables) qui permet de
former une relation déductible de la base initiale.

Prolog : Calcul des prédicats, Résolution et Unification 11 - 39 Khaled Barbaria

Sémantique déclarative et procédurale II

Sémantique procédurale
On peut considérer le "moteur" de la résolution de Prolog comme
une boîte noire qui reçoit en entrée une question et produit en
sortie soit un échec soit un succès constitué par un ensemble de
substitutions.
Pour obtenir les solutions à la question posée, Prolog utilise la
base initiale pour prouver les affirmations non directement
présentes dans la base en faisant des unifications.
Le moteur d’inférence de Prolog ne fonctionne pas par chaînage
avant (déduction récursive de faits à partir d’autres faits) mais par
chaînage arrière (à partir des faits à obtenir, recherche récursive
des faits qui permettent de les déduire).

Prolog : Calcul des prédicats, Résolution et Unification 12 - 39 Khaled Barbaria

Principe de résolution de Prolog I

Le programme est la base de connaissances C.

Le but original est la requête soumise par l’utilisateur, la négation
de ce dernier est implicitement ajoutée à la base, l’objectif est
alors de dériver la clause vide.
Trouver une clause dont la tête s’unifie se ramène à trouver une
clause dont le litéral positif s’unifie avec le litéral négatif sur lequel
on se concentre actuellement.
Le programme original (C) est le seul endroit où on peut trouver
des litéraux positifs
Les résultat de la résolution sont toujours des litéraux négatifs.

Prolog : Calcul des prédicats, Résolution et Unification 13 - 39 Khaled Barbaria

Principe de résolution de Prolog II

Principe de résolution
On crée la résolvante (suite de buts) < r1 , ..., rk >
On essaie de réduire la résolvante à la clause vide □.
Pour ceci, on modifie la résolvante courante ainsi : on choisit une
clause t : −q1 , ..., qn dont la tête t s’unifie avec r1 grâce à
l’unificateur σ , on obtient ainsi la résolvante
< q1σ , ..., qnσ , r2σ , ..., rkσ >.
On continue ainsi jusqu’à rencontrer un échec (aucune clause ne
peut effacer un but) ou obtenir □ .
En cas d’échec, on revient sur le dernier choix de clause. Les
clauses sont choisies dans l’ordre donné par le programme.

Prolog : Calcul des prédicats, Résolution et Unification 14 - 39 Khaled Barbaria

Principe de résolution de Prolog III

Recherche de solutions
Prolog cherche à produire toutes les solutions (système de
contraintes) qui permettent de satisfaire la question. Il va donc
chercher a réaliser tous les effacements possibles pour un terme
de la résolvante et va parcourir un arbre de résolution. Il fait ce
parcours en profondeur d’abord.
Prolog fonctionne de gauche à droite : il réécrit le premier terme
de la résolvante et place la réécriture de ce terme en tête de la
nouvelle résolvante.
La substitution obtenue pour unifier le premier terme avec la tête
de la règle choisie est appliquée simultanément à tous les autres
termes de la résolvante.

Prolog : Calcul des prédicats, Résolution et Unification 15 - 39 Khaled Barbaria

Principe de résolution de Prolog IV

Succès et échec de la procédure d’effacement

Afin d’effacer le terme T = pre(A1 , ...An ), Prolog parcourt
l’ensemble des clauses correspondant au prédicat pre/n dans
l’ordre dans lequel elles ont été définies dans la base initiale. Cet
ordre est donc très important.
L’effacement d’un terme à l’aide d’un fait diminue strictement la
taille de la résolvante. Prolog ne dérive vers la résolvante vide que
par l’utilisation de faits de la base initiale.
Prolog explore donc un arbre de résolvantes dont les feuilles sont
soit des résolvantes vides soit des résolvantes dont le premier
terme (gauche) ne peut être effacé.

Prolog : Calcul des prédicats, Résolution et Unification 16 - 39 Khaled Barbaria

Principe de résolution de Prolog V

Retour arrière ( backtracking )

Lorsque Prolog ne peut pas trouver de clause pour réécrire T1 il
backtrack pour explorer un autre chemin de résolution.
Il le fait aussi lorsqu’il a obtenu une résolvante vide (une solution)
pour fournir les autres solutions potentielles.
Lorsque l’on effectue un nouveau choix pour tenter d’effacer
différemment un but b, on « défait » toutes les affectations de
variables qui ont eu lieu depuis le précédent choix fait pour
effacer b

Pour éviter les problèmes de boucles infinies

Faire attention à l’ordre des déclarations.
Forcer les parcours en largeur
Détecter les cycles lors de l’application des règles.
Utiliser les coupures

Prolog : Calcul des prédicats, Résolution et Unification 17 - 39 Khaled Barbaria

Unification I

Prolog manipule des arbres qui peuvent contenir des parties

variables.
L’unification consiste à décider si deux arbres peuvent être rendus
égaux, ou non.
Le cas échéant, l’égalité est réalisée en affectant des variables
aux valeurs figurant dans l’un ou l’autre des arbres considérés.

Prolog : Calcul des prédicats, Résolution et Unification 18 - 39 Khaled Barbaria

Unification II

Algorithme classique d’unification

Soient deux arbres t1 et t2 .
t1 est constant ou est une variable de valeur connue, t2 est
constant ou est variable de valeur connue. Alors t1 = t2 .
t1 est une variable de valeur inconnue et t2 est constant ou est
variable de valeur connue. Alors valeur(t1 ) → t2 , vrai.
t1 et t2 sont des variables de valeur inconnue. Alors valeur(t1 )
→ t2 , vrai.
t1 = f (u1 , ..., un ) et t2 = f (u1′ , ..., un′ ). Alors Unification(u1 , u1′ ),
...,Unification(un , un′ ).

Prolog : Calcul des prédicats, Résolution et Unification 19 - 39 Khaled Barbaria

Unification III

L’unification est l’opération élémentaire que réalise Prolog pour rendre

deux termes identiques. Cette opération consiste a établir une
substitution (ensemble de couples (variable, valeur)) qui permettra
d’obtenir une équivalence des deux termes.
Cette substitution peut être assimilée à un ensemble de contraintes e
que l’on fait porter sur les variables de la substitution.
Cette opération peut échouer si aucune substitution ne permet
d’obtenir cette équivalence. L’unification est dépendante du fait
qu’apparaissent ou non des variables dans les termes, que les termes
soient atomiques ou non.

Prolog : Calcul des prédicats, Résolution et Unification 20 - 39 Khaled Barbaria

Unification IV

Deux termes atomiques sont unifiables s’ils sont identiques,

Une variable libre s’unifie toujours en s’instanciant a l’autre terme
Une variable instanciée se comporte comme son terme,
l’unification de deux variables libres les lie,
toutes les variables liées ne peuvent s’instancier qu’au même
terme,
Deux termes composés s’unifient composant a composant.

Prolog : Calcul des prédicats, Résolution et Unification 21 - 39 Khaled Barbaria

Unification V

Exemples
Terme1 Terme 2 ? Substitution Commentaire
√ Deux termes constants sont
a a {}
unifiables
a b × {} ssi ils sont identiques
√ L’unification d’un terme avec
A b {A=b} une variable libre est pos-
sible
a a
√ les variables X et Y sont
{X=a,Y=b}
liées
a X Y b
a a

X b Y b √ on donne la valeur de Y en
{X=c,Y=c}
remplaçant X par sa valeur
Y c c X

Prolog : Calcul des prédicats, Résolution et Unification 22 - 39 Khaled Barbaria

Unification VI

Exemples (2)
a a
l’unification de X
b Y b avec c nécessiterait
X {X=Y,X=c,
× l’unification des
Y=d}
Y c d X deux termes ato-
miques c et d.
a
a
b b on donne la valeur
√ {X=b,
X Y de Y en remplaçant
Y=b(d,b)}
d X X par sa valeur

Prolog : Calcul des prédicats, Résolution et Unification 23 - 39 Khaled Barbaria

Exemples d’unification I

Unification des constantes

Unification(0,1) ⇔ 0 = 1 : faux.
Unification(X,0) ⇔ valeur(X) ← 0, vrai.
Unification(X,1),Unification(X,0) ⇔ 0 = 1 : faux.
nul(0). un(1).
?- nul(1). No
?- nul(X).X = 0 ;
?- nul(X), un(X).No

Prolog : Calcul des prédicats, Résolution et Unification 24 - 39 Khaled Barbaria

Exemples d’unification II

Unification de variables
egal(X,X)
?- egal(Y,Z). Y = _G153 Z = _G153
_G153 est un nom de variable qui lie Y à Z.
?- egal(f(0,X),f(Y,1)).
X = 1 Y = 0 ;
No
Première unification : f(0,X) avec f(Y,1).
Deuxième unification : 0 avec Y.
Troisième unification : X avec 1.
?- egal(f(X,2,g(Z)),f(g(1),Y,g(4))).
X = g(1) Z = 4 Y = 2 ;
No

Prolog : Calcul des prédicats, Résolution et Unification 25 - 39 Khaled Barbaria

Exemples d’unification III

Autres exemples
egal(f(Y,1,g(X)),f(X,Y,g(2))).
No
Première unification : f(Y,1,g(X)) avec f(X,Y,g(2)).
Deuxième unification : X = Y.
Troisième unification : Y = 1 (donc X=1).
Quatrième unification : g(X) avec g(2).
Cinquième unification : X=2, or X=1, donc 1=2 : faux.
inf(X,f(aa,X)).
?- inf(Y,Z).
Y = _G147 Z = f(aa, _G147) ; No
?- inf(Y,Y).
Y = f(aa,X) et Y non connu. Donc Y de la forme Y =
f(aa,T), et T = f(aa,T). Ça part à l’infini : objet à définition
récursive.

Prolog : Calcul des prédicats, Résolution et Unification 26 - 39 Khaled Barbaria

Exemples d’unification IV

Unification des expressions arithmétiques

mult(X,Y,Z) :- 2*(X+5) = Y * Z.
?- mult(X,Y,Z).
X = _G165 Y = 2 Z = _G165+5
Yes ?
égal_à_deux(X) :- X = 1+1.
?- égal_à_deux(2).
No
On tente l’unification de 2 et de 1+1, qui sont deux expressions
correspondant à deux arbres de racines différentes : 2 et +, d’où
l’échec.

Prolog : Calcul des prédicats, Résolution et Unification 27 - 39 Khaled Barbaria

Motivation de la coupure I

Premier exemple : appartenance à une liste

Soit la fonction qui vérifie qu’un élément est bien dans une liste.
Première solution :
membre1(X,[Y|L]) :- X = Y.
membre1(X,[Y|L]) :- X \= Y, membre1(X,L).
Deuxième solution :
membre2(X,[X|_]).
membre2(X,[_|L]) :- membre2(X,L).
L’idée ici, c’est que le cas d’égalité a été traité avec la première
règle et que l’on n’a pas à en tenir compte lors de l’écriture de la
deuxième règle.

Prolog : Calcul des prédicats, Résolution et Unification 28 - 39 Khaled Barbaria

Motivation de la coupure II

Comparaisons des deux solutions

membre2(1,[1,1])

X=1,L=[1] X=1,Y=1,L=[1]
réussite membre2(1,[1])

X=1,L=[] X’=1,Y’=1,L’=[]
membre1(1,[1,1])
réussite membre2(1,[])

X=1,Y=1,L=[1] échec échec échec

L’écriture du programme a de grosses conséquences sur son

exécution.
Seule la première occurrence de X dans L nous intéresse. Est t il
possible de spécifier le programme pour qu’il s’arrête dès la
première occurrence trouvée.

Prolog : Calcul des prédicats, Résolution et Unification 29 - 39 Khaled Barbaria

Motivation de la coupure III

Deuxième exemple : fonctions booléennes

On s’intéresse ici au codage des fonctions booléennes. On veut
associer une valeur booléenne, 0 ou 1, à chaque formule.
Soit une formule p. Si p s’efface, p est vraie,
d’où :valeur_booléenne(p,1) :- p.
Comment faire pour associer la valeur 0 à p quand p ne s’efface
pas ? Première idée :
valeur_booléenne(P,1) :- P.
valeur_booléenne(P,0).
?- valeur_booléenne(membre1(2,[1]),Y). Y = 0 ;No
?- valeur_booléenne(membre1(1,[1]),Y). Y = 1 ; Y = 0
; No
Si p ne s’efface pas, la valeur 0 lui est associée, OK. Pas contre,
si p s’efface, les valeurs 1 et 0 lui sont associées ! Solution : la
coupure !

Prolog : Calcul des prédicats, Résolution et Unification 30 - 39 Khaled Barbaria

Coupures I

Coupure
La coupure permet d’oublier des points de choix lors de
l’effacement.
Notation : « ! » (point d’exclamation).
Solution au problème de valeurs booléennes :
valeur_booléenne(P,1) :- P, !.
valeur_booléenne(P,0).
?- valeur_booléenne(membre1(2,[1]),Y). Y = 0 ; No
?- valeur_booléenne(membre1(1,[1]),Y). Y = 1 ; No

Prolog : Calcul des prédicats, Résolution et Unification 31 - 39 Khaled Barbaria

Coupures II

Interprétation
Deux cas à considérer :
1 p peut être évalué à vrai : Une fois que p a été évalué à vrai, on «
évalue » la coupure (« ! »). Celle-ci supprime le backtracking sur
les choix mis en attente entre le moment où elle a été introduite et
celui où elle a été effacée.
2 p ne s’efface pas (p ne peut pas être évalué à vrai). Comme p ne
s’efface pas, la coupure n’est pas atteinte et il y a backtracking.

Prolog : Calcul des prédicats, Résolution et Unification 32 - 39 Khaled Barbaria

Coupures III

Solution avec coupure pour l’appartenance à une liste

Dans la recherche d’appartenance d’un élément à une liste, la coupure
permet d’arrêter le programme lors de la découverte de la première
solution possible :
membre3(X,[X|L]) :- !.
membre3(X,[Y|L]) :- membre3(X,L).

Prolog : Calcul des prédicats, Résolution et Unification 33 - 39 Khaled Barbaria

Coupures IV

Vue théorique
Soit b1 , ., bn la suite de buts à effacer à un instant donné, et soit
c1 , .., cm la suite des choix en attente à cet instant, du plus ancien
au plus récent. c1 , ., cm sont donc des buts déjà effacés. Notation :
[c1 , .., cm ]b1 , b2 , ., bn .
Supposons que pour effacer b1 on utilise la règle p :-
q1 , .., qi , !, qi+1 , ..., ql , avec la contrainte b1 = p. On obtient donc le
nouvel état : [c1 , ..., cm , b1 ]q1 , ..., qi , !, qi+1 , .., ql , b2 , .., bn
Les effacement successifs donnent :
[c1 , .., cm , b1 , q1 ]q2 , .., qi , !, qi+1 , .., ql , b2 , .., bn ,
[c1 , .., cm , b1 , q1 , .., qi ]!, qi+1 , .., ql , b2 , .., bn
[c1 , .., cm ]qi+1 , .., ql , b2 , .., bn
L’effacement de la coupure supprime tous les choix (quelque soit
la règle concernée) mis en attente, depuis le plus récent et jusqu’à
celui dont l’effacement a provoqué l’apparition de la coupure.

Prolog : Calcul des prédicats, Résolution et Unification 34 - 39 Khaled Barbaria

Coupures V

Autre exemple : la conditionnelle

On veut réaliser ici une conditionnelle if C then A else B.
ifthenelse(C,A,B) :- C, !, A.
ifthenelse(C,A,B) :- B.

Si C s’évalue à vrai on s’interdit d’avoir recours à la deuxième règle et

on évalue A. Sinon, on évalue B.
Attention : les règles doivent être écrites dans cet ordre !

Retour sur les fonctions booléennes

et(P,Q,1) :- P, Q, !.
et(P,Q,0).
ou(P,Q,1) :- P, !.
ou(P,Q,1) :- Q, !.
ou(P,Q,0).

Prolog : Calcul des prédicats, Résolution et Unification 35 - 39 Khaled Barbaria

Coupures rouges et coupures vertes I

Attention : la coupure peut changer la sémantique d’un prédicat !

Coupure verte
Si la sémantique d’un prédicat est inchangée quand on lui ajoute
le cut, on dit que la coupure est verte
Exemple de coupure verte :
genre(P,masculin) :- homme(P), ! .
genre(P,feminin) :- femme(P).

Prolog : Calcul des prédicats, Résolution et Unification 36 - 39 Khaled Barbaria

Coupures rouges et coupures vertes II

Coupure rouge
Si la sémantique d’un prédicat est changée après l’ajout de la
coupure, la coupure est dite rouge
Exemple de coupure rouge : Exemple de coupure rouge :
Exemple du membre3. Le but member3(X,[a,b,c]). délivre une
seule solution pour X et pas toutes les solutions.
membre3(X,[X|L]) :- !.
membre3(X,[Y|L]) :- membre3(X,L).

Prolog : Calcul des prédicats, Résolution et Unification 37 - 39 Khaled Barbaria

Négation I

Négation
non(P) :- si P est vrai alors renvoyer faux... Comment coder
une telle propriété ? On utilise le prédicat fail qui est toujours
faux.
non(P) :- P, fail.
non(P).
Si p est vrai alors faux, sinon vrai. Le problème ici, c’est que si p
est vrai, non(P) vaut simultanément vrai et faux. On doit donc
utiliser la coupure :
non(P) :- P, !, fail.
non(P).
On effectue ce que l’on appelle une « négation par l’échec ». La
coupure oblige la première règle à échouer et interdit le
backtracking.

Prolog : Calcul des prédicats, Résolution et Unification 38 - 39 Khaled Barbaria

Négation II

Interprétation de la (double) négation

On considère la base suivante :
1 non ( P) : − P , ! , f a i l .
2 non ( P) .
3
4 chiffre (1) .
5 chiffre (2) .
6 chiffre (3) .

Qu’est-ce qu’il existe comme solution ?

?- chiffre(X).
X = 1 ; X = 2 ; X = 3.
Est ce ce prédicat ne s’évalue jamais à vrai ?
?- non(chiffre(X)).
false.
Existe-t-il une solution ?
?- non(non(chiffre(X))). true.

Prolog : Calcul des prédicats, Résolution et Unification 39 - 39 Khaled Barbaria