Prove XOR is commutative and associative?

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.


An intuitive way to convince yourself that $\oplus$ is associative is the following. (Note: we're not really proving it through rigid algebra here - but I think it's a very intuitive argument and shows another nice way to look at $\oplus$.)

Let's first have a look at the truth table again: \begin{array}{cc|c} x & y & x\oplus y\\ \hline 0 & 0 & 0\\ 0 & 1 & 1\\ 1 & 0 & 1\\ 1 & 1 & 0\\ \end{array} Commutativity: From the truth table, we can easily convince us that we may commute the arguments. Since in any case, commuting it will give us the same result.

Associativity: Further, we see from the truth table we can see that we may rewrite $x\oplus y$ as a predicate and an addition: $$ x\oplus y \quad\Longleftrightarrow \quad \text{odd}(x+y) $$ Now using this way of rewriting the $\oplus$, we can easily see that $\oplus$ is associative. $$ \begin{align*} x\oplus (y\oplus z) &\Longleftrightarrow \text{odd}(x+\text{odd}(y+z))\\ &\Longleftrightarrow \text{odd}(x+y+z)\\ &\Longleftrightarrow \text{odd}(\text{odd}(x+y)+z)\\ &\Longleftrightarrow (x\oplus y)\oplus z \end{align*} $$

Tags:

Boolean Algebra

Propositional Calculus

Binary Operations

Related

When log is written without a base, is the equation normally referring to log base 10 or natural log? How to prove that the set is not a regular surface? Is A∨¬A a tautology when there is a proof (by contradiction)? How do I prove that $f(x)f(y)=f(x+y)$ implies that $f(x)=e^{cx}$, assuming f is continuous and not zero? Prove Petersen graph is not Hamiltonian using deduction and no fancy theorems How to show that $[0,1]^{\omega}$ is not locally compact in the uniform topology? Rotating one 3d-vector to another What is the Topology of point-wise convergence? Evaluate:: $ 2 \sum_{n=1}^\infty \frac{(-1)^{n+1}}{n+1}\left( 1 + \frac12 +\cdots + \frac 1n\right) $ Calculus question taking derivative to find horizontal tangent line Proof : cannot draw this figure without lifting the pen How to determine whether a function of many variables is convex or non-convex?

Recent Posts