- Erfüllbare Aussage
-
Erfüllbarkeit ist in der Logik und Mathematik ein metasprachliches Prädikat für die Eigenschaft von Aussagen und Aussageformen, wahr sein zu können. Anders ausgedrückt ist ein Ausdruck genau dann erfüllbar, wenn es eine Belegung (Interpretation, Bewertung) der Variablen gibt, für die der Wahrheitswert des gesamten Ausdrucks wahr ist.
Ist eine Aussage(formel) nicht erfüllbar, ist sie „unerfüllbar“ (kontradiktorisch, widersprüchlich)[1]. "Unerfüllbarkeit ist Allgemeingültigkeit der Negation"[2].
In der klassischen Aussagenlogik ist jeder Ausdruck, aus dem kein Widerspruch (Kontradiktion) herleitbar ist, erfüllbar. „Ein Ausdruck ist dann und nur dann erfüllbar, wenn er keine Kontradiktion ist.“ [3]
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 allgemein gü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.
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).
Auf der Basis des Bewertungsbegriffs lassen sich der grundlegende Begriff der Erfüllung und mit seiner Hilfe die Begriffe der logischen Wahrheit und Folgerung definieren.[4]
Siehe auch
Einzelnachweise
Wikimedia Foundation.
