Tautologie – Serlo „Mathe für Nicht-Freaks“

Tautologie

Die Aussage „Wenn der Hahn kräht auf dem Mist, dann ändert sich das Wetter oder es bleibt wie es ist.“ ist eine Tautologie.

Es gibt Aussagen, die sind immer wahr. Das klassische Beispiel hierfür ist die Bauernregel: „Wenn der Hahn kräht auf dem Mist, dann ändert sich das Wetter oder es bleibt wie es ist.“ $H$ stehe für die Aussage „Der Hahn kräht auf dem Mist“ und $X$ für „Das Wetter ändert sich“, dann können wir diese Bauernregel folgendermaßen formalisieren:

$\underbrace {H\implies X\lor \neg X} _{{\text{Wenn }}H{\text{ dann }}X{\text{ oder }}\neg X.}$

Da Aussagen entweder „wahr“ oder „falsch“ sind, ist leicht zu sehen, dass die Bauernregel immer wahr ist. Dabei kommt es überhaupt nicht darauf an, ob der Hahn kräht oder nicht. Denn $X$ oder $\neg X$ – eine dieser beiden Aussagen ist wahr. Es spielt auch keine Rolle, was genau mit $X$ gemeint ist: es muss nur eine Aussage sein! $X$ könnte auch für die Behauptung stehen: „Es gibt kleine, grüne Männchen auf dem Mars.“

Woran liegt es, dass diese Aussage immer wahr ist? Es liegt daran, wie die Aussage mit Junktoren aus Teilaussagen zusammengebaut ist. Wir wissen, dass die Negation $\neg$ den Wahrheitswert umdreht: aus ${\mathsf {W}}$ wird ${\mathsf {F}}$ und umgekehrt aus ${\mathsf {F}}$ wird ${\mathsf {W}}$. Die Oder-Verbindung $\lor$ wird wahr, wenn eine der beiden Teilaussagen wahr ist. Also ist $X\lor \neg X$ immer wahr. Die Implikation $A\implies B$ ist nur dann falsch, wenn die Prämisse $A$ wahr ist und die Konklusion $B$ falsch ist. In unserem Beispiel aber ist die Konklusion $X\lor \neg X$ immer wahr. Daher ist auch $H\implies X\lor \neg X$ immer wahr. Mit Junktoren zusammengesetzte Aussagen, die immer wahr sind, werden Tautologien oder auch allgemeingültige Aussagen genannt:

Definition (Tautologie)

Eine mit Junktoren zusammengesetzte Aussage heißt tautologisch oder allgemeingültig, wenn sie bei jeder möglichen Interpretation seiner Teilaussagen mit Wahrheitswerten wahr ist.

Besonders wichtige Tautologien sind Äquivalenzen. Zwei Aussagen $A$ und $B$ sind nämlich genau dann äquivalent, wenn die zusammengesetzte Aussage $A\iff B$ eine Tautologie ist. Das wird oft bei Beweisen genutzt. Statt direkt die Aussage $A$ zu beweisen, wird eine dazu äquivalente Aussage $B$ gezeigt.

Beispiel (Äquivalente Aussagen)

Die folgenden drei Aussagen sind äquivalent:

• $A\implies B$
• $\neg B\implies \neg A$ (Kontraposition)
• $\neg (A\land \neg B)$ (Widerspruchsbeweis)

Es sind also tautologisch:

• $A\implies B\iff \neg B\implies \neg A$
• $A\implies B\iff \neg (A\land \neg B)$

Eine alternative Formulierung des Widerspruchbeweises ist im Übrigen $A\land \neg B\implies {\mathsf {F}}$.

Überprüfung einer Tautologie

Wir werden jetzt drei Möglichkeiten vorstellen, wie du überprüfen kannst, ob eine Aussage eine Tautologie ist oder nicht. Alle diese Möglichkeiten sollen am Beispiel der Kontraposition $(A\Rightarrow B)\Leftrightarrow (\neg B\Rightarrow \neg A)$ demonstriert werden.

Wahrheitstabelle erstellen

Erklärung der Äquivalenz von dem direktem Beweis, der Kontraposition und dem Widerspruchsbeweis. (YouTube-Video vom Kanal Quatematik)

