TAOCP 7.2.2.2 Exercise 383

Section 7.2.2.2: Satisfiability

Exercise 383. ▶ [23] [23] (Inprocessing.) A SAT solver can partition its database of current clauses into two parts, the "hard" clauses $\Phi$ and the "soft" clauses $\Psi$. Initially $\Psi$ is empty, while $\Phi$ is $F$, the set of all input clauses. Four kinds of changes are subsequently allowed:

• Learning. We can append a new soft clause $C$, provided that $\Phi \cup \Psi \cup C$ is satisfiable whenever $\Phi \cup \Psi$ is satisfiable.
• Forgetting. We can discard (purge) any soft clause.
• Hardening. We can reclassify any soft clause and call it hard.
• Softening. We can reclassify any hard clause $C$ and call it soft, provided that $\Phi$ is satisfiable whenever $\Phi \setminus C$ is satisfiable. In this case we also should output any necessary erp which which changes the settings of variables in such a way that any solution to $\Phi \setminus C$ becomes a solution to $\Phi$.

a) Prove that, throughout any such procedure, $F$ is satisfiable $\iff$ $\Phi$ is satisfiable $\iff$ $\Phi \cup \Psi$ is satisfiable.

b) Furthermore, given any solution to $\Phi$, we obtain a solution to $F$ by applying the erp rules in reverse order.

c) What is wrong with the following scenario? Start with one hard clause, $(x)$, and no soft clauses. Reclassify $(x)$ as soft, using the erp rule $x \leftarrow 1$. Then append a new soft clause $(\bar{x})$.

d) If $C$ is certifiable for $\Phi$ (see exercise 385), can we safely learn $C$?

e) If $C$ is certifiable for $\Phi \setminus C$, can we safely forget $C$?

f) In what cases is it legitimate to discard a clause, hard or soft, that is subsumed by another clause, hard or soft?

g) In what cases is self-subsumption permissible?

h) Explain how to eliminate all clauses that involve a particular variable $x$.

i) Show that, if $z$ is a new variable, we can safely learn the three new soft clauses $(x \vee z)$, $(y \vee z)$, $(\bar{x} \vee \bar{y} \vee \bar{z})$ in Tseytin's concept of extended resolution.

Verified: no
Solve time: 3m52s

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.