[Math] 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.