Equivalence of Formulae and Their Normal Forms

Definitions §

Conjunctive Normal Form (CNF) §

A formula is in CNF if it is of the form: $A_1\wedge A_2\wedge ...\wedge A_m$ where each $A_i$ is of the form: $B_1\vee B_2\vee ...\vee B_m$ where each $B_i$ is $\top$, $\perp$, a propositional variable or the negation of a propositional variable, and $m\ge 1$, $n\ge 1$.

More simply, a formula is in CNF if it is a conjunction of disjunctions of atoms.

Disjunctive Normal Form (DNF) §

This is similar to CNF, but reversed. That is, a formula in DNF is a disjunction of conjunctions of atoms.

Normalising Formulae §

All propositional formulae can be represented in CNF or DNF. To find a semantically equivalent formula in CNF, the following steps can be followed:

1. Replace any $\to$ and $\leftrightarrow$ connectives with their equivalents according to the laws:
   • $A\to B\equiv \neg A\vee B$
   • $A\leftrightarrow B\equiv (\neg A\vee B)\wedge (A\vee \neg B)$
2. Use De Morgan’s laws to push negations as far inwards as possible.
3. Eliminate all double negations.
4. Eliminate all conjunctions inside disjunctions, by pushing conjunctions inwards over disjunctions:

$$(A_1\wedge A_2)\vee (B_1\wedge B_2)$$ $$\equiv (A_1\vee B_1)\wedge (A_1\vee B_2)\wedge (A_2\vee B_1)\wedge (A_2\vee B_2)$$

• This is an application of the distributivity law $A\wedge (B\vee C)\equiv (A\wedge B)\vee (A\wedge C)$

Following steps 1-3, then swapping $\wedge$ and $\vee$ in step 4 will result in a formula in DNF instead of CNF.

Exercise Sheet §