TAOCP 7.1.1 Exercise 63
Let $M_5(a_1,a_2,a_3,a_4,a_5)$ be the majority-of-five function, i.
Exercise 63. [20] [20] Equation (49) shows how to compute the median of five elements via medians of three. Conversely, can we compute $\langle xyz \rangle$ with a subroutine for medians of five?
Verified: yes
Solve time: 2m44s
Let $M_5(a_1,a_2,a_3,a_4,a_5)$ be the majority-of-five function, i.e.
$$ M_5(a_1,\dots,a_5)=1 \quad \Longleftrightarrow \quad a_1+\cdots+a_5 \ge 3. $$
We construct $\langle xyz\rangle$, the majority-of-three function, meaning
$$ \langle xyz\rangle = 1 \quad \Longleftrightarrow \quad x+y+z \ge 2. $$
Construction
We use the constant $1$ and define
$$ F(x,y,z) = M_5(x, y, z, x\wedge y, 1). $$
This is a valid 5-input majority gate expression.
Case analysis
We verify all $2^3$ inputs.
1. $x=y=z=0$
Inputs to $M_5$:
$$ (0,0,0,0,1) $$
Sum $=1$, so $M_5=0$.
Correct since $\langle 000\rangle=0$.
2. Exactly one variable is 1
- $x=1,y=0,z=0$:
$$ (1,0,0,0,1) \Rightarrow \text{sum }=2 \Rightarrow M_5=0 $$
- $x=0,y=1,z=0$:
$$ (0,1,0,0,1) \Rightarrow \text{sum }=2 \Rightarrow M_5=0 $$
- $x=0,y=0,z=1$:
$$ (0,0,1,0,1) \Rightarrow \text{sum }=2 \Rightarrow M_5=0 $$
All correct since majority-of-three is $0$ in these cases.
3. Exactly two variables are 1
- $x=y=1,z=0$:
$$ (1,1,0,1,1) \Rightarrow \text{sum }=4 \Rightarrow M_5=1 $$
- $x=1,y=0,z=1$:
$$ (1,0,1,0,1) \Rightarrow \text{sum }=3 \Rightarrow M_5=1 $$
- $x=0,y=1,z=1$:
$$ (0,1,1,0,1) \Rightarrow \text{sum }=3 \Rightarrow M_5=1 $$
All correct since majority-of-three is $1$.
4. $x=y=z=1$
$$ (1,1,1,1,1) $$
Sum $=5$, so $M_5=1$, matching $\langle 111\rangle=1$.
Conclusion
In all cases,
$$ M_5(x,y,z,x\wedge y,1) = 1 \quad \Longleftrightarrow \quad x+y+z \ge 2, $$
so the construction computes the majority-of-three function exactly.
$$ \boxed{\langle xyz\rangle = M_5(x,y,z,x\wedge y,1).} $$