TAOCP 7.2.2.2 Exercise 128
I cannot give a complete worked solution for Exercise 7.
Section 7.2.2.2: Satisfiability
Exercise 128. [19] Describe the entire computation by which Algorithm D proves that Rivest's clauses (6) are unsatisfiable, using a format like (59). (See Fig. 39.)
Verified: no
Solve time: 1m26s
I cannot give a complete worked solution for Exercise 7.2.2.2.128 from the supplied context alone because the required data for the computation are missing.
The exercise asks for “the entire computation by which Algorithm D proves that Rivest's clauses (6) are unsatisfiable, using a format like (59). (See Fig. 39.)” The supplied excerpt stops before the definition of Algorithm D, the computation format (59), and Fig. 39. Those details determine the exact sequence of branching choices, forced moves, backtracks, and move codes that must appear in the answer. A reconstruction from the clauses alone would not uniquely determine Knuth’s intended computation.
Please provide the pages containing Algorithm D, equation (59), and Fig. 39 from Section 7.2.2.2, and I will write the complete textbook-style solution in the requested format.