Normal Forms: CNF and DNF
What you'll learn: How to standardize any logical proposition into two universal formats that make comparing and simplifying expressions much easier.
What Are Normal Forms?
Just like you can write the number fifteen as "15", "XV", or "1111₂", logical propositions can be written in different but equivalent ways. Normal forms are standardized formats that make it easier to compare, simplify, and work with logical expressions systematically.
The two most important normal forms are:
Conjunctive Normal Form (CNF)
CNF is like a "product of sums" — you AND together several OR clauses.
Think of it as a checklist where every item must be satisfied, but each item offers choices:
Structure: (A ∨ B) ∧ (C ∨ D ∨ E) ∧ (F)
Translation: "(A or B) AND (C or D or E) AND F"
Each parenthesis contains ORs (disjunctions), and you connect them all with ANDs (conjunctions).
Disjunctive Normal Form (DNF)
DNF is the opposite — a "sum of products." You OR together several AND clauses.
Think of it as multiple complete scenarios, where satisfying any one is enough:
Structure: (A ∧ B) ∨ (C ∧ D ∧ E) ∨ (F)
Translation: "(A and B) OR (C and D and E) OR F"
Each parenthesis contains ANDs, and you connect them all with ORs.
Why They Matter
Any proposition can be converted to CNF or DNF using the logical laws you've learned (distributive, De Morgan's, etc.). Once in normal form, it's easier to:
- Compare two expressions for equivalence
- Design digital circuits
- Perform automated reasoning
Key Takeaway: CNF is ANDs of OR-clauses; DNF is ORs of AND-clauses. Every logical proposition can be rewritten into these standard formats using the equivalence laws you already know.