Kommutativgesetze für ᴧ und v Assoziativgesetze für ᴧ und v
Gilt für eine Verknüpfung das Assoziativgesetz, dann spielt die Reihenfolge der Ausführung der einzelnen Verknüpfungen keine Rolle. Die Klammerung mehrerer assoziativer Verknüpfungen ist also beliebig.
In der Logik sind die Disjunktion und die Konjunktion assoziative Verknüpfungen. Bei der Hintereinanderausführung mehrerer Oder-Verknüpfungen oder Und-Verknüpfungen kommt es auf die Reihenfolge der Ausführungen nicht an. Das Ergebnis wird das gleiche sein, auch wenn sich die Reihenfolge der einzelnen Verknüpfungen ändert.
Die Äquivalenz ist ebenfalls eine assoziative Verknüpfung, die Implikation dagegen nicht.
Assoziativgesetze für \(\lor\) und \(\land\):
Für die Formeln \(\alpha\), \(\beta\) und \(\gamma\) gelten die folgenden Tautologien:
- \(((\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
Beispiel:
Wir zeigen die Assoziativität der Äquivalenz, d.h. wir zeigen, dass die folgende Aussage
\(\qquad\) | \(((\alpha \iff \beta) \iff \gamma) \iff (\alpha \iff (\beta \iff \gamma))\) |
eine Tautologie ist.
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 \iff \beta) \iff \gamma\) lautet:
\(\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}\) |
Die Wahrheitstabelle für \(\nu=\alpha \iff (\beta \iff \gamma)\) lautet:
\(\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}\) |
\(\mu\) und \(\nu\) führen auf die gleichen Wahrheitswerte. Die beiden Seiten der Gleichung sind also logisch äquivalent, d.h. die Aussage
\(\qquad ((\alpha \iff \beta) \iff \gamma) \iff (\alpha \iff (\beta \iff \gamma))\)
ist eine Tautologie und damit ein logisches Gesetz.
Beispiel:
Wir zeigen, dass die Implikation nicht assoziativ ist, d.h. wir zeigen, dass die folgende Aussage
\(\qquad\) | \(((\alpha \implies \beta) \implies \gamma) \iff (\alpha \implies (\beta \implies \gamma))\) |
keine Tautologie ist.
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 \implies \beta) \implies\gamma\) lautet:
\(\qquad\) | \(\begin{array}{|c|c|c|c|c|c|c|c|} \hline \alpha & \beta & \gamma & \hspace{-0.8em} & \alpha \implies \beta &(\alpha \implies \beta) \implies \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{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{f}\ \\ \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}\) |
Die Wahrheitstabelle für \(\nu=\alpha \implies (\beta \implies \gamma)\) lautet:
\(\qquad\) | \(\begin{array}{|c|c|c|c|c|c|c|c|} \hline \alpha & \beta & \gamma & \hspace{-0.8em} & \beta\implies \gamma &\alpha \implies (\beta \implies \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{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{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{w}\ \\ \hline\end{array}\) |
\(\mu\) und \(\nu\) führen auf unterschiedliche Wahrheitswerte. Die beiden Seiten der Gleichung sind also nicht logisch äquivalent, d.h. die Aussage
\(\qquad\) | \(((\alpha \implies \beta) \implies \gamma) \iff (\alpha \implies (\beta \implies \gamma))\) |
ist keine Tautologie.
Merke:
Aufgrund der Assoziativgesetze sind Ausdrücke der Form
\(\qquad\) | \(\alpha_1 \lor \alpha_2 \lor \ldots \lor \alpha_n\) |
sowie
\(\qquad\) | \(\alpha_1 \land \alpha_2 \land \ldots \land \alpha_n\) |
eindeutig definiert, ohne dass man noch zusätzliche Klammern einfügen muss. Dabei gilt:
- \(\alpha_1 \lor \alpha_2 \lor \ldots \lor \alpha_n\) ist genau dann wahr, wenn wenigstens eine der Teilaussagen \(\alpha_1, \ldots, \alpha_n\) wahr ist.
- \(\alpha_1 \land \alpha_2 \land \ldots \land \alpha_n\) ist genau dann wahr, wenn alle Teilaussagen \(\alpha_1, \ldots, \alpha_n\) wahr sind.
\(\enspace\)