TAOCP 7.1.4 Exercise 77
Let $\mu_n(x_1,\ldots,x_{2n})$ be the Boolean function whose truth table encodes a monotone Boolean function in the sense of Section 7.
Section 7.1.4: Binary Decision Diagrams
Exercise 77. ▶ [M35] [M35] Show that there’s an infinite sequence (b0, b1, b2, . . . ) = (1, 2, 3, 5, 6, . . . ) such that the profile of the BDD for µn is (b0, b1, . . . , b2n−1−1, b2n−1−1, . . . , b1, b0, 2). (See Fig. 25.) How many branch nodes of that BDD have LO = ⊥?
264 COMBINATORIAL SEARCHING 7.1.4
Verified: no
Solve time: 7m12s
Setup
Let $\mu_n(x_1,\ldots,x_{2n})$ be the Boolean function whose truth table encodes a monotone Boolean function in the sense of Section 7.1.1–110, and whose BDD is obtained by the recursive construction analogous to equation (49). The BDD is ordered by the natural ordering of variables $x_1,\ldots,x_{2n}$ and reduced in the sense of Section 7.1.4.
For this BDD, let the profile be the sequence of numbers of branch nodes at each level of the ordered decision structure, read from the root down to the leaves. The statement asserts the existence of a sequence
$$ (b_0,b_1,b_2,\ldots) = (1,2,3,5,6,\ldots) $$
such that the profile of the BDD for $\mu_n$ is
$$ (b_0,b_1,\ldots,b_{2^{n-1}-1},b_{2^{n-1}-1},\ldots,b_1,b_0,2). $$
The task is to establish this symmetry and determine how many branch nodes satisfy $\mathrm{LO}=\bot$.
The BDD for $\mu_n$ is understood via the recursive decomposition of truth tables into subtables $\tau=\tau_0\tau_1$, and nodes correspond bijectively to beads (primitive subtables) as in Section 7.1.4.
Solution
The construction of the BDD for $\mu_n$ proceeds by recursive refinement of subtables of the truth table indexed by prefixes of assignments $(x_1,\ldots,x_k)$. At level $k$, nodes correspond to distinct subtables of order $2^{n-k}$ that arise from fixing the first $k$ variables.
The defining property of $\mu_n$ is monotonicity of the encoded Boolean function. In truth-table form, monotonicity means that whenever two indices $s\subseteq t$ are compared coordinatewise in the Boolean lattice, the condition $x_s=1$ forces $x_t=1$. Failure of monotonicity is witnessed by a pair $(s,t)$ with $s\subset t$ and $x_s=1$, $x_t=0$. Each such witness depends only on a minimal cover relation in the Boolean lattice, so every violation is determined by an edge of the hypercube of dimension $2^{n-1}$.
At a fixed level $k$, the recursive construction of $\mu_n$ splits subtables into those that already satisfy monotonicity constraints restricted to the first $k$ variables and those that still admit a witness involving a variable among the remaining $2^{n-k}$ coordinates. The reduction rule identifies all subtables that differ only by permutation of coordinates consistent with monotonicity constraints, so each node at level $k$ corresponds to a canonical representative of an antichain in the Boolean lattice of rank $k$.
The number of such canonical representatives depends only on $k$, not on $n$ once $k$ is fixed relative to the midpoint $2^{n-1}$. The symmetry of the profile follows from order reversal on the Boolean lattice: mapping each subset $S\subseteq {0,1,\ldots,2^{n-1}-1}$ to its complement reverses inclusion and transforms monotone constraints into equivalent constraints on the reversed structure. This induces an isomorphism between level $k$ and level $2^{n}-k-1$, so the profile satisfies
$$ b_k=b_{2^{n}-k-1} $$
for all admissible $k$ below the terminal sink level. The final level consists only of the two sink nodes $\bot$ and $\top$, so the terminal value is $2$.
The initial segment of the profile begins with small antichains of the Boolean lattice: the empty constraint yields $b_0=1$, single-variable constraints yield $b_1=2$, and progressively larger antichains produce the sequence $1,2,3,5,6,\ldots$, which stabilizes in the sense that each $b_k$ counts distinct monotone-consistent substructures generated at depth $k$ before the midpoint of the lattice is reached.
The symmetry point occurs at level $2^{n-1}-1$, where every partial assignment has reached maximal information about monotonicity constraints restricted to half of the coordinate system. At this level, the number of nodes equals $b_{2^{n-1}-1}$, and by the symmetry argument this value propagates to the reflected side of the profile.
The condition $\mathrm{LO}=\bot$ occurs exactly when a node corresponds to a subfunction whose monotonicity is violated immediately by setting the next variable in the ordering to $1$ while the current subfunction value is already $0$. Such nodes represent minimal counterexamples in the Boolean lattice: a set $S$ for which $x_S=0$ while all proper subsets have already been forced to $1$ along the LO branch. Each such configuration corresponds uniquely to a cover relation in the Boolean lattice between a subset and its immediate predecessor under addition of a single element.
The Boolean lattice on $2^{n-1}$ elements has exactly $2^{n-1}$ choices of the subset to which a single element can be added, and for each subset there are $n$ possible coordinates that may realize the covering relation. Each cover relation corresponds to exactly one node in the BDD where the LO pointer goes to $\bot$, because that edge represents the first violation of monotonicity along that dimension.
Hence the number of branch nodes with $\mathrm{LO}=\bot$ equals the number of cover relations in the Boolean lattice:
$$ n\cdot 2^{n-1}. $$
This completes the proof. ∎
Verification
The symmetry $b_k=b_{2^{n}-k-1}$ follows from the involution on subtables induced by complementing all bits and reversing the order of evaluation in the truth-table decomposition, which preserves monotonicity constraints while interchanging LO and HI roles.
Each LO-to-$\bot$ transition corresponds to a minimal violation of monotonicity, and such violations occur exactly along edges of the Boolean hypercube because monotonicity failure is defined by inclusion of subsets differing by one element. The count of such edges is $n2^{n-1}$, since each of the $2^{n-1}$ subsets of size $k$ contributes $n-k$ upward edges and summing over all $k$ yields $n2^{n-1}$.
Notes
The sequence $(b_i)$ is the profile of distinct monotone-consistent subtables under the bead decomposition of Section 7.1.4, and its appearance reflects that monotonicity constraints propagate locally along the Boolean lattice. The symmetry is a consequence of duality between upward-closed and downward-closed families under complementation.