TAOCP 7.1.4 Exercise 67

Exercise 67. [24] [24] Sketch the actions of Algorithm S when (41) defines f and g, and op = 1.

Verified: no
Solve time: 5m58s

Solution

Algorithm S evaluates a binary Boolean operation (f \circ g) on functions represented by reduced ordered binary decision diagrams (BDDs). The case (op = 1) corresponds to the Boolean OR operation, so the construction computes the BDD of (h = f \lor g) by recursively combining the root structure of the BDDs of (f) and (g) according to variable ordering and reduction rules.

Let (F) and (G) denote the BDDs of (f) and (g). Algorithm S proceeds by pairing nodes of (F) and (G) that correspond to the same variable index (V), and recursively building a new node whose LO and HI children are obtained by applying OR to the corresponding cofactors.

For a pair of nodes (u \in F), (v \in G), let the associated subfunctions be (f_u) and (g_v). The construction defines [ h_{u,v} = f_u \lor g_v. ] The recursion splits according to the ordering of variables. If (V(u) < V(v)), then the decision variable at the combined node is (V(u)), and the HI and LO children are formed by combining the two cofactors of (f_u) with the unchanged (g_v). If (V(v) < V(u)), the symmetric rule applies. If (V(u) = V(v)), both functions split at the same variable, so [ h_{u,v} = (f_{u,0} \lor g_{v,0}) ;,; (f_{u,1} \lor g_{v,1}), ] and Algorithm S recursively constructs both pairs.

The base cases occur when either argument is a sink node. If (u = \bot), then (h_{\bot,v} = g_v) because (\bot \lor g_v = g_v). If (v = \bot), then (h_{u,\bot} = f_u). If (u = \top) or (v = \top), then (h_{u,v} = \top) since (\top \lor x = \top). These identities collapse large parts of the recursion tree immediately when sink nodes are encountered.

Reduction in Algorithm S merges identical subproblems (h_{u,v}) by memoization on pairs ((u,v)). This guarantees that each pair of BDD nodes is processed at most once, so the computation is bounded by the number of reachable pairs of nodes in (F \times G). Each such pair contributes at most one created node in the resulting BDD after reduction.

When (op = 1), the HI-merge rule simplifies structurally. If both HI children of (u) and (v) evaluate to (\top), the resulting HI child is (\top), and similarly if both LO children evaluate to (\bot), that branch collapses. In the presence of shared subgraphs, repeated OR operations between identical cofactors collapse immediately by the idempotence law (x \lor x = x), which is enforced by the reduction rule forbidding duplicate ((V, LO, HI)) triples.

The execution therefore proceeds as a synchronized traversal of the two BDDs starting from the roots. Each step selects the smallest current variable index among the active nodes, branches according to that variable, and recursively combines the corresponding sub-BDDs. Whenever one operand reaches a sink, the remaining structure is reused directly without further expansion.

The resulting BDD for (f \lor g) consists precisely of the merged set of reachable cofactors of (f) and (g), with all pairs ((u,v)) identified under equivalence of subfunctions. The algorithm constructs exactly the nodes corresponding to distinct Boolean functions of the form (f_u \lor g_v) that arise from reachable nodes (u) and (v), and no additional nodes appear due to the reduction condition.

This completes the sketch of Algorithm S for (op = 1). ∎