TAOCP 7.1.4 Exercise 64
Let $B(f)$ denote the number of beads of a Boolean function $f$, equivalently the number of nodes in its reduced ordered BDD.
Section 7.1.4: Binary Decision Diagrams
Exercise 64. [M21] [M21] We can compute the median ⟨f1f2f3⟩of three Boolean functions by forming f4 = f1 ∨f2, f5 = f1 ∧f2, f6 = f3 ∧f4, f7 = f5 ∨f6. Then B(f4) = O(B(f1)B(f2)), B(f5) = O(B(f1)B(f2)), B(f6) = O(B(f3)B(f4)) = O(B(f1)B(f2)B(f3)); therefore B(f7) = O(B(f5)B(f6)) = O(B(f1)2B(f2)2B(f3)). Prove, however, that B(f7) is actually only O(B(f1)B(f2)B(f3)), and the running time to compute it from f5 and f6 is also O(B(f1)B(f2)B(f3)).
Verified: no
Solve time: 6m55s
Solution
Let $B(f)$ denote the number of beads of a Boolean function $f$, equivalently the number of nodes in its reduced ordered BDD. Each node corresponds to a distinct subfunction of $f$ under restrictions of variables, and distinct nodes correspond to distinct subfunctions.
The construction defines
$$ f_4 = f_1 \lor f_2,\quad f_5 = f_1 \land f_2,\quad f_6 = f_3 \land f_4,\quad f_7 = f_5 \lor f_6. $$
Every subfunction of $f_5$ is obtained by restricting variables in $f_1 \land f_2$, hence is of the form $g_1 \land g_2$ where $g_1$ is a subfunction of $f_1$ and $g_2$ is a subfunction of $f_2$. Therefore every bead of $f_5$ is determined by an ordered pair of beads from $f_1$ and $f_2$, and this yields
$$ B(f_5) \le B(f_1)B(f_2). $$
Similarly, every subfunction of $f_4 = f_1 \lor f_2$ is of the form $g_1 \lor g_2$ with $g_1$ a subfunction of $f_1$ and $g_2$ a subfunction of $f_2$, so every node of $f_4$ is determined by a pair $(g_1,g_2)$, giving
$$ B(f_4) \le B(f_1)B(f_2). $$
Now consider $f_6 = f_3 \land f_4$. Every restriction of $f_6$ has the form
$$ h_3 \land (h_1 \lor h_2), $$
where $h_3$ is a subfunction of $f_3$ and $(h_1,h_2)$ is a pair of subfunctions of $(f_1,f_2)$ coming from a subfunction of $f_4$. Hence every subfunction of $f_6$ is determined by a triple $(h_1,h_2,h_3)$ with $h_i$ a subfunction of $f_i$, and therefore
$$ B(f_6) \le B(f_1)B(f_2)B(f_3). $$
The crucial point for $f_7$ is that although it is written as $f_5 \lor f_6$, the two operands are not independent. Both $f_5$ and $f_6$ are functions built from the same pair $(f_1,f_2)$, and $f_6$ adds only dependence on $f_3$ applied to $f_1 \lor f_2$. Consequently every subfunction of $f_7$ arises from a simultaneous restriction of $f_1,f_2,f_3$, and is completely determined by the triple of corresponding subfunctions.
Formally, let $h$ be any subfunction of $f_7$ obtained by fixing a partial assignment to $(x_1,\dots,x_n)$. Let $h_1,h_2,h_3$ be the induced subfunctions of $f_1,f_2,f_3$ under the same restriction. The construction of $f_4,f_5,f_6,f_7$ uses only $\lor$ and $\land$, so restriction commutes with these operations, giving
$$ h_4 = h_1 \lor h_2,\quad h_5 = h_1 \land h_2,\quad h_6 = h_3 \land h_4,\quad h = h_5 \lor h_6. $$
Thus every subfunction of $f_7$ is uniquely determined by a triple $(h_1,h_2,h_3)$.
Distinct triples yield distinct subfunctions, since if two triples differ in any component, evaluation under assignments separating the corresponding subfunctions of $f_i$ produces different Boolean values at the level of $f_7$. Therefore the mapping from nodes of the BDD of $f_7$ to triples of nodes from $(f_1,f_2,f_3)$ is injective.
Hence the number of beads of $f_7$ satisfies
$$ B(f_7) \le B(f_1)B(f_2)B(f_3), $$
so
$$ B(f_7) = O(B(f_1)B(f_2)B(f_3)). $$
For the running time, the BDD construction for $\lor$ and $\land$ using memoized apply procedures processes each reachable pair or triple of subfunctions a bounded number of times. Since every intermediate state in the computation of $f_7$ is determined by a triple of subfunctions of $(f_1,f_2,f_3)$, the total number of distinct states is $O(B(f_1)B(f_2)B(f_3))$, and each transition performs only constant work up to recursive calls on strictly smaller variables. Therefore the total running time to construct $f_7$ from $f_5$ and $f_6$ is also
$$ O(B(f_1)B(f_2)B(f_3)). $$
This completes the proof. ∎