Mathe für Nicht-Freaks: Logik: Tautologie

Tautologie

Eine Tautologie ist eine allgemeingültige Aussage. Dies ist eine Aussage, die aus logischen Gründen stets wahr ist (unabhängig von dem Wahrheitsgehalt ihrer Teilaussagen). 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.)

Ein weiteres Beispiel für eine Tautologie ist die Aussage „Wenn $x > 0$ und $x < 0$ ist, ist $x = 4$“. Hier ist die Prämisse der Aussage für $x\in\R$ nicht erfüllbar und damit ist die Implikation unabhängig, ob $x$ gleich 4 ist oder nicht, stets wahr („Aus Falschem folgt beliebiges“).

Verständnisfrage: Welche der folgenden Aussagen 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:

1. Tautologie (Entweder die Prämisse ist falsch und damit die gesamte Implikation wahr oder die Prämisse und damit die Konklusion ist wahr und damit die Implikation wieder wahr.)
2. keine Tautologie (Wenn $x$ nicht gerade ist, ist sowohl die erste als auch die zweite Teilaussage der Disjunktion falsch und damit die gesamte Aussage falsch)
3. Tautologie (Entweder die erste oder die zweite Teilaussage ist wahr und damit ist die Disjunktion immer wahr)

Eine Anwendung des Begriffs einer Tautologie findest unter anderem dann, wenn du überprüfen möchtest, ob 2 Aussagen äquivalent zueinander sind oder nicht (ob also $A\Leftrightarrow B$ gilt). Zwei Aussagen $A$ und $B$ sind nämlich dann genau äquivalent, wenn die zusammengesetzte Aussage $A \Leftrightarrow 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. All diese Möglichkeiten sollen am Beispiel der Tautologie $(A \Rightarrow B) \Leftrightarrow (\neg B \Rightarrow \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 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) \Leftrightarrow (\neg B \Rightarrow \neg A)$ auf (Wenn diese Aussage eine Tautologie sein soll, müsste der resultierende Wahrheitswert immer $\mathrm W$ sein).

$A$	$B$	$A \Rightarrow B$	$\neg B \Rightarrow \neg A$	$(A \Rightarrow B) \Leftrightarrow (\neg B \Rightarrow \neg A)$
$\mathrm F$	$\mathrm F$	$\mathrm W$	$\mathrm W$	$\mathbf{W}$
$\mathrm F$	$\mathrm W$	$\mathrm W$	$\mathrm W$	$\mathbf{W}$
$\mathrm W$	$\mathrm F$	$\mathrm F$	$\mathrm F$	$\mathbf{W}$
$\mathrm W$	$\mathrm W$	$\mathrm W$	$\mathrm W$	$\mathbf{W}$

Ergebnis: Die Aussage ist eine Tautologie.

Äquivalenzumformungen verwenden

Wenn du die Tautologie einer Äquivalenz $A \Leftrightarrow 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{align} & A \Rightarrow B \\[5px] \Leftrightarrow \quad & \neg A \or B \\[5px] \Leftrightarrow \quad & B \or \neg A \\[5px] \Leftrightarrow \quad & \neg B \Rightarrow \neg A \\[5px] \end{align}$

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) \Leftrightarrow (\neg B \Rightarrow \neg A)$ falsch ist. Dann muss entweder $A \Rightarrow B$ falsch sein und $\neg B \Rightarrow \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 $\neg B \Rightarrow \neg A$ wahr ist (weil für $A=\mathrm W$ und $B=\mathrm F$ die Aussage $\neg B \Rightarrow \neg A$ falsch ist). Im zweiten Fall muss $B=\mathrm F$ und $A=\mathrm W$ sein, was auch ein Widerspruch zu $A \Rightarrow B = \mathrm W$ ist (weil für $B=\mathrm F$ und $A=\mathrm W$ die Aussage $A\Rightarrow B$ falsch ist). Schematisch könnte man dies in einem Baum darstellen (deswegen auch der Name). Dabei stellt jeder Ast einen zu betrachtenden Fall dar:

$(A \Rightarrow B) \Leftrightarrow (\neg B \Rightarrow \neg A) : F$
$\downarrow$	$\downarrow$
$A \Rightarrow B: \mathrm F$	$\neg B \Rightarrow \neg A: \mathrm F$
$\neg B \Rightarrow \neg A: \mathrm W$	$A \Rightarrow B: \mathrm W$
$\downarrow$	$\downarrow$
$A : \mathrm W$	$B: \mathrm F$
$B : \mathrm F$	$A: \mathrm W$
$\neg B \Rightarrow \neg A: \mathrm W$	$A \Rightarrow B: \mathrm W$
$\downarrow$	$\downarrow$
$\mathrm{x}$ (Widerspruch)	$\mathrm{x}$ (Widerspruch)

Ü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).

Assoziativgesetze

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

Kommutativgesetze

Tautologie	Bedeutung
$(A \or B) \Leftrightarrow (B \or 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 2 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 \and B) \Leftrightarrow (B \and A)$

Distributivgesetze

Tautologie	Bedeutung
$A \or (B \and C) \Leftrightarrow (A \or B) \and (A \or C)$	Eine Disjunktion kann in eine Konjunktion reingezogen werden und umgekehrt.
$A \and (B \or C) \Leftrightarrow (A \and B) \or (A \and C)$

