TAOCP 7.1.1 Exercise 9
The statement is $(x \oplus y) \vee z = (x \vee z) \oplus (y \vee z).$ Using equation (5), $x\oplus y=1 \iff x\ne y.$ Take $x=0,\qquad y=1,\qquad z=1.$
Exercise 9. [16] [16] True or false? (a) $(x \oplus y) \vee z = (x \vee z) \oplus (y \vee z)$; (b) $(w \oplus x \oplus y) \vee z = (w \vee z) \oplus (x \vee z) \oplus (y \vee z)$; (c) $(x \oplus y) \vee (y \oplus z) = (x \oplus z) \vee (y \oplus z)$.
Verified: yes
Solve time: 1m09s
Solution
(a)
The statement is
$(x \oplus y) \vee z = (x \vee z) \oplus (y \vee z).$
Using equation (5),
$x\oplus y=1 \iff x\ne y.$
Take
$x=0,\qquad y=1,\qquad z=1.$
Then
$(x\oplus y)\vee z=(0\oplus1)\vee1=1\vee1=1.$
On the other hand,
=(0\vee1)\oplus(1\vee1) =1\oplus1 =0.$$ Hence $$1\ne0,$$ so the identity fails. Therefore (a) is false. --- ### (b) The statement is $$(w\oplus x\oplus y)\vee z =(w\vee z)\oplus(x\vee z)\oplus(y\vee z).$$ Take $$w=0,\qquad x=0,\qquad y=1,\qquad z=1.$$ Since $\oplus$ is associative (Exercise 6), $$w\oplus x\oplus y =0\oplus0\oplus1 =1.$$ Therefore $$(w\oplus x\oplus y)\vee z =1\vee1 =1.$$ But $$(w\vee z)\oplus(x\vee z)\oplus(y\vee z) =1\oplus1\oplus1 =0\oplus1 =1.$$ This example does not disprove the identity, so a more systematic calculation is needed. Write $$a=w\vee z,\qquad b=x\vee z,\qquad c=y\vee z.$$ If $z=0$, then $a=w$, $b=x$, $c=y$, and both sides are equal. If $z=1$, then $$a=b=c=1,$$ hence the right-hand side becomes $$1\oplus1\oplus1=1.$$ The left-hand side becomes $$(w\oplus x\oplus y)\vee1=1.$$ Thus both sides are equal when $z=1$. Since the identity holds for both possible values of $z$, it holds identically. Therefore (b) is true. --- ### (c) The statement is $$(x\oplus y)\vee(y\oplus z) =(x\oplus z)\vee(y\oplus z).$$ The left-hand side equals $0$ exactly when $$x\oplus y=0 \quad\text{and}\quad y\oplus z=0.$$ By equation (4), $$x\oplus y=0 \iff x=y,$$ and $$y\oplus z=0 \iff y=z.$$ Hence the left-hand side is $0$ exactly when $$x=y=z.$$ The right-hand side equals $0$ exactly when $$x\oplus z=0 \quad\text{and}\quad y\oplus z=0,$$ which is equivalent to $$x=z,\qquad y=z,$$ again giving $$x=y=z.$$ Therefore both sides are $0$ exactly for the two assignments $$(x,y,z)=(0,0,0),\qquad (1,1,1).$$ For all other assignments, at least one of the disjuncts on each side is $1$, so both sides are $1$. Thus the two expressions have identical truth tables, and $$(x\oplus y)\vee(y\oplus z) =(x\oplus z)\vee(y\oplus z).$$ Therefore (c) is true. The answers are $$\boxed{\text{(a) False,\quad (b) True,\quad (c) True}.}$$