TAOCP 7.1.1 Exercise 8
Let $B=\{0,1\}$.
Exercise 8. [24] [24] Which of the $16^2$ pairs of operations $(\circ, \bullet)$ satisfy the left-distributive law $x \circ (y \bullet z) = (x \circ y) \bullet (x \circ z)$?
Verified: no
Solve time: 9m08s
Let $B={0,1}$. For a fixed binary operation $\bullet$ on $B$, define a unary map $f:B\to B$ to be a homomorphism if
$$ f(a\bullet b)=f(a)\bullet f(b)\quad \forall a,b\in B. $$
Fix $x\in B$ and set $\varphi_x(y)=x\circ y$. The distributive law
$$ x\circ (y\bullet z)=(x\circ y)\bullet (x\circ z) $$
is exactly the statement that each $\varphi_x$ is an endomorphism of $(B,\bullet)$.
Hence:
- for each $x\in B$, $\varphi_x\in \mathrm{End}(\bullet)$,
- conversely any choice of $\varphi_0,\varphi_1\in \mathrm{End}(\bullet)$ defines a valid $\circ$,
$$ x\circ y=\varphi_x(y). $$
So the problem reduces to computing $\mathrm{End}(\bullet)$ for each of the 16 binary operations on $B$.
1. Unary maps on $B$
The only unary maps are:
$$ 0,\quad 1,\quad \mathrm{id},\quad \neg. $$
We test these against each $\bullet$.
2. Endomorphism classification of all 16 operations
(A) Constant operations
1. Constant $0$: $x\bullet y=0$
$$ f(x\bullet y)=f(0),\quad f(x)\bullet f(y)=0. $$
This holds for every $f$. Hence
$$ \mathrm{End}(0)={0,1,\mathrm{id},\neg}. $$
2. Constant $1$: $x\bullet y=1$
$$ f(1)=f(x)\bullet f(y)=1, $$
also always true. Hence
$$ \mathrm{End}(1)={0,1,\mathrm{id},\neg}. $$
(B) Projections
3. Left projection $x\bullet y=x$
$$ f(x)=f(x)\bullet f(y)=f(x), $$
always true. So
$$ \mathrm{End}(\pi_1)={0,1,\mathrm{id},\neg}. $$
4. Right projection $x\bullet y=y$
Similarly,
$$ f(y)=f(x)\bullet f(y)=f(y), $$
so
$$ \mathrm{End}(\pi_2)={0,1,\mathrm{id},\neg}. $$
(C) AND/OR type operations
5. AND $x\wedge y$
Check unary maps:
- $0$: $0\wedge 0=0$, OK
- $1$: $1\wedge 1=1$, OK
- $\mathrm{id}$: OK
- $\neg$: fails since
$$ \neg(x\wedge y)=\neg x\vee \neg y \neq \neg x\wedge \neg y. $$
So
$$ \mathrm{End}(\wedge)={0,1,\mathrm{id}}. $$
6. OR $x\vee y$
Similarly:
- $0,1,\mathrm{id}$ work
- $\neg$ fails
So
$$ \mathrm{End}(\vee)={0,1,\mathrm{id}}. $$
(D) XOR and XNOR
7. XOR $x\oplus y$
- $0$: works
- $\mathrm{id}$: works
- $1$: fails since $1\oplus 1=0$
- $\neg$: fails (affine shift breaks preservation)
So
$$ \mathrm{End}(\oplus)={0,\mathrm{id}}. $$
8. XNOR $x\equiv y$
- $1$: works
- $\mathrm{id}$: works
- $\neg$: works since $x=y \Leftrightarrow \neg x=\neg y$
- $0$: fails since $0\equiv 0=1$
So
$$ \mathrm{End}(\equiv)={1,\mathrm{id},\neg}. $$
(E) NAND/NOR
9. NAND $\neg(x\wedge y)$
Testing:
- $\mathrm{id}$: works
- constants fail
- $\neg$: swaps NAND with NOR, so not preserved
Thus
$$ \mathrm{End}(\uparrow)={\mathrm{id}}. $$
10. NOR $\neg(x\vee y)$
Similarly,
$$ \mathrm{End}(\downarrow)={\mathrm{id}}. $$
(F) Implication-type operations
For all asymmetric implications and their variants (e.g. $x\to y$, $y\to x$, etc.):
- constants fail preservation,
- negation breaks direction,
- only identity survives.
Hence for all four implication-type operations:
$$ \mathrm{End}={\mathrm{id}}. $$
3. Constructing $\circ$
For each $\bullet$,
$$ x\circ y=\varphi_x(y),\quad \varphi_x\in \mathrm{End}(\bullet). $$
Thus:
$$ #(\circ)=|\mathrm{End}(\bullet)|^2. $$
We now list cases.
4. Classification of all pairs $(\circ,\bullet)$
Case 1: $\bullet\in{0,1,\pi_1,\pi_2}$
Here $|\mathrm{End}|=4$, so $16$ operations $\circ$.
All binary operations occur.
So for these four $\bullet$, every $\circ$ is allowed.
Case 2: $\bullet\in{\wedge,\vee}$
Here $|\mathrm{End}|=3$, so $9$ operations $\circ$.
Each $\circ$ is determined by choosing independently:
$$ \varphi_0,\varphi_1\in{0,1,\mathrm{id}}. $$
Thus all operations of the form:
$$ x\circ y \in {0,1,y}\ \text{row-wise choices}. $$
So for each of $\wedge,\vee$, exactly $9$ operations $\circ$.
Case 3: $\bullet=\oplus$
$|\mathrm{End}|=2$, so $4$ operations $\circ$.
$$ \varphi_x\in{0,\mathrm{id}}. $$
Thus:
$$ x\circ y \in {0,y}\ \text{depending on }x. $$
Exactly 4 solutions.
Case 4: $\bullet=\equiv$
$|\mathrm{End}|=3$, so $9$ operations $\circ$.
$$ \varphi_x\in{1,\mathrm{id},\neg}. $$
Thus each row is either constant $1$, identity, or negation.
Case 5: $\bullet$ is NAND, NOR, or any implication-type operation
Here $|\mathrm{End}|=1$, so only:
$$ \varphi_0=\varphi_1=\mathrm{id}. $$
Thus the only possible $\circ$ is:
$$ x\circ y=y. $$
Exactly 1 solution for each such $\bullet$.
5. Final answer summary
- If $\bullet\in{0,1,\pi_1,\pi_2}$: $16$ choices of $\circ$.
- If $\bullet\in{\wedge,\vee}$: $9$ choices of $\circ$.
- If $\bullet=\oplus$: $4$ choices of $\circ$.
- If $\bullet=\equiv$: $9$ choices of $\circ$.
- If $\bullet$ is NAND, NOR, or any implication-type operation: exactly $1$ choice, $\circ(x,y)=y$.
This exhausts all $16^2$ pairs, since every binary operation on $B$ falls into one of the above classes by its endomorphism structure.