Jewiki unterstützen. Jewiki, die größte Online-Enzy­klo­pädie zum Judentum.

Helfen Sie Jewiki mit einer kleinen oder auch größeren Spende. Einmalig oder regelmäßig, damit die Zukunft von Jewiki gesichert bleibt ...

Vielen Dank für Ihr Engagement! (→ Spendenkonten)

How to read Jewiki in your desired language · Comment lire Jewiki dans votre langue préférée · Cómo leer Jewiki en su idioma preferido · בשפה הרצויה Jewiki כיצד לקרוא · Как читать Jewiki на предпочитаемом вами языке · كيف تقرأ Jewiki باللغة التي تريدها · Como ler o Jewiki na sua língua preferida

Erfüllbarkeit

Aus Jewiki
(Weitergeleitet von Kontingenz (Logik))
Zur Navigation springen Zur Suche springen

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 lösbar, also diese Aussage erfüllbar.

Das Gleichungssystem ist dagegen nicht lösbar, denn die einzige Lösung für wäre , aber diese Lösung erfüllt nicht . 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 ist für sich erfüllbar, sogar eine Kontingenz. Es ist ja die Eigenschaft einer Aussagenvariablen, daß ihr Wahrheitswert entweder wahr oder falsch ist.

Die Aussage ist eine Tautologie, also auch erfüllbar, denn jede Belegung von mit wahr oder falsch liefert eine wahre Aussage. Folglich ist die Aussage 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 ist eine Tautologie, die Aussage eine Kontingenz (nur erfüllbar, wenn es mehr als ein Objekt gibt), die Aussage eine Kontradiktion.

Siehe auch

Dieser Artikel basiert ursprünglich auf dem Artikel Erfüllbarkeit aus der freien Enzyklopädie Wikipedia und steht unter der Doppellizenz GNU-Lizenz für freie Dokumentation und Creative Commons CC-BY-SA 3.0 Unported. In der Wikipedia ist eine Liste der ursprünglichen Wikipedia-Autoren verfügbar.