TAOCP 7.2.2.2 Exercise 11
In the representation leading to (12), each clause is converted into implications of the form “literals on the left of $\rightarrow$ imply literals or clauses on the right,” and a clause contributes t...
Section 7.2.2.2: Satisfiability
Exercise 11. ▶ [**] [20] Find all the clauses with the property that no clauses can occur to the right of "$\rightarrow$" in (12).
Verified: yes
Solve time: 57s
In the representation leading to (12), each clause is converted into implications of the form “literals on the left of $\rightarrow$ imply literals or clauses on the right,” and a clause contributes terms on the right-hand side exactly when it contains at least two literals.
A clause of length $k \ge 2$ produces implications in which other literals appear on the right of $\rightarrow$, since removing one literal still leaves a nonempty clause. Hence such clauses cannot satisfy the stated property.
A unit clause ${l}$ produces no nontrivial clause on the right-hand side, since there is no second literal to form a remaining clause after deletion. The empty clause ${}$ likewise produces no right-hand contribution.
Therefore the only clauses with the property that no clauses occur to the right of $\rightarrow$ in (12) are the unit clauses and the empty clause $\epsilon$:
$\boxed{\text{all unit clauses and the empty clause } \epsilon.}$
This completes the solution. ∎