Benutzer:Chris Ke/Spielwiese Tautologie

Tautologie

Eine Tautologie ist eine allgemeingültige Aussageform, deren Variable Aussagen sind. Mit allgemeingültig ist hierbei gemeint, dass bei Belegung der freien Variablen der Tautologie mit beliebigen wahren oder falschen Teilaussagen, stets eine wahre zusammengesetzte Aussage entsteht. Ein Beispiel dafür ist die Aussage „Es regnet oder es regnet nicht“. Da es entweder regnet oder es nicht regnet, ist diese Aussage immer wahr (unabhängig davon, ob es nun tatsächlich regnet oder nicht; also unabhängig davon, ob die Teilaussagen „Es regnet.“ bzw. „Es regnet nicht.“ wahr sind oder nicht.)

Verständnisfrage: Welche der folgenden Aussageformen ist eine Tautologie?

1. Wenn $x$ durch 2 teilbar ist, ist $x$ gerade.
2. $x$ ist gerade oder $x$ ist durch 2 teilbar.
3. $x$ ist gerade oder $x$ ist nicht durch 2 teilbar.

Antwort: Keine. Es handelt sich um erfüllbare Aussageformen. Die Erste und Dritte sind allgemeingültig.

Eine Anwendung des Begriffs Tautologie findest du unter anderem dann, wenn du überprüfen möchtest, ob zwei Aussagen äquivalent zueinander sind oder nicht (ob also $A\iff B$ gilt). Zwei Aussagen $A$ und $B$ sind nämlich genau dann äquivalent, wenn die zusammengesetzte Aussage $A\iff B$ eine Tautologie ist.

Überprüfung einer Tautologie

Ich werde dir jetzt einige Möglichkeiten vorstellen, wie du überprüfen kannst, ob eine Aussage eine Tautologie ist oder nicht. Alle diese Möglichkeiten sollen am Beispiel der Tautologie $(A\Rightarrow B)\iff (\mathrm{\neg }B\Rightarrow \mathrm{\neg }A)$ demonstriert werden (Diese Tautologie ist als Kontraposition bekannt).

Wahrheitstabelle erstellen

Eine Methode ist es, eine Wahrheitstabelle für die zu untersuchende Aussage aufzustellen. Wenn in der letzten Spalte der Wahrheitstabelle nur „wahr“ als resultierender Wahrheitswert auftritt, ist die untersuchte Aussage eine Tautologie. Sobald ein resultierender Wahrheitswert „falsch“ ist, ist die Aussage keine Tautologie.

Aufgabe: Stelle die Wahrheitstabelle für $(A\Rightarrow B)\iff (\mathrm{\neg }B\Rightarrow \mathrm{\neg }A)$ auf (Wenn diese Aussage eine Tautologie sein soll, müssen die resultierenden Wahrheitswerte in der letzten Spalte immer $\mathrm{W}$ sein).

$A$	$B$	$A\Rightarrow B$	$\mathrm{\neg }B\Rightarrow \mathrm{\neg }A$	$(A\Rightarrow B)\iff (\mathrm{\neg }B\Rightarrow \mathrm{\neg }A)$
$\mathrm{F}$	$\mathrm{F}$	$\mathrm{W}$	$\mathrm{W}$	$𝐖$
$\mathrm{F}$	$\mathrm{W}$	$\mathrm{W}$	$\mathrm{W}$	$𝐖$
$\mathrm{W}$	$\mathrm{F}$	$\mathrm{F}$	$\mathrm{F}$	$𝐖$
$\mathrm{W}$	$\mathrm{W}$	$\mathrm{W}$	$\mathrm{W}$	$𝐖$

Ergebnis: Die Aussage ist eine Tautologie.

Äquivalenzumformungen verwenden

