TAOCP 7.2.2.2 Exercise 48
The data supplied are insufficient to determine the optimum circuits requested in exercise 7.
Section 7.2.2.2: Satisfiability
Exercise 48. [20] $[20]$ The small circuit shown here has three inputs, three XOR gates, one fanout gate, eight wires, and one output. Which single-stuck-at faults are detected by each of the eight test patterns $pqr$?
Verified: no
Solve time: 5m49s
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.