TAOCP 7.1.1 Exercise 62
Let $A = f(x_1, x_2, 0, x_4, \ldots, x_n), \quad B = f(x_1, x_2, x_3, x_4, \ldots, x_n), \quad C = f(x_1, x_2, 1, x_4, \ldots, x_n).$ Since $f$ is monotone, replacing a variable by a larger bit cannot...
Exercise 62. [25] [25] (C. Schensted.) If $f(x_1, \ldots, x_n)$ is a monotone Boolean function and $n \ge 3$, prove the median expansion formula
$$f(x_1, \ldots, x_n) = \langle f(x_1, x_2, x_3, x_4, \ldots, x_n) , f(x_1, x_2, \bar{x}_3, x_4, \ldots, x_n) , f(x_1, x_2, x_3, x_4, \ldots, x_n) \rangle.$$
Verified: yes
Solve time: 1m11s
Solution
Let
$A = f(x_1, x_2, 0, x_4, \ldots, x_n), \quad B = f(x_1, x_2, x_3, x_4, \ldots, x_n), \quad C = f(x_1, x_2, 1, x_4, \ldots, x_n).$
Since $f$ is monotone, replacing a variable by a larger bit cannot decrease the value of $f$. In the Boolean order $0 \le 1$, the inequality $0 \le x_3 \le 1$ holds for all $x_3$. Hence, by monotonicity in the third argument,
$A \le B \le C.$
The median function is defined by
$\langle x y z \rangle = (x \wedge y) \vee (y \wedge z) \vee (x \wedge z).$
Substituting $x=A$, $y=B$, $z=C$ yields
$\langle A B C \rangle = (A \wedge B) \vee (B \wedge C) \vee (A \wedge C).$
From $A \le B$ it follows that $A \wedge B = A$ and $A \wedge C = A$. From $B \le C$ it follows that $B \wedge C = B$. Hence
$\langle A B C \rangle = A \vee B \vee A = A \vee B.$
Since $A \le B$, we have $A \vee B = B$, so
$\langle A B C \rangle = B.$
Therefore
$f(x_1, \ldots, x_n) = \langle A B C \rangle.$
Substituting back $A,B,C$ gives
$f(x_1, \ldots, x_n) = \langle f(x_1, x_2, 0, x_4, \ldots, x_n),\ f(x_1, x_2, x_3, x_4, \ldots, x_n),\ f(x_1, x_2, 1, x_4, \ldots, x_n) \rangle.$
This completes the proof. ∎