Eigenschaft einer Formel oder eines Formelmengen, dass es mindestens eine Interpretation, ein Modell oder eine Zuweisung von Wahrheitswerten gibt, die jede Formel der Menge wahr macht.

Prinzip

Eine Formel oder Theorie ist erfüllbar genau dann, wenn ein Modell existiert, in dem alle ihre Sätze gemäß der Semantik der betrachteten Logik wahr sind.

Demonstration

In der Aussagenlogik ist die Klauselmenge {p ∨ q, ¬p} erfüllbar, weil die Zuweisung p = falsch, q = wahr beide Klauseln wahr macht; in der Prädikatenlogik ist eine Theorie mit ∃x P(x) erfüllbar, falls es eine Interpretation mit mindestens einem Element gibt, das P erfüllt.

Fehlanwendung

Syntaktische Herleitbarkeit aus Axiomen mit Erfüllbarkeit gleichzusetzen: Eine Menge kann beweistechnisch konsistent, aber in bestimmten nicht‑standard Semantiken unerfüllbar sein, oder erfüllbar ohne in einem eingeschränkten Beweissystem ableitbar zu sein.

Konsequenz

Ist eine Menge erfüllbar, so lässt sich mindestens ein konkretes Modell angeben oder darüber argumentieren; Erfüllbarkeit ermöglicht modellbasierte Methoden wie Gegenbeispielsuche und Modellprüfung.

Umkehrung

Die Umkehrung der Erfüllbarkeit ist die Unerfüllbarkeit (kein Modell existiert); im Gegensatz dazu ist Gültigkeit nicht einfach die Negation der Erfüllbarkeit, sondern eine universelle Wahrheitsbedingung für alle Modelle.

Abgrenzung

Erfüllbarkeit ist semantisch und hängt von der gewählten Logik und ihren zulässigen Modellen ab; in manchen nichtklassischen Logiken ändert sich, was als Modell gilt, und die Existenz endlicher versus unendlicher Modelle kann variieren.

Semantische Spannung

Erfüllbarkeit vs Beweisbarkeit: Erfüllbarkeit betrifft die Existenz von Modellen, Beweisbarkeit hingegen syntaktische Herleitungen — Vollständigkeitssätze verbinden beide, beseitigen aber praktische Differenzen nicht.

Synthese

Erfüllbarkeit besagt, dass eine Interpretation existiert, die alle Sätze wahr macht; es ist eine semantische Existenzbehauptung, die Modellkonstruktion, Gegenbeispielsuche und viele automatisierte Beweistechniken stützt.