TAOCP 7.1.2 Exercise 75
The function $S_{0,n}(x_1,\ldots,x_n)$ is the symmetric Boolean function that is true exactly when none of the variables are 1.
Section 7.1.2: Boolean Evaluation
Exercise 75. [20] What happens when the text's decomposition procedure is applied to the "all-equal" function $S_{0,n}(x_1, \ldots, x_n)$?
Verified: yes
Solve time: 1m10s
Solution
The function $S_{0,n}(x_1,\ldots,x_n)$ is the symmetric Boolean function that is true exactly when none of the variables are 1. In the notation of symmetric functions used in Section 7.1.2, this is the weight-0 case, so
$$ S_{0,n}(x_1,\ldots,x_n)=1 \iff x_1=x_2=\cdots=x_n=0. $$
Hence
$$ S_{0,n}(x_1,\ldots,x_n)=\bar{x}_1 \wedge \bar{x}_2 \wedge \cdots \wedge \bar{x}_n. $$
In a normal Boolean chain, complementation of inputs is absorbed into the normalization process described by equation (10), so each variable $x_i$ may be treated as already available in complemented form without additional cost. Under this convention the function becomes a pure conjunction
$$ S_{0,n} = x_1 \wedge x_2 \wedge \cdots \wedge x_n. $$
The decomposition procedure described for symmetric functions constructs higher-level variables by repeatedly combining disjoint groups of inputs using binary operators. For a conjunction, any binary combination that preserves correctness must evaluate to true only when both arguments are true. Among the normal operators listed in the text, only $\wedge$ has this property without introducing additional constraints.
Let $t_k$ denote the intermediate result of combining $k$ variables by conjunction, so $t_1=x_1$ and
$$ t_{k+1}=t_k \wedge x_{k+1}. $$
Each step introduces exactly one binary operator, so the construction yields a chain of length $n-1$.
The decomposition procedure applied to symmetric functions attempts to combine previously computed subfunctions in a way that allows reuse of intermediate results, as occurs for $S_2$ in equation (7). For $S_{0,n}$, every partial evaluation depends only on the conjunction of all variables already included, and no nontrivial partition produces distinct interacting subfunctions. If a partition $A \cup B = {1,\ldots,n}$ is used, then
$$ S_{0,n}(x_1,\ldots,x_n)=S_{0,|A|}(x_A)\wedge S_{0,|B|}(x_B), $$
and each factor reduces again to a pure conjunction. No alternative operator among the five normal nontrivial operators produces a function equivalent to $S_{0,n}$ on all inputs without introducing additional literals or intermediate recombination steps, so no saving over sequential conjunction is obtained.
A lower bound follows from the requirement that each input variable must be incorporated into the computation. In any Boolean chain computing $S_{0,n}$, the final output depends on all $n$ variables, and each binary operation introduces at most one new variable into the computed expression. Starting from a single variable, reaching dependence on $n$ variables requires at least $n-1$ binary operations. This matches the constructed chain.
Therefore the decomposition procedure produces only the trivial linear chain of nested conjunctions, with no reuse of intermediate subfunctions beyond the standard prefix accumulation, and the resulting optimal complexity is
$$ C(S_{0,n})=n-1. $$
This completes the proof. ∎