Negation normal form

A logical formula is in negation normal form ( NNF ) if negation operators occur in it only directly over atomic propositions.

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

In general, there are more than a negation normal form for any propositional formula. This can be illustrated by one bears in mind that each conjunctive and disjunctive normal form, each is at the same time a negation normal form.

Method

Classical logic can be accommodated in this form each formula, by proceeding as follows:

  • Dissolve occurring in their substantive implications and biconditional on means of applying to these equivalence laws. Examples are:

Example

Given the following formula:

The formula is not in NNF because negations occur in front of non-nuclear sub-formulas. This is the case both before and within the outer clip (pre). Therefore, considering the negation inwards and forms to: [Note 1]

Since also in this formula complex formulas are still negative, is further transformed into:

Now is still the case that occurred double negation to eliminate:

Thus, the NNF is achieved because only before atomic sub-formulas (ie, variables) occurs.

Comments

  • Mathematical Logic
596724
de