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:
¬(B ∨ C)
(A ∧ B) ∨ C
A ∧ (B ∨ (D ∧ E))
¬B ∧ ¬C
(A ∨ C) ∧ (B ∨ C)
A ∧ (B ∨ D) ∧ (B ∨ E)
(X1 ∧ Y1) ∨ (X2 ∧ Y2) ∨ ... ∨ (Xn ∧ Yn)
See Also: