Erfüllbarkeit

Erfüllbarkeit ist in der Logik und Mathematik ein metasprachliches Prädikat für die Eigenschaft von logischen Aussagen und Aussageformen. Eine Aussage ist erfüllbar, wenn es eine Belegung (Interpretation, Bewertung) der Variablen gibt, für die der Wahrheitswert des gesamten Ausdrucks wahr ist.

Mathematik

In der Mathematik ist die Erfüllbarkeit vor allem von (Un-) Gleichungen und (Un-) Gleichungssystemen interessant. Die allgemeine Definition kann dann umformuliert werden zu: "Es gibt (mindestens) eine Lösung".

Beispiele: In der Theorie der reellen Zahlen (also dem üblichen Zahlensystem) ist die Gleichung 2x + 1 = 3x lösbar, also diese Aussage erfüllbar.

Das Gleichungssystem $x < 0, x^2 \leq 0$ ist dagegen nicht lösbar, denn die einzige Lösung für $x^2 \leq 0$ wäre x = 0, aber diese Lösung erfüllt nicht x < 0. Diese Aussage ist also nicht erfüllbar.

Logik

In der Aussagenlogik kann man Aussagen auf Grund ihrer Erfüllbarkeit klassifizieren, wobei die auftretenden Variablen als Aussagen Wahrheitswerte annehmen. Eine Aussageform heißt...

• erfüllbar, wenn sie erfüllbar ist (also eine Belegung der Variablen eine wahre Aussage erzeugt).

• eine Tautologie, wenn jede (!) Belegung der Variablen eine wahre Aussage erzeugt.

• eine Kontradiktion, wenn sie nicht erfüllbar ist. Dann ist die Negation der Aussageform eine Tautologie.

• eine Kontingenz oder Neutralität, wenn sie weder eine Tautologie, noch eine Kontradiktion ist.

Beispiele: Eine (ansonsten nicht vorkommende) Aussagenvariable A ist für sich erfüllbar, sogar eine Kontingenz (denn das ist ja die Eigenschaft einer Aussagenvariable, dass sie entweder wahr oder falsch ist).

Die Aussage $A \vee \neg A$ ist eine Tautologie, also erfüllbar, denn jede Belegung von A mit wahr oder falsch liefert eine wahre Aussage. Folglich ist die Aussage $\neg(A \vee \neg A)$ eine Kontradiktion, also nicht erfüllbar.

Das Problem zu entscheiden, ob eine aussagenlogische Formel erfüllbar ist, nennt man das Erfüllbarkeitsproblem der Aussagenlogik. Dieses Problem ist unter anderem wichtig in der Komplexitätstheorie.

Analog zur Aussagenlogik wird der Begriff der Erfüllbarkeit auch in der Prädikatenlogik verwendet: Eine prädikatenlogische Formel ist erfüllbar, wenn es eine Interpretation der Prädikate und eine Belegung der Variablen gibt, für die die Formel den Wahrheitswert wahr annimmt (Erfüllbarkeitsäquivalenz).

Beispiele: Die Aussage $\forall x (x = x)$ ist eine Tautologie, die Aussage $\forall x \exists y (x \neq y)$ eine Kontingenz (nur erfüllbar, wenn es mehr als ein Objekt gibt), die Aussage $\exists x (x \neq x)$ eine Kontradiktion.

Siehe auch

• Berechenbarkeit
• Modelltheorie
• Resolution
• Unverträglichkeit