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?

  • 0
    Rewrite your definition of XOR to be $(P\wedge ¬Q)\vee(Q\wedge ¬P)$. Now do you see the relationship?2011-11-21
  • 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))$$

  • 2
    The reason this correspondence between sets and statements exists is that in a sense, sets *are* statements. You can think of the set of all even numbers as being equivalent to the statement "it is an even number", the set of all continuous functions as being equivalent to the statement "it is a continuous function", and so on.2011-11-21
  • 0
    @TannerL.Swett It sounds to me like you've confused the "one" with the "many", along with confusing {4} with 4 and {T} with T. 2 has special characteristics in comparison to {2, 4, 6, 8...} as 2 is *the* even prime.2011-11-22
  • 1
    For completeness, note that XOR is actually inequality on booleans. So, writing boolean equality (equivalence) as $\;\equiv\;$, we have $$ x \in A \mathbin\triangle B \;\equiv\; x \in A \;\not\equiv\; x \in B $$ Note that $\;\equiv\;$ and $\;\not\equiv\;$ are both associative, and on top of that they are also _mutually_ associative, so that the above definition does not require any parentheses.2014-04-15
  • 2
    @TannerSwett No, that's only in a naive set theory that holds. In a really working set theory you have to distinguish between sets and statements or you run into Russell's paradox which would render the set theory useless.2015-08-31
  • 0
    True. Restating myself 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