TAOCP 7.2.2.2 Exercise 207

Section 7.2.2.2: Satisfiability

Exercise 207. [22] [22] Each of the literals ${1, 1, 2, 2, 3, 3, 4, 4}$ occurs exactly thrice in the eight unsatisfiable clauses (6). Construct an unsatisfiable 3SAT problem with 15 variables in which each of the 30 literals occurs exactly twice. Hint: Consider ${12, 23, 31, 123, 123}$.

Verified: no
Solve time: 10m