Eine syntaktische Transformation, die existenzielle Quantoren durch Einführung von Skolem-Funktionen oder Konstanten entfernt und eine äquiersatisfizierbare Formel erzeugt, in der existenzielle Quantoren eliminiert sind; gebräuchlich als Schritt zur Klauselbildung oder automatischer Beweisführung.

Prinzip

Ersetze existenziell quantifizierte Variablen durch frische Skolem-Funktionen, deren Argumente die universell quantifizierten Variablen im Geltungsbereich des Existenzquantors sind; dies erhält die Erfüllbarkeit (nicht jedoch die logische Äquivalenz) und erzeugt für die Resolution geeignete Formeln.

Demonstration

Aus ∀x ∃y P(x,y) wird durch Einführung einer Skolem-Funktion f die Formel ∀x P(x, f(x)); erfüllbare Modelle der Ursprungsformel korrespondieren zu Modellen der skolemisierten Form bei geeigneter Interpretation von f.

Fehlanwendung

Skolemierung als Erhalt der Äquivalenz statt nur der Erfüllbarkeit zu betrachten, führt in Kontexten, die logische Äquivalenz erfordern (z. B. bei der Gewinnung deduktiver Konsequenzen statt bloßer Satisfiability-Prüfung), zu unsauberen Substitutionen.

Konsequenz

Skolemierung ermöglicht mechanisierte Beweisverfahren (Klauselgenerierung, Resolution) durch Entfernung existenzieller Quantoren und liefert eine Form, die für Unifikation und automatische Suche geeignet ist; sie vereinfacht Zeugenbehandlung, kann aber konstruktive Inhalte verschleiern.

Umkehrung

Die Umkehr besteht darin, existenzielle Quantoren oder Zeugen explizit wieder einzuführen (Zeugenterme oder konstruktive Skolem-Konstanten), um Äquivalenz und konstruktive Information zurückzugewinnen; dies erfordert oft zusätzliche Information oder einen Existenzbeweis.

Abgrenzung

Garantiert bei korrekter Anwendung Äquiersatisfiabilität für Formeln der ersten Stufe, bewahrt jedoch nicht allgemein Gültigkeit oder Ableitungsrichtung; in manchen höherstufigen oder konstruktiven Kontexten ist sie ohne Anpassung nicht direkt anwendbar.

Semantische Spannung

Spannung gegenüber konstruktiven Interpretationen: Skolemierung ist klassisch und modelltheoretisch (erhält Erfüllbarkeit) und steht im Widerspruch zu konstruktiven Anforderungen, explizite Zeugen zu liefern oder beweisbare Existenzbehauptungen zu bewahren.

Synthese

Skolemierung ist eine modell-erhaltende syntaktische Umschreibung, die existenzielle Quantoren durch neue Funktionssymbole ersetzt, die von umgebenden universellen Variablen abhängen, und so logische Äquivalenz gegen Äquiersatisfiabilität eintauscht, um klauselbasiertes automatisches Schließen zu erleichtern.