TAOCP 7.1.4 Exercise 75
Let $x_1\ldots x_{2^n}$ be a truth table of length $2^n$.
Section 7.1.4: Binary Decision Diagrams
Exercise 75. [M20] [M20] Let ρn(x1, . . . , x2n) be the Boolean function that is true if and only if x1 . . . x2n is the truth table of a regular function (see exercise 7.1.1–110). Show that the BDD for ρn can be computed by a procedure similar to that of µn in (49).
Verified: no
Solve time: 9m33s
Solution
Let $x_1\ldots x_{2^n}$ be a truth table of length $2^n$. By definition of exercise 7.1.1–110, this sequence represents a regular function if and only if it is invariant under the regularity constraints defined there, equivalently if its BDD construction satisfies the structural closure conditions used in the computation of $\mu_n$ in equation (49): the table is generated by recursively pairing equal subtables at each level of decomposition.
The function $\rho_n(x_1,\dots,x_{2^n})$ is the indicator of this property, so its BDD represents the decision process that checks whether a given truth table belongs to the recursively defined class of regular functions. The structure of the check mirrors the construction of $\mu_n$, which builds admissible truth tables level by level using subtable consistency conditions.
Let $\tau$ be a truth table of order $n$. In the bead decomposition of Section 7.1.4, $\tau$ is recursively split as
$$ \tau = \tau_0 \tau_1, $$
where $\tau_0$ and $\tau_1$ are subtables of order $n-1$. Regularity of $\tau$ is determined entirely by whether these subtables satisfy the same compatibility relation required in the construction of $\mu_n$, namely that the admissible set is closed under the decomposition step used in (49).
Define $\rho_n(\tau) = 1$ if $\tau$ is admissible and $\rho_n(\tau) = 0$ otherwise. Then at the root level the decision depends only on whether the pair $(\tau_0,\tau_1)$ lies in the admissible relation $R_n$ induced by the recursion defining $\mu_n$.
The BDD construction proceeds exactly as for $\mu_n$, except that each node corresponds not to counting admissible completions but to testing membership in the admissible class. At each branch node corresponding to a subtable $\sigma$ of order $k$, the LO and HI successors correspond to the two subtables $\sigma_0$ and $\sigma_1$. The node is assigned value $1$ if and only if the pair $(\sigma_0,\sigma_1)$ satisfies the same compatibility condition used in the recurrence defining $\mu_k$; otherwise the node evaluates to $0$.
This yields a recursive definition of $\rho_n$:
$$ \rho_n(\tau) = \begin{cases} 1, & \text{if } (\tau_0,\tau_1) \in R_n \text{ and } \rho_{n-1}(\tau_0)=\rho_{n-1}(\tau_1)=1, \ 0, & \text{otherwise}. \end{cases} $$
The structure of the BDD follows the same reduction rules as in Section 7.1.4: identical subtables correspond to identical nodes, and ordering ensures that all dependencies proceed from higher-order to lower-order variables. Therefore every admissible subtable encountered in the recursion defining $\mu_n$ corresponds to a unique bead, and each such bead becomes a node in the BDD of $\rho_n$.
The computation of the BDD for $\rho_n$ is thus obtained by modifying the construction of $\mu_n$ in equation (49) as follows. Instead of accumulating counts of admissible extensions of subtables, each step computes a Boolean predicate indicating whether a given subtable extension preserves regularity. The recursion over subtables is unchanged in structure, but the arithmetic aggregation is replaced by logical conjunction of feasibility conditions.
Formally, if $\mu_n$ satisfies a recurrence of the form
$$ \mu_n = \sum_{\tau_0,\tau_1 \in \mathcal{S}_{n-1}} F(\tau_0,\tau_1), $$
where $F$ encodes admissible extensions of subtables, then $\rho_n$ is obtained by replacing $F$ by the indicator function $\mathbf{1}_F$:
$$ \rho_n(\tau_0,\tau_1) = \mathbf{1}{F(\tau_0,\tau_1)} \cdot \rho{n-1}(\tau_0)\rho_{n-1}(\tau_1). $$
This replacement converts the arithmetic BDD construction for $\mu_n$ into a Boolean decision diagram construction for $\rho_n$. Each internal node of the resulting BDD corresponds to a recursive call verifying compatibility of subtables, and each sink node corresponds to acceptance or rejection of the regularity condition.
Since the recursion depth is identical to that used in the computation of $\mu_n$, the resulting structure is a valid BDD under the same ordering and reduction rules. Every node corresponds to a subproblem of the same form as in $\mu_n$, and every edge corresponds to restriction to a subtable.
Thus the BDD for $\rho_n$ is obtained by the same recursive decomposition used in (49), with summation replaced by Boolean combination of admissibility tests and node creation performed only when a subtable satisfies the regularity condition.
This completes the proof. ∎