Eine Methode ist es, eine Wahrheitstabelle für die zu untersuchende Aussage aufzustellen, vgl. Kapitel „Wahrheitstabelle“. 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\lor B)\Leftrightarrow (B\lor A)$ auf.

$A$	$B$	$A\lor B$	$B\lor A$	$(A\lor B)\Leftrightarrow (B\lor A)$
${\mathsf {W}}$	${\mathsf {W}}$	${\mathsf {W}}$	${\mathsf {W}}$	${\boldsymbol {\mathsf {W}}}$
${\mathsf {W}}$	${\mathsf {F}}$	${\mathsf {W}}$	${\mathsf {W}}$	${\boldsymbol {\mathsf {W}}}$
${\mathsf {F}}$	${\mathsf {W}}$	${\mathsf {W}}$	${\mathsf {W}}$	${\boldsymbol {\mathsf {W}}}$
${\mathsf {F}}$	${\mathsf {F}}$	${\mathsf {F}}$	${\mathsf {F}}$	${\boldsymbol {\mathsf {W}}}$

Ergebnis: Die Aussage ist eine Tautologie.

Aufgabe: Stelle die Wahrheitstabelle für $(A\Rightarrow B)\Leftrightarrow (B\Rightarrow A)$ auf.

$A$	$B$	$A\Rightarrow B$	$B\Rightarrow A$	$(A\Rightarrow B)\Leftrightarrow (B\Rightarrow A)$
${\mathsf {W}}$	${\mathsf {W}}$	${\mathsf {W}}$	${\mathsf {W}}$	${\boldsymbol {\mathsf {W}}}$
${\mathsf {W}}$	${\mathsf {F}}$	${\mathsf {F}}$	${\mathsf {W}}$	$\color {red}{\boldsymbol {\mathsf {F}}}$
${\mathsf {F}}$	${\mathsf {W}}$	${\mathsf {W}}$	${\mathsf {F}}$	$\color {red}{\boldsymbol {\mathsf {F}}}$
${\mathsf {F}}$	${\mathsf {F}}$	${\mathsf {W}}$	${\mathsf {W}}$	${\boldsymbol {\mathsf {W}}}$

Ergebnis: Die Aussage ist keine Tautologie.

Aufgabe: Stelle die Wahrheitstabelle für $(A\Rightarrow B)\Leftrightarrow (\neg B\Rightarrow \neg A)$ auf.

$A$	$B$	$\neg A$	$\neg B$	$A\Rightarrow B$	$\neg B\Rightarrow \neg A$	$(A\Rightarrow B)\Leftrightarrow (\neg B\Rightarrow \neg A)$
${\mathsf {W}}$	${\mathsf {W}}$	${\mathsf {F}}$	${\mathsf {F}}$	${\mathsf {W}}$	${\mathsf {W}}$	${\boldsymbol {\mathsf {W}}}$
${\mathsf {W}}$	${\mathsf {F}}$	${\mathsf {F}}$	${\mathsf {W}}$	${\mathsf {F}}$	${\mathsf {F}}$	${\boldsymbol {\mathsf {W}}}$
${\mathsf {F}}$	${\mathsf {W}}$	${\mathsf {W}}$	${\mathsf {F}}$	${\mathsf {W}}$	${\mathsf {W}}$	${\boldsymbol {\mathsf {W}}}$
${\mathsf {F}}$	${\mathsf {F}}$	${\mathsf {W}}$	${\mathsf {W}}$	${\mathsf {W}}$	${\mathsf {W}}$	${\boldsymbol {\mathsf {W}}}$

Ergebnis: Die Aussage ist eine Tautologie.

Aufgabe: Stelle die Wahrheitstabelle für $(X\Rightarrow Y)\Leftrightarrow (\neg X\lor Y)$ auf.

$X$	$Y$	$\neg X$	$X\Rightarrow Y$	$\neg X\lor Y$	$(X\Rightarrow Y)\Leftrightarrow (\neg X\lor Y)$
${\mathsf {W}}$	${\mathsf {W}}$	${\mathsf {F}}$	${\mathsf {W}}$	${\mathsf {W}}$	${\boldsymbol {\mathsf {W}}}$
${\mathsf {W}}$	${\mathsf {F}}$	${\mathsf {F}}$	${\mathsf {F}}$	${\mathsf {F}}$	${\boldsymbol {\mathsf {W}}}$
${\mathsf {F}}$	${\mathsf {W}}$	${\mathsf {W}}$	${\mathsf {W}}$	${\mathsf {W}}$	${\boldsymbol {\mathsf {W}}}$
${\mathsf {F}}$	${\mathsf {F}}$	${\mathsf {W}}$	${\mathsf {W}}$	${\mathsf {W}}$	${\boldsymbol {\mathsf {W}}}$

