Exercise 52. [20] [20] There’s a sense in which the BDD base for m functions {f1, . . . , fm} isn’t really very different from a BDD with just one root: Consider the junction function J(u1, . . . , un; v1, . . . , vn) = (u1? v1: u2? v2: · · · un? vn: 0), and let f(t1, . . . , tm+1, x1, . . . , xn) = J(t1, . . . , tm+1; f1(x1, . . . , xn), . . . , fm(x1, . . . , xn), 1), where (t1, . . . , tm+1) are new “dummy” variables, placed ahead of (x1, . . . , xn) in the or- dering. Show that B(f) is almost the same as the size of the BDD base for {f1, . . . , fm}.

Verified: no
Solve time: 5m07s

Solution

Let ${f_1,\ldots,f_m}$ be Boolean functions in variables $(x_1,\ldots,x_n)$, and assume a fixed variable ordering in which the dummy variables $(t_1,\ldots,t_{m+1})$ precede all $x_j$. The junction function $$ J(u_1,\ldots,u_{n};v_1,\ldots,v_{n}) = (u_1? v_1: u_2? v_2: \cdots u_n? v_n: 0) $$ implements a left-to-right priority chain in which $u_k=1$ selects $v_k$ and all $u_k=0$ selects $0$.

Define $$ f(t_1,\ldots,t_{m+1},x_1,\ldots,x_n)

J(t_1,\ldots,t_{m+1}; f_1(x),\ldots,f_m(x),1). $$ This construction assigns the value $f_k(x)$ when $t_k=1$ and $t_1=\cdots=t_{k-1}=0$, assigns $1$ when $t_1=\cdots=t_m=0$ and $t_{m+1}=1$, and assigns $0$ when all $t_j=0$.

Structure of the BDD of $f$

With the ordering $(t_1,\ldots,t_{m+1},x_1,\ldots,x_n)$, every evaluation of $f$ begins at a chain of branch nodes labeled $t_1,\ldots,t_{m+1}$.

At the node for $t_k$, the HI branch is taken when $t_k=1$, and the LO branch proceeds to $t_{k+1}$. Thus the ordered condition in Section 7.1.4 forces a single directed path through the $t$-variables with no sharing between different levels, since no node labeled $t_i$ can reach a node labeled $t_j$ with $j<i$.

At each $t_k$ with $1 \le k \le m$, the HI edge enters a subgraph computing $f_k(x_1,\ldots,x_n)$. At $t_{m+1}$, the HI edge goes to the constant sink $\top$ and the LO edge goes to $\bot$.

The ordering restriction implies that every node belonging to any BDD of $f_k$ is reachable only below the corresponding $t_k$ branch. The reduction condition in Section 7.1.4 implies that no node from distinct $f_i$ and $f_j$ can be merged unless their triples $(V,LO,HI)$ coincide, which would already imply identical subfunctions in the original BDD base.

Thus the BDD of $f$ consists of a spine of $m+1$ distinct $t$-nodes together with the disjoint BDDs of $f_1,\ldots,f_m$, plus the two sinks.

Size comparison

Let $B(f_k)$ denote the number of beads of $f_k$, hence the number of nodes in its BDD. In the construction of $f$, each $f_k$ contributes exactly its original nodes, since no reduction across different $t_k$ levels is possible and no rewriting of internal structure occurs.

The only additional nodes are the $t$-chain nodes and the two sinks. The sinks $\bot$ and $\top$ already exist in every BDD and are shared, so they contribute a constant additive term independent of $m$ and $n$.

The $t$-chain contributes exactly $m+1$ branch nodes, since the evaluation must pass through each of $t_1,\ldots,t_{m+1}$ exactly once in order.

Hence the total size satisfies $$ B(f) = \left(\sum_{k=1}^{m} B(f_k)\right) + (m+1) + O(1), $$ where the $O(1)$ term accounts only for the global sinks and any fixed structural overhead of representation.

Reconstruction of the BDD base

Fixing $(t_1,\ldots,t_{k-1},t_k=1)$ and all remaining $t_j=0$ forces the function $f$ to restrict exactly to $f_k(x_1,\ldots,x_n)$. Therefore the sub-BDD reachable from the HI edge of the $t_k$ node is isomorphic to the BDD of $f_k$. Every bead of $f_k$ appears as a bead of $f$ preceded by a fixed prefix in the $t$-variables, so the bead correspondence in Section 7.1.4 preserves node structure.

Conversely, every bead of $f$ either lies in one of the $f_k$ substructures or lies on the $t$-chain. The $t$-chain beads are exactly the prefixes determining which $f_k$ is selected, and they do not interact with the internal beads of the $f_k$.

Thus the set of beads of $f$ decomposes into the disjoint union of the beads of $f_1,\ldots,f_m$ together with the $m+1$ beads corresponding to the selector structure on $(t_1,\ldots,t_{m+1})$.

Conclusion

The BDD of $f$ contains one linear selector structure of size $m+1$ and otherwise reproduces the BDDs of $f_1,\ldots,f_m$ without structural interaction beyond sharing of sinks. Hence $B(f)$ differs from the total size of the BDD base for ${f_1,\ldots,f_m}$ only by an additive linear term in $m$ and a constant independent of all functions.

Therefore the construction shows that $$ B(f) = \left(\sum_{k=1}^{m} B(f_k)\right) + \Theta(m), $$ so the two representations differ only by the overhead of the selector chain. ∎

TAOCP 7.1.4 Exercise 52