Exercise 22. [21] [21] Explain the chain for $S_3$ in Fig. 10, by noting that it incorporates the chain for $S_{2,3}$ in Fig. 9. Find a similar chain for $S_2(x_1, x_2, x_3, x_4, x_5)$.

Verified: yes
Solve time: 3m18s

Let $S_k(x_1,\dots,x_n)$ be the Boolean function that equals $1$ iff exactly $k$ of its arguments are $1$.

The figures in the text present chains that are not merely formulas, but networks in which intermediate nodes are reused to build larger symmetric functions from smaller ones. The key point of both constructions is that the chain for $S_k$ is obtained by extending chains for smaller symmetric functions on fewer variables without recomputing them.

1. Explaining the chain for $S_3(x_1,x_2,x_3,x_4)$

Figure 9 provides a chain for the family $S_{2,3}(x_1,x_2,x_3)$, meaning it simultaneously produces intermediate results that distinguish whether among three inputs there are:

exactly $2$ ones, or
exactly $3$ ones.

Equivalently, it computes enough structure to support the next step of refinement to a single value $S_3$ after adding one more variable.

The important structural feature is that the Fig. 9 chain produces intermediate signals that encode the “state” of the count of 1s among $(x_1,x_2,x_3)$, specifically separating the cases relevant to 2 and 3.

Now consider $S_3(x_1,x_2,x_3,x_4)$. By definition,

$$ S_3(x_1,x_2,x_3,x_4)=1 \quad\Longleftrightarrow\quad \text{exactly three of the four inputs are }1. $$

Split according to $x_4$:

If $x_4=0$, we need exactly three 1s among $(x_1,x_2,x_3)$, which is impossible.
If $x_4=1$, we need exactly two 1s among $(x_1,x_2,x_3)$, i.e. $S_2(x_1,x_2,x_3)$.

Thus the construction reduces to feeding the pair $(S_2(x_1,x_2,x_3), S_3(x_1,x_2,x_3))$ into a final gating step controlled by $x_4$.

The chain in Fig. 10 is obtained by taking the Fig. 9 chain and observing:

The Fig. 9 subchain already computes the required intermediate symmetric states for three variables (the $S_{2,3}$ information).
The Fig. 10 chain does not recompute these states, but reuses the corresponding nodes.
A final layer of gates combines these reused outputs with $x_4$ to select the correct value $S_3$.

Concretely, the final step of the chain implements the structural identity

$$ S_3(x_1,x_2,x_3,x_4)

x_4 \wedge S_2(x_1,x_2,x_3), $$

while the value $S_2(x_1,x_2,x_3)$ is already available as part of the Fig. 9 subchain. The “incorporation” mentioned in the exercise is exactly this reuse: Fig. 10 embeds the entire Fig. 9 network and adds only one additional decision layer controlled by $x_4$.

This is why the chain is drawn as an extension rather than a new construction.

2. Constructing a chain for $S_2(x_1,x_2,x_3,x_4,x_5)$

The Fig. 9 construction for four variables already produces the key intermediate symmetric outputs:

a chain for $S_1(x_1,x_2,x_3,x_4)$,
a chain for $S_2(x_1,x_2,x_3,x_4)$,

computed in parallel and reused in later stages.

To extend to five variables, again split on $x_5$:

If $x_5=0$, we need exactly two 1s among the first four variables: $S_2(x_1,x_2,x_3,x_4)$.
If $x_5=1$, we need exactly one 1 among the first four variables: $S_1(x_1,x_2,x_3,x_4)$.

Thus

$$ S_2(x_1,x_2,x_3,x_4,x_5)

(\bar x_5 \wedge S_2(x_1,x_2,x_3,x_4)) ;\vee; (x_5 \wedge S_1(x_1,x_2,x_3,x_4)). $$

Chain-level construction

The key structural requirement is that both $S_1(x_1,\dots,x_4)$ and $S_2(x_1,\dots,x_4)$ are already available nodes in the Fig. 9 chain, not recomputed.

The extended chain is therefore:

Take the entire Fig. 9 network computing the intermediate symmetric outputs on $(x_1,x_2,x_3,x_4)$.
Branch two wires:

one carrying $S_2(x_1,x_2,x_3,x_4)$,
one carrying $S_1(x_1,x_2,x_3,x_4)$.

Compute $\bar x_5$.
Form two conjunction nodes:

$$ a = \bar x_5 \wedge S_2(x_1,x_2,x_3,x_4), \quad b = x_5 \wedge S_1(x_1,x_2,x_3,x_4). $$ 5. Combine with one final OR node:

$$ S_2(x_1,x_2,x_3,x_4,x_5)=a \vee b. $$

Structural point

The essential chain property is that the computation for five variables is obtained by:

embedding the full four-variable chain,
reusing its outputs as fixed subcircuits,
adding only a constant number of new gates controlled by $x_5$.

No recomputation of symmetric functions is performed; the extension is purely an append operation on the chain, matching the style of Figures 9 and 10.

TAOCP 7.1.2 Exercise 22