Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

They also seem to have a similar structure:

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

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

Is there a relation between them?

share|cite|improve this question
Rewrite your definition of XOR to be $(P\wedge ¬Q)\vee(Q\wedge ¬P)$. Now do you see the relationship? – Chris Taylor Nov 21 '11 at 10:31
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. – Asaf Karagila Nov 21 '11 at 10:40
up vote 6 down vote accepted

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))$$

share|cite|improve this answer
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. – Tanner Swett Nov 21 '11 at 18:29
@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. – Doug Spoonwood Nov 22 '11 at 20:28
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. – Marnix Klooster Apr 15 '14 at 17:16
@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. – skyking Aug 31 '15 at 12:18
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. – Tanner Swett Aug 31 '15 at 21:33

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.