TAOCP 7.1.1 Exercise 18

The reviewer’s objections identify the key issue: the original proof tries to assign values to variables separately for each clause literal, which does not define a single consistent valuation.

taocpmathematicsalgorithmsvolume-4hard

Section 7.1.1: Boolean Basics

Exercise 18. ▶ [30] [30] Let $u_1\wedge\cdots\wedge u_k$ be an implicant in a disjunctive normal form for a Boolean function $f$, and let $v_1\vee\cdots\vee v_p$ be a clause in a conjunctive normal form for the same function. Prove that $v_j = u_i$ for some $i, j$.

Verified: yes
Solve time: 4m

The reviewer’s objections identify the key issue: the original proof tries to assign values to variables separately for each clause literal, which does not define a single consistent valuation. The corrected argument must construct one global valuation and verify consistency variable by variable.

Corrected solution

Let

$$ u_1 \wedge \cdots \wedge u_k $$

be a term in a DNF for a Boolean function $f$, and let

$$ v_1 \vee \cdots \vee v_p $$

be a clause in a CNF for the same function $f$. Each $u_i$ and $v_j$ is a literal.

We prove that there exist indices $i,j$ such that $v_j = u_i$.

Step 1. Assume the contrary

Assume that for all $i,j$,

$$ v_j \ne u_i. $$

We will construct a single valuation that makes all $u_i$ true and all $v_j$ false, contradicting that both forms define the same function.

Step 2. Construct a valuation satisfying the DNF term

Define a valuation on variables as follows.

For each variable $x$:

  • If $x = u_i$ for some $i$, set $x = 1$.
  • If $\bar{x} = u_i$ for some $i$, set $x = 0$.
  • If neither $x$ nor $\bar{x}$ appears among the $u_i$, leave $x$ temporarily undefined.

This is consistent because a variable cannot appear both as $x$ and $\bar{x}$ in the same conjunction; otherwise the term would be identically false.

Now extend the assignment to all remaining variables in the following way:

For each variable $x$ not fixed above, assign a value that will make every literal in the clause false:

  • If some clause literal is $x$, set $x = 0$.
  • If some clause literal is $\bar{x}$, set $x = 1$.
  • If neither occurs in the clause, assign $x$ arbitrarily.

This is well-defined because a clause cannot contain both $x$ and $\bar{x}$; such a clause would be a tautology and could be removed without changing the CNF.

Step 3. Verify that all $u_i$ remain true

We check that the extension does not break any $u_i$.

Fix a variable $x$.

  • If $x$ is forced by the term, its value is fixed to satisfy that literal.
  • If $x$ is not in the term, changing $x$ does not affect any $u_i$.

Thus every $u_i$ remains true under the final assignment, so

$$ u_1 \wedge \cdots \wedge u_k = 1. $$

Hence $f = 1$ under this valuation.

Step 4. Show every clause literal is false

Fix any clause literal $v_j$.

Case 1: $v_j = x$

By construction, either:

  • $x$ appears in the term as $x$, so $x = 1$, but this would imply $v_j = u_i$, contradicting the assumption, or
  • $x$ does not appear in the term, in which case we explicitly set $x = 0$.

Thus $v_j = 0$.

Case 2: $v_j = \bar{x}$

Similarly:

  • If $\bar{x}$ appears in the term, then $v_j = u_i$, contradiction.
  • Otherwise, either $x$ is fixed to $0$ or assigned $1$ to falsify $\bar{x}$, so in all cases $\bar{x} = 0$.

Thus $v_j = 0$.

Since every clause literal is false, we have

$$ v_1 \vee \cdots \vee v_p = 0. $$

So the CNF evaluates to $f = 0$.

Step 5. Contradiction

We have constructed a valuation such that:

  • The DNF term is true, so $f = 1$.
  • The CNF clause is false, so $f = 0$.

This contradicts that both expressions define the same Boolean function $f$.

Step 6. Conclusion

The assumption that no $v_j$ equals any $u_i$ is false. Therefore, there exist indices $i,j$ such that

$$ v_j = u_i. $$

This completes the proof.