Erfüllbarkeit

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


Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

Schlagen Sie auch in anderen Wörterbüchern nach:

  • 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,… …   Deutsch Wikipedia

  • Aussagenlogik — Die Aussagenlogik ist ein Teilgebiet der Logik, das sich mit Aussagen und deren Verknüpfung durch Junktoren befasst, ausgehend von strukturlosen Elementaraussagen (Atomen), denen ein Wahrheitswert zugeordnet wird. In der klassischen Aussagenlogik …   Deutsch Wikipedia

  • True Wert — Die Aussagenlogik (veraltet Urteilslogik) ist der Bereich der Logik, der sich mit Aussagen und deren Verknüpfung durch Junktoren befasst, ausgehend von strukturlosen Elementaraussagen (Atomen), denen semantisch ein Wahrheitswert zugeordnet wird.… …   Deutsch Wikipedia

  • Urteilslogik — Die Aussagenlogik (veraltet Urteilslogik) ist der Bereich der Logik, der sich mit Aussagen und deren Verknüpfung durch Junktoren befasst, ausgehend von strukturlosen Elementaraussagen (Atomen), denen semantisch ein Wahrheitswert zugeordnet wird.… …   Deutsch Wikipedia

  • Horn-Klausel — Horn Formeln sind eine spezielle Teilmenge der aussagenlogischen Formeln. Benannt wurden sie nach dem US amerikanischen Logiker Alfred Horn. Inhaltsverzeichnis 1 Definition mit Horn Klauseln 1.1 Beispiele 1.2 Darstellungsformen von Horn Klauseln… …   Deutsch Wikipedia

  • Horn-Klauseln — Horn Formeln sind eine spezielle Teilmenge der aussagenlogischen Formeln. Benannt wurden sie nach dem US amerikanischen Logiker Alfred Horn. Inhaltsverzeichnis 1 Definition mit Horn Klauseln 1.1 Beispiele 1.2 Darstellungsformen von Horn Klauseln… …   Deutsch Wikipedia

  • Hornformel — Horn Formeln sind eine spezielle Teilmenge der aussagenlogischen Formeln. Benannt wurden sie nach dem US amerikanischen Logiker Alfred Horn. Inhaltsverzeichnis 1 Definition mit Horn Klauseln 1.1 Beispiele 1.2 Darstellungsformen von Horn Klauseln… …   Deutsch Wikipedia

  • Hornklausel — Horn Formeln sind eine spezielle Teilmenge der aussagenlogischen Formeln. Benannt wurden sie nach dem US amerikanischen Logiker Alfred Horn. Inhaltsverzeichnis 1 Definition mit Horn Klauseln 1.1 Beispiele 1.2 Darstellungsformen von Horn Klauseln… …   Deutsch Wikipedia

  • Horn-Formel — Horn Formeln sind eine wichtige Teilmenge der prädikatenlogischen Formeln. Sie spielen eine zentrale Rolle in der Logischen Programmierung und sind von Bedeutung für die konstruktive Logik. Benannt wurden sie nach dem US amerikanischen Logiker… …   Deutsch Wikipedia

  • Skolem-Normalform — Skolemform ist ein Begriff der Prädikatenlogik und bezeichnet eine prädikatenlogische Formel, die sich in einer Normalform nach Albert Thoralf Skolem befindet. Für Formeln in Skolemform existiert ein berechenbarer Test auf Erfüllbarkeit. Dies ist …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”