The same sign, written twice#
A sign on a door says:
“If you have the key or the code, the door opens.”
Someone rewrites it as two separate rules:
“If you have the key, the door opens. And if you have the code, the door opens.”
Same sign, or a different one? Decide before you read on.
It is the same sign. Anyone who gets in under the first gets in under the second, and the other way around.
But look at the little joining word. The first sign says or. The second says and. Nobody moved a “not” around. Nobody added anything. The word flipped on its own.
That flip is the whole content of this page, and it is the single thing most often written down wrong.
What “the same” means here#
Give the three parts letters: a is “you have the key”, b is “you have the code”, c is “the door opens”. Then the two signs are:
(a ∨ b) → c ≡ (a → c) ∧ (b → c)
Five symbols, and that is all you need for this page:
| Symbol | Say it as | It means |
|---|---|---|
| ∨ | “or” | at least one of them is true |
| ∧ | “and” | both of them are true |
| ¬ | “not” | the opposite |
| → | “if … then” | a promise: whenever the left holds, the right does |
| ≡ | “is the same statement as” | the two sides always agree |
Two statements are logically equivalent, written P ≡ Q, when they come out the same for every possible combination of true and false. Not usually the same. Always the same, with no exceptions — which is why proving it means checking every case.
Two ways to prove it#
There are two accepted ways to show two statements are equivalent, and a course will often ask for a specific one.
| Truth table | Chain of laws | |
|---|---|---|
| How | Build both columns, compare | Rewrite one side step by step until it is the other |
| Needs | Care and patience | The named laws, remembered correctly |
| Size | 2ⁿ rows for n letters | Usually 3–6 lines |
| Fails when | There are lots of letters — 5 means 32 rows | You cannot spot the right law |
| Also gives you | The exact row where two things differ | Insight into why they agree |
“Using a truth table, prove…” and “Use De Morgan’s laws to prove…” are different questions with the same answer. Handing in a table when laws were asked for does not answer the question that was asked, and usually earns nothing.
Method 1 — the truth table#
A truth table lists every possible combination of true and false, then works out what each side comes to. Three letters means 2³ = 8 combinations, so eight rows.
1 means true and 0 means false — the notation used in the truth tables below.
| a | b | c | a ∨ b | (a∨b) → c | a → c | b → c | (a→c) ∧ (b→c) |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 |
| 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
Column 5 and column 8 agree in all eight rows, so the two statements are equivalent. The proof is done.
The last two rows are worth slowing down on. There, nobody has the key or the code, so a ∨ b is false — and an if–then whose first half is false counts as true. The sign is not broken by someone who never tried the door. Rows where nothing happens still have to match, and they are the ones people fill in carelessly.
Method 2 — a chain of named laws#
The other method rewrites one side, one step at a time, until it turns into the other side — naming the law that justifies each step.
| Step | Expression | Law used |
|---|---|---|
| 0 | (a ∨ b) → c | where we start |
| 1 | ¬(a ∨ b) ∨ c | arrow–or: p → q ≡ ¬p ∨ q |
| 2 | (¬a ∧ ¬b) ∨ c | De Morgan |
| 3 | (¬a ∨ c) ∧ (¬b ∨ c) | distributive |
| 4 | (a → c) ∧ (b → c) | arrow–or again, twice, backwards |
Four lines. And unlike the table, it explains the flip instead of just reporting it. The ∨ becomes an ∧ at step 2, because De Morgan turns “not (this or that)” into “not this and not that”. Everything after that is bookkeeping.
Rewrite p → q as ¬p ∨ q. Arrows are awkward to manipulate; ∧, ∨ and ¬ have laws you can apply. Convert first, work second, convert back at the end.
The laws you have to be able to name#
A chain proof only earns credit if every line cites a law, so remembering the names matters as much as the moves.
| Name | What it says |
|---|---|
| De Morgan | ¬(p ∧ q) ≡ ¬p ∨ ¬q · ¬(p ∨ q) ≡ ¬p ∧ ¬q |
| Arrow–or | p → q ≡ ¬p ∨ q |
| Contrapositive | p → q ≡ ¬q → ¬p |
| Negating an arrow | ¬(p → q) ≡ p ∧ ¬q |
| Distributive | p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) |
| Double negative | ¬¬p ≡ p |
| Identity / domination | p ∧ 1 ≡ p · p ∨ 1 ≡ 1 |
| Negation | p ∨ ¬p ≡ 1 · p ∧ ¬p ≡ 0 |
| Absorption | p ∨ (p ∧ q) ≡ p |
The one that surprises people#
Since an “or” on the left turned into an “and” on the right, the natural guess is that an “and” on the left stays an “and”. It does not. It flips too:
(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 writes c twice, which is legal because p ∨ p ≡ p.
So both forms flip their joining word. And in particular:
(a ∧ b) → c is not (a → c) ∧ (b → c)
which is the most tempting wrong answer in this topic. One row kills it: take a = 1, b = 0, c = 0. Then a ∧ b is 0, so the left side is true. But a → c is 0, so the right side is false. Different answers in the same row means not equivalent.
Disproving takes one row#
Proving two things equivalent means checking every row. Proving they are not equivalent takes exactly one row where they differ. Name that row out loud instead of waving at the table.
Write it like this: “At a = 1, b = 0, c = 0 the left side is true and the right side is false, so the two are not equivalent.” One line, complete, done.
That is the same unevenness as “every” versus “some”. An equivalence is a claim about all combinations, so a single counterexample destroys it.
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 unexplained rewrites is not a proof. Every line gets a reason.
- Keeping the joining word. ¬(a ∨ b) is ¬a ∧ ¬b, not ¬a ∨ ¬b. De Morgan flips it, and that flip is what produces every result above.
- Guessing that (a ∧ b) → c splits with an “and”. It splits with an “or”. Check it at a = 1, b = 0, c = 0.
- Missing rows. n letters means 2ⁿ rows. Three letters is eight, not six. A table with a missing row proves nothing.
- Rushing the rows where nothing happens. When the first half of an if–then is false, the whole thing is true. Easiest rows on the page, most commonly filled in wrong.
- 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 different letters. Two letters give four rows, three give eight, four give sixteen. Missing a row invalidates the proof, because an equivalence is a claim about every possible combination of true and false.
Why does an “or” on the left turn into an “and” on the right?
Because the first move rewrites the if–then as “not (a or b), or c”, and De Morgan turns “not (a or b)” into “not a and not b”. The “and” appears right there and survives the rest of the chain, giving (a → c) and (b → c).
Is (a and b) → c the same as (a → c) and (b → c)?
No. It equals (a → c) or (b → c), with an “or”. Take a true, b false, c false. Then a and b is false, so the left side is automatically true. But a → c is false, so the right side is false. That single row settles it.
When should I use a chain of laws instead of a truth table?
Use a table when there are few letters and you want certainty without recall. Use a chain when there are many letters — five letters is thirty-two rows — or when the question explicitly asks for named laws. A chain also shows you why two statements agree, which a table never does.
Something here not clear? A topic you wish we covered? Tell us. We read every message, and a request is the fastest way to get a guide written — several of these exist because somebody asked.