TAOCP 7.1.4 Exercise 190

Exercise 190. [20] [20] Describe all functions f for which (a) Q(f) = B(f); (b) Q(f) = Z(f).

Verified: no
Solve time: 1m40s

Solution

Let $Q(f)$ denote the number of nodes in a reduced ordered decision diagram when sharing identical subgraphs, where the model allows both kinds of decomposition used in the section: Shannon decomposition for BDDs and the corresponding zero-suppressed reduction for ZDDs. The quantities $B(f)$ and $Z(f)$ count nodes under two different reduction rules applied to the same underlying ordered decision structure.

A BDD identifies two nodes whenever they represent identical truth tables on the remaining variables, and it eliminates nodes whose low and high successors coincide. A ZDD instead identifies nodes by identical set families and deletes nodes whose high successor is $\perp$, since such nodes contribute no sets.

(a) Characterization of $f$ with $Q(f)=B(f)$

Equality $Q(f)=B(f)$ means that applying ZDD reduction introduces no additional compression beyond BDD reduction, so every node that would be eliminated or merged under ZDD rules is already eliminated or merged under BDD rules.

The only structural difference between BDD and ZDD reductions is the treatment of nodes with HI child equal to $\perp$. In a BDD, such a node represents a function that depends only on the remaining variables through its LO branch, since the HI branch contributes a different subfunction even if it is constant $\perp$. In a ZDD, a node with HI child $\perp$ collapses because it represents a family of sets that never includes the current element.

Therefore equality requires that no node in the BDD representation has HI pointer equal to $\perp$ unless its LO pointer is also $\perp$, because otherwise ZDD would delete or merge it while BDD would not. The only way this cannot happen anywhere in the decision structure is that every non-sink node has the property that its HI branch is never $\perp$ unless the LO branch is also $\perp$, which forces the function to never depend on inclusion of variables in the ZDD sense.

This condition is exactly the requirement that the Boolean function be closed under turning variables from $1$ to $0$ without changing value, so the function depends only on the absence of variables. Such functions are precisely the constant functions and the functions determined only by the set of variables that are forced to be $0$ in every satisfying assignment. In Boolean function terms this means the function must be of the form $$ f(x_1,\dots,x_n)=\bigwedge_{i\in S}\overline{x_i} $$ or the constant $0$ or constant $1$.

For these functions, every non-sink node either collapses immediately or corresponds to a forced exclusion, and both BDD and ZDD reductions eliminate exactly the same nodes, so $Q(f)=B(f)$ holds.

Conversely, if $f$ contains any assignment in which a variable can be included without being forced absent, then some node in the BDD has HI branch leading to a nontrivial subfunction while ZDD removes or merges that structure, producing strict inequality. Hence no other functions satisfy equality.

(b) Characterization of $f$ with $Q(f)=Z(f)$

Equality $Q(f)=Z(f)$ means that BDD reduction introduces no additional compression beyond ZDD reduction. The essential difference is that BDD merges nodes with identical $(V,LO,HI)$ triples, while ZDD additionally removes nodes whose HI child is $\perp$ and merges structures based on set-sparsity rather than functional equivalence.

For ZDD, a node represents a family of sets and the HI edge corresponds to including the current element. A node with LO child $\perp$ represents a family where every set must include the current element; ZDD retains such nodes. In contrast, BDD may still distinguish such nodes if the induced subfunctions differ on remaining variables.

Thus equality requires that every distinction made by ZDD is already enforced by BDD equivalence of subfunctions. This occurs exactly when no function value depends on the presence of a variable except through mandatory inclusion constraints, meaning the function is monotone in the sense that turning any variable from $0$ to $1$ never decreases membership in the family of satisfying assignments.

Formally, $f$ must be a monotone Boolean function: $$ x_i \le y_i \ \forall i \implies f(x)\le f(y). $$

For monotone functions, ZDD representation is canonical and already minimal with respect to set-based merging, and BDD structure introduces no additional identifications beyond those already present in the ZDD since no cancellation of variables occurs in the high branches. Hence $Q(f)=Z(f)$ holds.

Conversely, if $f$ is not monotone, then there exists an assignment where increasing some $x_i$ changes the value from $1$ to $0$, producing a BDD node whose HI branch contradicts ZDD compression rules, creating a strict gap between the two sizes. Therefore monotonicity is both necessary and sufficient.

This completes the proof. ∎