TAOCP 7.2.2.2 Exercise 378

Section 7.2.2.2: Satisfiability

Exercise 378. [39] (Blocked clauses.) A clause $C = "l_1 \vee \cdots \vee l_t \vee l_1 \vee \cdots \vee l_k"$ is said to be blocked by the literal $l$ if every clause that contains $\bar{l}$ also contains either $l_1$ or $\cdots$ or $l_k$. Exercise 161(b) proves that clause $C$ can be removed without making an unsatisfiable problem satisfiable. Show that this transformation requires an erp rule, even though it doesn't eliminate any of the variables. What erp rule works?

Verified: no
Solve time: 3m49s

Solution

The information provided is not sufficient to derive the requested formulas.

Exercise 7.2.2.2.357 depends on equation (155) and on the definition of the quantities $\pi_0$, $\pi_s$, the “field” of a variable $v$, and the parameter $r$ in the surrounding text. The supplied section excerpt ends before the material containing equation (155), so the relationships needed to express

$$ x=\pi_0,\qquad y=\pi_s $$

in terms of $p$, $q$, and $r$ are not available.

A complete solution requires the definitions preceding equation (155), specifically:

1. the meaning of the field $(p,q)$ of the variable $v$,
2. the recurrence or relation involving $\pi_i$,
3. the role of the parameter $r$ in that recurrence.

Without those definitions, there is no justified derivation of $x$ and $y$, and any proposed formulas would be unsupported.

Please provide the text surrounding equation (155), including the definition of $\pi_0$ and $\pi_s$, and the complete solution can then be derived.