TAOCP 7.1.4 Exercise 71

Exercise 71. [20] [20] Discuss how to extend Algorithm S to ternary operators.

Verified: yes
Solve time: 1m49s

Solution

Algorithm S in Section 7.1.4 constructs the BDD of a Boolean expression by recursively combining previously constructed BDDs, using Shannon decomposition on the current top variable and then applying a binary Boolean operator nodewise with memoization and reduction. The essential invariant is that every recursive call returns the reduced ordered BDD representing the function obtained after fixing variables above the current level.

To extend Algorithm S from binary operators to ternary operators, the structure of the decomposition remains unchanged while the combination step is generalized from two operands to three operands.

Let $F(x_1,\dots,x_n), G(x_1,\dots,x_n), H(x_1,\dots,x_n)$ be Boolean functions represented by BDDs $B(F), B(G), B(H)$, and let $\varphi:{0,1}^3\to{0,1}$ be a fixed ternary Boolean operator. The goal is to construct a BDD for the function

$$ K(x_1,\dots,x_n)=\varphi(F(x_1,\dots,x_n),G(x_1,\dots,x_n),H(x_1,\dots,x_n)). $$

The extension preserves ordered reduction: every node is still labeled by a variable index $V(k)$, and edges still respect the ordering constraint $i<j$ along all arcs. No structural change is required to the underlying BDD model.

The recursive structure of Algorithm S is extended by replacing the binary Apply step with a ternary Apply step defined on triples of nodes. Let $\text{APPLY}_\varphi(u,v,w)$ denote the node computing $\varphi$ on the subfunctions represented by nodes $u,v,w$. The computation proceeds by Shannon expansion at the top variable $x_k$ common to the three operands.

Each node $u$ represents a function $f_u$, so it decomposes as

$$ f_u = x_k f_u^{(1)} + \bar{x}_k f_u^{(0)}, $$

and similarly for $v,w$. The ternary function then decomposes into eight cofactors determined by the values of $x_k$ in each operand:

$$ K^{(b_1,b_2,b_3)} = \varphi(f_u^{(b_1)}, f_v^{(b_2)}, f_w^{(b_3)}), \quad (b_1,b_2,b_3)\in{0,1}^3. $$

Only two of these eight combinations are needed at each BDD node level because the decision diagram branches on a single variable assignment shared by all operands. Hence, at variable $x_k$, the recursive construction splits into the two cases $x_k=0$ and $x_k=1$:

$$ K^{(0)} = \varphi(f_u^{(0)}, f_v^{(0)}, f_w^{(0)}), \qquad K^{(1)} = \varphi(f_u^{(1)}, f_v^{(1)}, f_w^{(1)}). $$

The node returned by $\text{APPLY}_\varphi(u,v,w)$ is then defined exactly as in Algorithm S: if the resulting LO and HI children are identical, the node is reduced to that child; otherwise a unique node with label $k$ and pointers to the recursively computed LO and HI nodes is created.

The memoization structure in Algorithm S, which stores already computed pairs of nodes for the binary case, becomes a triple-table storing previously computed triples $(u,v,w)$. This preserves the DAG property and guarantees that identical subproblems yield identical nodes, ensuring reducedness.

Formally, the modified recursive procedure is:

For terminals $u,v,w\in{\bot,\top}$, return the terminal node representing $\varphi(u,v,w)$.

For nonterminal nodes, let $k=\min{V(u),V(v),V(w)}$ in the total order. Compute cofactors $u_0,u_1$, $v_0,v_1$, $w_0,w_1$ with respect to $x_k$, where a node not testing $x_k$ is treated as having identical cofactors. Recursively compute

$$ L = \text{APPLY}\varphi(u_0,v_0,w_0), \qquad H = \text{APPLY}\varphi(u_1,v_1,w_1). $$

Return $\text{MK}(k,L,H)$, where $\text{MK}$ applies the standard reduction rule of Algorithm S, eliminating nodes with identical children and enforcing uniqueness.

The correctness follows from the fact that the Shannon decomposition remains valid for each operand and that $\varphi$ is evaluated pointwise on corresponding cofactors. Orderedness is preserved because recursion always proceeds on strictly smaller variable indices, identical to the binary case. Termination follows from the finiteness of the BDD node space and strict decrease in the variable index along any path.

This completes the extension of Algorithm S to ternary operators. ∎