TAOCP 7.2.2.2 Exercise 159

For part (a), the statement is false.

taocpmathematicsalgorithmsvolume-4math-medium

Section 7.2.2.2: Satisfiability

Exercise 159. [M17] [M17] True or false: (a) $A$ is an autarky for $F$ if and only if $F \mid A \subseteq F$. (b) If $A$ is an autarky for $F$ and $A' \subseteq A$, then $A \setminus A'$ is an autarky for $F|A'$.

Verified: yes
Solve time: 1m29s

Solution

For part (a), the statement is false. Take

$$ F={{\bar{1},2},{2}} $$

and let

$$ A={1}. $$

The set $A$ is not an autarky for $F$, because the clause ${\bar{1},2}$ contains the variable $1$, but the literal $1$ does not satisfy this clause. Restricting $F$ by $A$ sets $1$ to true and removes the false literal $\bar{1}$ from the first clause, giving

$$ F|A={{2}}. $$

Since ${2}\in F$, we have

$$ F|A\subseteq F, $$

while $A$ is not an autarky. Hence the implication from $F|A\subseteq F$ to $A$ being an autarky fails, and therefore the claimed equivalence in (a) is false.

For part (b), the statement is true. Let $A$ be an autarky for $F$, and let

$$ A'\subseteq A. $$

Consider the restricted formula

$$ F|A'. $$

Take any clause $C'$ of $F|A'$ that contains a literal from

$$ A\setminus A'. $$

The clause $C'$ arises from some clause $C\in F$ after the literals falsified by $A'$ have been removed. Since $C'$ contains a literal from $A\setminus A'$, the original clause $C$ contains a variable assigned by a literal in $A$.

Because $A$ is an autarky for $F$, every clause of $F$ containing a variable assigned by $A$ is satisfied by $A$. Therefore $C$ contains a literal from $A$ that satisfies it. This satisfying literal cannot belong to $A'$, because any clause containing a literal from $A'$ would have been removed when forming $F|A'$. Hence the satisfying literal belongs to

$$ A\setminus A'. $$

The same literal remains in $C'$, so $C'$ is satisfied by $A\setminus A'$. Every clause of $F|A'$ that contains a variable from $A\setminus A'$ is therefore satisfied by $A\setminus A'$, which is exactly the condition that

$$ A\setminus A' $$

is an autarky for $F|A'$.

This completes the proof. ∎

Thus the answers are

$$ \boxed{\text{(a) false,\qquad (b) true}.} $$