Encyclopedia > Conjunctive normal form

  Article Content

Conjunctive normal form

Conjunctive Normal Form or CNF is a method of standardizing and normalizing formulas in Boolean logic. A logical formula is considered to be in CNF if and only if it is a single conjunction of disjunctions. Thus all simple conjunctions are in CNF, but also all simple disjunctions are degenerately in CNF. For example, all of the following formulas are in CNF:

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

But the following are not:

  1. ¬(B ∨ C)
  2. (A ∧ B) ∨ C
  3. A ∧ (B ∨ (D ∧ E))

The above three formulas are respectively equivalent to the following three formulas that are in conjunctive normal form:

  1. ¬B ∧ ¬C
  2. (A ∨ C) ∧ (B ∨ C)
  3. A ∧ (B ∨ D) ∧ (B ∨ E)

Note that all logical formulas can be converted into conjunctive normal form, thus when making proofs on formulas or on the structure of formulas it is often convenient to assume that everything is in CNF. However, in some cases conversion to CNF can lead to an exponential explosion of the formula. For example, in CNF form, logical formulas of the following form have 2^n terms:

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

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
Anna Karenina

... the editor, Mikhail Katkov, over issues that arose in the final installment. Consequently, the novel's first complete appearance was in book form. Relate ...

 
 
 
This page was created in 38.1 ms