Encyclopedia > Disjunctive normal form

  Article Content

Disjunctive normal form

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 contain literals[?] or conjunctions of literals. For example, all of the following formulas are in DNF:

 A ∨ B
 A
 (A ∧ B) ∨ C
 (A ∧ ¬B ∧ ¬C) ∨ (¬D ∧ E ∧ F)

However, the following formulas are not in DNF:

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

Note that all logical formulas can be converted into disjunctive normal form. However, in some cases conversion to DNF can lead to an exponential explosion of the formula. For example, in DNF form, logical formulas of the following form have 2^n terms:

(X1 ∨ Y1) ∧ (X2 ∨ Y2) ∧ ... ∧ (Xn ∨ Yn)

The following is a formal grammar for DNF:

  1. <or> -> ∨
  2. <and> -> ∧
  3. <not> -> ¬
  4. <disjunct> -> <conjunct>
  5. <disjunct> -> <disjunct> <or> <conjunct>
  6. <conjunct> -> <literal>
  7. <conjunct> -> (<conjunct> <and> <literal>)
  8. <literal> -> <term>
  9. <literal> -> <not><term>

Where <term> is any variable.

See Also:



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
242

...   Contents 242 Centuries: 2nd century - 3rd century - 4th century Decades: 190s 200s 210s 220s 230s - 240s - 250s 260s 270s 280s 290s Years: 237 238 239 ...

 
 
 
This page was created in 23.1 ms