TAOCP 7.1.1 Exercise 61
The statement claims that for any Boolean binary operation $\circ$ in Table 1, the identity x \circ (yz) \;=\; (w \lor x)(w \lor y)(w \lor z) holds for some fixed Boolean value $w$ depending only on $...
Exercise 61. [13] [13] True or false: If any one of the Boolean binary operations in Table 1, we have the distributive law $x \circ (yz) = \langle w \lor x \rangle \langle w \lor y \rangle \langle w \lor z \rangle$.
Verified: yes
Solve time: 1m01s
Solution
The statement claims that for any Boolean binary operation $\circ$ in Table 1, the identity
$$ x \circ (yz) ;=; (w \lor x)(w \lor y)(w \lor z) $$
holds for some fixed Boolean value $w$ depending only on $\circ$.
It suffices to disprove this claim by exhibiting a single operation $\circ$ for which no choice of $w$ makes the identity valid for all $x,y,z \in {0,1}$.
Take $\circ$ to be left projection $\mathsf{L}$ from Table 1, so
$$ x \mathsf{L} t = x $$
for all $x,t$. Then
$$ x \circ (yz) = x. $$
Assume there exists $w \in {0,1}$ such that
$$ x = (w \lor x)(w \lor y)(w \lor z) $$
for all $x,y,z \in {0,1}$.
Set $x=0$. Then
$$ 0 = (w \lor 0)(w \lor y)(w \lor z). $$
If $w=1$, then $(w \lor 0)(w \lor y)(w \lor z)=1$, contradicting the equation $0=1$.
Hence $w=0$. Substituting $w=0$ yields
$$ x = x \cdot y \cdot z. $$
Set $x=1$. Then
$$ 1 = y z. $$
Choosing $y=0$ and $z=0$ gives $yz=0$, contradicting $1=0$.
Both choices of $w$ lead to contradiction, so no such $w$ exists for $\circ = \mathsf{L}$.
Since the claim is asserted to hold for every binary operation in Table 1, it is false.
This completes the proof. ∎