TAOCP 7.2.2.2 Exercise 217

The statement is false.

Section 7.2.2.2: Satisfiability

Exercise 217. [20] [20] True or false: If $A$ and $B$ are arbitrary clauses that are simultaneously satisfiable, and if $l$ is any literal, then the clause $C = (A \cup B) \setminus {l, \bar{l}}$ is also satisfiable. (We're thinking here of $A$, $B$, and $C$ as sets of literals, not as disjunctions of literals.)

Verified: yes
Solve time: 2m36s


Solution

The statement is false.

Let $l$ be any literal, and choose

$$ A={l,\bar l},\qquad B={l,\bar l}. $$

Both $A$ and $B$ are satisfiable, because each clause contains both a literal and its complement. For example, an assignment with $l=1$ satisfies both clauses, since the literal $l$ occurs in each. Hence $A$ and $B$ are simultaneously satisfiable.

For these clauses,

$$ A\cup B={l,\bar l}. $$

Therefore the clause specified in the statement is

$$ C=(A\cup B)\setminus{l,\bar l} ={l,\bar l}\setminus{l,\bar l} =\epsilon . $$

The empty clause $\epsilon$ is unsatisfiable, by the definition in Section 7.2.2.2. Thus $C$ is not satisfiable even though $A$ and $B$ are simultaneously satisfiable.

Therefore the proposed assertion is false.

This completes the proof.