1
DNF is read off the true rows
For each row where the formula is true, write the conjunction that describes that row; join them with ∨. The result is equivalent by construction.
Lesson · Logic and Proof · Propositional logic
Normal Forms and Boolean Algebra
Disjunctive and conjunctive normal form give every formula a canonical shape, readable straight off its truth table. The same algebra runs digital circuits, which is why ∧, ∨ and ¬ are AND, OR and NOT gates.
DNF (p ∧ ¬q) ∨ (¬p ∧ q) an OR of ANDs — read off the TRUE rows
CNF (p ∨ q) ∧ (¬p ∨ ¬q) an AND of ORs — read off the FALSE rows
Every formula has both. {∧, ∨, ¬} is functionally complete.
Two shapes, one formula
Core ideas
What this lesson establishes
A normal form is a standard shape. Its value is that any formula can be put into it, so two formulas can be compared structurally.
2
CNF is read off the false rows
For each false row, write a disjunction ruling that row out; join them with ∧. This is the form SAT solvers consume.
3
Three connectives suffice
{∧, ∨, ¬} can express every truth function. So can {∧, ¬} alone, and remarkably so can NAND by itself.
The material
Canonical forms
How to produce each from a truth table, and why it always works.
Definition · Literal, clause, term
A literal is a variable or its negation (p, ¬q). A clause is a disjunction of literals; a term is a conjunction of literals.
Definition · Disjunctive normal form
A formula is in DNF when it is a disjunction of terms — an OR of ANDs of literals.
Definition · Conjunctive normal form
A formula is in CNF when it is a conjunction of clauses — an AND of ORs of literals.
Theorem · Every formula has a DNF and a CNF
Given any truth table, an equivalent DNF and an equivalent CNF can be written down directly from it.
For DNF: take each row where the formula is true, and write the conjunction of literals that is true in exactly that row — p if p is T there, ¬p if it is F. Each such term is true in one row and false in every other. Their disjunction is therefore true in exactly the rows where the original is true.
For CNF, do the same with the false rows and take the complementary clause for each: the clause is false in exactly that row and true everywhere else, so the conjunction is false in exactly the rows where the original is false.
If the formula has no true rows it is a contradiction and its DNF is empty, conventionally F; if it has no false rows its CNF is T.
□
Example · Reading DNF off a table
Suppose a formula in p, q is true exactly in rows TF and FT. Its DNF is (p ∧ ¬q) ∨ (¬p ∧ q), which is exactly p ⊕ q — and this is how any truth function whatever gets a formula.
Functional completeness
Definition · Functionally complete
A set of connectives is functionally complete if every truth function can be expressed using only those connectives.
{∧, ∨, ¬} is functionally complete, by the theorem above. {∧, ¬} is too, because De Morgan gives p ∨ q ≡ ¬(¬p ∧ ¬q); symmetrically so is {∨, ¬}. What is striking is that a single connective can suffice: NAND, written p ↑ q ≡ ¬(p ∧ q), expresses negation as p ↑ p and conjunction as (p ↑ q) ↑ (p ↑ q).
The same algebra, in hardware
Replace T with 1, F with 0, ∧ with AND, ∨ with OR and ¬ with NOT, and every law of “Logical Equivalence” becomes a fact about digital circuits. A formula in DNF is a two-level circuit: a layer of AND gates feeding one OR gate. That correspondence is why NAND being functionally complete matters commercially — a chip can be built from one kind of gate.
The two-level DNF circuit is fast and often enormous. Minimising it — finding the smallest equivalent formula — is its own hard problem, and is what Karnaugh maps and the Quine–McCluskey algorithm address.
Interactive
Truth table
Every assignment, evaluated
Method
Producing a normal form
From a formula, either go through the table or push negations inward.
1
Build the truth table
The table route always works and needs no cleverness. Its cost is 2ⁿ rows, and its output may be far from minimal.
2
For DNF, take the true rows
One term per true row, each literal positive where the variable is T and negated where it is F. Join with ∨.
3
For CNF, take the false rows
One clause per false row, each literal negated relative to the row. Join with ∧. Getting this polarity backwards is the standard slip.
4
Or transform algebraically
Eliminate → and ↔, push negations in with De Morgan until they sit on variables, then distribute. This can be much shorter, and can also blow up.
Normal forms
Score 0 / 0Choose the answer you can justify.
CNF of p → (q ∧ r)
The algebraic route, since the table would be eight rows.
p → (q ∧ r)
≡ ¬p ∨ (q ∧ r) conditional law
≡ (¬p ∨ q) ∧ (¬p ∨ r) distribution
Two clauses, each a disjunction of literals — this is CNF.
Check one row: p = T, q = T, r = F
original T → (T ∧ F) = T → F = F
CNF (F ∨ T) ∧ (F ∨ F) = T ∧ F = F agree
Spot-checking a single row does not prove the equivalence — the chain of named laws does that. The check is there to catch a slip in the chain, which is a different job and worth doing every time.
Common mistakes
1
Getting the polarity backwards in CNFFor a false row, a variable that is T in that row contributes the NEGATIVE literal. Reversing this produces a formula false in all the wrong places.
2
Assuming the canonical form is minimalThe canonical DNF of a formula true in seven of eight rows has seven terms of three literals each. The same formula is ¬p ∨ ¬q ∨ ¬r — its one false row, ruled out by one clause. Canonical and small are different goals.
3
Believing conversion is always cheapConverting CNF to DNF can multiply the size exponentially. That the two forms always exist says nothing about the cost of getting between them.
Check your understanding
✓
Finish when you can write both normal forms of a three-variable formula from its table.
Take (p ⊕ q) ∧ r, build the table, and produce the canonical DNF and CNF. Check the term count against the number of true and false rows — they must match exactly.
Note: Algorithms and Complexity's discussion of NP-completeness uses CNF-SAT specifically. The restriction to CNF costs nothing there, because any formula can be converted to an equisatisfiable CNF in linear time by naming its subformulas — the Tseytin transformation.