Wenn du die Tautologie einer Äquivalenz $A\iff B$ beweisen musst, kannst du versuchen die Aussage $A$ durch bereits bekannte Äquivalenzbeziehungen in die Aussage $B$ umzuformen. Um auf die notwendigen Umformungen zu kommen, kannst du eine ähnliche Technik benutzen wie bei den Termumformungen. Du kannst die beiden Aussagen nebeneinanderschreiben und versuchen diese schrittweise auf die gleiche Aussage umzuformen.

Da Äquivalenzbeziehungen erst später in diesem Kapitel behandelt werden, kannst du das folgende Beispiel überspringen und es dir später wieder anschauen. Für das Beispiel der Kontraposition lautet der Beweis dieser Tautologie:

$\begin{array}{cc}& A\Rightarrow B\\ \iff & \mathrm{\neg }A\vee B\\ \iff & B\vee \mathrm{\neg }A\\ \iff & \mathrm{\neg }B\Rightarrow \mathrm{\neg }A\\ \end{array}$

Baummethode

Diese Methode ist eine Art des Widerspruchsbeweises. Du beweist hier, dass eine Aussage $A$ eine Tautologie ist, indem du zeigst, dass diese Aussage nie falsch sein kann, weil sich sonst ein Widerspruch ergibt. Dabei zerlegst du die zu untersuchende Aussage schrittweise in ihre Teilaussagen und schaust dir nur diejenigen Fälle an, die zu einer falschen Aussage führen würden.

Nehmen wir an, dass $(A\Rightarrow B)\iff (\mathrm{\neg }B\Rightarrow \mathrm{\neg }A)$ falsch ist. Dann muss entweder $A\Rightarrow B$ falsch sein und $\mathrm{\neg }B\Rightarrow \mathrm{\neg }A$ wahr sein oder umgekehrt. Im ersten Fall muss $A=\mathrm{W}$ und $B=\mathrm{F}$ sein. Dies ist aber ein Widerspruch dazu, dass $\mathrm{\neg }B\Rightarrow \mathrm{\neg }A$ wahr ist (weil für $A=\mathrm{W}$ und $B=\mathrm{F}$ die Aussage $\mathrm{\neg }B\Rightarrow \mathrm{\neg }A$ falsch ist).

Im zweiten Fall muss $\mathrm{\neg }B=\mathrm{W}$ und $\mathrm{\neg }A=\mathrm{F}$ sein. Dies bedeutet $B=\mathrm{F}$ und $A=\mathrm{W}$. Aber auch das führt zu einem Widerspruch, weil $A\Rightarrow B=\mathrm{W}$ ist (für $B=\mathrm{F}$ und $A=\mathrm{W}$ ist die Aussage $A\Rightarrow B$ falsch). Schematisch könnte man dies in einem Baum darstellen (deswegen auch der Name). Dabei stellt jeder Ast einen zu betrachtenden Fall dar:

$\begin{array}{ccc}(A\Rightarrow B)& \iff & (\mathrm{\neg }B\Rightarrow \mathrm{\neg }A):F\\ \downarrow & & \downarrow \\ A\Rightarrow B:\mathrm{F}& & \mathrm{\neg }B\Rightarrow \mathrm{\neg }A:\mathrm{F}\\ \mathrm{\neg }B\Rightarrow \mathrm{\neg }A:\mathrm{W}& & A\Rightarrow B:\mathrm{W}\\ \downarrow & & \downarrow \\ A:\mathrm{W}& & B:\mathrm{F}\\ B:\mathrm{F}& & A:\mathrm{W}\\ \mathrm{\neg }B\Rightarrow \mathrm{\neg }A:\mathrm{W}& & A\Rightarrow B:\mathrm{W}\\ \downarrow & & \downarrow \\ \text{Widerspruch}& & \text{Widerspruch}\end{array}$

Übersicht zu Tautologien

In der folgenden Tabelle sind die wichtigsten Äquivalenzbeziehungen aufgelistet. Auf den Beweis aller dieser Tautologien verzichte ich erst einmal (hier kannst du als Übungsaufgabe einige für dich interessante Tautologien beweisen).

