TAOCP 7.1.1 Exercise 7
Let $f(x,y)$ denote the operation $x \circ y$.
Exercise 7. [20] [20] Which operations in Table 1 have the property that $x \circ y = z$ if and only if $y \circ z = x$?
Verified: yes
Solve time: 2m12s
Solution
Let $f(x,y)$ denote the operation $x \circ y$. The required condition is
$$ f(x,y)=z \quad \Longleftrightarrow \quad f(y,z)=x. $$
This implies that for every fixed $y$, the mapping $x \mapsto f(x,y)$ is a bijection on ${0,1}$, since it has inverse $z \mapsto f(y,z)$. Hence, for each fixed $y$, the two values $f(0,y)$ and $f(1,y)$ must be distinct, so
$$ f(0,y) \neq f(1,y). $$
Over ${0,1}$ this forces
$$ f(1,y) = 1 \oplus f(0,y). $$
Define $a(y)=f(0,y)$. Then for all $x,y$,
$$ f(x,y)=x \oplus a(y), $$
since this expression yields $f(0,y)=a(y)$ and $f(1,y)=1\oplus a(y)$.
Substituting this form into the condition $f(x,y)=z \Longleftrightarrow f(y,z)=x$ gives
$$ x \oplus a(y) = z \quad \Longleftrightarrow \quad y \oplus a(z) = x. $$
The left equation yields $x = z \oplus a(y)$, and the right yields $x = y \oplus a(z)$. Hence, for all $x,y,z$,
$$ z \oplus a(y) = y \oplus a(z). $$
Rearranging,
$$ a(z) \oplus z = a(y) \oplus y. $$
The left side depends only on $z$ and the right side only on $y$, so both must equal a constant bit $c$. Hence
$$ a(t) = t \oplus c \quad \text{for all } t \in {0,1}. $$
Substituting back,
$$ f(x,y)=x \oplus (y \oplus c)=x \oplus y \oplus c. $$
If $c=0$, then $f(x,y)=x\oplus y$, which is the exclusive-or operation $\oplus$. If $c=1$, then
$$ f(x,y)=1 \oplus x \oplus y, $$
which is the equivalence operation $\equiv$ as given in equation (3).
Verification for $f(x,y)=x\oplus y$ uses associativity and cancellation in $\mathbb{Z}_2$:
$$ x \oplus y = z \Longleftrightarrow x = z \oplus y = y \oplus z = f(y,z). $$
Verification for $f(x,y)=1\oplus x\oplus y$ follows from the same algebra:
$$ 1 \oplus x \oplus y = z \Longleftrightarrow x = 1 \oplus y \oplus z = f(y,z). $$
No other value of $c$ exists in ${0,1}$, so no other operation satisfies the condition.
Thus the operations are exactly those with truth tables $0110$ and $1001$, namely $\oplus$ and $\equiv$.
This completes the proof. ∎