Erfüllbarkeit - LinkFang.de





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 [math]2x +1 = 3x[/math] lösbar, also diese Aussage erfüllbar.

Das Gleichungssystem [math]x \lt 0, x^2 \leq 0[/math] ist dagegen nicht lösbar, denn die einzige Lösung für [math]x^2 \leq 0[/math] wäre [math]x = 0[/math], aber diese Lösung erfüllt nicht [math]x \lt 0[/math]. 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 mindestens 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. Die Negation einer Kontradiktion ist immer eine Tautologie. Das Gegenteil des Begriffs "Kontradiktion" ist jedoch nicht "Tautologie", sondern "Erfüllbarkeit".
  • eine Kontingenz oder Neutralität, wenn sie weder eine Tautologie, noch eine Kontradiktion ist.
  • falsifizierbar, wenn mindestens eine Belegung kein Modell darstellt, also eine falsche Aussage erzeugt.

Beispiele: Eine (ansonsten nicht vorkommende) Aussagenvariable [math]A[/math] ist für sich erfüllbar, sogar eine Kontingenz. Es ist ja die Eigenschaft einer Aussagenvariablen, dass ihr Wahrheitswert entweder wahr oder falsch ist.

Die Aussage [math]A \vee \neg A[/math] ist eine Tautologie, also auch erfüllbar, denn jede Belegung von [math]A[/math] mit wahr oder falsch liefert eine wahre Aussage. Folglich ist die Aussage [math]\neg(A \vee \neg A)[/math] 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 [math]\forall x (x = x)[/math] ist eine Tautologie, die Aussage [math]\forall x \exists y (x \neq y)[/math] eine Kontingenz (nur erfüllbar, wenn es mehr als ein Objekt gibt), die Aussage [math]\exists x (x \neq x)[/math] eine Kontradiktion.

Siehe auch


Kategorien: Keine Kategorien vorhanden!

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Erfüllbarkeit (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.