imported>JustNeptun: Ergänzt, dass das zweite Beispiel auch für die leere Menge gilt.

2024-05-05T12:17:59Z

Ergänzt, dass das zweite Beispiel auch für die leere Menge gilt.

Neue Seite

'''Erfüllbarkeit''' ist in der [[Logik]] und [[Mathematik]] ein [[Metasprache|metasprachliches]] [[Prädikat (Logik)|Prädikat]] für die [[Eigenschaft]] von logischen [[Logische Aussage|Aussagen]] und [[Aussageform]]en. Eine Aussage ist erfüllbar, wenn es eine [[Belegung (Logik)|Belegung]] (Interpretation, [[Bewertung (Logik)|Bewertung]]) der [[Variable (Logik)|Variablen]] gibt, für die der [[Wahrheitswert]] des gesamten Ausdrucks ''wahr'' ist.

== Mathematik ==

In der Mathematik ist die Erfüllbarkeit vor allem von (Un-)[[Gleichung]]en und (Un-)[[Gleichungssystem]]en 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 < 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 < 0</math>. Diese Aussage ist also nicht erfüllbar.

== Logik ==

=== Aussagenlogik ===
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 [[Modelltheorie|Modell]] darstellt, also eine falsche Aussage erzeugt.

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]].

==== 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> (sprich: <math>A</math> oder nicht <math>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> (die Negierung des vorigen Beispiels) eine Kontradiktion, also nicht erfüllbar.

=== Prädikatenlogik ===
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 (Logik)|Interpretation]] der Prädikate und eine Belegung der Variablen gibt, für die die Formel den Wahrheitswert ''wahr'' annimmt ([[Erfüllbarkeitsäquivalenz]]).

==== Beispiele ====
* <math>\forall x (x = x)</math> "für jedes x gilt: x ist x" ist eine Tautologie, da x immer mit sich selbst ident ist.
* <math>\forall x \exists y (x \neq y)</math> "für jedes x existiert ein y, für das gilt: x ist ungleich y" ist eine Kontingenz, da sie nur erfüllbar ist, wenn es in der Menge der Objekte, aus der x und y gewählt werden, mehr als ein Objekt gibt oder die Menge gleich der [[Leere Menge|leeren Menge]] ist. Der zweite Fall wäre ein Beispiel einer [[Leere Wahrheit|leeren Wahrheit]].
* <math>\exists x (x \neq x)</math> "es existiert ein x für das gilt: x ist nicht gleich x" ist eine Kontradiktion, die Aussage ist gerade die Negation des ersten Beispiels.

== Siehe auch ==
* [[Berechenbarkeit]]
* [[Modelltheorie]]
* [[Resolution (Logik)|Resolution]]
* [[Unverträglichkeit (Logik)|Unverträglichkeit]]

{{SORTIERUNG:Erfullbarkeit}}
[[Kategorie:Logik]]

Erfüllbarkeit - Versionsgeschichte

imported>JustNeptun: Ergänzt, dass das zweite Beispiel auch für die leere Menge gilt.