TAOCP 7.2.2.2 Exercise 369

Section 7.2.2.2: Satisfiability

Exercise 369. ▶ [**] [M EA] (N. Eén, A. Biere.) Suppose $l$ appears in clauses $C_1, \ldots, C_p$ and $\bar{l}$ appears only in clauses $C'_1, \ldots, C'_q$, where we have $C_i = (lV l_1 \vee \cdots \vee l_r)$ and $C'_j = (\bar{l}V l'_1)$ for $1 \le j \le r$. We can eliminate $|l|$ by replacing those $p + q$ clauses by only $(p-2)r + q$ others, namely

$${C_1 \circ C'_j \mid r < j \le q} \cup {C_i \circ C'_j \mid 1 \le i \le p, 1 \le j \le r}$$

(The case $r = 1$ is especially important. In many applications, for example in the examples of fault testing, tomography, and the "Life in 4" problem about extending Fig. 35, more than half of all variable eliminations admit this simplification.)

Verified: no
Solve time: 3m53s

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.