is bitwise xor completely associative?

Question

The bitwise xor (exclusive or) operator has the following truth table:

$$ \begin{array}{c|cc} \text{^}&0&1\\ \hline 0&0&1\\ 1&1&0 \end{array} $$

It is true that if $a,b,c,d$ are boolean variables, then $a\text{^}b\text{^}c\text{^}d$ is unambiguous.

I proved this using the following truth charts and induction:

((0^0)^0)^0=0

((1^0)^0)^0=1, ((0^1)^0)^0=1, ((0^0)^1)^0=1, ((0^0)^0)^1=1

((1^1)^0)^0=0, ((1^0)^1)^0=0, ((1^0)^0)^1=0, ((0^1)^1)^0=0, ((0^1)^0)^1=0, ((0^0)^1)^1=0

((1^1)^1)^0=1, ((1^1)^0)^1=1, ((1^0)^1)^1=1, ((0^1)^1)^1=1

((1^1)^1)^1=0

---

(0^0)^(0^0)=0

(1^0)^(0^0)=1, (0^1)^(0^0)=1, (0^0)^(1^0)=1, (0^0)^(0^1)=1

(1^1)^(0^0)=0, (1^0)^(1^0)=0, (1^0)^(0^1)=0, (0^1)^(1^0)=0, (0^1)^(0^1)=0, (0^0)^(1^1)=0

(1^1)^(1^0)=1, (1^1)^(0^1)=1, (1^0)^(1^1)=1, (0^1)^(1^1)=1

(1^1)^(1^1)=0

I feel there must be a better solution though.

Answer 1

Xor is the same as integer addition modulo 2. Addition you can take in any order.

---

Edit: To clarify addition modulo 2 is a group which has group elements in the set $\{0,1\}$ and the operation table:

$$\left[\begin{array}{c|cc}+&0&1\\\hline0&0&1\\1&1&0\end{array}\right]$$ The table for the group with set $\{f,t\}$ and operation xor is:

$$\left[\begin{array}{c|cc}xor&f&t\\\hline f&f&t\\t&t&f\end{array}\right]$$

So we see there is a one-to-one correspondence between the groups. If we replace $f$ with $0$ and $t$ with $1$ and xor with $+$, then they become the same.

For all groups it is required that the operation is associative, i.e. that $(a+b)+c = a+(b+c)$

If I am not being tired or confused we can check this in matlab / octave with the following code:

 T2 = [1,2;2,1]; % matrix with indexes to the corresponding elements
 line1 = reshape((T2(vec(T2),:)),[2,2,2])
 line2 = reshape(vec(T2(T2,:)),[2,2,2])

And see that line1 and line2 print the same. And to show another example that it actually is the right group we can do:

 T3 = [1,2,3;2,3,1;3,1,2];
 reshape(vec(T3(T3,:)),[3,3,3])(a+1,b+1,c+1)-1

will be $\mod((a+b+c),3), \forall a,b,c \in\{0,1,2\}$

Answer 2

Hints:

1. Denoting XOR by $\Delta$, it would be enough to prove $(a\Delta b)\Delta c=a\Delta(b\Delta c)$, then apply this several times.
2. $a_1\Delta a_2\Delta a_3\Delta\dots\Delta a_n\ $ is true iff exactly an odd number of $a_i$'s are true.