TAOCP 7.1.4 Exercise 7
Let $f(x_1,\ldots,x_n)$ be represented by its reduced ordered BDD under variable order $x_1<\cdots<x_n$, and define $g_k(x_0,x_1,\ldots,x_n)=f(x_1',\ldots,x_n')$ where For truth tables, each entry of...
Section 7.1.4: Binary Decision Diagrams
Exercise 7. [21] [21] Given a Boolean function f(x1, . . . , xn), let gk(x0, x1, . . . , xn) = f(x0, . . . , xk−2, xk−1∨xk, xk+1, . . . , xn) for 1 ≤k ≤n. Find a simple relation between (a) the truth tables and (b) the BDDs of f and gk.
Verified: no
Solve time: 3m08s
Let $f(x_1,\ldots,x_n)$ be represented by its reduced ordered BDD under variable order $x_1<\cdots<x_n$, and define
$g_k(x_0,x_1,\ldots,x_n)=f(x_1',\ldots,x_n')$
where
\begin{cases} x_{i-1}, & 1\le i\le k-2,\ x_{k-2}\ \vee\ x_{k-1}, & i=k-1,\ x_i, & k\le i\le n. \end{cases}$$ For truth tables, each entry of $g_k$ is obtained from the corresponding entry of $f$ by applying the substitution map $T:{0,1}^{n+1}\to{0,1}^n$ defined above and then evaluating $f$. Hence the truth table of $g_k$ is the length-$2^{n+1}$ string $$g_k = \bigl(f(T(0,\ldots,0)),\ f(T(0,\ldots,0,1)),\ \ldots,\ f(T(1,\ldots,1))\bigr)2.$$ The effect of $T$ is that the two coordinates $x{k-2},x_{k-1}$ in the argument of $f$ are replaced by their Boolean disjunction $x_{k-2}\vee x_{k-1}$. Consequently, every pair of input assignments that differ only in these two coordinates is mapped to the same argument of $f$, and the corresponding two entries of the expanded truth table of $g_k$ are identical and equal to the value of $f$ at the OR-compressed point. Thus the truth table of $g_k$ is obtained from that of $f$ by replacing the two-variable block $(x_{k-2},x_{k-1})$ with a single variable equal to their disjunction. For BDDs, consider the level in the BDD of $f$ where $x_{k-1}$ is tested followed immediately by $x_k$. In the BDD of $g_k$, these two successive decisions are replaced by a single decision node whose semantic test is whether $x_{k-2}\vee x_{k-1}=0$ or $1$. The LO branch corresponds to $(x_{k-2},x_{k-1})=(0,0)$, since this is the only case where the disjunction is $0$, while the HI branch aggregates the cases $(0,1)$, $(1,0)$, and $(1,1)$, since each yields disjunction $1$. Thus the two consecutive levels labeled $x_{k-1}$ and $x_k$ in the BDD of $f$ collapse into one level in the BDD of $g_k$, with edges redirected according to the OR relation on the pair of variables. After this contraction, reduction may merge identical subgraphs in the usual way, producing the reduced ordered BDD of $g_k$. This completes the proof. ∎