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?
$\begingroup$
$\endgroup$
2
asked Nov 21, 2011 at 10:22
-
$\begingroup$ Rewrite your definition of XOR to be $(P\wedge ¬Q)\vee(Q\wedge ¬P)$. Now do you see the relationship? $\endgroup$– Chris TaylorCommented Nov 21, 2011 at 10:31
-
4$\begingroup$ 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. $\endgroup$– Asaf Karagila ♦Commented Nov 21, 2011 at 10:40
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
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))$$
answered Nov 21, 2011 at 10:31
-
3$\begingroup$ 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. $\endgroup$ Commented Nov 21, 2011 at 18:29
-
$\begingroup$ @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. $\endgroup$ Commented Nov 22, 2011 at 20:28
-
3$\begingroup$ 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. $\endgroup$ Commented Apr 15, 2014 at 17:16
-
3$\begingroup$ @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. $\endgroup$– skykingCommented Aug 31, 2015 at 12:18
-
2$\begingroup$ 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. $\endgroup$ Commented Aug 31, 2015 at 21:33