La méthode de résolution de Robinson
La méthode de résolution de Robinson
Logique mathématique, Programmation logique · course
Fiche de révisionFiche de cours
Rédigée à partir de ce document, puis vérifiée avant publication.
Ce document présente la méthode de résolution de Robinson, une technique fondamentale en logique mathématique destinée aux étudiants en informatique et mathématiques. Cette méthode permet de démontrer la validité ou l'insatisfiabilité de formules logiques, notamment dans le cadre des preuves automatiques et de la programmation logique.
La résolution est une méthode purement syntaxique, automatisable, développée par Robinson en 1965. Elle produit des preuves par réfutation, similaire à la démonstration par contradiction : pour prouver la validité d’une formule, on démontre l’insatisfiabilité de sa négation. Cette méthode est simple, efficace et complète, ce qui en fait un choix privilégié pour les preuves automatiques. Elle est à la base du langage de programmation logique Prolog.
La méthode applique une ou deux règles d'inférence sur des formules sous forme clausale.
Soient deux clauses closes (sans variables) C’ et C’’, et un atome p. La clause résolvante de C’ et C’’ sur p est obtenue en supprimant p dans C’ et ¬p dans C’’, puis en prenant l’union des restes.
Exemple :
C’ = {¬p, r}
C’’ = {p, q}
Résolvante = {r, q}
La clause facteur d’une clause C’ est une sous-clause contenant un seul littéral l de C’. Par exemple :
Clause facteur de {q, p} est {q}
Clause facteur de {¬p, q} est {¬p}
Le système d’inférence R0 pour la résolution close est défini par :
La règle de résolution (Res) s’écrit :
De C’ ∪ {p} et C’’ ∪ {¬p} on déduit la clause résolvante C’ ∪ C’’
La règle de factorisation (Fact) permet de simplifier une clause en supprimant les littéraux redondants.
La clause vide (notée □) représente la contradiction, obtenue lorsqu’on déduit p et ¬p.
Pour montrer qu’un ensemble ℰ de formules closes est insatisfiable :
Soit ℰ = {p ∨ q, ¬p ∨ q, p ∨ ¬q, ¬p ∨ ¬q}
On applique la résolution et la factorisation pour obtenir la clause vide, prouvant l’insatisfiabilité.
L’unification est essentielle pour appliquer la résolution aux clauses contenant des variables. Elle consiste à rendre identiques deux expressions en instanciant leurs variables par une substitution.
E = {f(x,g(y)), f(x,g(h(b))), f(a,z)}
s = {x ← a, y ← h(b), z ← g(h(b))}
E1s = E2s = E3s = f(a, g(h(b)))
Un unificateur n’est pas unique. Par exemple, pour A = f(x,b) et B = f(g(y),z) :
Pour unifier deux expressions A et B :
A : P(x, f(x), a)
B : P(y, z, u)
Étapes :
s = {}
s := s ∪ {x ← y}
s := s ∪ {z ← f(y)}
s := s ∪ {u ← a}
Résultat : s = {x ← y, z ← f(y), u ← a}
Le système d’inférence R1 étend R0 aux clauses du premier ordre avec variables. Il inclut :
La règle de résolution devient :
De C’ ∪ {l’} et C’’ ∪ {¬l’’} on déduit (C’ ∪ C’’) s
où s est le p.g.u de l’ et l’’
Il faut veiller à ce que deux clauses différentes n’aient pas de variables communes, ce qui nécessite un renommage préalable des variables.
Clauses initiales :
P(x), Q(x)
Renommage :
P(x), Q(y)
Résolution avec s = {x ← a} :
De P(a) et ¬Q(a) on déduit ...
Pour montrer qu’un ensemble ℰ de formules du premier ordre est insatisfiable :
Soit ℰ = {¬P(x) ∨ O(x), ¬M(x) ∨ ¬O(x), M(a), P(a)}. On montre que ℰ est insatisfiable par résolution.
La méthode de résolution est non déterministe car le choix des clauses pour appliquer Res et Fact n’est pas fixé. Une stratégie vise à guider ces choix tout en conservant la complétude.
La stratégie linéaire est complète, mais la stratégie linéaire input ne l’est pas forcément.
Un littéral positif (l+) est un atome, un littéral négatif (l-) est une négation d’atome.
Les stratégies négatives et positives sont complètes.
Les littéraux de chaque clause sont ordonnés (par exemple, les littéraux positifs en tête), et la résolution n’est permise que sur certains littéraux (ex. le premier littéral).
Une stratégie à la fois linéaire et ordonnée est complète.
Chaque clause résolvante est négative et de la forme {¬A1, ..., ¬An} avec A un atome.
La SLD est généralement non complète sauf si les clauses initiales sont des clauses de Horn (au plus un littéral positif par clause), ce qui est le principe de Prolog.
La règle de factorisation n’est plus nécessaire avec la SLD.
Clauses :
¬p ∨ q
¬q ∨ r
¬r ∨ s
¬s
Résolution SLD conduit à la clause vide □