Erfüllbarkeit

Eine Formel $\phi$ ist erfüllbar, wenn es mindestens eine Belegung $\beta$ gibt mit $\beta \models \phi$.
Sie ist unerfüllbar, wenn keine solche Belegung existiert.

Äquivalente Sicht

• $\phi$ ist erfüllbar $⟺$ $\mathrm{\neg }\phi$ ist nicht allgemeingültig (keine Tautologie).
• Zusammenhang zu Modell: Erfüllbarkeit bedeutet „es existiert ein Modell“.

Beispiele

• $X\vee \mathrm{\neg }X$ ist erfüllbar (sogar allgemeingültig).
• $X\wedge \mathrm{\neg }X$ ist unerfüllbar.