Every sentence in propositional logic can be written in Conjunctive Normal Form

Question

While reading through Artificial Intelligence: A Modern Approach by Stuart Russell and Peter Norvig, I came upon the following question:

Any propositional logic sentence is logically equivalent to the assertion that each possible world in which it would be false is not the case. From this observation, prove that any sentence can be written in CNF.

Does anyone have a reference or a proof that Every sentence in propositional logic can also be written in Conjunctive Normal Form?

My (lousy) attempt was that since CNF requires $\forall x\ \mathit{Clauses}(x)$, and propositional logic implies that all sentences it declares must be true for the statement to hold true, then one implies you can convert it?

Answer 1

Wikipedia's article on conjunctive normal form gives an idea of why a sentence is logically equivalent to its conjunctive normal form:

Every propositional formula can be converted into an equivalent formula that is in CNF. This transformation is based on rules about logical equivalences: the double negative law, De Morgan's laws, and the distributive law.

I think that what Russell and Norvig are getting at (the question is sort of vague, in my opinion) is that if you have a sentence like

$$ ((A \lor B) \to C) \land \lnot(D \land E) \tag{1}$$

you could then ask "in what cases would this sentence be false?" In this case, it's when

• One side of the conjunction is false, which means that
• • either $(A \lor B) \to C$ is false, which means that
• • • $A$ or $B$ is true and $C$ is false, which means that
• • • • either $A$ is true and $C$ is false
• • • • or $B$ is true and $C$ is false
• • or $\lnot(D \land E)$ is false, which means that
• • • $D$ is true and $E$ is true

From those you can read off a disjunctive normal form:

$$ (A \land \lnot C) \lor (B \land \lnot C) \lor (D \land E) \tag{2} $$

Those are all the cases where $(1)$ is false. If we negate $(2)$, it is like the "assertion that each possible world in which it would be false is not the case," and we get

$$ \lnot( (A \land \lnot C) \lor (B \land \lnot C) \lor (D \land E) ) \tag{3} $$

which by De Morgan's laws is

$$ \lnot(A \land \lnot C) \land \lnot(B \land \lnot C) \land \lnot(D \land E) \tag{4} $$

and then

$$ (\lnot A \lor C) \land (\lnot B \lor C) \land (\lnot D \lor \lnot E) \tag{6} $$

which is conjunctive normal form for $(1)$. So, by enumerating all the ways that a sentence could be false, turning that into a single sentence, negating it, and applying De Morgan's laws, we have a logically equivalent sentence in conjunctive normal form.

Answer 2

The quote you provided is the essence of the proof. Given a sentence with $n$ propositional variables, there are some (at most $2^{n}$) assignments of truth values ("possible worlds") that evaluate the sentence to FALSE. For each one of these assignments, disjunct the variables that are assigned FALSE and disjunct to those the negation of the variables that are assigned TRUE. Now conjunct all of those disjuncts.