Im folgenden steht $W$ für „wahr“ und $F$ für „falsch“. Für alle Aussagen $A$, $B$, $C$ gilt:

Assoziativgesetze

Tautologie	Bedeutung
$(A\vee B)\vee C\iff A\vee (B\vee C)$	Bei der Disjunktion und bei der Konjunktion ist es egal, in welcher Weise die einzelnen Teilaussagen verknüpft werden.
$(A\wedge B)\wedge C\iff A\wedge (B\wedge C)$

Kommutativgesetze

Tautologie	Bedeutung
$(A\vee B)\iff (B\vee A)$	Bei der Disjunktion und bei der Konjunktion ist es egal, in welcher Reihenfolge die einzelnen Teilaussagen verknüpft werden. (Dies ist in der natürlichen Sprache nicht unbedingt der Fall. Betrachte dazu folgende zwei Aussagen, welche in der Bedeutung einen leichten Unterschied aufweisen: „Ralf ging in die Kirche und seine Tochter starb.“ und „Seine Tochter starb und Ralf ging in die Kirche.“)
$(A\wedge B)\iff (B\wedge A)$

Distributivgesetze

Tautologie	Bedeutung
$A\vee (B\wedge C)\iff (A\vee B)\wedge (A\vee C)$	Eine Disjunktion kann in eine Konjunktion reingezogen werden und umgekehrt.
$A\wedge (B\vee C)\iff (A\wedge B)\vee (A\wedge C)$

Absorptionsgesetze

Tautologie	Bedeutung
$A\wedge (A\vee B)\iff A$	wichtige Gesetze zur Vereinfachung von Aussagen
$A\vee (A\wedge B)\iff A$

Idempotenzgesetze

Tautologie	Bedeutung
$A\wedge A\iff A$	wichtige Gesetze zur Vereinfachung von Aussagen
$A\vee A\iff A$

Gesetze von ausgeschlossenen Dritten

Tautologie	Bedeutung
$A\wedge \mathrm{\neg }A\iff \mathrm{F}$	wichtige Gesetze zur Vereinfachung von Aussagen
$A\vee \mathrm{\neg }A\iff \mathrm{W}$

Darstellung von Implikation und Äquivalenz

Tautologie	Bedeutung
$A\Rightarrow B\iff \mathrm{\neg }A\vee B$	Mit Hilfe dieser Gesetze kann die Implikation und die Äquivalenz auf Aussagen mit anderen Junktoren zurückgeführt werden. So können bestimmte Aufgaben gelöst werden (wie: Finden sie die Negation der Implikation).
$(A\iff B)\iff (A\Rightarrow B)\wedge (B\Rightarrow A)$
$(A\iff B)\iff (\mathrm{\neg }A\vee B)\wedge (A\vee \mathrm{\neg }B)$
$(A\Rightarrow B)\iff (\mathrm{\neg }B\Rightarrow \mathrm{\neg }A)$	Prinzip der Kontraposition (Diese Äquivalenz kann insbesondere für Beweise verwendet werden)

Gesetze zur Negation einer Aussage

De Morgansche Regeln

Tautologie	Bedeutung
$\mathrm{\neg }(A\wedge B)\iff \mathrm{\neg }A\vee \mathrm{\neg }B$	Bei der Negation einer Und- bzw. Oder-Verknüpfung wird die Negation reingeklammert und die Klammer aufgelöst. Aus einem $\wedge$ wird ein $\vee$ und umgekehrt.
$\mathrm{\neg }(A\vee B)\iff \mathrm{\neg }A\wedge \mathrm{\neg }B$

Negation von Implikation und Äquivalenz

Tautologie	Bedeutung
$\mathrm{\neg }(A\Rightarrow B)\iff A\wedge \mathrm{\neg }B$
$\mathrm{\neg }(A\iff B)\iff (\mathrm{\neg }A\iff B)$

