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