Règle de résolution

En logique mathématique, la règle de résolution ou principe de résolution de Robinson est une règle d'inférence logique qui généralise le modus ponens. Cette règle est principalement utilisée dans les systèmes de preuve automatiques, elle est à la base du langage de programmation logique Prolog.

En logique propositionnelle

La règle du modus ponens s'écrit ${\frac {p\qquad p\rightarrow q}{q}}$ et se lit : de p et de "p implique q", je déduis q. On peut réécrire l'implication "p implique q" comme "p est faux ou q est vraie". Ainsi, la règle du modus ponens s'écrit ${\frac {p\qquad (\lnot p\lor q)}{q}}$.

La règle de résolution, elle, généralise la règle du modus ponens car elle s'applique sur des clauses quelconques. Une clause est une formule qui est une disjonction (un "ou") de littéraux (une proposition atomique ou une proposition atomique précédée d'une négation). Par exemple $(\lnot p\lor q)$ est une clause avec deux littéraux ("non p" et "q"). Ainsi, en logique propositionnelle, la règle de résolution s'écrit :

${\frac {(p\lor L_{1}\lor \dots L_{n})\qquad (\lnot p\lor M_{1}\lor \dots \lor M_{k})}{(L_{1}\lor \dots L_{n}\lor M_{1}\lor \dots \lor M_{k})}}$

Autrement dit, étant donné deux clauses $(p\lor L_{1}\lor \ldots \lor L_{n})$ et $(\lnot p\lor M_{1}\lor \ldots \lor M_{k})$, on en déduit $(L_{1}\lor \dots L_{n}\lor M_{1}\lor \dots \lor M_{k})$. La formule déduite, c'est-à-dire $(L_{1}\lor \dots L_{n}\lor M_{1}\lor \dots \lor M_{k})$ est appelé résolvant de $(p\lor L_{1}\lor \ldots \lor L_{n})$ et $(\lnot p\lor M_{1}\lor \ldots \lor M_{k})$. Bien sûr, l'application de la règle est donnée à permutation près des littéraux.

Exemples

Par exemple :

${\frac {(a\lor \lnot b\lor \lnot c)\qquad (b\lor e\lor \lnot f)}{(a\lor \lnot c\lor e\lor \lnot f)}}$

${\frac {p\qquad \lnot p}{\bot }}$ où ${\bot }$ dénote la contradiction (clause vide).

En logique des prédicats

En logique des prédicats les formules atomiques sont de la forme $P(t_{1},\ldots ,t_{n})$ où $P$ est un symbole de prédicat et les $t_{i}$ sont des termes composés de constantes, de variables et de symboles de fonctions. La règle de résolution en logique des prédicats est similaire à la règle de résolution en logique propositionnelle mais les formules atomiques partagées par deux clauses ne doivent pas être identiques mais unifiables. Deux formules atomiques sont unifiables s'il existe une substitution des variables par des termes qui rend les deux formules identiques (voir unification). Par exemple :

${\frac {P(a)\qquad (\lnot P(x)\lor Q(x))}{Q(a)}}$

est une application de la règle de résolution en logique des prédicats. Elle se lit : de "P(a)" et de "(pour tout x) non P(x) ou Q(x)", je déduis "Q(a)". Ici, la formule atomique $P(a)$ et la formule atomique $P(x)$ sont unifiables avec la substitution $x\mapsto a$. Plus généralement, la règle de résolution en logique des prédicats est :

${\frac {(A\lor L_{1}\lor \dots L_{n})\qquad (\lnot B\lor M_{1}\lor \dots \lor M_{k})}{(L_{1}[\sigma ]\lor \dots L_{n}[\sigma ]\lor M_{1}[\sigma ]\lor \dots \lor M_{k}[\sigma ])}}$

où $\sigma$ est un unificateur principal des formules atomiques $A$ et $B$.

On peut effectuer la résolution sur deux littéraux s'ils portent sur des formules atomiques identiques ou sur des formules unifiables.

Par exemple, les formules atomiques

$P(x,a,y)$ et $P(c,a,z)$, où a et c sont des constantes,

sont unifiables par la substitution $x\to c,y\to z$. Par contre

$P(x,a,y)$ et $P(c,b,z)$, où a, b et c sont des constantes,

ne sont pas unifiables car les constantes ne peuvent être remplacées.

