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))
The above three formulas are respectively equivalent to the following three formulas that are in conjunctive normal form:
¬B ∧ ¬C
(A ∨ C) ∧ (B ∨ C)
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:
Search Encyclopedia

Featured Article
