The symmetric difference $A$ △ $B$ of $A$ and $B$ is defined as $(A - B) \cup (B - A)$. (The set of elements that belong to A or B but not both.)
(a) Construct a truth table to show that △ is associative.
(b) Show that $x$ belongs to $A$ △ $(B$ △ $C)$ if and only if $x$ belongs to an odd number of the sets $A$, $B$ and $C$ and use this observation to give a second proof that △ is associative.
For part (a), I'd be grateful is someone could post the full truth table, as I'm not entirely sure what column headings they are looking for.
For part (b), this is what I did:
(For the left to right implication) Let $x \in $ $A$ △ $(B$ △ $C)$. Then, by the definition of △, we have either $x \in $ $A$ or $x \in $ $(B$ △ $C)$ but not both. So if $x \in A$ then either it is not in $B$ nor $C$ or it is in both $B$ and $C$. So here $x$ can be in just $A$, or in $A, B$ and $C$. If $x \in (B$ △ $C)$, then $x \notin A$. So by a similar logic $x$ can be in $B$ or $C$, but not both. The implication works both ways, hence the 'iff'.
However, I'm not sure how this proves associativity. I tried to write it as
$A$ △ $(B$ △ $C)$ = ($A$ △ $B$) $\cap$ ($A$ △ $C$) $\cap$ ($B$ △ $C$) $ \cup$ $ (A\cap B\cap C)$ And then associativity would follow by swapping $A$ and $C$ but I'm not sure if this is the right way of doing it.
$\endgroup$2 Answers
$\begingroup$Here is a proof:
$\left(A\triangle B\right)\triangle C=\left(A\cup B\cup C\right)\cap\left(A\cup B^{c}\cup C^{c}\right)\cap(A^{c}\cup B\cup C^{c})\cap(A^{c}\cup B^{c}\cup C)=(B\cup C\cup A)\cap(B\cup C^{c}\cup A^{c})\cap(B^{c}\cup C\cup A^{c})\cap(B^{c}\cup C^{c}\cup A)=(B\bigtriangleup C)\bigtriangleup A=A\bigtriangleup(B\bigtriangleup C)$
The proof of symmetric difference operator associativity comes from late professor David Meredith home page:
practically one page paper contains prepositions and eventually proof of associativity. Proof assume that operator $\triangle$ is commutative as proven below from preposition 7:
$A\triangle B=(A\cup B)\cap(A^{c}\cup B^{c})=(B\cup A)\cap(B^{c}\cup A^{c})=B\triangle A$
Hope it helps.
$\endgroup$ $\begingroup$Here is a truth table with an intermediate column;
$$\ \begin{array}{|ccc|c|c|} \hline A&B&C&A\Delta B&(A\Delta B)\Delta C\\ \hline 0&0&0&0&0\\ 0&0&1&0&1\\ 0&1&0&1&1\\ 0&1&1&1&0\\ 1&0&0&1&1\\ 1&0&1&1&0\\ 1&1&0&0&0\\ 1&1&1&0&1\\ \hline \end{array}$$
$\endgroup$ 2
