TAOCP 7.2.2.2 Exercise 120

Section 7.2.2.2: Satisfiability

Exercise 120. [M20] [M20] True or false: $F|L = (C \setminus \bar{L} \mid C \in F \text{ and } C \cap L = \emptyset)$, if $\bar{L} = {\bar{l} \mid l \in L}$.

Verified: yes
Solve time: 1m23s

Solution

The statement is true.

Let $L$ be a set of literals, and let $\bar{L}={\bar{l}\mid l\in L}$. The reduction $F|L$ is obtained by assigning every literal in $L$ the value $1$. A clause $C\in F$ with $C\cap L\ne\emptyset$ is already satisfied by this assignment, so it disappears from the reduced formula. A clause $C\in F$ with $C\cap L=\emptyset$ remains, except that every literal made false by the assignment must be deleted. The literals made false are precisely the members of $\bar{L}$, so the remaining clause is

$$ C\setminus\bar{L}. $$

Consequently every clause of $F|L$ has the form

$$ C\setminus\bar{L} $$

for some $C\in F$ satisfying

$$ C\cap L=\emptyset. $$

Thus,

$$ F|L={C\setminus\bar{L}\mid C\in F\text{ and }C\cap L=\emptyset}. $$

The reverse inclusion also holds. Take any clause appearing on the right-hand side. It comes from some $C\in F$ with $C\cap L=\emptyset$. Since none of the literals of $C$ are made true by the assignment, $C$ is not removed. The only literals that can be removed from $C$ are the complements of literals in $L$, namely the members of $\bar{L}$. Hence the reduction process replaces $C$ by exactly

$$ C\setminus\bar{L}, $$

so this clause belongs to $F|L$.

Both inclusions have been proved, and therefore the stated equality holds.

This completes the proof.

$$ \boxed{\text{True}} $$

∎