Ergebnis: Die Aussage ist eine Tautologie.

Äquivalenzumformungen verwenden

Wenn du die Tautologie einer Äquivalenz $X\Leftrightarrow Y$ beweisen musst, kannst du versuchen, die Aussage $X$ durch bereits bekannte Äquivalenzbeziehungen in die Aussage $Y$ umzuformen. Für unser Beispiel nehmen wir an, dass wir die folgenden Äquivalenzen bereits kennen:

1. $X\Rightarrow Y\Leftrightarrow \neg X\lor Y$   (Umformung der Implikation)
2. $X\lor Y\Leftrightarrow Y\lor X$   (Kommutativität von $\lor$)

Mit diesen beiden Äquivalenzen können wir die Kontraposition beweisen:

${\begin{aligned}&A\Rightarrow B\\&{\color {RedOrange}\updownarrow {\text{ Umformung nach 1.}}}\\[0.3em]\Leftrightarrow \quad &\neg A\lor B\\&{\color {RedOrange}\updownarrow {\text{ Kommutativität nach 2.}}}\\[0.3em]\Leftrightarrow \quad &B\lor \neg A\\&{\color {RedOrange}\updownarrow {\text{ Umformung nach 1.}}}\\[0.3em]\Leftrightarrow \quad &\neg B\Rightarrow \neg A\\\end{aligned}}$

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={\mathsf {W}}$ und $B={\mathsf {F}}$ sein. Dies ist aber ein Widerspruch dazu, dass $\neg B\Rightarrow \neg A$ wahr ist (weil für $A={\mathsf {W}}$ und $B={\mathsf {F}}$ die Aussage $\neg B\Rightarrow \neg A$ falsch ist).

