Une procédure de preuve dirigée par les buts, de type tableau, qui tente de réfuter un ensemble de clauses en éliminant systématiquement des modèles candidats par des expansions dirigées et la fermeture de branches.

Principe

Sélectionner un littéral but et l'étendre en résolvant avec des clauses pour générer des sous-buts ; fermer les branches lorsqu'apparaissent des contradictions, écartant ainsi des modèles satisfaisant l'ensemble de clauses initial jusqu'à obtenir une réfutation.

Démonstration

Un prouveur qui tente de réfuter un ensemble de clauses choisit un littéral L, résout avec des clauses dont la tête unifie avec L pour produire de nouveaux sous-buts, et ferme une branche lorsqu'un littéral et sa négation apparaissent, donnant un arbre de réfutation compact.

Mauvaise application

Confondre l'élimination de modèles avec une saturation aveugle (résolution globale), négliger les vérifications de boucle ou les stratégies de sélection appropriées, ce qui peut rendre la procédure non terminante ou générer des expansions non pertinentes.

Conséquence

Donne des réfutations dirigées par les buts souvent plus compactes que des preuves par saturation et permet l'extraction de preuves et le raisonnement constructif sur contre-modèles en logique des prédicats clausale.

Inversion

La résolution globale ou les procédures de construction de modèles qui saturent l'ensemble de clauses sans direction par but constituent l'inverse conceptuel ; elles cherchent la contradiction par inférence exhaustive plutôt qu'en écartant des modèles candidats via l'expansion de buts.

Limite

S'applique aux cadres de logique clausale du premier ordre ; son efficacité dépend des stratégies de sélection et d'ordonnancement et elle diffère par des détails opérationnels des méthodes de tableaux, de résolution et de recherche de modèles.

Tension sémantique

Tension entre élimination de modèles, résolution, tableaux et méthodes de recherche de modèles : chacune échange direction par but, saturation et forme des preuves ou contre-modèles produits.

Synthèse

L'élimination de modèles est un calcul de réfutation orienté but qui écarte des modèles candidats en développant des buts et en fermant des branches contradictoires, conjuguant l'intuition des tableaux et l'unification de la résolution pour produire des réfutations.