Key takeaways
- Two statements are logically equivalent when they have the same truth value in every row, which is the same as saying their biconditional is a tautology.
- A truth table proves equivalence mechanically and works for any statement, but the number of rows doubles with every variable.
- A proof by laws rewrites one statement into the other one step at a time, naming the law used at each step, such as De Morgan's, distributive or absorption.
- Replace conditionals with p → q ≡ ¬p ∨ q first; most equivalence proofs become manipulation of and, or and not.
- To show two statements are not equivalent, one row where they differ is enough.
Two compound statements are logically equivalent when they are true in exactly the same situations. Written P ≡ Q (or P ⇔ Q), it means that under every assignment of true and false to the variables, P and Q come out the same. OpenStax phrases the test in terms of the biconditional: P and Q are equivalent when the last column of the truth table for P ↔ Q is all true.
There are two standard ways to prove an equivalence: OpenStax uses the truth table, and Applied Discrete Structures sets out the laws of logic for rewriting one statement into the other.
Method 1: compare truth tables
Build one table with a final column for each statement. If the columns match in every row, the statements are equivalent; if they differ in any row, they are not.
Prove p → q ≡ ¬p ∨ q.
| p | q | p → q | ¬p | ¬p ∨ q |
|---|---|---|---|---|
| T | T | T | F | T |
| T | F | F | F | F |
| F | T | T | T | T |
| F | F | T | T | T |
Columns 3 and 5 match, so the two are equivalent. This identity, which Applied Discrete Structures lists as conditional equivalence, is the most useful single fact in this topic, because it turns any arrow into "or" and "not".
Truth tables are mechanical and cannot miss a case, which is their strength. Their weakness is size: the row count doubles with each variable, so four variables need 16 rows and five need 32. The truth table guide covers the layout.
Method 2: rewrite with the laws of logic
The second method starts from one statement and rewrites it, one law at a time, until it becomes the other. Each step must cite the law it uses. These are the laws you will use most; Applied Discrete Structures tabulates the full set, writing 1 for a statement that is always true and 0 for one that is always false.
| Law | Form |
|---|---|
| Commutative | p ∨ q ≡ q ∨ p; p ∧ q ≡ q ∧ p |
| Associative | (p ∨ q) ∨ r ≡ p ∨ (q ∨ r), and likewise for ∧ |
| Distributive | p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r); p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) |
| Identity | p ∨ 0 ≡ p; p ∧ 1 ≡ p |
| Negation | p ∧ ¬p ≡ 0; p ∨ ¬p ≡ 1 |
| Idempotent | p ∨ p ≡ p; p ∧ p ≡ p |
| Null (domination) | p ∧ 0 ≡ 0; p ∨ 1 ≡ 1 |
| Absorption | p ∧ (p ∨ q) ≡ p; p ∨ (p ∧ q) ≡ p |
| De Morgan's | ¬(p ∨ q) ≡ ¬p ∧ ¬q; ¬(p ∧ q) ≡ ¬p ∨ ¬q |
| Double negation (involution) | ¬¬p ≡ p |
| Conditional equivalence | p → q ≡ ¬p ∨ q |
Note that "or" distributes over "and" as well as the other way round, unlike ordinary arithmetic, where addition does not distribute over multiplication.
Worked proof 1: ¬(p → q) ≡ p ∧ ¬q.
- ¬(p → q)
- ≡ ¬(¬p ∨ q) — conditional equivalence
- ≡ ¬¬p ∧ ¬q — De Morgan's law
- ≡ p ∧ ¬q — double negation
Three steps, and it explains why the negation of a conditional is "the hypothesis holds and the conclusion fails". The De Morgan's laws guide explains step 3.
Worked proof 2: (p ∧ q) → p is a tautology, meaning it is equivalent to 1.
- (p ∧ q) → p
- ≡ ¬(p ∧ q) ∨ p — conditional equivalence
- ≡ (¬p ∨ ¬q) ∨ p — De Morgan's law
- ≡ (¬p ∨ p) ∨ ¬q — commutative and associative laws
- ≡ 1 ∨ ¬q — negation law
- ≡ 1 — null law
Worked proof 3: (p ∨ q) ∧ ¬p ≡ q ∧ ¬p.
- (p ∨ q) ∧ ¬p
- ≡ ¬p ∧ (p ∨ q) — commutative
- ≡ (¬p ∧ p) ∨ (¬p ∧ q) — distributive
- ≡ 0 ∨ (¬p ∧ q) — negation law
- ≡ ¬p ∧ q — identity law
- ≡ q ∧ ¬p — commutative
Proof 3 is the logic behind disjunctive syllogism: knowing "p or q" and "not p" leaves exactly "q and not p".
A strategy that usually works
- Remove arrows first. Replace every → with conditional equivalence and every ↔ with (p → q) ∧ (q → p).
- Push negations inward with De Morgan's laws until each ¬ sits directly on a variable, then cancel double negations.
- Look for p and ¬p together. They collapse to 1 or 0 via the negation laws, and then the null and identity laws tidy up.
- Use absorption to delete redundant terms: p ∨ (p ∧ anything) is just p.
- Work from both ends. If you are stuck, simplify the target statement too and aim to meet in the middle.
Writing the law at each step is not a formality. It is how a marker checks your proof, and it is how you catch a step that is not actually an instance of any law.
Which method to choose
| Situation | Better method |
|---|---|
| Two or three variables, no instruction | Either; a table is safer under time pressure |
| Four or more variables | Laws |
| "Prove without using a truth table" | Laws, necessarily |
| Proving non-equivalence | Neither: find one row where they differ |
| You want to understand why it holds | Laws |
Non-equivalence deserves emphasis. To show p → q is not equivalent to q → p, a full table is overkill. Take p false and q true: the first statement is true and the second is false. One row is a complete proof, which is the point made in tautology, contradiction or contingency? about falsifying rows.
Where this shows up later
The same laws, written with 0 and 1, are the laws of Boolean algebra used to simplify digital circuits; Boolean algebra and logic gates makes that connection. In programming, they justify rewriting a complicated condition into a simpler one that behaves the same on every input. The discrete math cheat sheet collects the laws on one page for revision.
For checking your work, the tools section of Discrete Math: Study & Quiz includes a logical-equivalence checker, which checks whether two statements are equivalent, and a statement simplifier. The app belongs to our education and brain-training collection; the discrete math hub lists every guide in this series.
Good to know
Frequently asked questions
What does it mean for two statements to be logically equivalent?
Is p → q logically equivalent to ¬p ∨ q?
Should I use a truth table or the laws of logic?
How do I show two statements are not equivalent?
Sources
- The Laws of Logic (Applied Discrete Structures) (opens in a new tab)discretemath.org — accessed
- 2.5 Equivalent Statements (Contemporary Mathematics) (opens in a new tab)OpenStax — accessed
- Propositional Logic (Discrete Mathematics: An Open Introduction, 3rd edition, Oscar Levin) (opens in a new tab)Open Math Books — accessed
About the author
Reign Creative LLC — The independent app studio that builds the apps covered on this site and publishes every article here. On Google Play it publishes as Reign Collective Apps.
We use AI tools to help research, draft and edit our articles. Each article lists the sources its factual claims rely on, and details about our apps come from their live Google Play listings. No article on this site has been reviewed by an independent expert unless the reviewer is named on it.
No person at Reign Creative LLC has read this article in full. It was published after automated checks and an AI editorial review, which are described in our editorial policy and are not the same as a person reading every sentence.
Spotted an error? Tell us — how corrections are handled is set out in our editorial policy.