Im zweiten Fall muss $\neg B={\mathsf {W}}$ und $\neg A={\mathsf {F}}$ sein. Dies bedeutet $B={\mathsf {F}}$ und $A={\mathsf {W}}$. Aber auch das führt zu einem Widerspruch, weil $A\Rightarrow B={\mathsf {W}}$ ist (für $B={\mathsf {F}}$ und $A={\mathsf {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)&\Leftrightarrow &(\neg B\Rightarrow \neg A):F\\\color {RoyalBlue}{\text{1. Fall}}&&\color {RedOrange}{\text{2. Fall}}\\\color {RoyalBlue}\downarrow &&\color {RedOrange}\downarrow \\A\Rightarrow B:{\mathsf {F}}&&A\Rightarrow B:{\mathsf {W}}\\\neg B\Rightarrow \neg A:{\mathsf {W}}&&\neg B\Rightarrow \neg A:{\mathsf {F}}\\\color {RoyalBlue}\downarrow &&\color {RedOrange}\downarrow \\A:{\mathsf {W}}&&B:{\mathsf {F}}\\B:{\mathsf {F}}&&A:{\mathsf {W}}\\\neg B\Rightarrow \neg A:{\mathsf {W}}&&A\Rightarrow B:{\mathsf {W}}\\\color {RoyalBlue}\downarrow &&\color {RedOrange}\downarrow \\\color {RoyalBlue}{\text{Widerspruch}}&&\color {RedOrange}{\text{Widerspruch}}\end{array}}$

Liste von Tautologien

Assoziativgesetze

Bei der Disjunktion und bei der Konjunktion ist es egal, in welcher Reihenfolge du die Aussagen auswertest:

• $(A\lor B)\lor C\Leftrightarrow A\lor (B\lor C)$
• $(A\land B)\land C\Leftrightarrow A\land (B\land C)$

Kommutativgesetze

Bei der Disjunktion und bei der Konjunktion ist es egal, in welcher Reihenfolge die einzelnen Teilaussagen verknüpft werden. Dies ist in der deutschen Sprache nicht unbedingt der Fall. Betrachte dazu folgende zwei Aussagen, welche in der Bedeutung einen leichten Unterschied aufweisen: „Ralf aß Haferbrei und er bekam Bauchschmerzen“ und „Er bekam Bauchschmerzen und Ralf aß Haferbrei“.

• $(A\lor B)\Leftrightarrow (B\lor A)$
• $(A\land B)\Leftrightarrow (B\land A)$

Distributivgesetze

Eine Disjunktion kann in eine Konjunktion hineingezogen werden und umgekehrt.

• $A\lor (B\land C)\Leftrightarrow (A\lor B)\land (A\lor C)$
• $A\land (B\lor C)\Leftrightarrow (A\land B)\lor (A\land C)$

Absorptionsgesetze

• $A\land (A\lor B)\Leftrightarrow A$
• $A\lor (A\land B)\Leftrightarrow A$

Idempotenzgesetze

• $A\land A\Leftrightarrow A$
• $A\lor A\Leftrightarrow A$

Doppelte Verneinung

• $\neg \neg A\Leftrightarrow A$

Satz vom ausgeschlossenen Dritten

• $A\lor \neg A$ (lateinisch: tertium non datur, übersetzt: ein Drittes gibt es nicht.)

Satz vom Widerspruch

• $\neg (A\land \neg A)$

Durch Anwendung der de Morganschen Regel, der doppelten Verneinung und der Kommutativität lässt sich der Satz vom Widerspruch in den Satz vom ausgeschlossenen Dritten umformen: $\neg (A\land \neg A)\iff \neg A\lor \neg \neg A\iff \neg A\lor A\iff A\lor \neg A$

Die de-Morgansche Regel

Bei der Negation einer Und- beziehungsweise einer Oder-Verknüpfung wird die Negation reingezogen und die Klammer aufgelöst. Aus einem $\land$ wird dabei ein $\lor$ und umgekehrt.

• $\neg (A\land B)\Leftrightarrow \neg A\lor \neg B$
• $\neg (A\lor B)\Leftrightarrow \neg A\land \neg B$

Negation von Implikation und Äquivalenz

• $\neg (A\Rightarrow B)\Leftrightarrow A\land \neg B$
• $\neg (A\Leftrightarrow B)\Leftrightarrow (A\Leftrightarrow \neg B)$
• $\neg (A\Leftrightarrow B)\Leftrightarrow (\neg A\Leftrightarrow B)$

Prinzip der Kontraposition

Diese Äquivalenz wird oft genutzt, um eine Implikation zu beweisen, Redewendung: Beweis der Kontraposition.

• $(A\Rightarrow B)\Leftrightarrow (\neg B\Rightarrow \neg A)$

Beweis durch Widerspruch

Auch mit Hilfe der folgenden Äquivalenz kann eine Implikation bewiesen werden, Redewendung: Beweis durch Widerspruch.

• $(A\Rightarrow B)\Leftrightarrow \neg (A\land \neg B)$
• $(A\Rightarrow B)\Leftrightarrow (A\land \neg B)\Rightarrow {\mathsf {F}}$

Darstellung von Implikation und Äquivalenz

Mit Hilfe dieser Gesetze kann die Implikation und die Äquivalenz auf Aussagen mit anderen Junktoren zurückgeführt werden.

• $A\Rightarrow B\Leftrightarrow \neg A\lor B$
• $(A\Leftrightarrow B)\Leftrightarrow (A\Rightarrow B)\land (B\Rightarrow A)$
• $(A\Leftrightarrow B)\Leftrightarrow (\neg A\lor B)\land (A\lor \neg B)$

Gesetze mit Wahr und Falsch

Im Folgenden steht ${\mathsf {W}}$ für „wahr“ und ${\mathsf {F}}$ für „falsch“. ${\mathsf {W}}$ und ${\mathsf {F}}$ können als 0-stellige Junktoren angesehen werden.

• ${\mathsf {F}}\Rightarrow A$ (Aus Falschem folgt Beliebiges.)
• $A\Rightarrow {\mathsf {W}}$
• $A\land {\mathsf {W}}\Leftrightarrow A$
• $A\lor {\mathsf {F}}\Leftrightarrow A$
• $A\lor {\mathsf {W}}$
• $\neg (A\land {\mathsf {F}})$
• $\lnot A\Leftrightarrow (A\Rightarrow {\mathsf {F}})$ (Wird gelegentlich als Definition für $\neg$ verwendet.)