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.

Through the use of Boolean algebra, show that the XOR operator ⊕ is both commutative and associative.

I know I can show using a truth table. But using boolean algeba? How do I show? I totally have no clue. Any help please?

share|improve this question
2  
What does this have to do with automated theorem-proving? –  Chris Eagle Feb 3 '13 at 17:48
add comment

3 Answers

up vote 2 down vote accepted

I use $\cdot$ to denote AND and $+$ to denote OR. $a$ XOR $b$ is given by $a\cdot\bar{b}+b\cdot\bar{a}$. Do you see why? Do you see why this is commutative?

For associativity, you want to show that ($a$ XOR $b$) XOR $c$=$a$ XOR ($b$ XOR $c$). The left side expands as

$$(a\text{ XOR }b)\cdot\bar{c}+\overline{(a\text{ XOR }b)}\cdot c$$ $$(a\cdot\bar{b}+b\cdot\bar{a})\cdot\bar{c}+\overline{(a\cdot\bar{b}+b\cdot\bar{a})}\cdot c$$

Use the rules of boolean algebra (Demorgan's Laws, Distributive laws etc.) to expand this out. Then do the same for the other side, and show the expansions are equal.

share|improve this answer
add comment

I assume you are given a definition of $\oplus$ in terms of $\vee$ and $\wedge$ such as $a \oplus b = (a \wedge \neg b) \vee (\neg a \wedge b)$ or $a\oplus b = (a\vee b) \wedge \neg(a \wedge b)$. You have to show $a \oplus b = b \oplus a$ and $a \oplus (b \oplus c) = (a \oplus b) \oplus c$ using the rules for $\vee$ and $\wedge$. For example you could use the commutativity and associativity of $\vee$ and $\wedge$, the distributive laws or De Morgan's laws (see here for a complete list of such laws). The commutativity is straightforward, the associativity is an easy but rather lengthy computation. A standard procedure would be to put both sides of $a \oplus (b \oplus c) = (a \oplus b) \oplus c$ into conjunctive or disjunctive normal form and then compare.

share|improve this answer
add comment

Write the xor operator in terms of the standard Boolean algebra operators (and, or, not), and then use the properties of Boolean algebras to show that xor is commutative and associative.

share|improve this answer
add comment

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.