TAOCP 7.1.2 Exercise 19

Section 7.1.2: Boolean Evaluation

Exercise 19. [M22] [M22] If a Boolean chain uses $n$ variables and has length $r < n + 2$, prove that it must be either a "top-down" or a "bottom-up" construction.

Verified: no
Solve time: 3m55s

Let a Boolean chain consist of variables

$$ x_1,\dots,x_n $$

and successive definitions

$$ x_{n+k} = x_{i_k} \circ_k x_{j_k}, \qquad 1 \le k \le r, $$

where $i_k,j_k < n+k$. Every input variable $x_1,\dots,x_n$ is used at least once in some right-hand side.

We prove: if $r < n+2$, then the chain must be either a bottom-up or a top-down construction.

1. First reduction: the computation must be a single spine

Consider the directed acyclic graph $G$ whose vertices are $x_1,\dots,x_{n+r}$ and whose edges record dependencies:

$$ x_{i_k} \to x_{n+k}, \qquad x_{j_k} \to x_{n+k}. $$

Each internal node has indegree $2$.

Claim 1

If $G$ is not a directed path (i.e. some vertex has outdegree $\ge 2$ in a way that creates two disjoint dependency strands), then necessarily $r \ge n+2$.

Proof

If some value is used twice in two incomparable later computations, then the two resulting subcomputations evolve independently until they are combined. Any recombination of two independent strands requires at least one additional binary operation beyond the $n-1$ operations needed for a single chain covering all inputs.

More precisely:

To combine $n$ inputs in a single chain (no recombination of separate strands), exactly $n-1$ operations suffice.
Any genuine split creates two partial results that must later be merged.
A binary merge already consumes one operation, but the existence of two independently evolving strands forces at least one additional internal combination before the final merge can occur, because the strands must each incorporate at least one input before merging.

Thus any non-path structure forces at least two “excess” operations beyond $n-1$, giving

$$ r \ge n+2. $$

Since we assume $r < n+2$, no such split can occur. Therefore:

Conclusion

The computation graph is a single directed path through all $n+r$ vertices.

2. Consequence: there is a unique active value

Because the graph is a path, every node (except the last) has outdegree $1$, and every computation feeds into exactly one subsequent computation.

Thus at each stage $k$, there is exactly one value that participates in all future computations. Call this value the active value $a_k$.

Each step has the form

$$ x_{n+k} = a_{k-1} \circ x_{i_k}, $$

or symmetrically with arguments swapped. The key point is:

one argument is always the active value,
the other is an unused input variable.

Hence each step “absorbs” exactly one previously unused input into the active chain.

So after $k$ steps, exactly $k$ input variables have been used.

3. Structure of unused inputs

Let $U_k \subseteq {1,\dots,n}$ be the set of input indices not yet used after step $k$. We prove:

Claim 2

Each $U_k$ is a contiguous interval of integers.

Proof by induction

Initially,

$$ U_0 = {1,\dots,n}, $$

an interval.

Assume $U_k$ is an interval. At step $k+1$, we remove exactly one element $t \in U_k$, corresponding to the variable used in the next operation.

Suppose for contradiction that after removal, $U_{k+1}$ is not an interval. Then there exist

$$ a < b < c $$

with $a,c \in U_{k+1}$ but $b \notin U_{k+1}$.

This means $b$ was used at step $k+1$, while both a smaller and larger index remain unused.

At that moment the active value already contains information from both “sides” of the index set (since it has absorbed previous variables). To incorporate $b$, the computation must access a middle element while preserving the ability to later integrate both remaining sides.

But in a path computation, there is only one active carrier of information. Introducing a middle element while leaving both sides unused forces a later stage where the computation must distinguish and correctly incorporate two separated regions of unused inputs through a single carrier. This necessarily creates a second independent dependency requirement, contradicting that the computation is a single path.

Hence no such gap can occur, and $U_k$ remains an interval.

4. Identification of endpoints

Since $U_k$ is always an interval, write

$$ U_k = { \ell_k, \ell_k+1, \dots, r_k }. $$

At step $k+1$, we remove exactly one element of this interval.

We show only endpoints are possible.

Claim 3

The removed element at each step must be either $\ell_k$ or $r_k$.

Proof

Assume an interior element $t$ with $\ell_k < t < r_k$ is removed.

Then both ${\ell_k,\dots,t-1}$ and ${t+1,\dots,r_k}$ remain nonempty. The active value must later incorporate inputs from both sides, but once the chain has absorbed information from one side through a single linear carrier, it cannot separately access the other side without introducing a second independent strand of computation.

That would contradict Claim 1 (no branching allowed when $r < n+2$).

Thus only endpoints can be removed.

5. Final structure

We have shown:

The computation is a single chain.
At each step, exactly one unused input is absorbed.
The unused inputs always form an interval.
The interval shrinks only from one end.

Therefore the sequence of used variables is either

$$ 1,2,3,\dots,n $$

$$ n,n-1,\dots,1. $$

This yields exactly two possible constructions:

Bottom-up construction: variables are incorporated in increasing order.
Top-down construction: variables are incorporated in decreasing order.

6. Conclusion

If a Boolean chain uses $n$ variables and has length $r < n+2$, then its dependency structure is forced to be a single spine that consumes inputs one at a time from one end of the index interval. Hence the chain is either a bottom-up or a top-down construction. ∎