Symmetric Difference is Associative/Proof 2
Jump to navigation
Jump to search
Theorem
Symmetric difference is associative:
- $R \symdif \paren {S \symdif T} = \paren {R \symdif S} \symdif T$
Proof
Expanding the right hand side:
| \(\ds \) | \(\) | \(\ds \paren {R \symdif S} \symdif T\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds \paren {\paren {\paren {R \cup S} \cap \paren {\overline R \cup \overline S} } \cup T} \cap \paren {\overline {R \symdif S} \cup \overline T}\) | Definition 4 of Symmetric Difference | |||||||||||
| \(\ds \) | \(=\) | \(\ds \paren {\paren {\paren {R \cup S} \cap \paren {\overline R \cup \overline S} } \cup T} \cap \paren {\overline {\paren {\paren {R \cap \overline S} \cup \paren {\overline R \cap S} } } \cup \overline T}\) | Definition 3 of Symmetric Difference | |||||||||||
| \(\ds \) | \(=\) | \(\ds \paren {R \cup S \cup T} \cap \paren {\overline R \cup \overline S \cup T} \cap \paren {\paren {\overline {\paren {R \cap \overline S} } \cap \overline {\paren {\overline R \cap S} } } \cup \overline T}\) | Union Distributes over Intersection and De Morgan | |||||||||||
| \(\ds \) | \(=\) | \(\ds \paren {R \cup S \cup T} \cap \paren {\overline R \cup \overline S \cup T} \cap \paren {\paren {\paren {\overline R \cup S} \cap \paren {R \cup \overline S} } \cup \overline T}\) | De Morgan | |||||||||||
| \(\ds \) | \(=\) | \(\ds \paren {R \cup S \cup T} \cap \paren {\overline R \cup \overline S \cup T} \cap \paren {\overline R \cup S \cup \overline T} \cap \paren {R \cup \overline S \cup \overline T}\) | Union Distributes over Intersection |
Expanding the left hand side:
| \(\ds \) | \(\) | \(\ds R \symdif \paren {S \symdif T}\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds \paren {R \cup \paren {\paren {S \cup T} \cap \paren {\overline S \cup \overline T} } } \cap \paren {\overline R \cup \overline {S \symdif T} }\) | Definition 4 of Symmetric Difference | |||||||||||
| \(\ds \) | \(=\) | \(\ds \paren {R \cup \paren {\paren {S \cup T} \cap \paren {\overline S \cup \overline T} } } \cap \paren {\overline R \cup \overline {\paren {\paren {S \cap \overline T} \cup \paren {\overline S \cap T} } } }\) | Definition 3 of Symmetric Difference | |||||||||||
| \(\ds \) | \(=\) | \(\ds \paren {R \cup S \cup T} \cap \paren {R \cup \overline S \cup \overline T} \cap \paren {\overline R \cup \paren {\overline {\paren {S \cap \overline T} } \cap \overline {\paren {\overline S \cap T} } } }\) | Union Distributes over Intersection and De Morgan | |||||||||||
| \(\ds \) | \(=\) | \(\ds \paren {R \cup S \cup T} \cap \paren {R \cup \overline S \cup \overline T} \cap \paren {\overline R \cup \paren {\paren {\overline S \cup T} \cap \paren {S \cup \overline T} } }\) | De Morgan | |||||||||||
| \(\ds \) | \(=\) | \(\ds \paren {R \cup S \cup T} \cap \paren {R \cup \overline S \cup \overline T} \cap \paren {\overline R \cup \overline S \cup T} \cap \paren {\overline R \cup S \cup \overline T}\) | Union Distributes over Intersection |
From Intersection is Commutative, it can be seen that the left hand side and right hand side are the same, and the result is proved.
$\blacksquare$