##  [Erfüllbarkeit](/de/node/59946) 

 Definition

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

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

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

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

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

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

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

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

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.