La procédure décisionnelle ou la tâche algorithmique consistant à déterminer si un ensemble de prémisses Γ implique sémantiquement une conclusion φ dans une logique et une sémantique données (noté Γ ⊨ φ), souvent par recherche de preuves ou de contre-modèles.

Principe

La vérification d'entailment se ramène soit à montrer que chaque modèle de Γ est un modèle de φ (approche sémantique), soit à montrer que φ est dérivable de Γ dans un système de preuve correct (approche syntaxique) ; l'équivalence dépend de la correction et de l'exhaustivité du système de preuve par rapport à la sémantique.

Démonstration

En logique propositionnelle, Γ ⊨ φ se vérifie en testant la satisfaisabilité : Γ ⊨ φ sii Γ ∪ {¬φ} est insatisfiable, donc un solveur SAT peut confirmer l'entailment en signalant l'insatisfaisabilité de la formule combinée.

Mauvaise application

Confondre la démontrabilité syntaxique (Γ ⊢ φ) avec l'entailment sémantique lorsque le système de preuve choisi est incomplet pour la sémantique visée, ou appliquer des procédures de vérification d'entailment en dehors de leur domaine de décidabilité (supposer une procédure de décision pour des logiques indécidables).

Conséquence

Une vérification d'entailment fiable permet la démonstration automatisée, la vérification de programmes et le traitement de requêtes ; sa complexité ou sa décidabilité guide la conception des outils (par exemple NP-complet en propositionnel, semi-décidable ou indécidable pour de nombreux fragments du premier ordre).

Inversion

Le non-entailment (Γ ⊭ φ) se traduit par un témoin informatif : un contre-modèle satisfaisant Γ et falsifiant φ, qui réfute la conséquence candidate et aide au débogage ou à la révision d'hypothèses.

Limite

Décidable et souvent efficacement résoluble en logique propositionnelle et dans de nombreux fragments décidables restreints ; indécidable ou seulement semi-décidable en logique du premier ordre générale selon le fragment et la sémantique ; dépend de la logique choisie, de la signature et de la question de l'entailment sur modèles finis.

Tension sémantique

La tension vient de la différence entre entailment model-théorique (sémantique) et démontrabilité proof-théorique (syntaxique) : les systèmes pratiques équilibrent ces dimensions via des heuristiques sonores, complètes ou incomplètes et en sacrifiant parfois l'exhaustivité pour la performance.

Synthèse

La vérification de la conséquence logique est la tâche opérationnelle consistant à décider si des prémisses impliquent une conclusion, par recherche de modèles sémantiques ou de preuves syntaxiques ; ses garanties et son applicabilité dépendent de la décidabilité de la logique et de la stratégie de vérification choisie.