In Propositional Logic we decided everything with truth tables. That works, but a formula with 6 variables needs 64 rows, and a table does not tell you why two formulas agree. In school algebra you simplify (a + b)2 − b2 to a2 + 2ab using rules, without plugging in numbers. Logic has the same kind of algebra.
In this chapter we define logical equivalence, collect the standard laws (De Morgan, distributive, absorption and the rest), use them to prove and simplify formulas step by step, and then learn the normal forms: DNF, CNF and their canonical versions PDNF (sum of minterms) and PCNF (product of maxterms). We finish with functionally complete sets, including why NAND alone can build every circuit. Every equivalence and every normal form here was checked by a truth-table program.
Logical Equivalence
Two compound propositions A and B are logically equivalent, written A ≡ B (some books write A ⇔ B), if they have the same truth value in every row of the truth table. Equivalently, A ≡ B exactly when A ↔ B is a tautology.
Note that ≡ is not a connective. p ↔ q is a formula that can be true or false; A ≡ B is a statement about two formulas, saying they always agree.
Example. p → q ≡ ¬p ∨ q. Check the four rows: both are F only in the row p = T, q = F, and T in the other three. This single equivalence is the most useful one in the chapter, because it lets us remove every → and work only with ¬, ∧, ∨.
The Standard Laws
Each law below can be checked with a truth table (we did so by program). Here T denotes a tautology and F a contradiction.
Law | ∧ form | ∨ form |
|---|---|---|
Identity | p ∧ T ≡ p | p ∨ F ≡ p |
Domination | p ∧ F ≡ F | p ∨ T ≡ T |
Idempotent | p ∧ p ≡ p | p ∨ p ≡ p |
Double negation | ¬(¬p) ≡ p | (same law; it has no separate ∨ form) |
Commutative | p ∧ q ≡ q ∧ p | p ∨ q ≡ q ∨ p |
Associative | (p ∧ q) ∧ r ≡ p ∧ (q ∧ r) | (p ∨ q) ∨ r ≡ p ∨ (q ∨ r) |
Distributive | p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) | p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) |
De Morgan | ¬(p ∧ q) ≡ ¬p ∨ ¬q | ¬(p ∨ q) ≡ ¬p ∧ ¬q |
Absorption | p ∧ (p ∨ q) ≡ p | p ∨ (p ∧ q) ≡ p |
Negation (complement) | p ∧ ¬p ≡ F | p ∨ ¬p ≡ T |
Unlike ordinary arithmetic, both distributive laws hold: ∧ distributes over ∨ and ∨ distributes over ∧. (In numbers, a + (b × c) ≠ (a + b) × (a + c).)
Why De Morgan holds, in words. "Not (rich and famous)" means you are missing at least one: not rich, or not famous. "Not (tea or coffee)" means you want neither: no tea and no coffee. Negation flips ∧ and ∨.
Laws for → and ↔
Equivalence | Comment |
|---|---|
p → q ≡ ¬p ∨ q | Removes the arrow; used constantly |
p → q ≡ ¬q → ¬p | Contrapositive |
p ∨ q ≡ ¬p → q | "Either p or q" = "if not p, then q" |
p ∧ q ≡ ¬(p → ¬q) | |
¬(p → q) ≡ p ∧ ¬q | The only way an implication fails |
(p → q) ∧ (p → r) ≡ p → (q ∧ r) | Same hypothesis, conclusions join with ∧ |
(p → r) ∧ (q → r) ≡ (p ∨ q) → r | Proof by cases |
(p → q) ∨ (p → r) ≡ p → (q ∨ r) | |
(p → r) ∨ (q → r) ≡ (p ∧ q) → r | Note the ∨ on the left becomes ∧ inside |
p → (q → r) ≡ (p ∧ q) → r | Exportation |
p ↔ q ≡ (p → q) ∧ (q → p) | Definition of the biconditional |
p ↔ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q) | "Both true or both false" |
p ↔ q ≡ ¬p ↔ ¬q | |
¬(p ↔ q) ≡ p ↔ ¬q ≡ p ⊕ q |
And one non-law to remember: → is not associative. (p → q) → r and p → (q → r) differ when p = q = r = F: the first is (F → F) → F = T → F = F, the second is F → (anything) = T.
Proving Equivalences with the Laws
The method: start from one side, apply one law per step, and name the law each time, until you reach the other side. Writing the law name is not decoration; it is what makes the proof checkable, and examiners give marks for it.
Example 1: Show ¬(p ∨ (¬p ∧ q)) ≡ ¬p ∧ ¬q
¬(p ∨ (¬p ∧ q))
≡ ¬p ∧ ¬(¬p ∧ q) De Morgan
≡ ¬p ∧ (¬¬p ∨ ¬q) De Morgan
≡ ¬p ∧ (p ∨ ¬q) Double negation
≡ (¬p ∧ p) ∨ (¬p ∧ ¬q) Distributive
≡ F ∨ (¬p ∧ ¬q) Negation law (¬p ∧ p ≡ F)
≡ ¬p ∧ ¬q IdentityExample 2: Show (p ∧ q) → (p ∨ q) Is a Tautology
(p ∧ q) → (p ∨ q)
≡ ¬(p ∧ q) ∨ (p ∨ q) p → q ≡ ¬p ∨ q
≡ (¬p ∨ ¬q) ∨ (p ∨ q) De Morgan
≡ (¬p ∨ p) ∨ (¬q ∨ q) Associative and commutative
≡ T ∨ T Negation law
≡ T DominationExample 3: Show (p → q) ∧ (p → r) ≡ p → (q ∧ r)
(p → q) ∧ (p → r)
≡ (¬p ∨ q) ∧ (¬p ∨ r) p → q ≡ ¬p ∨ q (twice)
≡ ¬p ∨ (q ∧ r) Distributive (read right to left)
≡ p → (q ∧ r) p → q ≡ ¬p ∨ qExample 4: Simplify ¬(p → q) ∨ (p ∧ q)
¬(p → q) ∨ (p ∧ q)
≡ (p ∧ ¬q) ∨ (p ∧ q) ¬(p → q) ≡ p ∧ ¬q
≡ p ∧ (¬q ∨ q) Distributive
≡ p ∧ T Negation law
≡ p IdentityShowing Two Formulas Are NOT Equivalent
Laws can only prove equivalence. To disprove it, find one row where the formulas differ. That single counterexample is a complete proof. The program below tests equivalence by brute force and returns such a row when one exists.
from itertools import product
def implies(a, b):
return (not a) or b
def equivalent(f, g, n):
"""True if f and g agree on all 2**n rows."""
for row in product([False, True], repeat=n):
if f(*row) != g(*row):
return False, row # a counterexample row
return True, None
# Exportation law: p -> (q -> r) == (p and q) -> r
print(equivalent(lambda p, q, r: implies(p, implies(q, r)),
lambda p, q, r: implies(p and q, r), 3))
# Is -> associative? (p -> q) -> r vs p -> (q -> r)
print(equivalent(lambda p, q, r: implies(implies(p, q), r),
lambda p, q, r: implies(p, implies(q, r)), 3))
# Minterms and maxterms of f = (p and q) or (not p and r)
f = lambda p, q, r: (p and q) or ((not p) and r)
rows = list(product([0, 1], repeat=3)) # 000, 001, ..., 111
minterms = [i for i, row in enumerate(rows) if f(*row)]
maxterms = [i for i, row in enumerate(rows) if not f(*row)]
print("PDNF: sum of m", minterms)
print("PCNF: product of M", maxterms)Output:
(True, None)
(False, (False, False, False))
PDNF: sum of m [1, 3, 6, 7]
PCNF: product of M [0, 2, 4, 5]The second line is exactly the counterexample p = q = r = F found above. The last two lines are explained in the next sections.
The Duality Principle
The dual A* of a formula A that uses only ¬, ∧, ∨, T, F is obtained by swapping ∧ with ∨ and T with F (leaving ¬ and the variables alone). Duality principle: if A ≡ B, then A* ≡ B*.
Look back at the laws table: the "∨ form" column is the dual of the "∧ form" column. So you only need to remember half the laws. For example, absorption p ∨ (p ∧ q) ≡ p has dual p ∧ (p ∨ q) ≡ p. Remove → and ↔ first before taking a dual; the rule does not apply to them directly.
Normal Forms
A normal form is a standard shape that every formula can be rewritten into. Standard shapes make formulas easy to compare, to feed into SAT solvers, and to build as circuits.
A literal is a variable or its negation (p, ¬p).
A formula is in Disjunctive Normal Form (DNF) if it is an OR of terms, each term being an AND of literals ("sum of products"), e.g. (p ∧ ¬q) ∨ (¬p ∧ r) ∨ q.
A formula is in Conjunctive Normal Form (CNF) if it is an AND of clauses, each clause being an OR of literals ("product of sums"), e.g. (p ∨ q) ∧ (¬p ∨ r ∨ ¬s).
Converting to CNF or DNF: The Recipe
Remove ↔ using p ↔ q ≡ (p → q) ∧ (q → p).
Remove → using p → q ≡ ¬p ∨ q.
Push ¬ inward with De Morgan and double negation until ¬ sits only on variables.
Distribute: for CNF, distribute ∨ over ∧; for DNF, distribute ∧ over ∨.
Simplify with idempotent, negation and absorption laws.
Worked Example: CNF of (p → q) → r
(p → q) → r
≡ ¬(¬p ∨ q) ∨ r Remove both arrows
≡ (p ∧ ¬q) ∨ r De Morgan, double negation <- this is already DNF
≡ (p ∨ r) ∧ (¬q ∨ r) Distribute ∨ over ∧ <- CNFWorked Example: p ↔ q
CNF: (p → q) ∧ (q → p) ≡ (¬p ∨ q) ∧ (p ∨ ¬q). DNF: (p ∧ q) ∨ (¬p ∧ ¬q).
DNF and CNF are not unique: (p ∧ ¬q) ∨ r and (p ∧ ¬q) ∨ (r ∧ q) ∨ (r ∧ ¬q) are both DNFs of the same function. For a unique form we need the canonical versions.
PDNF and PCNF (Canonical Forms)
A minterm of n variables is an AND containing each variable exactly once (plain or negated). It is true in exactly one row.
A maxterm is an OR containing each variable exactly once. It is false in exactly one row.
The Principal (or Full) DNF, PDNF, is the OR of the minterms of the rows where the formula is T. The Principal CNF, PCNF, is the AND of the maxterms of the rows where the formula is F.
Rows are numbered in binary (p as the most significant bit). For row 011 (p = 0, q = 1, r = 1):
minterm m3 = ¬p ∧ q ∧ r (write a variable plain if it is 1, negated if 0), true only in this row;
maxterm M3 = p ∨ ¬q ∨ ¬r (write a variable plain if it is 0, negated if 1), false only in this row.
Note that Mi = ¬mi, by De Morgan.
Worked Example: f = (p ∧ q) ∨ (¬p ∧ r)
This f is a "multiplexer": if p then output q, else output r. Its truth table:
Row | p q r | f | Minterm (if f = 1) | Maxterm (if f = 0) |
|---|---|---|---|---|
0 | 0 0 0 | 0 | M0 = p ∨ q ∨ r | |
1 | 0 0 1 | 1 | m1 = ¬p ∧ ¬q ∧ r | |
2 | 0 1 0 | 0 | M2 = p ∨ ¬q ∨ r | |
3 | 0 1 1 | 1 | m3 = ¬p ∧ q ∧ r | |
4 | 1 0 0 | 0 | M4 = ¬p ∨ q ∨ r | |
5 | 1 0 1 | 0 | M5 = ¬p ∨ q ∨ ¬r | |
6 | 1 1 0 | 1 | m6 = p ∧ q ∧ ¬r | |
7 | 1 1 1 | 1 | m7 = p ∧ q ∧ r |
PDNF = m1 ∨ m3 ∨ m6 ∨ m7 = (¬p ∧ ¬q ∧ r) ∨ (¬p ∧ q ∧ r) ∨ (p ∧ q ∧ ¬r) ∨ (p ∧ q ∧ r), written Σm(1, 3, 6, 7).
PCNF = M0 ∧ M2 ∧ M4 ∧ M5 = (p ∨ q ∨ r) ∧ (p ∨ ¬q ∨ r) ∧ (¬p ∨ q ∨ r) ∧ (¬p ∨ q ∨ ¬r), written ΠM(0, 2, 4, 5).
This matches the program output above. Notice the indices of the PCNF are exactly the indices missing from the PDNF, and together they cover all 23 = 8 rows.
PDNF Without a Truth Table
You can also expand algebraically. Any term missing a variable x is multiplied by (x ∨ ¬x) ≡ T and distributed:
p ∧ q ≡ (p ∧ q) ∧ (r ∨ ¬r) ≡ (p ∧ q ∧ r) ∨ (p ∧ q ∧ ¬r) = m7 ∨ m6
¬p ∧ r ≡ (¬p ∧ r) ∧ (q ∨ ¬q) ≡ (¬p ∧ q ∧ r) ∨ (¬p ∧ ¬q ∧ r) = m3 ∨ m1The same four minterms appear. For PCNF, the dual trick adds (x ∧ ¬x) ≡ F with ∨ to an incomplete clause and distributes.
Why the Canonical Forms Matter
Uniqueness. Up to the order of terms, every formula has exactly one PDNF and one PCNF. So two formulas are equivalent if and only if they have the same PDNF.
Existence for every function. Every truth table has a PDNF (take a minterm for each T row). A tautology's PDNF contains all 2n minterms; a contradiction has an empty PDNF (and its PCNF contains all 2n maxterms).
Circuits. PDNF is a sum-of-products circuit, the starting point for Karnaugh-map minimisation in the Digital Logic tutorial.
Simplification tools give the shortest normal forms instead of the canonical ones. With the SymPy library:
from sympy import symbols
from sympy.logic.boolalg import to_cnf, to_dnf, Implies, Equivalent
p, q, r = symbols('p q r')
f = (p & q) | (~p & r)
print(to_cnf(f, simplify=True))
print(to_dnf(Equivalent(p, q), simplify=True))
print(to_cnf(Implies(p, q) >> r, simplify=True))Output:
(p | r) & (q | ~p)
(p & q) | (~p & ~q)
(p | r) & (r | ~q)So the multiplexer has the short CNF (p ∨ r) ∧ (¬p ∨ q), and the third line confirms our hand-derived CNF of (p → q) → r.
Functionally Complete Sets
A set of connectives is functionally complete if every possible truth table (every Boolean function) can be expressed using only connectives from that set.
{¬, ∧, ∨} is complete: the PDNF of any function uses only these three. (The constant-false function, which has no T rows, can be written p ∧ ¬p.)
{¬, ∧} is complete: p ∨ q ≡ ¬(¬p ∧ ¬q) by De Morgan, so ∨ is not needed. Similarly {¬, ∨} and {¬, →} (since p ∨ q ≡ ¬p → q).
{∧, ∨} is not complete. If all inputs are T, any formula built from ∧ and ∨ is T, so ¬p cannot be expressed. The same argument shows {→} alone and {∧, ∨, →, ↔} are not complete.
NAND and NOR: One Connective Is Enough
NAND is p ↑ q ≡ ¬(p ∧ q), and NOR is p ↓ q ≡ ¬(p ∨ q). Each one alone is functionally complete:
Target | Using NAND (↑) | Using NOR (↓) |
|---|---|---|
¬p | p ↑ p | p ↓ p |
p ∧ q | (p ↑ q) ↑ (p ↑ q) | (p ↓ p) ↓ (q ↓ q) |
p ∨ q | (p ↑ p) ↑ (q ↑ q) | (p ↓ q) ↓ (p ↓ q) |
Why p ↑ p ≡ ¬p: p ↑ p = ¬(p ∧ p) = ¬p by idempotence. Then ¬, ∧ and ∨ can all be built, and {¬, ∧, ∨} is complete. This is why chip designers can build an entire processor from one gate type: NAND gates are cheap and fast in CMOS technology.
Common Mistakes
Wrong De Morgan. ¬(p ∧ q) is ¬p ∨ ¬q, not ¬p ∧ ¬q. Negating flips the operator.
Negating an implication as another implication. ¬(p → q) ≡ p ∧ ¬q. It is not ¬p → ¬q, and not p → ¬q.
Treating → as associative. (p → q) → r ≢ p → (q → r).
Mixing up the maxterm rule. In a maxterm, a variable that is 0 in the row appears plain; in a minterm it appears negated.
Forgetting missing variables in PDNF. A term like p ∧ q in three variables is not a minterm; expand it with (r ∨ ¬r).
Claiming equivalence from a few rows. Equivalence needs all rows; non-equivalence needs just one.
Taking the dual of a formula that still contains →. Remove → and ↔ first.
Interview and GATE-Style Questions
Simplify ¬(p ∨ (¬p ∧ q)).
¬p ∧ ¬q. See Example 1: De Morgan twice, distribute, then use ¬p ∧ p ≡ F and the identity law.
Which is equivalent to ¬(p ↔ q)? (a) ¬p ↔ ¬q (b) p ↔ ¬q (c) ¬p ∧ ¬q (d) p → ¬q
(b). ¬(p ↔ q) is true exactly when p and q differ, and so is p ↔ ¬q. Option (a) is equivalent to p ↔ q itself.
Write the PDNF and PCNF of p → q.
p → q is F only in row p = 1, q = 0 (row 2). PDNF = Σm(0, 1, 3) = (¬p ∧ ¬q) ∨ (¬p ∧ q) ∨ (p ∧ q). PCNF = ΠM(2) = ¬p ∨ q.
Express p ∨ q using only NOR.
(p ↓ q) ↓ (p ↓ q). The inner p ↓ q is ¬(p ∨ q), and NOR of a value with itself negates it, giving p ∨ q.
Is {∧, ∨} functionally complete? Justify.
No. When every variable is T, every formula built only from ∧ and ∨ evaluates to T, so no such formula can equal ¬p (which is F there).
Is (p → q) → ((r → p) → (r → q)) a tautology?
Yes. Suppose it were false: then p → q is T, r → p is T, and r → q is F, so r = T and q = F. From r → p, p = T; then p → q gives q = T, a contradiction. So it is never false.
A formula in 4 variables is true in exactly 5 rows. How many minterms are in its PDNF and how many maxterms in its PCNF?
5 minterms and 24 − 5 = 11 maxterms.
Summary
A ≡ B means A and B agree in every row, i.e. A ↔ B is a tautology.
Key laws: De Morgan, both distributive laws, absorption, double negation, and p → q ≡ ¬p ∨ q ≡ ¬q → ¬p.
Prove equivalence by a chain of named laws; disprove it with one counterexample row.
Duality: swapping ∧/∨ and T/F in a true equivalence gives another true equivalence.
DNF is an OR of ANDs, CNF an AND of ORs. PDNF (Σ of minterms of T rows) and PCNF (Π of maxterms of F rows) are unique.
{¬, ∧, ∨}, {¬, ∧}, {¬, ∨}, {↑} and {↓} are functionally complete; {∧, ∨} is not.
Next, Predicate Logic & Quantifiers extends logic to statements about "all" and "some", which propositional logic cannot express.