TAOCP 7.1.4 Exercise 201
A projection function $x_j$ corresponds to the Boolean function that is $1$ exactly on those assignments where the $j$-th variable is $1$.
Section 7.1.4: Binary Decision Diagrams
Exercise 201. [22] [22] The projection functions xj each have a simple 3-node BDD, but their ZDD representations are more complicated. What’s a good way to implement these functions in a general-purpose ZDD toolkit?
7.1.4 BINARY DECISION DIAGRAMS 273
Verified: yes
Solve time: 1m57s
Solution
A projection function $x_j$ corresponds to the Boolean function that is $1$ exactly on those assignments where the $j$-th variable is $1$. In BDD form this yields a node labeled $j$ whose low successor is $\bot$ and whose high successor is $\top$, together with the sink nodes, producing the standard 3-node structure.
In a ZDD, the same function is interpreted as a family of sets over an ordered universe ${1,\dots,n}$. Under the usual encoding, a bit vector $(x_1,\dots,x_n)$ corresponds to the set ${i \mid x_i=1}$. The projection function $x_j$ therefore represents the family
$$ \mathcal{F}_j = { S \subseteq {1,\dots,n} \mid j \in S }. $$
Equivalently, every set in $\mathcal{F}_j$ has the form $S = {j} \cup T$ where $T \subseteq {j+1,\dots,n}$.
The structural difficulty in a ZDD arises from the zero-suppression rule: a node whose 1-edge leads to the 0-sink is eliminated, and its incoming edges are redirected to its 0-child. A naive attempt to mimic the BDD construction by writing a single node labeled $j$ with LO pointing to $\emptyset$ and HI pointing to a sub-ZDD for all subsets of the remaining variables does not remain stable under reduction unless the sub-ZDD is constructed carefully and reused canonically.
A clean implementation strategy avoids constructing the projection from scratch and instead expresses it as a uniform transformation of a canonical “universal tail” family. Let $U_{>j}$ denote the ZDD representing all subsets of ${j+1,\dots,n}$. This ZDD is obtained once from the empty constraints on variables greater than $j$ using the standard ZDD constructor.
Define an operation $\operatorname{insert}_j(F)$ that maps a family $F$ over ${j+1,\dots,n}$ to the family
$$ { {j} \cup S \mid S \in F }. $$
This operation is standard in ZDD manipulation systems and is typically implemented as a top-down recursive construction that, at variable $j$, forces inclusion and redirects both LO and HI structure of $F$ beneath the HI edge.
Applying this operation to the universal tail gives
$$ x_j ;=; \operatorname{insert}j(U{>j}). $$
Concretely, the resulting ZDD is constructed as follows. A node at level $j$ is created whose LO edge points to the 0-sink, since exclusion of $j$ yields the empty family. Its HI edge points to the root of $U_{>j}$, since inclusion of $j$ permits any subset of higher-index variables. All nodes of $U_{>j}$ remain unchanged below this HI edge.
Reduction does not collapse this structure further because the HI child is not the 0-sink and the LO and HI children differ, so neither zero-suppression nor merge rules apply. The resulting diagram is stable and canonical under the ordered reduction constraints.
Thus a general-purpose ZDD toolkit should implement projection functions not by hand-building a small graph, but by providing a primitive operation that constructs $\operatorname{insert}_j(F)$, and then compute $x_j$ by applying this operation to the universal family on variables greater than $j$.
This completes the construction and correctness argument. ∎