TAOCP 7.2.2.2 Exercise 7

We restate the system of clauses: \begin{aligned} C_1 &= x_1 \vee x_2 \vee x_3,\\ C_2 &= x_2 \vee \neg x_3 \vee x_4,\\ C_3 &= x_3 \vee x_4 \vee x_1,\\

taocpmathematicsalgorithmsvolume-4medium

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: yes
Solve time: 3m04s

We restate the system of clauses:

$$ \begin{aligned} C_1 &= x_1 \vee x_2 \vee x_3,\ C_2 &= x_2 \vee \neg x_3 \vee x_4,\ C_3 &= x_3 \vee x_4 \vee x_1,\ C_4 &= x_4 \vee \neg x_1 \vee x_2,\ C_5 &= \neg x_1 \vee x_2 \vee x_3,\ C_6 &= x_2 \vee x_3 \vee x_4,\ C_7 &= \neg x_3 \vee x_4 \vee \neg x_1,\ C_8 &= \neg x_4 \vee \neg x_1 \vee x_2. \end{aligned} $$

We determine all satisfying assignments directly from constraints.

1. First structural consequences

From $C_2$ and $C_6$, the variable $x_2$ plays a dominant role. We analyze by cases on $x_2$.

Case 1: $x_2 = 1$

With $x_2 = 1$, the clauses simplify as follows:

  • $C_1, C_4, C_5, C_6, C_8$ are automatically satisfied.
  • Remaining constraints reduce to:

$$ C_2: \neg x_3 \vee x_4,\quad C_3: x_1 \vee x_3 \vee x_4,\quad C_7: \neg x_3 \vee x_4 \vee \neg x_1. $$

We split further on $x_4$.

Subcase 1a: $x_4 = 1$

Then:

  • $C_2, C_3, C_7$ are all satisfied regardless of $x_1,x_3$, except that no clause forces additional constraints.

Hence $x_1,x_3$ are free.

This gives two assignments:

$$ (0,1,0,1), \quad (0,1,1,1), $$

and also $(1,1,0,1)$, $(1,1,1,1)$. However, we must check $C_7$ carefully:

$C_7 = \neg x_3 \vee x_4 \vee \neg x_1$ is always true since $x_4=1$. So all four combinations with $x_2=1, x_4=1$ satisfy all clauses.

Thus we already have four satisfying assignments in this case:

$$ (0,1,0,1), (0,1,1,1), (1,1,0,1), (1,1,1,1). $$

Subcase 1b: $x_4 = 0$

Then $C_2$ becomes $\neg x_3$, so $x_3 = 0$.

Now:

  • $C_3$ forces $x_1 = 1$.
  • $C_7$ becomes true since $\neg x_1$ must compensate, but $x_1=1$ so we need $x_3=0$, already satisfied.

Thus we obtain:

$$ (x_1,x_2,x_3,x_4) = (1,1,0,0). $$

This is a valid solution.

Case 2: $x_2 = 0$

From $C_6$, we require:

$$ x_3 \vee x_4 = 1. $$

From $C_8$:

$$ \neg x_4 \vee \neg x_1 = 1. $$

From $C_4$:

$$ x_4 \vee \neg x_1 = 1. $$

Combining the last two gives:

$$ x_4 \vee \neg x_1 = 1 \quad \text{and} \quad \neg x_4 \vee \neg x_1 = 1, $$

which implies $\neg x_1 = 1$, hence:

$$ x_1 = 0. $$

Now $C_3$ becomes:

$$ x_3 \vee x_4 = 1, $$

which is already required by $C_6$.

We split on $x_4$.

Subcase 2a: $x_4 = 1$

Then $x_1=0$. Check remaining constraints:

  • $C_1$ forces $x_3 = 1$.
  • All other clauses are satisfied.

Thus we get:

$$ (0,0,1,1). $$

Subcase 2b: $x_4 = 0$

Then $C_6$ forces $x_3 = 1$, and $x_1=0$.

Check all clauses:

  • $C_2$: satisfied by $\neg x_3$ false, but $x_4=0$, so this case forces consistency check: $C_2$ becomes $\neg x_3$, which is false since $x_3=1$. Hence this subcase is impossible.

So no solution here.

2. Complete list of satisfying assignments

All satisfying assignments are:

$$ (0,1,0,1),\quad (0,1,1,1),\quad (1,1,0,1),\quad (1,1,1,1),\quad (1,1,0,0),\quad (0,0,1,1). $$

So the system does not have a unique satisfying assignment.

3. Conclusion for part (a)

The satisfying assignments are not unique; in fact there are multiple solutions, including:

$$ (0,1,0,1), (0,1,1,1), (1,1,0,0), (0,0,1,1), \text{etc.} $$

4. Part (b): uniqueness claim

The claim that the system becomes uniquely determined when excluding $C_5$ and $C_8$ is false.

The reduced system still admits multiple satisfying assignments, and even the full system admits several assignments. Therefore no uniqueness result can be derived from the remaining clauses alone.

In particular, assignments with different values of $x_2$, $x_1$, and $x_4$ all satisfy the constraints, so no single assignment is forced.

Final conclusion

The original proof fails because it incorrectly inferred forced variable assignments (notably $x_4=1$). A correct analysis shows that the clause system is underconstrained and admits multiple satisfying assignments, so no uniqueness statement holds for part (b).