7
$\begingroup$

I noticed that XOR and symmetric difference use the same symbol, $\oplus$.

They also seem to have a similar structure:

XOR: $(Q \wedge \neg P)\vee(P\wedge \neg Q)$

Symmetric Difference: $(A\cap B^C)\cup(B\cap A^C)$

Is there a relation between them?

  • 2
    It is the same thing. Symmetric difference is XOR for sets, XOR is symmetric difference for truth values. Thinking of both as Boolean algebra operations then they are indeed the same.2011-11-21

1 Answers 1

10

Yes, there is. Let $A\;\triangle\; B$ denote the symmetric difference of the sets $A$ and $B$. Given an object $x$, $x\in A\;\triangle\; B\iff (x\in A)\text{ XOR }(x\in B).$ In general, one has a correspondence between statements in set theory and statements in logic, e.g. $x\in A\cup B\iff (x\in A)\text{ OR }(x\in B)$ $x\in A\cap B\iff (x\in A)\text{ AND }(x\in B)$ $x\in A^c\iff\text{NOT }(x\in A)$

So, for example, $A\setminus B=A\cap B^c$, so $x\in A\setminus B\iff x\in A\cap B^c\iff(x\in A)\text{ AND }(x\in B^c)\iff (x\in A)\text{ AND }(\text{NOT }(x\in B))$

  • 0
    True. Restating mysel$f$ more precisely: there's a one-to-one correspondence between the subsets of a set and the predicates on that set, but in a set theory such as ZFC, not every predicate defines a set.2015-08-31