The short answer#
Two compound propositions are logically equivalent, written P ≡ Q, when they have the same truth value under every assignment to their variables. Equivalently, P ↔ Q is a tautology.
| Truth table | Chain of laws | |
|---|---|---|
| How | Build both columns, compare | Rewrite P step by step until it is Q |
| Needs | Care and patience | The named laws, recalled correctly |
| Size | 2ⁿ rows for n variables | Usually 3–6 lines |
| Fails when | n is large — 5 variables is 32 rows | You cannot find the right law |
| Also gives you | The exact row where two things differ | Insight into why they agree |
The example, worked both ways#
Take the equivalence
(a ∨ b) → c ≡ (a → c) ∧ (b → c)
In English: "if either a or b happens, then c" says exactly the same thing as "if a happens then c, and if b happens then c." Notice the connective changed from ∨ on the left to ∧ on the right. That flip is the whole content of the result and the thing most often written down wrong.
Method 1 — truth table
Three variables, so 2³ = 8 rows. Build the two columns and compare them.
| a | b | c | a ∨ b | (a∨b) → c | a → c | b → c | (a→c) ∧ (b→c) |
|---|---|---|---|---|---|---|---|
| T | T | T | T | T | T | T | T |
| T | T | F | T | F | F | F | F |
| T | F | T | T | T | T | T | T |
| T | F | F | T | F | F | T | F |
| F | T | T | T | T | T | T | T |
| F | T | F | T | F | T | F | F |
| F | F | T | F | T | T | T | T |
| F | F | F | F | T | T | T | T |
Column 5 and column 8 agree in all eight rows, so the two propositions are equivalent. ∎
The last two rows are worth pausing on. There a ∨ b is false, so the left side is vacuously true — and both a → c and b → c are vacuously true too. Rows where nothing is happening still have to match, and they are the ones people forget to fill in carefully.
Method 2 — chain of named laws
Rewrite the left side until it becomes the right side, naming the justification at every step.
| Step | Expression | Law used |
|---|---|---|
| 0 | (a ∨ b) → c | given |
| 1 | ¬(a ∨ b) ∨ c | conditional–disjunction: p → q ≡ ¬p ∨ q |
| 2 | (¬a ∧ ¬b) ∨ c | De Morgan |
| 3 | (¬a ∨ c) ∧ (¬b ∨ c) | distributive |
| 4 | (a → c) ∧ (b → c) | conditional–disjunction, twice, in reverse |
Four lines. And it explains the flip that the table only reports: the ∨ becomes ∧ at step 2, because De Morgan turns the negation of a disjunction into a conjunction of negations. Everything after that is bookkeeping.
The laws you have to be able to name#
A chain proof is only worth credit if each step cites a law, so recall of the names matters as much as the manipulations.
| Name | Statement |
|---|---|
| De Morgan | ¬(p ∧ q) ≡ ¬p ∨ ¬q · ¬(p ∨ q) ≡ ¬p ∧ ¬q |
| Conditional–disjunction | p → q ≡ ¬p ∨ q |
| Contrapositive | p → q ≡ ¬q → ¬p |
| Negating a conditional | ¬(p → q) ≡ p ∧ ¬q |
| Distributive | p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) |
| Double negation | ¬¬p ≡ p |
| Identity / domination | p ∧ T ≡ p · p ∨ T ≡ T |
| Negation | p ∨ ¬p ≡ T · p ∧ ¬p ≡ F |
| Absorption | p ∨ (p ∧ q) ≡ p |
The dual, which surprises people#
Since a disjunction in the antecedent turns into a conjunction, the natural guess is that a conjunction turns into a conjunction too. It does not.
(a ∧ b) → c ≡ (a → c) ∨ (b → c)
The chain is short: ¬(a ∧ b) ∨ c ≡ (¬a ∨ ¬b) ∨ c ≡ (¬a ∨ c) ∨ (¬b ∨ c) ≡ (a → c) ∨ (b → c). The middle step just duplicates c, which is legal because p ∨ p ≡ p.
So both forms flip their connective. And in particular
(a ∧ b) → c is not (a → c) ∧ (b → c),
which is the single most tempting false equivalence in this topic. One row kills it: take a = T, b = F, c = F. Then a ∧ b is false so the left side is true, but a → c is false so the right side is false.
Disproving an equivalence takes one row#
Proving P ≡ Q requires checking every row. Proving P ≢ Q requires exactly one row where they differ — and you should state that row explicitly rather than gesturing at the table.
This is the same asymmetry as universal versus existential claims. An equivalence is a statement about all assignments, so it dies to a single counterexample.
Where these go wrong#
- Answering with the wrong method. If the question says "using a truth table", build the table. If it says "using De Morgan's laws", write the chain. Being right in the wrong format is not being right.
- Not naming the laws. A chain of unjustified rewrites is not a proof. Every line gets a reason.
- Keeping the connective. ¬(a ∨ b) is ¬a ∧ ¬b, not ¬a ∨ ¬b. De Morgan flips it, and that flip propagates into the antecedent results above.
- Guessing that (a ∧ b) → c distributes over ∧. It distributes over ∨. Check with a = T, b = F, c = F.
- Missing rows. n variables means 2ⁿ rows. Three variables is eight, not six. A table with a missing row proves nothing.
- Rushing the vacuous rows. Rows where the antecedent is false make conditionals true. They are the easiest rows and the most commonly mis-filled.
- Disproving with a whole table. Correct but wasteful. Name the one row.
Test yourself in the free Kestrel Exams app
Discrete Math practice is free and works offline — topic-selectable drills on equivalences, truth tables, and the named laws.
Drill logical equivalences →Frequently asked questions#
How many rows does a truth table need?
Two to the power of the number of distinct variables. Two variables give four rows, three give eight, four give sixteen. Missing a row invalidates the proof, because an equivalence is a claim about every possible assignment.
Why does a disjunction in the antecedent become a conjunction?
Because the first move in the chain rewrites the conditional as ¬(a ∨ b) ∨ c, and De Morgan turns ¬(a ∨ b) into ¬a ∧ ¬b. The conjunction appears there and survives the distribution step, giving (a → c) ∧ (b → c).
Is (a ∧ b) → c the same as (a → c) ∧ (b → c)?
No. It equals (a → c) ∨ (b → c), with a disjunction. Take a true, b false, c false: then a ∧ b is false so the left side is vacuously true, but a → c is false so (a → c) ∧ (b → c) is false. That single row settles it.
How do you show two propositions are not equivalent?
Exhibit one assignment of truth values where they differ, and say which one it is. Proving equivalence needs every row; disproving it needs exactly one, in the same way a universal claim falls to a single counterexample.