# Prove XOR is commutative and associative?

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?

-
What does this have to do with automated theorem-proving? – Chris Eagle Feb 3 '13 at 17:48

I use $\cdot$ to denote AND and $+$ to denote OR. $a \oplus 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 \oplus b) \oplus c=a \oplus (b \oplus c)$. The left side expands as

$$(a \oplus b)\cdot\bar{c}+\overline{(a \oplus 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.

-

An intuitive way of understanding why XOR is associative is as follows:

First recognize that XOR is commutative, that is, $a \oplus b = b \oplus a$. This can be done using a truth table or as in Robert Mastragostino's answer.

Then, think of the XOR operator as a 'conditional flip' operator, that is think of $a \oplus b$ as saying if $a$ is 1, take flipped $b$ as the output, while if $a$ is 0, take $b$ as the output. Because of the commutative property, $a \oplus b$ is completely equivalent to $b \oplus a$ which says that $b$ conditionally flips $a$.

Now consider $a \oplus (b \oplus c)$. This is saying that $b$ conditionally flips $c$, the result of which is itself conditionally flipped by $a$. Because of the nature of the flipping operation, ultimately $c$ is conditionally flipped by both $b$ and $a$, and it doesn't matter in which order these two flip operations are performed. Because of this, it is seen that $a \oplus (b \oplus c)$ is equivalent to $b \oplus (a \oplus c)$.

Finally, by using commutativity, one can write $a \oplus (b \oplus c) = (b \oplus c) \oplus a$, which was just showed to be equivalent to $b \oplus (a \oplus c)$, itself equivalent to $b \oplus (c \oplus a)$ by commutativity.

Therefore, $(b \oplus c) \oplus a = b \oplus (c \oplus a)$ which proves associativity.

-
Great explanation! – hack3r Jan 24 at 14:13

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.

-

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.

-