Absorptionsgesetze

Tautologie	Bedeutung
$A \and (A \or B) \Leftrightarrow A$	wichtige Gesetze zur Vereinfachung von Aussagen
$A \or (A \and B) \Leftrightarrow A$

Idempotenzgesetze

Tautologie	Bedeutung
$A \and A \Leftrightarrow A$	wichtige Gesetze zur Vereinfachung von Aussagen
$A \or A \Leftrightarrow A$

Gesetze von ausgeschlossenen Dritten

Tautologie	Bedeutung
$A \and \neg A \Leftrightarrow \mathrm F$	wichtige Gesetze zur Vereinfachung von Aussagen
$A \or \neg A \Leftrightarrow \mathrm W$

Darstellung von Implikation und Äquivalenz

Tautologie	Bedeutung
$A \Rightarrow B \Leftrightarrow \neg A \or 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 \Leftrightarrow B) \Leftrightarrow (A \Rightarrow B) \and (B \Rightarrow A)$
$(A \Leftrightarrow B) \Leftrightarrow (\neg A \or B) \and (A \or \neg B)$
$(A \Rightarrow B) \Leftrightarrow (\neg B \Rightarrow \neg A)$	Prinzip der Kontraposition (Diese Äquivalenz kann insbesondere für Beweise verwendet werden)

Gesetze zur Negation einer Aussage

De Morgansche Regeln

Tautologie	Bedeutung
$\neg (A \and B) \Leftrightarrow \neg A \or \neg B$	Bei der Negation einer Und- bzw. Oder-Verknüpfung wird die Negation reingeklammert und die Klammer aufgelöst. Aus einem "Und" wird ein "Oder" und umgekehrt.
$\neg (A \or B) \Leftrightarrow \neg A \and \neg B$

Negation von Implikation und Äquivalenz

Tautologie	Bedeutung
$\neg (A \Rightarrow B) \Leftrightarrow A \and \neg B$
$\neg (A \Leftrightarrow B) \Leftrightarrow (\neg A \Leftrightarrow B)$

Negation von quantizierten Aussagen

Tautologie	Bedeutung
$\neg (\forall x:\, A(x)) \Leftrightarrow \exists x:\, \neg A(x)$
$\neg (\forall x\in M:\, A(x)) \Leftrightarrow \exists x\in M:\, \neg A(x)$
$\neg (\exists x:\, A(x)) \Leftrightarrow \forall x:\, \neg A(x)$
$\neg (\exists x\in M:\, A(x)) \Leftrightarrow \forall x\in M:\, \neg A(x)$

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

Tautologie	Bedeutung
$A \and \mathrm W \Leftrightarrow A$	wichtige Gesetze zum Vereinfachen von Aussagen
$A \or\mathrm W \Leftrightarrow\mathrm W$
$A \and \mathrm F \Leftrightarrow \mathrm F$
$A \or\mathrm F \Leftrightarrow A$
$\neg \neg A \Leftrightarrow A$	Doppelte Verneinung ist wieder die Ausgangsaussage.

Äquivalenzen über quantifizierte Aussagen

Tautologie	Bedeutung
$\left(\forall x:\, A(x) \right)\Leftrightarrow \neg \left(\exists x: \neg A(x)\right)$	Aussagen mit dem Allquantor können durch den Existenzquantor ausgedrückt werden und umgekehrt.
$\left(\exists x:\, A(x) \right)\Leftrightarrow \neg \left(\forall x: \neg A(x)\right)$
$\forall x:\, \forall y:\, A(x,y) \Leftrightarrow \forall y:\, \forall x:\, A(x,y)$	Allquantoren sind untereinander vertauschbar.
$\exists x:\, \exists y:\, A(x,y) \Leftrightarrow \exists y:\, \exists x:\, A(x,y)$	Existenzquantoren sind untereinander vertauschbar.
$\left(\forall x:\, A(x)\right) \and \left(\forall x:\, B(x)\right) \Leftrightarrow \forall x:\, \left(A(x) \and B(x)\right)$	Allquantoren können aus Konjunktionen rausgezogen werden.
$\left(\exists x:\, A(x)\right) \or \left(\exists x:\, B(x)\right) \Leftrightarrow \exists x:\, \left(A(x) \or B(x)\right)$	Existenzquantoren können aus Disjunktionen rausgezogen werden.

Implikationen über quantifizierte Aussagen

Tautologie	Bedeutung
$\left(\forall x:\,A(x)\right) \or \left(\forall x:\,B(x)\right) \Rightarrow \forall x:\,\left(A(x)\or B(x)\right)$
$\exists x:\,\left(A(x)\and B(x)\right) \Rightarrow \left(\exists x:\,A(x)\right) \and \left(\exists x:\,B(x)\right)$
$\forall x:\, \left( A(x) \Rightarrow B(x) \right) \Rightarrow \left(\forall x:\,A(x) \Rightarrow \forall x:\,B(x) \right)$
$\forall x:\, \left( A(x) \Leftrightarrow B(x) \right) \Rightarrow \left(\forall x:\,A(x) \Leftrightarrow \forall x:\,B(x) \right)$
$\exists x:\, \forall y:\, A(x,y) \Rightarrow \forall y:\,\exists x:\, A(x,y)$

Hinweis: In der obigen Tabelle sind die Implikationen nicht umkehrbar.