TAOCP 7.1.4 Exercise 32
Exercise 31 describes a generic BDD evaluation scheme in which a function is computed by replacing each internal decision node labeled by variable $x_j$ with an algebraic combination of the values of...
Section 7.1.4: Binary Decision Diagrams
Exercise 32. ▶ [M20] [M20] What interpretations of ‘◦’, ‘•’, ‘⊥’, ‘⊤’, ‘¯xj’, and ‘xj’ will make the general algorithm of exercise 31 specialize to the algorithms of exercises 25, 26, 29, and 30?
Verified: no
Solve time: 1m50s
Solution
Exercise 31 describes a generic BDD evaluation scheme in which a function is computed by replacing each internal decision node labeled by variable $x_j$ with an algebraic combination of the values of its two subfunctions. The two binary operations are denoted by $\circ$ and $\bullet$, and the constants at the sinks are $\bot$ and $\top$. The literals $\bar{x}_j$ and $x_j$ specify how the variable test contributes to the combination of the LO and HI branches.
At a node labeled $x_j$ with LO-subfunction value $u$ and HI-subfunction value $v$, the general algorithm constructs an expression of the form
$$ (\bar{x}_j \bullet u)\ \circ\ (x_j \bullet v). $$
The meaning of the exercise is that different choices of the algebraic system $(\circ,\bullet,\bot,\top,\bar{x}_j,x_j)$ cause this same recursion to specialize to the algorithms of earlier exercises.
The specialization is determined by interpreting the same BDD recurrence in different semirings or algebraic models.
For Boolean evaluation of the function itself (the standard interpretation of a BDD), the LO branch corresponds to $x_j=0$ and the HI branch to $x_j=1$. The correct combination is the Shannon expansion
$$ f = (\bar{x}_j \land f_0)\ \lor\ (x_j \land f_1). $$
Matching this with the generic form forces
$$ \circ = \lor,\quad \bullet = \land,\quad \bot = \text{FALSE},\quad \top = \text{TRUE},\quad \bar{x}_j = \neg x_j,\quad x_j = x_j. $$
With this interpretation, each node computes exactly the Boolean function represented by the BDD, so the general algorithm reduces to the standard evaluation procedure underlying the construction in exercises 25 and 26.
For the reliability polynomial in exercise 29, each variable $x_j$ represents the operational state of a component with success probability $p_j$. A minterm contributes weight
$$ (1-p_j)^{1-x_j} p_j^{x_j}. $$
The combination over independent components is multiplicative, and combining disjoint sub-BDDs corresponds to addition of probabilities. Hence the correct algebraic structure is the sum-product semiring:
$$ \circ = +,\quad \bullet = \times,\quad \bot = 0,\quad \top = 1,\quad \bar{x}_j = 1-p_j,\quad x_j = p_j. $$
With this interpretation, each node computes the total probability contribution of all assignments satisfying the subfunction, and the root value becomes the reliability polynomial $F(p)$ as defined in exercise 28, together with the same recursion extended in exercise 29.
For exercise 30, the quantity associated with a minterm is again a product of local weights, but the global objective is to select a single assignment maximizing total contribution. This replaces summation over disjoint cases by maximization, while preserving multiplicative independence along paths. The correct algebraic structure is therefore the max-product semiring:
$$ \circ = \max,\quad \bullet = \times,\quad \bot = 0,\quad \top = 1,\quad \bar{x}_j = 1-p_j,\quad x_j = p_j. $$
Under this interpretation, each node computes the maximum contribution attainable from its sub-BDD, and the root value equals the maximum minterm contribution.
For exercise 31 itself, the goal is not numerical evaluation but reconstruction of the full truth table. Each node represents splitting a table into two halves corresponding to $x_j=0$ and $x_j=1$, and the combination operation is concatenation of bit strings. The sink values are the one-bit tables. Thus the algebraic structure is the concatenation algebra:
$$ \circ = \text{concatenation},\quad \bullet = \text{concatenation},\quad \bot = 0,\quad \top = 1, $$
while the literals $\bar{x}_j$ and $x_j$ do not introduce weighting but only determine selection of subtable components through the recursive decomposition. In this model, each node with subtable outputs $\tau_0$ and $\tau_1$ produces the concatenated truth table
$$ \tau = \tau_0 \tau_1, $$
and the algorithm reconstructs the full $2^n$-bit truth table by repeated application of this rule along the BDD.
Each of these interpretations preserves the same structural recursion on the BDD while changing only the algebra in which node combinations are evaluated. This completes the correspondence between the general algorithm of exercise 31 and the specialized algorithms of exercises 25, 26, 29, and 30. ∎