I'm working on a problem:
If A, B, C, and D are sets, does it follow that (A $\oplus$ B) $\oplus$ (C $\oplus$ D) = (A $\oplus$ C) $\oplus$ (B $\oplus$ D)?
How does one approach something like this? I don't even know where to start.
$\endgroup$3 Answers
$\begingroup$Yes, the symmetric difference is commutative. However, Symmetric Difference is not XOR. The two are similar, but they are by no means the same. XOR is a logical operation, Symmetric Difference is an operation you apply to sets.
There are several ways to attack it.
I denote symmetric difference with $\Delta$. Take $A\Delta B$ and $B \Delta A$. Can you show that the two sets are equal? You can show that two sets are equal by showing that they are subsets of each other: if whenever $x \in X, x \in Y$, then $X \subseteq Y$, and then if $Y \subseteq X$, the two sets must be equal.
You could also just consider all the possible cases: $a \in A, a \notin B$, etc. and see if the cases for both sets always work out to be the same.
$\endgroup$ 13 $\begingroup$(Below I use the symbols $P\oplus Q\equiv(P\vee Q)\wedge\neg(P\wedge Q)$ for the propositional XOR function and $A\,\triangle\,B=(A\cup B)\setminus(A\cap B)$ for the symmetric difference operator.)
It follows immediately if you know that the regular binary XOR function $P\oplus Q$ is associative and commutative, since $x\in A\,\triangle\,B$ iff $(x\in A)\oplus (x\in B)$. If you don't know that XOR is associative and commutative, you can see it by recognizing it as the same as addition mod 2, where true is 1 and false is 0.
To show how it applies directly to your example:
$$\begin{align} x\in(A\,\triangle\,B)\,\triangle\,(C\,\triangle\,D)&\iff x\in A\,\triangle\,B\oplus x\in C\,\triangle\,D\\ &\iff (x\in A\oplus x\in B)\oplus (x\in C\oplus x\in D)\\ &\iff (x\in A\oplus x\in C)\oplus (x\in B\oplus x\in D)\\ &\iff x\in A\,\triangle\,C\oplus x\in B\,\triangle\,D\\ &\iff x\in(A\,\triangle\,C)\,\triangle\,(B\,\triangle\,D)\end{align}$$
I am applying associativity and commutativity of XOR in the third step.
$\endgroup$ 9 $\begingroup$The $\oplus$ operation is commutative, since $$P\oplus Q \iff \hbox{Exactly one of $P$, $Q$ is true}.$$ This formulation is symmetric in $P$ and $Q$.
The $\oplus$ operation is associative since $$(P\oplus Q)\oplus R \iff \hbox{An odd number of $P$, $Q$ and $R$ is true},$$ and since this formulation is symmetric in the three arguments.
$\endgroup$
