TAOCP 7.2.2.2 Exercise 380

Section 7.2.2.2: Satisfiability

Exercise 380. [21] Sometimes we can use self-subsumption backwards, for example by weakening the clause $(l_1 \vee l_2 \vee l_k)$ to $(l_1 \vee \cdots \vee l_j)$ if each intermediate replacement of $(l_1 \vee \cdots \vee l_j)$ by $(l_1 \vee \cdots \vee l_{j-1})$ is justifiable for $3 < j \le k$. Then, if we're lucky, the clause $(l_1 \vee \cdots \vee l_j)$ is weak enough to be eliminated; in such cases we are allowed to eliminate $(l_1 \vee l_2 \vee l_k)$. a) Show that $(a \vee b \vee c)$ can be eliminated if it is accompanied by the additional clauses $(a \vee \bar{b} \vee d) \wedge (a \vee d \vee \bar{c})$, $(b \vee d \vee \bar{c})$. b) Show that $(a \vee b \vee c)$ can also be eliminated when accompanied by $(a \vee b \vee d)$, $(b \vee \bar{c} \vee d)$, $(b \vee c \vee \bar{e})$, provided that no other clauses contain $\bar{c}$.

c) What erp rules, if any, are needed for those eliminations?

Verified: no
Solve time: 3m48s

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.