3. Conjunctive Normal Form

Conjunctive Normal Form

Conjunctive Normal Form

Conjunctive Normal Form (CNF) is when a formula: ?

• contains no connectives other than conjunction, disjunction and negation.
• only applies negation to propositional symbols (within literals)
• no conjunction appears in a sub-formula of a formula whose main connective is disjunction

Alternatively, you can see it as a conjunction of one or more formulae, each of which is a disjunction of one or more literals.

Link to original

Rewrite Rules

CNF Rewrite Rules

To obtain CNF, we can perform a series of transformations:

$$\begin{array}{rl}F\to G& \Rightarrow \neg F\vee G\\ F⟺G& \Rightarrow (F\to G)\vee (G\to F)\\ \neg (F\vee G)& \Rightarrow \neg F\wedge \neg G\\ \neg (F\wedge G)& \Rightarrow \neg F\vee \neg G\\ \neg \neg F& \Rightarrow F\\ F\vee (G\wedge H)& \Rightarrow (F\vee G)\wedge (F\vee H)\\ (F\wedge G)\vee H& \Rightarrow (F\vee H)\wedge (G\vee H)\end{array}$$Link to original

Truth Table to CNF

We cannot go directly from a truth table to CNF, as we will end up with DNF. We can use rules such as De Morgan’s Law to fix our formula.

Suppose we are given $P⟺Q$:

interpretation	$p$	$q$	$p⟺q$
$v_0$	0	0	1
$v_1$	0	1	0
$v_2$	1	0	0
$v_3$	1	1	1

The highlighted values make the formula false.

So when the formula $(\neg P\wedge Q)\vee (P\wedge \neg Q)$ is true, the formula is false, so we can find when $P⟺Q$ is true when the formula we just found is false.

$$\neg ((\neg P\wedge Q)\vee (P\wedge \neg Q))=\boxed{(P\vee \neg Q)\wedge (\neg P\vee Q)}$$

We can manipulate the formula to find it in CNF.