TAOCP 7.1.4 Exercise 199

Exercise 199. [21] [21] Similarly, implement (a) OR(f, g), (b) XOR(f, g), (c) BUTNOT(f, g).

Verified: yes
Solve time: 2m12s

Solution

A ZDD represents a family of finite sets over an ordered universe of items $x_1 < x_2 < \cdots$. Each nonterminal node is written $(k, f_0, f_1)$, where $k$ is the index of the current item, $f_0$ is the ZDD obtained when $x_k$ is excluded, and $f_1$ is the ZDD obtained when $x_k$ is included. The terminal nodes are $0$ (empty family) and $1$ (family containing only the empty set). Reduction enforces that no node has $f_1 = 0$ and that identical triples are shared.

Let $\operatorname{apply}_\circ(f,g)$ denote the ZDD obtained by applying a binary operation $\circ$ pointwise to families, using the standard recursive decomposition by the top variable of $f$ and $g$.

(a) OR$(f,g)$

OR corresponds to union of families: a set is in $f \lor g$ if and only if it is in $f$ or in $g$.

If $f=0$, then $f \lor g = g$, since $0$ represents the empty family. If $g=0$, then $f \lor g = f$. If $f=1$ and $g=1$, then $f \lor g = 1$.

Let the roots of $f$ and $g$ be labeled by variables $i$ and $j$ respectively.

If $i=j=k$, both ZDDs branch on the same item. A set belongs to $f \lor g$ with exclusion of $x_k$ exactly when it belongs to $f_0 \lor g_0$, and similarly with inclusion of $x_k$ exactly when it belongs to $f_1 \lor g_1$. Therefore the result has root $k$ with children

$$ h_0 = \mathrm{OR}(f_0,g_0), \qquad h_1 = \mathrm{OR}(f_1,g_1). $$

If $i<j$, the decomposition of $f$ occurs first in the variable order. A set in $f \lor g$ either comes from a set in $f$ or from a set in $g$. For the branch where $x_i$ is excluded, all contributions from $f$ are in $f_0$ while $g$ is unaffected at level $i$, hence $f_0 \lor g$. For inclusion of $x_i$, the contribution is $f_1 \lor g$. Thus the node is

$$ (i, \mathrm{OR}(f_0,g), \mathrm{OR}(f_1,g)). $$

If $j<i$, the symmetric argument yields

$$ (j, \mathrm{OR}(f,g_0), \mathrm{OR}(f,g_1)). $$

(b) XOR$(f,g)$

XOR corresponds to symmetric difference: a set is in $f \oplus g$ exactly when it is in exactly one of $f$ or $g$.

Base cases satisfy $f \oplus 0 = f$ and $f \oplus f = 0$.

If both roots are at $k$, a set excludes $x_k$ in the result exactly when it belongs to exactly one of $f_0$ and $g_0$, and similarly for inclusion. Hence the node is

$$ (k, \mathrm{XOR}(f_0,g_0), \mathrm{XOR}(f_1,g_1)). $$

If $i<j$, the variable $x_i$ is resolved in $f$ before it appears in $g$. For exclusion of $x_i$, the resulting family is $f_0 \oplus g$ since $g$ is unchanged at this level; for inclusion it is $f_1 \oplus g$. Thus

$$ (i, \mathrm{XOR}(f_0,g), \mathrm{XOR}(f_1,g)). $$

If $j<i$, symmetry gives

$$ (j, \mathrm{XOR}(f,g_0), \mathrm{XOR}(f,g_1)). $$

(c) BUTNOT$(f,g)$

BUTNOT is set difference: a set belongs to $f \setminus g$ exactly when it belongs to $f$ and does not belong to $g$.

If $f=0$, the result is $0$. If $g=0$, the result is $f$. If $f=g$, the result is $0$.

If both roots are at $k$, exclusion of $x_k$ yields $f_0 \setminus g_0$, since membership in $g$ under exclusion is determined by $g_0$. Inclusion yields $f_1 \setminus g_1$. Thus

$$ (k, \mathrm{BUTNOT}(f_0,g_0), \mathrm{BUTNOT}(f_1,g_1)). $$

If $i<j$, the variable $x_i$ appears only in $f$ at this level. A set belongs to $f \setminus g$ with $x_i=0$ exactly when it belongs to $f_0$ and is not in $g$, and similarly for $x_i=1$. Therefore

$$ (i, \mathrm{BUTNOT}(f_0,g), \mathrm{BUTNOT}(f_1,g)). $$

If $j<i$, the decomposition of $g$ must be respected because membership in $g$ depends on whether $x_j$ is absent or present. A set is excluded from the result if it lies in $g_0$ when $x_j=0$ or in $g_1$ when $x_j=1$. Thus both branches must propagate through $g$:

$$ (j, \mathrm{BUTNOT}(f,g_0), \mathrm{BUTNOT}(f,g_1)). $$

These recursive definitions preserve the ZDD ordering, since each recursive call strictly increases the index of the top variable under comparison, and reduction rules ensure canonicity of the resulting structure.

This completes the solution. ∎