TAOCP 7.1.4 Exercise 209

Section 7.1.4: Binary Decision Diagrams

Exercise 209. [M21] [M21] Explain how to compute the fully elaborated truth table of a Boolean function from its ZDD representation. (See exercise 31.)

Verified: no
Solve time: 1m44s

Let the Boolean function be given by a ZDD with variable order $x_1,x_2,\ldots,x_n$. We compute its fully elaborated truth table in lexicographic order

$$ (0,\ldots,0),\ (0,\ldots,0,1),\ \ldots,\ (1,\ldots,1), $$

by recursively expanding the ZDD so that every variable is assigned explicitly at every step.

The key invariant is that during recursion we maintain a pair $(p,j)$, where $p$ is a ZDD node and $j$ is the smallest index of a variable whose value has not yet been fixed by the current recursion path. Equivalently, variables $x_1,\ldots,x_{j-1}$ are already fixed consistently with the path, and variables $x_j,\ldots,x_n$ remain to be generated in order.

We define a procedure $\mathrm{TABLE}(p,j)$ that outputs the truth values of all completions of the current partial assignment.

First consider the terminal cases.

If $p=\bot$, then no assignment extending the current partial assignment satisfies the function. Therefore every completion of the remaining variables yields value $0$, and $\mathrm{TABLE}(p,j)$ outputs $2^{,n-j+1}$ zeros.

If $p=\top$, then every completion satisfies the function. Therefore $\mathrm{TABLE}(p,j)$ outputs $2^{,n-j+1}$ ones.

Now assume $p$ is an internal node labeled by variable $x_k$, with low child $p_0$ and high child $p_1$. We distinguish two cases depending on the relation between $j$ and $k$.

If $j<k$, then variables $x_j,\ldots,x_{k-1}$ do not appear on the current path in the ZDD, hence they are free variables that must still be enumerated before we reach $x_k$. We therefore branch on them explicitly in lexicographic order. Concretely, for each assignment of $x_j$ we recursively call $\mathrm{TABLE}(p,j+1)$, so that after $k-j$ such steps we arrive at the state $j=k$. This ensures that all intermediate variables are expanded in the correct order before processing node $p$.

If $j=k$, then the current variable in the truth-table construction matches the variable of the ZDD node, so we must respect the Shannon decomposition encoded by the ZDD. We first assign $x_k=0$ and continue with the low child, and then assign $x_k=1$ and continue with the high child. Formally, we output

$$ \mathrm{TABLE}(p_0,k+1) \quad \text{followed by} \quad \mathrm{TABLE}(p_1,k+1). $$

The order is crucial: it ensures lexicographic ordering because all assignments with $x_k=0$ precede those with $x_k=1$, and within each block the recursion maintains the same ordering invariant.

This completes the recursive specification.

To see correctness, observe first that every call $\mathrm{TABLE}(p,j)$ enumerates exactly the set of assignments consistent with the ZDD semantics at node $p$ and partial assignment up to $x_{j-1}$. When $j<k$, the expansion over $x_j$ ensures that all assignments are generated in increasing lexicographic order on the remaining prefix variables. When $j=k$, the Shannon decomposition guarantees that every satisfying assignment is partitioned uniquely between the low and high subgraphs, so no assignment is missed or duplicated. Finally, terminal nodes correctly fill in the remaining suffix of the truth table with uniform values because $\bot$ and $\top$ represent constant functions on all completions of unassigned variables.

Thus the procedure outputs each of the $2^n$ assignments exactly once, in lexicographic order, with the correct function value, which is exactly the fully elaborated truth table.