Satz vom Widerspruch Regeln zur Disjunktion und Konjunktion
Beim Rechnen mit Zahlen gibt es für die Addition und die Multiplikation das Kommutativgesetz, das Assoziativgesetz und die Distributivgesetze. Gleichartige Gesetze gibt es ebenfalls in der Logik für die Oder- und die Und-Verknüpfung.
Für die Formeln \(\alpha\), \(\beta\) und \(\gamma\) gelten die folgenden Tautologien:
Kommutativgesetze für \(\lor\) und \(\land\):
- \((\alpha \lor \beta) \iff (\beta \lor \alpha)\enspace\) ist eine Tautologie
- \((\alpha \land \beta) \iff (\beta \land \alpha)\enspace\) ist eine Tautologie
Assoziativgesetze für \(\lor\) und \(\land\):
- \(((\alpha \lor \beta) \lor \gamma) \iff (\alpha \lor (\beta \lor \gamma))\enspace\) ist eine Tautologie
- \(((\alpha \land \beta) \land \gamma) \iff (\alpha \land (\beta \land \gamma))\enspace\) ist eine Tautologie
Distributivgesetze:
- \(((\alpha \lor \beta) \land \gamma) \iff ((\alpha \land \gamma) \lor (\beta \land \gamma))\enspace\) ist eine Tautologie
- \(((\alpha \land \beta) \lor \gamma) \iff ((\alpha \lor \gamma) \land (\beta \lor \gamma))\enspace\) ist eine Tautologie
Beweis der Kommutativgesetze
Beweis des 1. Kommutativgesetzes:
Wir beweisen:
\(\qquad\) | \((\alpha \lor \beta) \iff (\beta \lor \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 \lor \beta & \beta \lor \alpha & (\alpha \lor \beta) \iff (\beta \lor \alpha)\ \\ \hline \mathrm{w} & \mathrm{w} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w} & \mathrm{w}\ \\ \hline \mathrm{w} & \mathrm{f} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w} & \mathrm{w}\ \\ \hline \mathrm{f} & \mathrm{w} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w} & \mathrm{w}\ \\ \hline \mathrm{f} & \mathrm{f} & \hspace{-0.8em} & \mathrm{f} & \mathrm{f} & \mathrm{w}\ \\ \hline\end{array}\) |
Die Aussage ist eine Tautologie.
Beweis des 2. Kommutativgesetzes:
Wir beweisen:
\(\qquad\) | \((\alpha \land \beta) \iff (\beta \land \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 \land \beta & \beta \land \alpha & (\alpha \land \beta) \iff (\beta \land \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{f} & \mathrm{f} & \mathrm{w}\ \\ \hline\end{array}\) |
Die Aussage ist eine Tautologie.
Beweis der Assoziativgesetze
Beweis des 1. Assoziativgesetzes:
Wir beweisen:
\(\qquad\) | \(\underbrace{((\alpha \lor \beta) \lor \gamma)}_{\mu} \iff \underbrace{(\alpha \lor (\beta \lor \gamma))}_{\nu}\enspace\) ist eine Tautologie |
Wir bilden Wahrheitstabellen für den linken Teil \(\mu\) und den rechten Teil \(\nu\) der Äquivalenz und zeigen, dass beide Seiten auf die gleichen Wahrheitswerte führen, also logisch äquivalent sind. Die Wahrheitstabelle für \(\mu=(\alpha \lor \beta) \lor \gamma\) lautet:
\(\qquad\) | \(\begin{array}{|c|c|c|c|c|c|c|c|} \hline \alpha & \beta & \gamma & \hspace{-0.8em} & \alpha \lor \beta & (\alpha \lor \beta) \lor \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{w}\ \\\hline \mathrm{w} & \mathrm{f} & \mathrm{w} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w}\ \\\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{w}\ \\\hline \mathrm{f} & \mathrm{w} & \mathrm{f} & \hspace{-0.8em} & \mathrm{w} & \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{f} & \mathrm{f}\ \\\hline\end{array}\) |
Die Wahrheitstabelle für \(\nu=\alpha \lor (\beta \lor \gamma)\) lautet:
\(\qquad\) | \(\begin{array}{|c|c|c|c|c|c|c|c|} \hline \alpha & \beta & \gamma & \hspace{-0.8em} & \beta\lor \gamma & \alpha \lor (\beta \lor \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{w}\ \\\hline \mathrm{w} & \mathrm{f} & \mathrm{w} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w}\ \\\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{w} & \mathrm{w}\ \\\hline \mathrm{f} & \mathrm{w} & \mathrm{f} & \hspace{-0.8em} & \mathrm{w} & \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{f} & \mathrm{f}\ \\\hline\end{array}\) |
\(\mu\) und \(\nu\) führen auf die gleichen Wahrheitswerte. Die beiden Seiten der Gleichung sind also logisch äquivalent, d.h. die Aussage ist eine Tautologie.
Beweis des 2. Assoziativgesetzes:
Wir beweisen:
\(\qquad\) | \(\underbrace{((\alpha \land \beta) \land \gamma)}_{\mu} \iff \underbrace{(\alpha \land (\beta \land \gamma))}_{\nu}\enspace\) ist eine Tautologie |
Wir bilden Wahrheitstabellen für den linken Teil \(\mu\) und den rechten Teil \(\nu\) der Äquivalenz und zeigen, dass beide Seiten auf die gleichen Wahrheitswerte führen, also logisch äquivalent sind. Die Wahrheitstabelle für \(\mu=(\alpha \land \beta) \land \gamma\) lautet:
\(\qquad\) | \(\begin{array}{|c|c|c|c|c|c|c|c|} \hline \alpha & \beta & \gamma & \hspace{-0.8em} & \alpha \land \beta & (\alpha \land \beta) \land \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{f}\ \\\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{f}\ \\\hline \mathrm{f} & \mathrm{f} & \mathrm{w} & \hspace{-0.8em} & \mathrm{f} & \mathrm{f}\ \\\hline \mathrm{f} & \mathrm{f} & \mathrm{f} & \hspace{-0.8em} & \mathrm{f} & \mathrm{f}\ \\\hline\end{array}\) |
Die Wahrheitstabelle für \(\nu=\alpha \land (\beta \land \gamma)\) lautet:
\(\qquad\) | \(\begin{array}{|c|c|c|c|c|c|c|c|} \hline \alpha & \beta & \gamma & \hspace{-0.8em} & \beta \land \gamma & \alpha \land (\beta \land \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{f} & \mathrm{f}\ \\\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{f}\ \\\hline \mathrm{f} & \mathrm{f} & \mathrm{w} & \hspace{-0.8em} & \mathrm{f} & \mathrm{f}\ \\\hline \mathrm{f} & \mathrm{f} & \mathrm{f} & \hspace{-0.8em} & \mathrm{f} & \mathrm{f}\ \\\hline\end{array}\) |
\(\mu\) und \(\nu\) führen auf die gleichen Wahrheitswerte. Die beiden Seiten der Gleichung sind also logisch äquivalent, d.h. die Aussage ist eine Tautologie.
Beweis der Distributivgesetze
Beweis des 1. Distributivgesetzes:
Wir beweisen:
\(\qquad\) | \(\underbrace{((\alpha \lor \beta) \land \gamma)}_{\mu} \iff \underbrace{((\alpha \land \gamma) \lor (\beta \land \gamma))}_{\nu}\enspace\) ist eine Tautologie |
Wir bilden Wahrheitstabellen für den linken Teil \(\mu\) und den rechten Teil \(\nu\) der Äquivalenz und zeigen, dass beide Seiten auf die gleichen Wahrheitswerte führen, also logisch äquivalent sind. Die Wahrheitstabelle für \(\mu=(\alpha \lor \beta) \land \gamma\) lautet:
\(\qquad\) | \(\begin{array}{|c|c|c|c|c|c|c|c|} \hline \alpha & \beta & \gamma & \hspace{-0.8em} & \alpha \lor \beta &(\alpha \lor \beta) \land \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{w} & \mathrm{w}\ \\\hline \mathrm{w} & \mathrm{f} & \mathrm{f} & \hspace{-0.8em} & \mathrm{w} & \mathrm{f}\ \\\hline \mathrm{f} & \mathrm{w} & \mathrm{w} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w}\ \\\hline \mathrm{f} & \mathrm{w} & \mathrm{f} & \hspace{-0.8em} & \mathrm{w} & \mathrm{f}\ \\\hline \mathrm{f} & \mathrm{f} & \mathrm{w} & \hspace{-0.8em} & \mathrm{f} & \mathrm{f}\ \\\hline \mathrm{f} & \mathrm{f} & \mathrm{f} & \hspace{-0.8em} & \mathrm{f} & \mathrm{f}\ \\\hline\end{array}\) |
Die Wahrheitstabelle für \(\nu=(\alpha \land \gamma) \lor (\beta \land \gamma)\) lautet:
\(\qquad\) | \(\begin{array}{|c|c|c|c|c|c|c|c|} \hline \alpha & \beta & \gamma & \hspace{-0.8em} & \alpha \land \gamma & \beta \land \gamma & (\alpha \land \gamma) \lor (\beta \land \gamma) \ \\\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{f}\ \\\hline \mathrm{w} & \mathrm{f} & \mathrm{w} & \hspace{-0.8em} & \mathrm{w} & \mathrm{f}& \mathrm{w}\ \\\hline \mathrm{w} & \mathrm{f} & \mathrm{f} & \hspace{-0.8em} & \mathrm{f} & \mathrm{f}& \mathrm{f}\ \\\hline \mathrm{f} & \mathrm{w} & \mathrm{w} & \hspace{-0.8em} & \mathrm{f} & \mathrm{w}& \mathrm{w}\ \\\hline \mathrm{f} & \mathrm{w} & \mathrm{f} & \hspace{-0.8em} & \mathrm{f} & \mathrm{f}& \mathrm{f}\ \\\hline \mathrm{f} & \mathrm{f} & \mathrm{w} & \hspace{-0.8em} & \mathrm{f} & \mathrm{f}& \mathrm{f}\ \\\hline \mathrm{f} & \mathrm{f} & \mathrm{f} & \hspace{-0.8em} & \mathrm{f} & \mathrm{f}& \mathrm{f}\ \\\hline\end{array}\) |
\(\mu\) und \(\nu\) führen auf die gleichen Wahrheitswerte. Die beiden Seiten der Gleichung sind also logisch äquivalent, d.h. die Aussage ist eine Tautologie.
Beweis des 2. Distributivgesetzes:
Wir beweisen:
\(\qquad\) | \(\underbrace{((\alpha \land \beta) \lor \gamma)}_{\mu} \iff \underbrace{((\alpha \lor \gamma) \land (\beta \lor \gamma))}_{\nu}\enspace\) ist eine Tautologie |
Wir bilden Wahrheitstabellen für den linken Teil \(\mu\) und den rechten Teil \(\nu\) der Äquivalenz und zeigen, dass beide Seiten auf die gleichen Wahrheitswerte führen, also logisch äquivalent sind. Die Wahrheitstabelle für \(\mu=(\alpha \land \beta) \lor \gamma\) lautet:
\(\qquad\) | \(\begin{array}{|c|c|c|c|c|c|c|c|} \hline \alpha & \beta & \gamma & \hspace{-0.8em} & \alpha \land \beta & (\alpha \land \beta) \lor \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{w}\ \\\hline \mathrm{w} & \mathrm{f} & \mathrm{w} & \hspace{-0.8em} & \mathrm{f} & \mathrm{w}\ \\\hline \mathrm{w} & \mathrm{f} & \mathrm{f} & \hspace{-0.8em} & \mathrm{f} & \mathrm{f}\ \\\hline \mathrm{f} & \mathrm{w} & \mathrm{w} & \hspace{-0.8em} & \mathrm{f} & \mathrm{w}\ \\\hline \mathrm{f} & \mathrm{w} & \mathrm{f} & \hspace{-0.8em} & \mathrm{f} & \mathrm{f}\ \\\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{f} & \mathrm{f}\ \\\hline\end{array}\) |
Die Wahrheitstabelle für \(\nu=(\alpha \lor \gamma) \land (\beta \lor \gamma)\) lautet:
\(\qquad\) | \(\begin{array}{|c|c|c|c|c|c|c|c|} \hline \alpha & \beta & \gamma & \hspace{-0.8em} & \alpha \lor \gamma & \beta \lor \gamma & (\alpha \lor \gamma) \land (\beta \lor \gamma) \ \\\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{w} & \mathrm{w}& \mathrm{w}\ \\\hline \mathrm{w} & \mathrm{f} & \mathrm{w} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w}& \mathrm{w}\ \\\hline \mathrm{w} & \mathrm{f} & \mathrm{f} & \hspace{-0.8em} & \mathrm{w} & \mathrm{f}& \mathrm{f}\ \\\hline \mathrm{f} & \mathrm{w} & \mathrm{w} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w}& \mathrm{w}\ \\\hline \mathrm{f} & \mathrm{w} & \mathrm{f} & \hspace{-0.8em} & \mathrm{f} & \mathrm{w}& \mathrm{f}\ \\\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{f}\ \\\hline\end{array}\) |
\(\mu\) und \(\nu\) führen auf die gleichen Wahrheitswerte. Die beiden Seiten der Gleichung sind also logisch äquivalent, d.h. die Aussage ist eine Tautologie.
\(\enspace\)