Definition einer erfüllbaren Aussage Beispiele
Beispiel:
Schon die Aussage \(A\) ist bereits eine erfüllbare Aussage, da sie den Wahrheitswert wahr annehmen kann.
\(\qquad\) | \(\begin{array}{|c|c|c|c|c|c|c|c|} \hline A \ \\ \hline \mathrm{w}\ \\ \mathrm{f}\ \\ \hline\end{array}\) |
Beispiel:
Die Aussage
\(\qquad\) | \(A \lor \lnot A\) |
ist eine erfüllbare Aussage – sie ist sogar eine Tautologie – da jede Belegung von \(A\) mit wahr oder falsch eine wahre Aussage liefert.
\(\qquad\) | \(\begin{array}{|c|c|c|c|c|c|c|c|} \hline A &\hspace{-0.8em} & \lnot A & A \lor \lnot A \ \\ \hline \mathrm{w}&\hspace{-0.8em}& \mathrm{f} & \mathrm{w} \ \\ \hline \mathrm{f}&\hspace{-0.8em}&\mathrm{w} & \mathrm{w} \ \\ \hline\end{array}\) |
Merke:
Jede Tautologie ist eine erfüllbare Aussage, aber nicht jede erfüllbare Aussage ist eine Tautologie.
Beispiel:
Die Aussage
\(\qquad\) | \(A \land \lnot A\) |
ist keine erfüllbare Aussage – sie ist sogar eine Kontradiktion – da jede Belegung von \(A\) mit wahr oder falsch eine falsche Aussage liefert.
\(\qquad\) | \(\begin{array}{|c|c|c|c|c|c|c|c|} \hline A &\hspace{-0.8em} & \lnot A & A \land \lnot A \ \\ \hline \mathrm{w}&\hspace{-0.8em}& \mathrm{f} & \mathrm{f} \ \\ \hline \mathrm{f}&\hspace{-0.8em}&\mathrm{w} & \mathrm{f} \ \\ \hline\end{array}\) |
Erklärung Lösung: Ja, die Formel ist erfüllbar. Erläuterung: Wir zeigen die Erfüllbarkeit der Formel durch eine Wahrheitstabelle.
Da mindestens eine Belegung der Aussagen \(A\) und \(B\) zu einer wahren Aussage der Formel führt, ist die Formel erfüllbar. |  |
\(\enspace\)