Aufgabe 4 Äquivalenzbeweis
Bisher haben wir uns mit Implikationen \(A\implies B\) beschäftigt und gezeigt, wie man mithilfe unterschiedlicher Ansätze diese Implikationen beweisen kann. Nun möchten wir diskutieren, wie wir Äquivalenzbeweise \(A \iff B\) führen.
Wir können eine Äquivalenz \(A \iff B\) mithilfe eines direkten Beweises zeigen, wobei wir darauf achten müssen, dass es sich bei den Umformungen von der Aussage zur Behauptung tatsächlich um Äquivalenzumformungen handelt.
Gelingt dies nicht, so lässt sich eine Äquivalenz auch geeignet in zwei Implikationen aufspalten, die wir mit einer Konjunktion verknüpfen. Die drei folgenden Prinzipien für Äquivalenzbeweise haben wir teilweise bereits in den vorhergehenden Lernmodulen bewiesen. Sie lassen sich aber auch auf einfache Weise durch Wahrheitstabellen zeigen.
Prinzipien für Äquivalenzbeweise:
\((1)\quad\) | \((A\iff B) \iff ((A\implies B) \land (B \implies A))\) ist eine Tautologie. Das bedeutet: Man kann eine Äquivalenz dadurch beweisen, dass man in einem Schritt die Implikation \(A \implies B\) und im anderen Schritt die Implikation \(B \implies A\) zeigt. |
\((2)\quad\) | \((A \iff B) \iff ((A \implies B) \land (\lnot A \implies \lnot B))\) ist eine Tautologie. Das bedeutet: Man kann eine Äquivalenz dadurch beweisen, dass man in einem Schritt die Implikation \(A \implies B\) und im anderen Schritt die Implikation \(\lnot A \implies \lnot B\) zeigt. |
\((3)\quad\) | \((A \iff B)\iff ((\lnot A \implies \lnot B ) \land (\lnot B \implies \lnot A))\) ist eine Tautologie. Das bedeutet: Man kann eine Äquivalenz dadurch beweisen, dass man in einem Schritt die Implikation \(\lnot A \implies \lnot B\) und im anderen Schritt die Implikation \(\lnot B \implies \lnot A\) zeigt. |
Beweise
Für alle drei Prinzipien erstellen wir zuerst die Wahrheitstabelle der Äquivalenz \(A \iff B\) und zeigen danach, dass die Behauptungen auf die gleichen Wahrheitswerte führen:
\(\qquad\) | \(\begin{array}{|c|c|c|c|c|c|c|c|} \hline A & B & \hspace{-0.8em} & A \iff B \ \\ \hline \mathrm{w} & \mathrm{w} & \hspace{-0.8em} & \mathrm{w} \ \\ \hline \mathrm{w} & \mathrm{f} & \hspace{-0.8em} & \mathrm{f} \ \\ \hline \mathrm{f} & \mathrm{w} & \hspace{-0.8em} & \mathrm{f}\ \\ \hline \mathrm{f} & \mathrm{f} & \hspace{-0.8em} & \mathrm{w} \ \\ \hline\end{array}\) |
Beweis von \((1)\):
Wir bilden die Wahrheitstabelle:
\(\qquad\) | \(\begin{array}{|c|c|c|c|c|c|c|c|} \hline A & B & \hspace{-0.8em} & A \implies B & B \implies A & (A \implies B) \land \ \\ & & \hspace{-0.8em} & & & (B \implies A) \ \\ \hline \mathrm{w} & \mathrm{w} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w} & \mathrm{w} \ \\ \hline \mathrm{w} & \mathrm{f} & \hspace{-0.8em} & \mathrm{f}& \mathrm{w}& \mathrm{f} \ \\ \hline \mathrm{f} & \mathrm{w} & \hspace{-0.8em} & \mathrm{w}& \mathrm{f}& \mathrm{f}\ \\ \hline \mathrm{f} & \mathrm{f} & \hspace{-0.8em} & \mathrm{w}& \mathrm{w}& \mathrm{w} \ \\ \hline\end{array}\) |
Wir sehen, dass die Wahrheitswerte der Spalte \(A \iff B\) mit den Wahrheitswerten der Spalte \((A \implies B) \land (B \implies A)\) übereinstimmen. Das bedeutet, dass beide Aussagen logisch äquivalent sind.
Beweis von \((2)\):
Wir bilden die Wahrheitstabelle:
\(\qquad\) | \(\begin{array}{|c|c|c|c|c|c|c|c|} \hline A & B & \hspace{-0.8em} & \lnot A & \lnot B & A \implies B & \lnot A \implies \lnot B & (A \implies B) \land \ \\ & & \hspace{-0.8em} & & & & & (\lnot A \implies \lnot B) \ \\ \hline \mathrm{w} & \mathrm{w} & \hspace{-0.8em} & \mathrm{f} & \mathrm{f} & \mathrm{w} & \mathrm{w} & \mathrm{w} \ \\ \hline \mathrm{w} & \mathrm{f} & \hspace{-0.8em} & \mathrm{f} & \mathrm{w} & \mathrm{f} & \mathrm{w} & \mathrm{f} \ \\ \hline \mathrm{f} & \mathrm{w} & \hspace{-0.8em} & \mathrm{w} & \mathrm{f} & \mathrm{w} & \mathrm{f} & \mathrm{f}\ \\ \hline \mathrm{f} & \mathrm{f} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w} & \mathrm{w}& \mathrm{w}& \mathrm{w} \ \\ \hline\end{array}\) |
Wir sehen, dass die Wahrheitswerte der Spalte \(A \iff B\) mit den Wahrheitswerten der Spalte \((A \implies B) \land (\lnot A \implies \lnot B)\) übereinstimmen. Das bedeutet, dass beide Aussagen logisch äquivalent sind.
Beweis von \((3)\):
Wir bilden die Wahrheitstabelle:
\(\qquad\) | \(\begin{array}{|c|c|c|c|c|c|c|c|} \hline A & B & \hspace{-0.8em} & \lnot A & \lnot B & \lnot A \implies \lnot B & \lnot B \implies \lnot A & (\lnot A \implies \lnot B) \land \ \\& & \hspace{-0.8em} & & & & & (\lnot B \implies \lnot A) \ \\ \hline \mathrm{w} & \mathrm{w} & \hspace{-0.8em} & \mathrm{f} & \mathrm{f} & \mathrm{w} & \mathrm{w} & \mathrm{w} \ \\ \hline \mathrm{w} & \mathrm{f} & \hspace{-0.8em} & \mathrm{f} & \mathrm{w} & \mathrm{w} & \mathrm{f} & \mathrm{f} \ \\ \hline \mathrm{f} & \mathrm{w} & \hspace{-0.8em} & \mathrm{w} & \mathrm{f} & \mathrm{f} & \mathrm{w} & \mathrm{f}\ \\ \hline \mathrm{f} & \mathrm{f} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w} & \mathrm{w}& \mathrm{w}& \mathrm{w} \ \\ \hline\end{array}\) |
Wir sehen, dass die Wahrheitswerte der Spalte \(A \iff B\) mit den Wahrheitswerten der Spalte \((\lnot A \implies \lnot B) \land (\lnot B \implies \lnot A)\) übereinstimmen. Das bedeutet, dass beide Aussagen logisch äquivalent sind.
\(\enspace\)