Aufgabe 3 Regeln für Äquivalenzen
Auch für Äquivalenzen gibt es eine Vielzahl an Regeln. Wir wollen hier nur die wichtigsten Regeln zusammenfassen, die teilweise an anderer Stelle bereits bewiesen wurden.
Regeln für Äquivalenzen:
Für die Formeln \(\alpha\), \(\beta\) und \(\gamma\) gelten die folgenden Tautologien:
\(\tiny\blacksquare\quad\) | Kommutativität von \(\iff\): \((\alpha \iff \beta) \iff (\beta \iff \alpha)\enspace\) ist eine Tautologie |
\(\tiny\blacksquare\quad\) | Assoziativität von \(\iff\): \(((\alpha \iff \beta) \iff \gamma) \iff (\alpha \iff (\beta \iff \gamma))\enspace\) ist eine Tautologie |
\(\tiny\blacksquare\quad\) | Darstellung von \(\iff\) mit \(\implies\): \((\alpha \iff \beta) \iff ((\alpha \implies \beta) \land (\beta \implies \alpha))\enspace\) ist eine Tautologie |
\(\tiny\blacksquare\quad\) | Kontrapositionsgesetz für \(\iff\): \((\alpha \iff \beta) \iff (\lnot \alpha \iff \lnot\beta)\enspace\) ist eine Tautologie |
Beweise
Beweis der Kommutativität von \(\iff\):
Wir beweisen:
\(\qquad\) | \((\alpha \iff \beta) \iff (\beta \iff \alpha)\enspace\) ist eine Tautologie |
Wir bilden die Wahrheitstabelle:
\(\qquad\) | \(\begin{array}{|c|c|c|c|c|c|c|c|} \hline \alpha & \beta & \hspace{-0.8em} & \alpha \iff\beta & \beta \iff \alpha & (\alpha \iff \beta) \\ & & \hspace{-0.8em} & & & \iff (\beta \iff \alpha)\ \\\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{f}& \mathrm{w}\ \\\hline \mathrm{f} & \mathrm{w} & \hspace{-0.8em} & \mathrm{f}& \mathrm{f}& \mathrm{w}\ \\\hline \mathrm{f} & \mathrm{f} & \hspace{-0.8em} & \mathrm{w}& \mathrm{w}& \mathrm{w}\ \\\hline\end{array}\) |
Die Aussage ist eine Tautologie.
Beweis der Assoziativität von \(\iff\):
Wir beweisen:
\(\qquad\) | \(\underbrace{((\alpha \iff \beta) \iff \gamma)}_{\mu} \iff \underbrace{(\alpha \iff (\beta \iff \gamma))}_{\nu}\enspace\) ist eine Tautologie |
Wir bilden die Wahrheitstabelle für den linken Teil \(\mu\) der Äquivalenz:
\(\qquad\) | \(\begin{array}{|c|c|c|c|c|c|c|c|} \hline \alpha & \beta & \gamma & \hspace{-0.8em} & \alpha \iff \beta &(\alpha \iff \beta) \iff \gamma \ \\\hline \mathrm{w} & \mathrm{w} & \mathrm{w} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w}\ \\\hline \mathrm{w} & \mathrm{w} & \mathrm{f} & \hspace{-0.8em} & \mathrm{w} & \mathrm{f}\ \\\hline \mathrm{w} & \mathrm{f} & \mathrm{w} & \hspace{-0.8em} & \mathrm{f} & \mathrm{f}\ \\\hline \mathrm{w} & \mathrm{f} & \mathrm{f} & \hspace{-0.8em} & \mathrm{f} & \mathrm{w}\ \\\hline \mathrm{f} & \mathrm{w} & \mathrm{w} & \hspace{-0.8em} & \mathrm{f} & \mathrm{f}\ \\\hline \mathrm{f} & \mathrm{w} & \mathrm{f} & \hspace{-0.8em} & \mathrm{f} & \mathrm{w}\ \\\hline \mathrm{f} & \mathrm{f} & \mathrm{w} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w}\ \\\hline \mathrm{f} & \mathrm{f} & \mathrm{f} & \hspace{-0.8em} & \mathrm{w} & \mathrm{f}\ \\\hline\end{array}\) |
Wir bilden die Wahrheitstabelle für den rechten Teil \(\nu\) der Äquivalenz:
\(\qquad\) | \(\begin{array}{|c|c|c|c|c|c|c|c|} \hline \alpha & \beta & \gamma & \hspace{-0.8em} & \beta \iff \gamma & \alpha \iff (\beta \iff \gamma) \ \\\hline \mathrm{w} & \mathrm{w} & \mathrm{w} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w}\ \\\hline \mathrm{w} & \mathrm{w} & \mathrm{f} & \hspace{-0.8em} & \mathrm{f} & \mathrm{f}\ \\\hline \mathrm{w} & \mathrm{f} & \mathrm{w} & \hspace{-0.8em} & \mathrm{f} & \mathrm{f}\ \\\hline \mathrm{w} & \mathrm{f} & \mathrm{f} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w}\ \\\hline \mathrm{f} & \mathrm{w} & \mathrm{w} & \hspace{-0.8em} & \mathrm{w} & \mathrm{f}\ \\\hline \mathrm{f} & \mathrm{w} & \mathrm{f} & \hspace{-0.8em} & \mathrm{f} & \mathrm{w}\ \\\hline \mathrm{f} & \mathrm{f} & \mathrm{w} & \hspace{-0.8em} & \mathrm{f} & \mathrm{w}\ \\\hline \mathrm{f} & \mathrm{f} & \mathrm{f} & \hspace{-0.8em} & \mathrm{w} & \mathrm{f}\ \\\hline\end{array}\) |
Wir bilden die Wahrheitstabelle für die Äquivalenz \(\mu \iff \nu\):
\(\qquad\) | \(\begin{array}{|c|c|c|c|c|c|c|c|} \hline \alpha & \beta & \gamma & \hspace{-0.8em} & \mu & \nu & \mu \iff \nu \ \\\hline \mathrm{w} & \mathrm{w} & \mathrm{w} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w} & \mathrm{w}\ \\\hline \mathrm{w} & \mathrm{w} & \mathrm{f} & \hspace{-0.8em} & \mathrm{f} & \mathrm{f} & \mathrm{w}\ \\\hline \mathrm{w} & \mathrm{f} & \mathrm{w} & \hspace{-0.8em} & \mathrm{f} & \mathrm{f} & \mathrm{w}\ \\\hline \mathrm{w} & \mathrm{f} & \mathrm{f} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w} & \mathrm{w}\ \\\hline \mathrm{f} & \mathrm{w} & \mathrm{w} & \hspace{-0.8em} & \mathrm{f} & \mathrm{f} & \mathrm{w}\ \\\hline \mathrm{f} & \mathrm{w} & \mathrm{f} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w} & \mathrm{w}\ \\\hline \mathrm{f} & \mathrm{f} & \mathrm{w} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w} & \mathrm{w}\ \\\hline \mathrm{f} & \mathrm{f} & \mathrm{f} & \hspace{-0.8em} & \mathrm{f} & \mathrm{f} & \mathrm{w}\ \\\hline\end{array}\) |
Die Aussage ist eine Tautologie.
Beweis der Darstellung von \(\iff\) mit \(\implies\):
Wir beweisen:
\(\qquad\) | \(\underbrace{(\alpha \iff \beta)}_{\mu} \iff \underbrace{(\alpha \implies \beta) \land (\beta \implies \alpha)}_{\nu}\enspace\) ist eine Tautologie |
Wir bilden die Wahrheitstabelle für den linken Teil \(\mu\) der Äquivalenz:
\(\qquad\) | \(\begin{array}{|c|c|c|c|c|c|c|c|} \hline \alpha & \beta & \hspace{-0.8em} & \alpha \iff \beta \ \\ \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}\) |
Wir bilden die Wahrheitstabelle für den rechten Teil \(\nu\) der Äquivalenz:
\(\qquad\) | \(\begin{array}{|c|c|c|c|c|c|c|c|} \hline \alpha & \beta & \hspace{-0.8em} & \alpha \implies \beta & \beta \implies \alpha & (\alpha \implies \beta) \\ & & \hspace{-0.8em} & & & \land \ (\beta \implies \alpha) \ \\ \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 bilden die Wahrheitstabelle für die Äquivalenz \(\mu \iff \nu\):
\(\qquad\) | \(\begin{array}{|c|c|c|c|c|c|c|c|} \hline \alpha & \beta & \hspace{-0.8em} & \mu & \nu & \mu \iff \nu \ \\ \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{f} & \mathrm{w}\ \\ \hline \mathrm{f} & \mathrm{w} & \hspace{-0.8em} & \mathrm{f} & \mathrm{f} & \mathrm{w}\ \\ \hline \mathrm{f} & \mathrm{f} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w} & \mathrm{w}\ \\ \hline\end{array}\) |
Die Aussage ist eine Tautologie.
Beweis des Kontrapositionsgesetzes für \(\iff\):
Wir beweisen:
\(\qquad\) | \((\alpha \iff \beta) \iff (\lnot \alpha \iff \lnot\beta)\enspace\) ist eine Tautologie |
Wir bilden die Wahrheitstabelle:
\(\qquad\) | \(\begin{array}{|c|c|c|c|c|c|c|c|} \hline \alpha & \beta & \hspace{-0.8em} & \alpha \iff \beta& \lnot \alpha & \lnot \beta & \lnot \alpha\iff\lnot \beta & (\alpha \iff \beta) \\ & & \hspace{-0.8em} & & & & & \iff (\lnot\alpha\iff\lnot \beta)\ \\\hline \mathrm{w} & \mathrm{w} & \hspace{-0.8em} & \mathrm{w}& \mathrm{f}& \mathrm{f}& \mathrm{w}& \mathrm{w}\ \\\hline \mathrm{w} & \mathrm{f} & \hspace{-0.8em} & \mathrm{f}& \mathrm{f}& \mathrm{w}& \mathrm{f}& \mathrm{w}\ \\\hline \mathrm{f} & \mathrm{w} & \hspace{-0.8em} & \mathrm{f}& \mathrm{w}& \mathrm{f}& \mathrm{f}& \mathrm{w}\ \\\hline \mathrm{f} & \mathrm{f} & \hspace{-0.8em} & \mathrm{w}& \mathrm{w}& \mathrm{w}& \mathrm{w}& \mathrm{w}\ \\\hline\end{array}\) |
Die Aussage ist eine Tautologie.
Wir werden die Regeln für Äquivalenzen im Lernmodul "Beweisprinzipien" erneut betrachten, wenn wir uns mit dem Beweisen von Behauptungen und Beweisprinzipien beschäftigen.
\(\enspace\)