TAOCP 7.2.2.2 Exercise 7

Section 7.2.2.2: Satisfiability

Exercise 7. [25] [25] (a) can find a satisfying assignment to clauses (6). Are there others? (b) Show that, in fact, (6) has a unique satisfying assignment without using clause $C_5$ or $C_8$.

Verified: no
Solve time: 1m47s

Solution

The statement of the exercise is inconsistent with the clause set displayed in equation (6). Let the truth values of $x_1,x_2,x_3,x_4$ be written as a binary string $x_1x_2x_3x_4$. Substitution into the eight clauses of

$$ R={123,2\bar{3}4,341,4\bar{1}2,\bar{1}23,234,\bar{3}4\bar{1},\bar{4}\bar{1}2} $$

shows that

$$ 0011 $$

satisfies every clause. For example, the eight clauses have the values

$$ \begin{array}{c|c} \text{clause}&\text{value under }0011\ \hline 123&1\ 2\bar{3}4&1\ 341&1\ 4\bar{1}2&1\ \bar{1}23&1\ 234&1\ \bar{3}4\bar{1}&1\ \bar{4}\bar{1}2&1 \end{array} $$

because $x_3=x_4=1$ and $x_1=x_2=0$.

A complete enumeration of the $2^4=16$ possible assignments gives the satisfying assignments

$$ 0011,\quad0101,\quad0110,\quad0111,\quad1100,\quad1101,\quad1111 . $$

Hence the displayed formula in (6) has seven satisfying assignments, not a unique satisfying assignment.

For the second part, omitting the use of clauses $C_5=\bar{1}23$ and $C_8=\bar{4}\bar{1}2$ in the proof of uniqueness cannot establish uniqueness for the displayed formula. If those clauses are removed from the conjunction entirely, the remaining six clauses have the satisfying assignments

$$ 0011,\quad0101,\quad0110,\quad0111,\quad1001,\quad1011,\quad1100,\quad1101,\quad1111, $$

so uniqueness still fails.

Therefore the exercise cannot be solved as written with the clause set (6). The claim in the surrounding text that the set $R$ is unsatisfiable and the claim in exercise 7 that it has a unique satisfying assignment refer to a different clause set or contain a transcription error.

$$ \boxed{\text{For the displayed clauses (6), there are seven satisfying assignments, and the uniqueness claim is false.}} $$