Jump to content

Disjunctive normal form

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by B4hand (talk | contribs) at 14:26, 19 August 2002 (lower cased link). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Disjunctive Normal Form or DNF is a method of standardizing and normalizing logical formulas. A logical formula is considered to be in DNF if and only if it is a single disjunction of conjunctions. More simply stated, the outermost operators of the formula are all ORs, and there is only one level of nesting allowed, which may only can literals or conjunctions of literals. For example, all of the following formulas are in DNF:

A ∨ B
A
(A ∧ B) ∨ C
(A ∧ ¬B &and ¬C) &or (¬D ∧ E ∧ F)

However, the following formulas are not in DNF:

¬(A ∨ B) — NOT is the outermost operator
A ∨ (B ∧ (C &or D)) — an OR is nested within an AND

Note that all logical formulas can be converted into disjunctive normal form. A formal grammar for DNF is as follows:

  1. o -> ∨
  2. a -> ∧
  3. n -> ¬
  4. A -> B
  5. A -> A o B
  6. B -> C
  7. B -> (B a C)
  8. C -> D
  9. C -> nD
  10. D -> term

See Also: