TAOCP 7.2.2.2 Exercise 455
Let $\tau$ denote the mapping in (187).
Section 7.2.2.2: Satisfiability
Exercise 455. [M20] $[M20]$ Suppose we know that (187) is an endomorphism of some given clauses $F$ on the variables ${x_1, x_2, x_3, x_4}$. Can we be sure that $F$ is satisfiable if and only if $F \wedge C$ is satisfiable, when (a) $C = 124$, i.e., $C = (\bar{x}_1 \vee x_2 \vee \bar{x}_4)$? (b) $C = 234$? (c) $C = 123$? (d) $C = 34$?
Verified: yes
Solve time: 6m26s
Solution
Let $\tau$ denote the mapping in (187). The relevant property of an endomorphism is that whenever $f(x)=1$, we also have $f(x\tau)=1$. Thus, if $S$ is the set of satisfying assignments of $F$, then $S$ is closed under $\tau$. The map (187) is the finite directed graph on the $16$ assignments of four Boolean variables. Its cycles, obtained by following the arrows in (187), are
$$ (0011),\qquad (1010\ 0101\ 0110),\qquad (1000). $$
The remaining assignments lie on directed trees whose roots are these cycles. In particular, every nonempty $\tau$-closed set of assignments contains at least one of these cycles. The cycle decomposition follows directly by tracing each row of (187); the same cycles are listed in the discussion immediately following (187).
Suppose that every cycle of $\tau$ contains an assignment satisfying a clause $C$. If $F$ is satisfiable, then its solution set $S$ is nonempty and $\tau$-closed. Choose any $x\in S$. Repeated application of $\tau$ eventually reaches a cycle contained in $S$. That cycle contains some assignment $y$ satisfying $C$, so $y$ satisfies both $F$ and $C$. Hence $F\wedge C$ is satisfiable.
The converse implication, from $F\wedge C$ satisfiable to $F$ satisfiable, is immediate because $F\wedge C$ contains $F$ as a conjunct. Therefore the equivalence
$$ F\text{ is satisfiable}\iff F\wedge C\text{ is satisfiable} $$
is guaranteed precisely when every cycle of $\tau$ contains an assignment satisfying $C$.
For the negative cases, the condition is also necessary. If a cycle $Y$ contains no assignment satisfying $C$, take a formula whose satisfying assignments are exactly the elements of $Y$. Such a formula exists because any finite set of Boolean assignments can be represented by a CNF formula: for every assignment outside $Y$, include a clause that is false on that assignment and true on every assignment in $Y$. Since $Y$ is closed under $\tau$, the mapping $\tau$ is an endomorphism of this formula. For this choice of $F$, the formula $F$ is satisfiable but $F\wedge C$ is not.
For part (a), let
$$ C=124=\bar{1}2\bar{4}. $$
On the three cycles, the assignments are checked as follows:
$$ 0011:\bar{1}=1, $$
$$ 1010:\bar{4}=1, $$
$$ 0101:\bar{1}=1, $$
$$ 0110:\bar{1}=1, $$
$$ 1000:\bar{4}=1. $$
Every cycle contains an assignment satisfying $C$. Therefore the equivalence is guaranteed.
$$ \boxed{\text{(a) Yes}} $$
For part (b),
$$ C=234=x_2\vee x_3\vee x_4. $$
The cycle $(0011)$ contains satisfying assignments because $x_4=1$. The cycle $(1010\ 0101\ 0110)$ contains satisfying assignments because $x_3=1$, $x_2=1$, and $x_2=1$, respectively. The cycle $(1000)$ has
$$ x_2=x_3=x_4=0, $$
so no element of that cycle satisfies $C$. Hence the cycle $(1000)$ gives a valid counterexample.
$$ \boxed{\text{(b) No}} $$
For part (c),
$$ C=123=x_1\vee x_2\vee x_3. $$
The cycle elements satisfy
$$ 0011:x_3=1, $$
$$ 1010:x_1=1, $$
$$ 0101:x_2=1, $$
$$ 0110:x_2=1, $$
$$ 1000:x_1=1. $$
Every cycle contains an assignment satisfying $C$, so adding this clause cannot remove satisfiability.
$$ \boxed{\text{(c) Yes}} $$
For part (d),
$$ C=34=x_3\vee x_4. $$
The cycle elements satisfy
$$ 0011:x_4=1, $$
$$ 1010:x_3=1, $$
$$ 0101:x_4=1, $$
$$ 0110:x_3=1, $$
but
$$ 1000:x_3=x_4=0. $$
The cycle $(1000)$ again supplies a counterexample, because a formula with exactly this cycle as its solution set is satisfiable and remains invariant under $\tau$, while its conjunction with $C$ is unsatisfiable.
$$ \boxed{\text{(d) No}} $$
This completes the proof.
∎