Exemple

$C_{1}=\lnot P(x)\lor \lnot Q(y)\lor R(x,y)$

$C_{2}=Q(a)$

$C_{3}=P(b)$

La substitution $y\to a$ permet d'appliquer la résolution sur Q, entre $C_{1}$ et $C_{2}$, ce qui produit

$C_{R}=\lnot P(x)\lor R(x,a)$

La substitution $x\to b$ permet d'appliquer la résolution sur P, entre $C_{3}$ et $C_{R}$ pour produire

$C_{S}=R(b,a)$

Résolution et preuves par réfutation

En général on utilise le principe de résolution pour effectuer des preuves par réfutation. Pour prouver que la formule $f$ est une conséquence logique des formules $f_{1},\ldots ,f_{n}$ on démontre que l'ensemble $\{f_{1},\ldots ,f_{n},\lnot f\}$ est inconsistant.

Pratiquement, il faut commencer par mettre toutes les formules sous forme clausale, pour cela on doit les mettre sous forme prénexe (tous les quantificateurs au début) puis les skolémiser.

Pour montrer qu'un ensemble de clauses est inconsistant, il faut réussir à engendrer la clause vide en appliquant la règle de résolution autant de fois que nécessaire.

Exemple

On veut montrer que les trois formules

1. $\forall x\ ((S(x)\lor T(x))\to P(x))$,
2. $\forall x\ (S(x)\lor R(x))$,
3. $\lnot R(a)$

ont pour conséquence la formule $P(a)$.

La première formule est équivalente à $\forall x\ (\lnot S(x)\land \lnot T(x))\lor P(x)$ qui est équivalente à $\forall x\ (\lnot S(x)\lor P(x))\land (\lnot T(x)\lor P(x))$ et produit donc les deux clauses

$C_{1}=\lnot S(x)\lor P(x)$

$C_{2}=\lnot T(x)\lor P(x)$

La seconde formule donne immédiatement la clause

$C_{3}=S(x)\lor R(x)$

et la troisième

$C_{4}=\lnot R(a)$.

La négation de la conséquence cherchée donne

$C_{5}=\lnot P(a)$

Par résolution sur $R$ de $C_{3}$ et $C_{4}$ avec $x\to a$ on produit

$C_{6}=S(a)$

Par résolution sur $S$ de $C_{1}$ et $C_{6}$ on produit

$C_{7}=P(a)$

Enfin $C_{5}$ et $C_{7}$ donnent la clause vide.

Stratégie d'application de la règle

Le principe de résolution étant complet, si l'ensemble de clauses considéré est inconsistant, on arrive toujours à générer la clause vide. Par contre, le problème de la consistance (satisfaisabilité) n'étant pas décidable en logique des prédicats, il n'existe pas de méthode pour nous dire quelles résolutions effectuer et dans quel ordre pour arriver à la clause vide.

On peut facilement trouver des exemples où l'on « s'enfonce » dans la génération d'une infinité des clauses sans jamais atteindre la clause vide, alors qu'on l'aurait obtenue en faisant les bons choix.

Différentes stratégies ont été développées pour guider le processus. Le système Prolog se base, par exemple, sur l'ordre d'écriture des clauses et l'ordre des littéraux dans les clauses. D'autres systèmes, comme CyC, utilisent une stratégie de coupure (en fonction des ressources consommées) pour éviter de générer des branches infinies.

Preuves de longueurs minimales

Haken a démontré que toute réfutation du principe des tiroirs avec n chaussettes (en anglais, il s'agit du pigeonhole principle) est de longueur au moins 2^{n/10[réf. nécessaire]}.

Liens externes

Exercices pour manipuler la règle de résolution, outil développé à l'ENS Rennes

Références

• (en) Robinson J. A., A Machine-Oriented Logic Based on the Resolution Principle, J. Assoc. Comput. Mach. 12, 23-41, 1965.
• (en) Kowalski, R., Logic for Problem Solving, North Holland, Elsevier, 1979.
• (fr) Benzaken, C., Systèmes formels : introduction à la logique et à la théorie des langages, Masson, Paris, 1991.
• (en) Bundy, A., The Computer Modelling of Mathematical Reasoning, Academic Press, London, 1983.
• (en) Huth, M., Ryan, M. Logic in Computer Science, Cambridge University Press, 2004.