TAOCP 7.1.1 Exercise 60
The median $\langle xyz \rangle$ in (43) equals the majority function $\langle xyz \rangle = (x \wedge y)\ \vee\ (y \wedge z)\ \vee\ (z \wedge x).$ For (a), let $a=x\wedge y$, $b=y\wedge z$, $c=x\wedg...
Exercise 60. [10] [10] Which of the following expressions yield the median $\langle xyz \rangle$, as defined in (43)?
(a) $(x \land y) \oplus (y \land z) \oplus (x \land z)$; (b) $(x \lor y) \oplus (y \lor z) \oplus (x \lor z)$; (c) $(x \land y) \lor (y \land z) \lor (x \oplus z)$; (d) $(x \oplus y) \oplus (y \oplus z) \oplus (x \oplus z)$; (e) $(x \land y) \oplus (y \oplus z) \oplus (x \lor z)$; (f) $(x \land y) \lor (y \land z) \lor (x \lor z)$; (g) $(x \land y) \oplus (y \land z) \oplus (x \lor z)$.
Verified: yes
Solve time: 1m15s
The median $\langle xyz \rangle$ in (43) equals the majority function
$\langle xyz \rangle = (x \wedge y)\ \vee\ (y \wedge z)\ \vee\ (z \wedge x).$
For (a), let $a=x\wedge y$, $b=y\wedge z$, $c=x\wedge z$. In every assignment of $(x,y,z)\in{0,1}^3$, the value of $a\oplus b\oplus c$ coincides with the number of true pairwise products modulo $2$, and a direct case analysis over the eight assignments shows it equals $1$ exactly when at least two of $x,y,z$ are $1$. Hence (a) equals $\langle xyz\rangle$.
For (b), let $A=x\vee y$, $B=y\vee z$, $C=x\vee z$. Evaluating all eight assignments shows $A\oplus B\oplus C=1$ precisely for those and only those assignments with at least two variables equal to $1$, so (b) also equals $\langle xyz\rangle$.
For (c), the assignment $(x,y,z)=(1,0,1)$ gives $(x\wedge y)\vee (y\wedge z)\vee (x\oplus z)=0$, while $\langle xyz\rangle=1$, so (c) does not equal the median.
For (d), each variable occurs twice in $(x\oplus y)\oplus (y\oplus z)\oplus (x\oplus z)$, hence cancellation in $\mathbb{F}_2$ yields $0$ for all inputs, so (d) is not the median.
For (e), the assignment $(x,y,z)=(1,0,1)$ gives value $0$ while $\langle xyz\rangle=1$, so (e) does not equal the median.
For (f), $(x\wedge y)\vee (y\wedge z)\vee (x\vee z) = x\vee z$, and the assignment $(1,0,0)$ yields $1$ while $\langle xyz\rangle=0$, so (f) is not the median.
For (g), the assignment $(x,y,z)=(1,0,0)$ gives value $1$ while $\langle xyz\rangle=0$, so (g) does not equal the median.
Thus the expressions that yield the median $\langle xyz\rangle$ are (a) and (b).
This completes the proof. ∎