Negation von quantifizierten Aussagen

Tautologie	Bedeutung
$\mathrm{\neg }(\mathrm{\forall }x:A(x))\iff \mathrm{\exists }x:\mathrm{\neg }A(x)$
$\mathrm{\neg }(\mathrm{\forall }x\in M:A(x))\iff \mathrm{\exists }x\in M:\mathrm{\neg }A(x)$
$\mathrm{\neg }(\mathrm{\exists }x:A(x))\iff \mathrm{\forall }x:\mathrm{\neg }A(x)$
$\mathrm{\neg }(\mathrm{\exists }x\in M:A(x))\iff \mathrm{\forall }x\in M:\mathrm{\neg }A(x)$

Gesetze mit $\mathrm{W}$ und $\mathrm{F}$ und zur doppelten Verneinung

Tautologie	Bedeutung
$A\wedge \mathrm{W}\iff A$	wichtige Gesetze zum Vereinfachen von Aussagen
$A\vee \mathrm{W}\iff \mathrm{W}$
$A\wedge \mathrm{F}\iff \mathrm{F}$
$A\vee \mathrm{F}\iff A$
$\mathrm{\neg }\mathrm{\neg }A\iff A$	Doppelte Verneinung ist wieder die Ausgangsaussage.

Äquivalenzen über quantifizierte Aussagen

Tautologie	Bedeutung
$(\mathrm{\forall }x:A(x))\iff \mathrm{\neg }(\mathrm{\exists }x:\mathrm{\neg }A(x))$	Aussagen mit dem Allquantor können durch den Existenzquantor ausgedrückt werden und umgekehrt.
$(\mathrm{\exists }x:A(x))\iff \mathrm{\neg }(\mathrm{\forall }x:\mathrm{\neg }A(x))$
$\mathrm{\forall }x:\mathrm{\forall }y:A(x,y)\iff \mathrm{\forall }y:\mathrm{\forall }x:A(x,y)$	Allquantoren sind untereinander vertauschbar.
$\mathrm{\exists }x:\mathrm{\exists }y:A(x,y)\iff \mathrm{\exists }y:\mathrm{\exists }x:A(x,y)$	Existenzquantoren sind untereinander vertauschbar.
$(\mathrm{\forall }x:A(x))\wedge (\mathrm{\forall }x:B(x))\iff \mathrm{\forall }x:(A(x)\wedge B(x))$	Allquantoren können aus Konjunktionen rausgezogen werden.
$(\mathrm{\exists }x:A(x))\vee (\mathrm{\exists }x:B(x))\iff \mathrm{\exists }x:(A(x)\vee B(x))$	Existenzquantoren können aus Disjunktionen rausgezogen werden.

Implikationen über quantifizierte Aussagen

Tautologie	Bedeutung
$(\mathrm{\forall }x:A(x))\vee (\mathrm{\forall }x:B(x))\Rightarrow \mathrm{\forall }x:(A(x)\vee B(x))$
$\mathrm{\exists }x:(A(x)\wedge B(x))\Rightarrow (\mathrm{\exists }x:A(x))\wedge (\mathrm{\exists }x:B(x))$
$\mathrm{\forall }x:(A(x)\Rightarrow B(x))\Rightarrow (\mathrm{\forall }x:A(x)\Rightarrow \mathrm{\forall }x:B(x))$
$\mathrm{\forall }x:(A(x)\iff B(x))\Rightarrow (\mathrm{\forall }x:A(x)\iff \mathrm{\forall }x:B(x))$
$\mathrm{\exists }x:\mathrm{\forall }y:A(x,y)\Rightarrow \mathrm{\forall }y:\mathrm{\exists }x:A(x,y)$

Hinweis

In der obigen Tabelle sind die Implikationen nicht umkehrbar.