TAOCP 7.1.4 Exercise 163

Exercise 163. [23] [23] Prove formulas (112) and (113) for the BDD sizes of read-once functions.

Verified: no
Solve time: 4m47s

Solution

A read-once Boolean function $f(x_1,\ldots,x_n)$ is represented by a formula tree in which each variable occurs exactly once. Fix any ordering of variables consistent with that tree. Every subfunction obtained by fixing the first $k$ variables is again a read-once function in the remaining variables, hence depends on a disjoint subset of the original variables.

Let $T_k$ denote the set of subfunctions obtained by fixing values of $x_1,\ldots,x_k$. Because the formula is read-once, the remaining variable sets in distinct nodes at the same depth are disjoint, hence distinct. No two different partial assignments to $x_1,\ldots,x_k$ yield identical residual functions, since such an equality would imply reuse of a variable in the original formula, contradicting the read-once condition.

Therefore, at level $k$ of the Shannon expansion tree there are exactly $2^k$ distinct subfunctions. Each such subfunction corresponds to a distinct node in the unreduced binary decision tree associated with $f$.

The unreduced decision tree has exactly one node for each partial assignment of the first $k$ variables for $0 \le k \le n$, hence

$$ \sum_{k=0}^{n} 2^k = 2^{n+1}-1 $$

nodes in total if leaves are not identified.

Reduction to a BDD merges identical sink subfunctions only. The two constant functions $\bot$ and $\top$ occur as leaves and correspond to the only duplicated terminal subfunctions. In a read-once function, no two nonterminal subfunctions are identical, so no further merging occurs.

Thus the reduced ordered BDD contains all internal nodes of the full decision tree plus the two sinks. The number of internal nodes is

$$ \sum_{k=0}^{n-1} 2^k = 2^n - 1, $$

and adding the two sinks yields

$$ B(f) = (2^n - 1) + 2 = 2^n + 1. $$

This gives formula (112):

$$ B(f) = 2^n + 1. $$

If $f$ is constant, the tree collapses immediately and the BDD consists only of the two sinks, giving $B(f)=2$, which is consistent with the same expression after removing the internal levels.

For formula (113), consider the decomposition by variable levels. At depth $k$, there are $2^k$ nodes corresponding to subfunctions on $n-k$ variables, each contributing exactly one distinct BDD node because no sharing occurs among distinct subfunctions in a read-once structure. Hence the total size can be expressed as the level sum

$$ B(f) = 2 + \sum_{k=0}^{n-1} 2^k, $$

where the initial term accounts for the two sinks and the summation accounts for all internal nodes generated by successive Shannon expansions along the read-once decomposition. Evaluating the geometric sum yields

$$ 2 + (2^n - 1) = 2^n + 1. $$

Both expressions coincide, establishing formulas (112) and (113).

This completes the proof. ∎