Voraussetzung

${\displaystyle A,\ B,\ C}$ seien beliebige Mengen.

Behauptung

${\displaystyle A\cap (B\cap C)=(A\cap B)\cap C}$

${\displaystyle A\cup (B\cup C)=(A\cup B)\cup C}$

Beweis

Zwei Mengen sind genau dann gleich, wenn sie genau dieselben Elemente enthalten. Nun gilt

${\displaystyle x\in A\cap (B\cap C)\iff x\in A\land x\in (B\cap C)\iff x\in A\land (x\in B\land x\in C)}$

sowie

${\displaystyle x\in (A\cap B)\cap C\iff x\in (A\cap B)\land x\in C\iff (x\in A\land x\in B)\land x\in C.}$

Die Gleichheit ${\displaystyle A\cap (B\cap C)=(A\cap B)\cap C}$ folgt also wegen der Assoziativität der logischen und-Verknüpfung, d.h. aus der Äquivalenz von ${\displaystyle p\land (q\land r)}$ und ${\displaystyle (p\land q)\land r}$.

Die Aussage für die Vereinigung folgt entsprechend aus der Assoziativität der logischen oder-Verknüpfung.

Voraussetzung

${\displaystyle A,\ B,\ C}$ seien beliebige Mengen.

Behauptung

${\displaystyle A\triangle (B\triangle C)=(A\triangle B)\triangle C}$

Beweis

Hier folgt die Gleichheit der Mengen aus der logischen Äquivalenz von ${\displaystyle p\not \leftrightarrow (q\not \leftrightarrow r)}$ und ${\displaystyle (p\not \leftrightarrow q)\not \leftrightarrow r}$. Beide sind genau dann wahr, wenn genau eine oder alle drei Teilaussagen wahr sind. Der Beweis wird im Folgenden direkt für Mengen geführt. Für die symmetrische Differenz gilt:

${\displaystyle {\begin{aligned}B\triangle C&=(B\cup C)\setminus (B\cap C)=(B\cup C)\cap (B\cap C)^{\mathsf {C}}\\&=(B\cup C)\cap (B^{\mathsf {C}}\cup C^{\mathsf {C}})=(B\cap C^{\mathsf {C}})\cup (C\cap B^{\mathsf {C}})\end{aligned}}}$

Die letzten beiden Ausdrücke benutzt man in der folgenden Rechnung.

${\displaystyle {\begin{aligned}A\triangle (B\triangle C)&=\left(A\cap (B\triangle C)^{\mathsf {C}}\right)\cup \left((B\triangle C)\cap A^{\mathsf {C}}\right)\\&=\left(A\cap \left((B^{\mathsf {C}}\cap C^{\mathsf {C}})\cup (B\cap C)\right)\right)\cup \left(\left((B\cap C^{\mathsf {C}})\cup (C\cap B^{\mathsf {C}})\right)\cap A^{\mathsf {C}}\right)\\&=(A\cap B^{\mathsf {C}}\cap C^{\mathsf {C}})\cup (A\cap B\cap C)\cup (B\cap C^{\mathsf {C}}\cap A^{\mathsf {C}})\cup (C\cap B^{\mathsf {C}}\cap A^{\mathsf {C}})\end{aligned}}}$

Dieser Ausdruck ist invariant unter Permutationen von ${\displaystyle A,\ B,\ C}$. Daher gilt das Assoziativgesetz.