Negative Normal Form

Negative normal form is a structured way of showing formulas, restricting logical connectives to only include $\wedge ,\vee$ and $\neg$, and only allowing direct negation. It can be used to then convert to conjunctive normal form (CNF).

Definition §

Negative Normal Form (CNF)

A formula, $P$ is in negative normal form iff:

• The only connectives used are $\wedge ,\vee ,\neg$ (no $\to$ and $\leftrightarrow$)
• All negations ($\neg$) can only directly affect an atom (so we can’t do something like $\neg (A\wedge B)$

Converting to NNF §

The procedure for converting a formula to NNF is the same for both propositional logic and predicate logic:

1. Convert $\leftrightarrow$ to $\to$ and $\wedge$ :

2. Convert $\to$ to $\neg$ and $\vee$:

3. Make negations direct (push ‘inwards’) using De Morgan’s:

4. Eliminate $\neg \neg$s:

Theorems §

T1: In propositional logic, every proposition has an logically equivalent NNF

Examples §

#todo

$$(\neg P\wedge (\neg Q\to R))\leftrightarrow S$$

1. Convert $\leftrightarrow$ to $\to$ and $\wedge$:

$$(\neg P\wedge (\neg Q\to R)\to S)\wedge (S\to (\neg P\wedge (\neg Q\to R)))$$

2. Convert $\to$ to $\neg$ and $\vee$:

$$(\neg P\wedge (\neg Q\to R)\to S)\wedge (S\to (\neg P\wedge (\neg Q\to R)))$$