The Art of Computer Programming: Satisfiability, Volume 4, Fascicle 6

Answers to Exercises

Section 7.2.2.2

1. (a) (no clauses). (b) {} (one clause, which is empty).

2. Letting 1 ↔ lazy, 2 ↔ happy, 3 ↔ unhealthy, 4 ↔ dancer, we’re given the respective clauses , matching R′ in (7). So all known Pincusians dance happily, and none are lazy. But we know nothing about their health. [And we might wonder why travelers have bothered to describe so many empty sets.]

3. f(j – 1, n) + f(k – 1, n), where , if we set q = n/p.