TAOCP 7.1.4 Exercise 6
The truth table of $g(x_1,x_2,x_3,x_4)=f(x_4,x_3,x_2,x_1)$ is obtained by reversing the bit indices of the truth table of $f$.
Section 7.1.4: Binary Decision Diagrams
Exercise 6. [10] [10] Let g(x1, x2, x3, x4) = f(x4, x3, x2, x1), where f has the BDD in (6). What is the truth table of g, and what are its beads?
Verified: no
Solve time: 2m55s
The truth table of $g(x_1,x_2,x_3,x_4)=f(x_4,x_3,x_2,x_1)$ is obtained by reversing the bit indices of the truth table of $f$. If $f$ has truth table indexed in lexicographic order $(x_1x_2x_3x_4)=0000,\dots,1111$ as
$$ f = 1100100100001111, $$
then $g[i]=f[\mathrm{rev}_4(i)]$, where $\mathrm{rev}_4$ reverses the 4-bit binary expansion of $i$. This yields
$$ g = 1011000110010011. $$
The beads of $g$ correspond exactly to the beads of $f$ under reversal of variable order $x_1 \leftrightarrow x_4$. Hence each bead of $g$ is obtained by reversing the bit-structure of the corresponding bead of $f$ at the same level of the decomposition. The beads are
$$ {1011000110010011,\ 10010011,\ 11110000,\ 0011,\ 1001,\ 01,\ 10,\ 0,\ 1}. $$