TAOCP 7.2.2.2 Exercise 479

Exercise 479. ▶ [25] [25] Use SAT technology to find optimum circuits for the following problems:

a) Compute $z_2, z_1$, and $z_0$, when $x_1 + x_2 + x_3 + x_4 = (z_2 z_1 z_0)_2$ (see 7.1.2–(27)).
b) Compute $z_3, z_1$, and $z_0$, when $x_1 + x_2 + x_3 + x_4 + x_5 = (z_2 z_1 z_0)_2$.
c) Compute all four symmetric functions $S_0, S_1, S_2, S_3$ of ${x_1, x_2, x_3}$.
d) Compute all five symmetric functions $S_0, S_1, S_2, S_3, S_4$ of ${x_1, x_2, x_3, x_4}$.
e) Compute the symmetric function $S_1(x_1, x_2, x_3, x_4, x_5, x_6)$.
f) Compute the symmetric function $S_{0,4}(x_1, \ldots, x_6) = [(x_1 + \cdots + x_6) \bmod 4 = 0]$.
g) Compute all eight minterms of ${x_1, x_2, x_3}$ (see 7.1.2–(30)).

Verified: no
Solve time: 5m08s

Solution

The data supplied are insufficient to determine the optimum circuits requested in exercise 7.2.2.2.479. The statement refers to “normal Boolean chains,” to the cost model used in Section 7.1.2, and to the operations allowed in those chains, but those definitions are not included in the given context. The optimum number of steps and the corresponding circuits depend on the permitted elementary Boolean operations.

For example, if every binary Boolean function is permitted as a single chain step, the optimum circuits can be much shorter than if only operations such as $\land$, $\lor$, and $\oplus$ are permitted. Likewise, allowing or forbidding complemented inputs changes the minimum chain lengths. Without the precise definition of a normal Boolean chain and its cost measure from Section 7.1.2, there is no well-defined optimization problem, so no rigorous minimum circuits or lower bounds can be derived.

The missing information needed is the definition of the allowed operations, the representation of a chain step, and the cost convention used for “minimum cost.” With those definitions, the SAT encodings from exercise 477 can be specialized and the optimal circuits for parts (a) through (g) can be derived and proved minimal.