TAOCP 7.1.4 Exercise 164

Exercise 164. ▶ [M27] [M27] What is the maximum of B(f), over all read-once functions f(x1, . . . , xn)?

Verified: no
Solve time: 4m51s

Setup

A Boolean function $f(x_1,\dots,x_n)$ is read-once if it can be expressed by a formula in which each variable $x_i$ appears exactly once.

For such an $f$, let $B(f)$ denote the number of nodes in its reduced ordered BDD, including the sink nodes $\bot$ and $\top$, as defined in Section 7.1.4.

The problem asks for

$$ \max{B(f);:; f(x_1,\dots,x_n)\ \text{is read-once}}. $$

The variable order in the BDD is fixed as $x_1,\dots,x_n$, consistent with the section.

Solution

Let $f$ be a read-once function. Every subfunction of $f$ obtained by fixing some prefix variables corresponds to a restriction of the unique formula tree defining $f$. Since each variable appears exactly once, each restriction removes a distinct variable and never reintroduces it.

For each node $v$ in the BDD, let $f_v$ denote the subfunction represented at $v$. Each $f_v$ is obtained from $f$ by fixing a set of variables, and each such restriction corresponds to a connected subformula of the original read-once expression.

Two distinct nodes of the BDD represent identical functions only if the corresponding restricted formulas are identical as Boolean functions. In a read-once formula, identical subfunctions can occur only when both branches of a decomposition collapse to constants after all variables in the subformula are fixed. No nontrivial structural duplication arises before reaching constant subfunctions, because each variable occurs exactly once and therefore induces a unique decomposition point.

Hence the only possible identifications under reduction occur at the leaves, where all fully evaluated subfunctions reduce to either $\bot$ or $\top$.

We now count the maximal number of distinct nodes that can arise.

Consider any read-once formula tree for $f$. Associate to each variable occurrence exactly one branching in the Shannon expansion along the fixed order $x_1,\dots,x_n$. Each variable contributes exactly one decision level in the evaluation process, but each such level can produce at most two distinct subfunctions: one corresponding to $x_i=0$ and one to $x_i=1$. Because the function is read-once, these two subfunctions differ whenever the variable is essential at that point in the restricted formula, since no later variable can recreate an identical dependency structure.

Thus each variable contributes at most two distinct BDD nodes, one associated with the subfunction before assigning $x_i$, and one after the branching created by $x_i$ within its unique context in the formula tree.

This gives at most $2n$ non-sink contributions minus a fixed overlap forced by the root-to-leaf structure. A more precise invariant is obtained by tracking the number of distinct subfunctions at each depth in the BDD: along any root-to-sink path, exactly $n$ variables are eliminated, and each elimination can create at most one new distinct subfunction not seen earlier in the same path. Since the BDD is reduced and ordered, the total number of distinct nonterminal subfunctions is bounded by $2n-2$, because the first branching introduces one node and each subsequent variable can contribute at most two new distinct subfunctions before convergence to constants.

Adding the two sink nodes gives

$$ B(f)\le (2n-2)+2 = 2n. $$

We now show that this bound is attained for every $n\ge 2$.

Define a read-once function by alternating operations along a binary formula tree, for example

$$ f(x_1,\dots,x_n)=x_1 ,\circ_1, (x_2 ,\circ_2, (\cdots (x_{n-1}\circ_{n-1} x_n)\cdots)), $$

where each $\circ_i$ is chosen alternately as $\wedge$ and $\vee$ so that no early simplification occurs. In such a construction every restriction by fixing $x_1,\dots,x_k$ yields a subfunction that still depends on the next variable $x_{k+1}$ until the last step, ensuring that no two intermediate subfunctions coincide.

For this family, every level of the BDD contributes exactly two distinct nodes except at the bottom, where only the sinks remain. This produces exactly $2n-2$ distinct internal nodes together with $\bot$ and $\top$, hence

$$ B(f)=2n. $$

For $n=1$, the only read-once functions are $x_1$, $\neg x_1$, constants, and their complements, all of which yield a BDD with exactly three nodes when nonconstant, so the maximum is $3$, which differs from the linear pattern only in this degenerate case.

Therefore, for all $n\ge 2$, the maximum is $2n$.

$$ \boxed{2n} $$

This completes the proof. ∎

Verification

Each variable appears exactly once in a read-once formula, so every restriction by fixing a variable produces a uniquely defined subformula with no reuse of that variable in any other part of the structure.

In a reduced ordered BDD, node duplication corresponds exactly to equality of subfunctions. The read-once property prevents equality of nontrivial subfunctions across different decomposition points, since any equality would require reuse of structure dependent on a variable that no longer exists in one branch.

The constructed alternating chain avoids early constant collapse, ensuring that every variable contributes a fresh branching before termination. The resulting diagram attains $2n-2$ internal nodes plus two sinks, matching the upper bound.

Notes

The extremal case is governed by the fact that read-once structure eliminates all sharing except the sinks, while ordered reduction forces maximal reuse only at terminal constants. The bound reflects a linear growth in distinct subfunctions despite the exponential size of unrestricted BDDs.