TAOCP 7.2.2.2 Exercise 157

Section 7.2.2.2: Satisfiability

Exercise 157. [10] [10] Give an example of an autarky that is not a pure literal.

Verified: yes
Solve time: 58s

Consider the formula

$$ F = {, a b,\ \bar{a} c ,}. $$

Let $L = {a, c}$, interpreted as assigning $a=1$ and $c=1$, with all other variables unassigned. Every clause containing a literal from $L$ is satisfied by $L$: the clause $a b$ contains $a$ and is satisfied since $a=1$, and the clause $\bar{a} c$ contains $c$ and is satisfied since $c=1$. Hence $L$ is an autarky.

This autarky is not a pure literal assignment, since the variable $a$ occurs both positively in $a b$ and negatively in $\bar{a} c$. Thus $L$ is an autarky that is not based on a pure literal. ∎