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.

Answer 3

Assume we have a fine set of atoms $A = \{ a_1, \dots, a_n \}$ (i.e. think of it as statements that are true or false, like a = "the rocks are made of material". Then what we want to show is:

Given any proposition $p$ (made up of logical connectives, atoms and other propositions) is equivalent to a disjunction $p_1 \lor \dots \lor p_k $ where each disjunct $p_i = a^{\epsilon_1}_1 \land \dots \land a^{\epsilon_n}_n$ and $a^1 := a$ and $a^{-1} := \neg a$.

So given a proposition $p$ we can transform it to another in "disjunctive normal form" as defined above. The idea is to show that there exists a proposition of that form and is equivalent to the original one. To show that its equivalent to the original one we need to show that they return the same truth tables, so with any truth assignment to the atoms they return the same truth value.

Notice that a row of a truth table only containing the atoms is just a truth assuagement $t:A \to \{0,1\}$ ("state of the world" since it assigns values to the atoms/building blocks). This is key because it means that we only have to go through the rows (truth assignments) that set the proposition $p$ true and essentially "encode" that in $p_i = a^{\epsilon_1}_1 \land \dots \land a^{\epsilon_n}_n$.

So list all such truth assignments $t_1, \dots, t_k$. Consider going through them and consider the current one we are considering be $t_j$. With this we will define $p_i = a^{\epsilon_1}_1 \land \dots \land a^{\epsilon_n}_n$ that is true when $t_j$ is true. i.e. $t_j(p_j) = 1$. We do this my setting $\epsilon_i = 1$ if $t_j(a_i) =1$ and $\epsilon_i = -1$ if $t_j(a_i) = 0$. This just picks up the fact that $p_j$ is 1 with the current row of the truth table we are considering. Since $p$ is a disjunction (OR's) then it must be that $t_j(p) = 1 $ since $t_j(p_j) = 1$. So $t(p) = 1 \iff t = t_j$ (its not hard to show it will be zero at the right places since none of these will be true for the remaining rows of the truth table). In fact if you notice you can actually make the notation more compact by doing:

$$ p_j = a^{2t_j(a_1) - 1}_1 \land \dots \land a^{2t_j(a_n) - 1}_n$$

since $\epsilon_i = 2t(a_i) - 1$.

Which completes the proof.

Now note that this argument is not special to atoms. If instead you had propositions instead of atoms, you can still write a (fake) "truth table" with propositions but instead you'd treat those propositions as your "building blocks" for the above algorithm.