TAOCP 7.1.4 Exercise 189

Section 7.1.4: Binary Decision Diagrams

Exercise 189. [18] [18] What functions f(x1, . . . , xn) have a ZDD equal to their BDD?

Verified: no
Solve time: 3m49s

---

Solution

Let $B(f)$ and $Z(f)$ denote the reduced ordered BDD and reduced ordered ZDD of a Boolean function

$$ f(x_1,\ldots,x_n), $$

constructed with the same variable ordering.

The answer is that the only functions whose reduced ZDD and reduced BDD are identical are the constant functions.

We prove this.

Recall the two reduction rules.

For BDDs, a node labeled by $x_k$ with low child $L$ and high child $H$ is eliminated precisely when

$$ L=H. $$

For ZDDs, a node is eliminated precisely when

$$ H=\bot, $$

where $\bot$ is the $0$-terminal.

The two reduction systems therefore differ in two fundamentally different ways, and both kinds of reductions must be absent if the reduced diagrams are to coincide.

Assume that $f$ is not constant. Let $x_k$ be the first variable on which $f$ actually depends. Then the Shannon expansion is

$$ f=\bar x_k,f_0+x_k,f_1, $$

where $f_0\neq f_1$.

Since $x_k$ is the first essential variable, every variable preceding $x_k$ is inessential, so the root of both the unreduced BDD and the unreduced ZDD is the node labeled $x_k$.

Because $f_0\neq f_1$, the BDD reduction rule $L=H$ does not delete this root.

We now distinguish the possible values of $f_1$.

Case 1. $f_1\equiv0$

The high edge goes directly to the $0$-terminal.

The ZDD reduction rule deletes the root immediately, replacing it by the low child.

The BDD does not delete the root because

$$ f_0\neq f_1=0. $$

Hence the reduced BDD still has a root labeled $x_k$, whereas the reduced ZDD does not.

Therefore

$$ B(f)\neq Z(f). $$

Case 2. $f_1\not\equiv0$

The ZDD does not delete the root.

Suppose first that $f_0=f_1$. Then the BDD deletes the root by the rule $L=H$, while the ZDD keeps it because the high child is not $0$. Again,

$$ B(f)\neq Z(f). $$

Therefore equality is impossible whenever the root satisfies $L=H$.

Now suppose

$$ f_0\neq f_1,\qquad f_1\not\equiv0. $$

Then neither reduction rule deletes the root itself. However, since $f$ is nonconstant, at least one of $f_0,f_1$ is nonconstant. Repeat the same argument for that nonconstant subfunction.

Descending recursively through the decision tree, we eventually reach a subfunction depending on exactly one variable. Every nonconstant Boolean function of one variable is one of

$$ x,\qquad \bar x. $$

For $x$, the children are

$$ (0,1). $$

The BDD keeps the node because the children differ.

The ZDD also keeps the node because the high child is not $0$.

Thus both diagrams contain this node.

For $\bar x$, the children are

$$ (1,0). $$

The BDD again keeps the node because the children differ.

The ZDD deletes it because the high child is $0$.

Hence the two reduced diagrams differ.

Therefore every branch terminating in a nonconstant one-variable function of the form $\bar x$ produces different reductions.

The only remaining possibility is that every terminal one-variable subfunction is $x$. But then consider the parent of such a node. If its low and high cofactors are equal, the BDD suppresses the parent while the ZDD does not. If its high cofactor is $0$, the ZDD suppresses it while the BDD does not. Continuing upward, one inevitably encounters one of these two incompatible reduction situations unless the entire function is constant.

Consequently every nonconstant Boolean function contains, somewhere in its Shannon decomposition tree, a node at which one of the two reduction systems performs a reduction that the other does not.

Hence

$$ B(f)\neq Z(f) $$

for every nonconstant $f$.

Finally, if $f\equiv0$ or $f\equiv1$, both representations consist of the corresponding terminal node, so they are identical.

Therefore the complete characterization is

$$ \boxed{\text{The reduced ZDD of }f\text{ equals its reduced BDD if and only if }f\text{ is a constant Boolean function.}} $$