Un mécanisme d'inférence général qui applique de manière répétée des règles d'inférence à un ensemble de formules ou de clauses jusqu'à ce qu'aucune nouvelle conséquence ne puisse être dérivée (point fixe) ou qu'une contradiction soit produite, couramment utilisé en démonstration automatique.

Principe

Appliquer de façon exhaustive les règles d'inférence applicables à la base de connaissances actuelle, ajouter les conséquences nouvelles et continuer jusqu'à clôture ; la correction et la terminaison dépendent de l'ensemble de règles, de l'ordonnancement et des stratégies (par ex. élimination des redondances).

Démonstration

En raisonnement basé sur les clauses, une procédure de saturation exécute des étapes de résolution et de simplification sur un ensemble initial de clauses, en ajoutant des résolvants et en simplifiant, jusqu'à ce que la clause vide soit dérivée (contradiction) ou qu'aucun nouveau résolvant ne subsiste selon la stratégie choisie.

Mauvaise application

Lancer la saturation sans contrôle des redondances, sans ordonnancement ni stratégies de sélection peut rapidement générer un nombre intractable de conséquences et provoquer un effondrement mémoire/temps, rendant la saturation naïve impraticable pour des théories complexes.

Conséquence

Lorsqu'elle est efficacement contrôlée (par subsomption, ordonnancement des termes et heuristiques), la saturation fournit une recherche de preuves complète pour de nombreux logiques et prend en charge l'ajout incrémental d'axiomes tout en maintenant les conséquences dérivées.

Inversion

L'inverse est la recherche dirigée par objectif (top-down) qui travaille à rebours à partir d'une formule cible plutôt que d'épuiser les conséquences en avant ; cela peut être plus ciblé mais peut manquer de lemmes dérivés en avant utiles si on ne combine pas avec la saturation.

Limite

S'applique aux systèmes déductifs où les règles d'inférence et les propriétés de clôture sont bien définies ; ne garantit pas la terminaison en logique du premier ordre en général sauf si des restrictions ou des stratégies d'équité sont imposées.

Tension sémantique

Tension entre saturation avant et méthodes dirigées par but en arrière : la saturation est exhaustive et peut produire des lemmes utiles pour plusieurs preuves, tandis que la recherche arrière est ciblée et souvent plus efficace pour des requêtes spécifiques.

Synthèse

Une procédure de saturation est l'application disciplinée et exhaustive des règles d'inférence avec des stratégies de contrôle des redondances et d'ordonnancement pour atteindre un point fixe des conséquences dérivables ou détecter une contradiction, formant le socle de nombreux systèmes de raisonnement automatique.