Erfüllbarkeit
Erfüllbarkeit ist die Eigenschaft mancher Aussagen in der Logik und Mathematik, unter gewissen Umständen gültig, also wahr zu sein. Anders ausgedrückt ist ein Ausdruck genau dann erfüllbar, wenn es eine Belegung der Variablen gibt, für die der Wahrheitswert des gesamten Ausdrucks wahr ist.
In der Mathematik heißt eine Gleichung erfüllbar, wenn sie eine Lösung hat. So ist z.B. x = x+1 nicht erfüllbar, 2x +1 = 3x aber schon (mit x=1).
In der Aussagenlogik ist jeder Ausdruck, der keinen Widerspruch (Kontradiktion) enthält, erfüllbar. Insbesondere sind alle Tautologien erfüllbar (und per Definition sogar immer erfüllt). So ist a und b erfüllbar (nämlich wenn sowohl a als auch b wahr ist), a und nicht a unerfüllbar (weil widersprüchlich) und a oder nicht a erfüllbar (weil allgemeingültig).
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.
Ausdrücke, die für manche Belegungen wahr und für manche falsch ist, nennt man neutrale Ausdrücke. Das sind genau die Ausdrücke, die weder eine Kontradiktion noch eine Tautologie sind.
Siehe auch: Berechenbarkeit