TAOCP 7.2.2.2 Exercise 10

Let $F=\{C_1,\dots,C_m\}$ be a consistent set of clauses over variables $x_1,\dots,x_n$.

taocpmathematicsalgorithmsvolume-4medium

Section 7.2.2.2: Satisfiability

Exercise 10. ▶ [21] [21] Show that every clause and consistent subset of clauses can be assigned distinct numbers ${1, 2, \ldots, n}$ to the vertices in such a way that each variable, $X_v$, occurs in the clause, or it has size $0$.

Verified: no
Solve time: 4m15s

Let $F={C_1,\dots,C_m}$ be a consistent set of clauses over variables $x_1,\dots,x_n$. Consistency means there exists a truth assignment $\tau$ satisfying every clause.

We must construct a numbering (a bijection) $f:{x_1,\dots,x_n}\to{1,\dots,n}$ such that every clause either has size $0$ or contains some variable $X_v$ (i.e., some variable of the system after numbering).

Step 1: Choose a hitting set of variables

For each clause $C_j$, choose a literal $\ell_j \in C_j$ that is true under $\tau$. This is possible because $\tau$ satisfies every clause.

Let $V_0\subseteq {x_1,\dots,x_n}$ be the set of variables that appear in the chosen literals:

$$ V_0={, x_v : \ell_j \text{ is } x_v \text{ or } \bar{x}_v \text{ for some } j ,}. $$

Then every clause $C_j$ contains at least one variable from $V_0$, because it contains the chosen literal $\ell_j$. Hence $V_0$ is a vertex set that intersects every nonempty clause.

Let $V_0={v_1,\dots,v_k}$.

Step 2: Construct a numbering

Define a bijection $f:{x_1,\dots,x_n}\to{1,\dots,n}$ by assigning:

$$ f(v_i)=i \quad (1\le i\le k), $$

and extend $f$ arbitrarily to a bijection on all remaining variables ${v_{k+1},\dots,v_n}$.

This gives a valid numbering of all vertices.

Step 3: Verify invariance under relabeling

Relabeling variables by a bijection does not change clause membership structure: each clause is still a set of literals over the same underlying variables, only their names (indices) change.

Thus it suffices to verify the property in terms of the assigned numbering $f$.

Step 4: Verify the required clause property

Let $C_j$ be any clause.

  • If $C_j$ is empty, it already satisfies the requirement.
  • Otherwise, by construction of $V_0$, the clause $C_j$ contains some variable $v \in V_0$.

By definition of the numbering $f$, every variable in $V_0$ receives a number in ${1,\dots,k}$. Hence $C_j$ contains a variable $X_v$ such that $f(v)\in{1,\dots,k}$, in particular it contains a variable of the system after numbering.

This establishes that every nonempty clause contains at least one variable $X_v$, and empty clauses have size $0$, exactly as required.

Step 5: Conclusion

We have constructed a numbering $f$ of the vertices such that every clause either is empty or contains a variable $X_v$. The construction is well-defined, and the property is preserved under the relabeling because it depends only on membership of variables in clauses, not their names.

Therefore, every consistent set of clauses admits such a numbering. ∎