1.3Normal forms, tautology and satisfiability
The idea
A formula is a tautology if true in every row, a contradiction if true in none, and satisfiable if true in at least one. Normal forms write it as an OR of ANDs (DNF) or an AND of ORs (CNF) straight from the truth table.
Think of it like this: A bouncer's list: DNF lists every allowed guest (each true row), CNF lists every excluded type (each false row).
Why it exists
Satisfiability is the first NP-complete problem, and counting Boolean functions or minterms comes up as a direct numeric question.
How it works
- Read off the true rows: each gives a minterm; OR them for the DNF.
- Read off the false rows: each gives a maxterm (flip every literal); AND them for the CNF.
- Number of Boolean functions of n variables: 2^(2ⁿ) (each of the 2ⁿ rows can be 0 or 1).
- Functionally complete sets: {¬,∧}, {¬,∨}, {→,¬}, NAND, NOR. {∧,∨} alone is not.
Worked example: How many Boolean functions of 3 variables?
There are 2³ = 8 rows and each can be 0 or 1, so 2⁸ = 256 functions.
Now play with it
- →Load "majority(p, q, r)" and read its minterms.
- →Switch to p ⊕ q and compare its DNF with its CNF.
| p | q | r | value |
|---|---|---|---|
| F | F | F | F |
| F | F | T | F |
| F | T | F | F |
| F | T | T | T |
| T | F | F | F |
| T | F | T | T |
| T | T | F | T |
| T | T | T | T |
| Set of connectives | Functionally complete? | Why |
|---|---|---|
| {¬, ∧} | ✓ | p ∨ q ≡ ¬(¬p ∧ ¬q) |
| {¬, ∨} | ✓ | p ∧ q ≡ ¬(¬p ∨ ¬q) |
| {¬, →} | ✓ | p ∨ q ≡ ¬p → q |
| {NAND} alone | ✓ | ¬p ≡ p NAND p; then build ∧ |
| {NOR} alone | ✓ | dual of NAND |
| {∧, ∨} | ✗ | every formula stays true when all inputs are true: ¬ is impossible |
| {→} | ✗ | cannot express ¬ |
| {↔, ⊕} | ✗ | every formula keeps the parity of its inputs |
Boolean functions of n variables: 2^(2ⁿ). Two variables: 16. Three variables: 256.
Check yourself
How many different Boolean functions exist for 2 variables?
Exam notes (the dense version)
A formula is a tautology (valid) if true in every row, a contradiction if true in none, satisfiable if true in at least one. DNF = OR of ANDs (one minterm per true row); CNF = AND of ORs (one maxterm per false row). SAT is NP-complete, but 2-SAT is in P. There are 2^(2ⁿ) Boolean functions of n variables. {∧,¬}, {∨,¬}, {→,¬}, {NAND} and {NOR} are functionally complete; {∧,∨} is not.
Previous year questions: Propositional & First-Order Logic (25)
PYQs are grouped by topic, so this is the full set for Propositional & First-Order Logic; try the ones that match this subtopic. Open all 25 on the topic page.