Negation normal form

A logical formula is in negation normal form (NNF) if the negation operators only appear in it directly via atomic statements.

A formula in negation normal form can be converted into conjunctive (CNF) or disjunctive normal form (DNF) by applying the distributive laws.

In general, there is more than one negation normal form for any propositional formula. This can be illustrated by realizing that every conjunctive and every disjunctive normal form is also a negation normal form at the same time.

method

In classical logic , any formula can be put into this form by doing the following:

• The material implications and biconditional elements occurring in it are resolved by means of the equivalence laws that apply to them. Examples are (see also: Implication ):
  • ${\displaystyle P\rightarrow Q\equiv \neg P\lor Q}$
  • ${\displaystyle \neg (P\rightarrow Q)\equiv P\land \neg Q}$
  • ${\displaystyle P\leftrightarrow Q\equiv (P\land Q)\lor (\neg P\land \neg Q)}$
• By means of De Morgan's laws, one shifts the negations inward and at the same time eliminates any double negations that may occur

example

The following formula is given:
${\displaystyle \neg (A\rightarrow (B\wedge \neg (C\vee D)))}$

The formula is not in NNF because negations occur before non-atomic sub-formulas. This is the case both in front of the outer bracket and within (before ). Therefore one pulls the negation inwards and reshapes: ${\displaystyle (C\vee D)}$
${\displaystyle \neg (A\rightarrow (B\wedge \neg (C\vee D)))\equiv (A\wedge \neg (B\wedge \neg (C\vee D)))}$

Since complex formulas are also negated in this formula, the following is further transformed:
${\displaystyle (A\wedge (\neg B\vee \neg \neg (C\vee D)))}$

Now the double negation that has occurred has to be eliminated:
${\displaystyle (A\wedge (\neg B\vee (C\vee D)))}$

The NNF has thus been reached because it only occurs before atomic partial formulas (i.e. variables). ${\displaystyle \neg }$