Ein allgemeiner Inferenzmechanismus, der Inferenzregeln wiederholt auf eine Menge von Formeln oder Klauseln anwendet, bis keine neuen Konsequenzen mehr ableitbar sind (Fixpunkt) oder eine Widerspruchsklausel erzeugt wird; gebräuchlich in Theorembeweisern und automatischem Schließen.

Prinzip

Wende exhaustiv anwendbare Inferenzregeln auf die aktuelle Wissensbasis an, füge neue Konsequenzen hinzu und fahre fort bis zum Abschluss; Korrektheit und Terminierung hängen von Regelmenge, Ordnung und Strategien (z. B. Redundanzkontrolle) ab.

Demonstration

In klauselbasierter Beweisführung führt ein Sättigungsverfahren Resolution- und Vereinfachungsschritte auf einer Anfangsmenge von Klauseln aus, fügt Resolventen hinzu und vereinfacht, bis entweder die leere Klausel abgeleitet wird (Widerspruch) oder unter der gewählten Strategie keine neuen Resolventen verbleiben.

Fehlanwendung

Sättigung ohne Redundanzkontrolle, Ordnung oder Selektionsstrategien auszuführen kann sehr schnell zu einer intractablen Anzahl von Konsequenzen führen und Zeit- sowie Speicheraufwand explodieren lassen, wodurch naive Sättigung unpraktikabel wird.

Konsequenz

Wird Sättigung effektiv kontrolliert (durch Subsumption, Termordnungen und Heuristiken), liefert sie vollständige Beweissuche für viele Logiken und unterstützt inkrementelles Hinzufügen von Axiomen bei Erhalt abgeleiteter Konsequenzen.

Umkehrung

Das Gegenteil ist zielgerichtete, rückwärtsgerichtete Beweissuche (Top-Down), die von einer Zielformel ausgeht statt Vorwärtskonsequenzen zu erschöpfen; sie kann fokussierter sein, verpasst aber möglicherweise nützliche vorwärts abgeleitete Lemmata ohne Kombination mit Sättigung.

Abgrenzung

Gilt für deduktive Systeme, in denen Inferenzregeln und Abschluss-Eigenschaften klar definiert sind; garantiert nicht die Terminierung in allgemeiner Prädikatenlogik erster Ordnung, sofern keine Einschränkungen oder Fairnessstrategien gelten.

Semantische Spannung

Es besteht Spannung zwischen Vorwärtssättigung und rückwärtsgerichteten, zielorientierten Methoden: Sättigung ist umfassend und kann beweisübergreifend nützliche Lemmata erzeugen, während Rückwärtssuche für konkrete Anfragen oft effizienter ist.

Synthese

Ein Sättigungsverfahren ist die disziplinierte, erschöpfende Anwendung von Inferenzregeln mit Strategien zur Redundanzkontrolle und Ordnung, um einen Fixpunkt der ableitbaren Konsequenzen zu erreichen oder Widerspruch zu detektieren; es bildet die Grundlage vieler automatisierter Beweissysteme.