TAOCP 7.2.2.2 Exercise 1
A set of clauses is interpreted as the conjunction of its clauses.
Section 7.2.2.2: Satisfiability
Exercise 1. [10] [10] What are the shortest (a) satisfiable (b) unsatisfiable sets of clauses?
Verified: yes
Solve time: 52s
A set of clauses is interpreted as the conjunction of its clauses. The empty set of clauses contains no constraints, so every assignment satisfies it. Any nonempty set of clauses has at least one clause, hence at least one constraint to satisfy, so it is longer than the empty set. The shortest satisfiable set is therefore the empty family of clauses $\emptyset$.
The empty clause is denoted by $\epsilon$ and is always false under any assignment, since it contains no literal that can be satisfied. A set consisting of a single clause ${\epsilon}$ has conjunction value $0$ for every assignment, hence is unsatisfiable. No shorter unsatisfiable set exists because $\emptyset$ is satisfiable. The shortest unsatisfiable set is therefore ${\epsilon}$. This completes the solution. ∎