Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
1  
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

1 Answer 1

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|improve this answer
1  
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 at 17:16

Your Answer

 
discard

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.