TAOCP 7.1.1 Exercise 21
Let variables range over ${0,1}^n$.
Exercise 21. [M20] [M20] Prove that a nonconstant Boolean function is monotone if and only if it can be expressed entirely in terms of the operations $\wedge$ and $\vee$.
Verified: yes
Solve time: 1m33s
Solution
Let variables range over ${0,1}^n$. For vectors $x=(x_1,\dots,x_n)$ and $y=(y_1,\dots,y_n)$ write $x \le y$ when $x_i \le y_i$ for all $i$. A Boolean function $f$ is monotone when $x \le y$ implies $f(x) \le f(y)$.
Assume first that $f$ is expressed entirely in terms of $\wedge$ and $\vee$. Each of the basic operations $\wedge$ and $\vee$ is monotone in each argument: if $a \le a'$ and $b \le b'$, then $a \wedge b \le a' \wedge b'$ and $a \vee b \le a' \vee b'$, since the truth tables of $\wedge$ and $\vee$ preserve order under coordinatewise increase. Any expression built from variables using only $\wedge$ and $\vee$ is obtained by repeated composition of these monotone operations. Induction on the structure of the expression shows that replacing any variable tuple $x$ by a larger tuple $y \ge x$ cannot decrease the value of the expression, hence $f(x) \le f(y)$. This proves monotonicity.
Assume conversely that $f$ is monotone and not constant. Let $A$ be the set of all vectors $a \in {0,1}^n$ such that $f(a)=1$ and no $b < a$ satisfies $f(b)=1$. Such $a$ are minimal true points under the partial order. Since $f$ is not identically $0$, at least one such $a$ exists. Since $f$ takes values in ${0,1}$, every $x$ with $f(x)=1$ has a chain descending under $\le$ that reaches a minimal element of $A$.
For each $a \in A$, define the term
$$ T_a ;=; \bigwedge_{i: a_i=1} x_i. $$
This term evaluates to $1$ exactly on those $x$ satisfying $a \le x$, since all coordinates where $a_i=1$ must also be $1$ in $x$, and no negations occur.
Define
$$ g(x) ;=; \bigvee_{a \in A} T_a(x). $$
If $f(x)=1$, then some $a \in A$ satisfies $a \le x$, since repeated lowering of coordinates where possible preserves the value $1$ by monotonicity and eventually reaches a minimal true point. For this $a$, $T_a(x)=1$, hence $g(x)=1$.
If $g(x)=1$, then $T_a(x)=1$ for some $a \in A$, so $a \le x$. Monotonicity of $f$ gives $f(x) \ge f(a)=1$, hence $f(x)=1$.
Thus $f(x)=g(x)$ for all $x$. The expression $g$ uses only $\wedge$ within each $T_a$ and $\vee$ across terms, so it is built entirely from $\wedge$ and $\vee$.
This completes the proof. ∎