# Proofs sets exclusive or

I know this might be easy for you but I am struggling with this question. $\oplus$ means XOR:

How would you break down $\overline{B} \oplus A$. I have to show that its equal to $(A-\overline{B})\cup (\overline{B}-A)$.

• Here, you can take $\overline B$ to mean the complement of $B$. – Namaste Oct 12 '13 at 14:06
• what does the complement of B mean sorry I am a newbie. – George Gronge Oct 12 '13 at 14:22
• See my answer below. $x \in \overline B$ means $x \notin B$: $\overline B$ it is the set of all elements NOT IN $B$. Make sure to review your text and notes to understand the definitions you need here, which I summarized in my answer below. – Namaste Oct 12 '13 at 14:23

## 1 Answer

We know from the definition of XOR, denoted here as $\oplus$, that $$x\in (P \oplus Q) \iff (x \in P \;\text{ AND }\; x \notin Q) \;\text{ OR }\; (x \notin P \;\text{ AND } \; x \in Q)$$

We know from the definition of the complement of a set $B$, denoted using an "overline": $\overline B$, that $$x\in \overline B \iff x \notin B$$

Of course, set union $\cup$ means that $x\in P \cup Q \iff x\in P \;\text{ OR }\; x \in Q$.

And from the definition of set minus, we have that $x \in P - Q \iff x \in P \;\text{ AND }\; x\notin Q$.

These definitions are all you need to show, by "element chasing", that $$x \in \overline B \oplus A \iff x \in (A - \overline B) \cup (\overline B - A)$$

and hence, that $$\overline B \oplus A = (A - \overline B) \cup (\overline B - A)$$

• Very clear write up +1 – Amzoti Oct 12 '13 at 14:34
• I know X-( P AND Q) is the same as X AND (P AND comp Q), but is X - (P OR Q) the same as X or ( P Or comp Q)? – George Gronge Oct 12 '13 at 14:37