1.2Equivalences and the standard laws
The idea
Two formulas are equivalent if they have the same truth table. A handful of laws let you transform formulas without a table: De Morgan, p → q ≡ ¬p ∨ q, and the contrapositive.
Think of it like this: Different routes to the same town: the contrapositive "no lamp, so no power" says exactly what "power means lamp" says.
Why it exists
Options in GATE questions are usually four rewrites of one statement; only the equivalent ones survive the laws.
How it works
- De Morgan: push ¬ inside and flip ∧ with ∨.
- Implication: p → q ≡ ¬p ∨ q.
- Contrapositive: p → q ≡ ¬q → ¬p. The converse q → p and the inverse ¬p → ¬q are not equivalent.
- Negate an implication: ¬(p → q) ≡ p ∧ ¬q.
- When stuck, compare the truth tables of the two sides.
Worked example: Is (p → q) ∧ (p → r) ≡ p → (q ∧ r)?
Rewrite the left as (¬p ∨ q) ∧ (¬p ∨ r) ≡ ¬p ∨ (q ∧ r) by distribution, which is p → (q ∧ r). Yes, equivalent.
Now play with it
- →Pick "Converse is NOT equivalent" and read the rows where A and B disagree.
- →Check that ¬(p → q) really equals p ∧ ¬q.
| p | q | A | B | same? |
|---|---|---|---|---|
| F | F | T | T | = |
| F | T | T | T | = |
| T | F | T | T | = |
| T | T | F | F | = |
Two formulas are equivalent exactly when A ↔ B is a tautology, that is, when every row agrees.
| Law | Statement | Mistake it prevents |
|---|---|---|
| De Morgan | ¬(p ∧ q) ≡ ¬p ∨ ¬q; ¬(p ∨ q) ≡ ¬p ∧ ¬q | forgetting to flip ∧/∨ when negating |
| Implication | p → q ≡ ¬p ∨ q | treating → as a causal "if" |
| Contrapositive | p → q ≡ ¬q → ¬p | using the converse q → p instead |
| Negated implication | ¬(p → q) ≡ p ∧ ¬q | writing ¬p → ¬q |
| Biconditional | p ↔ q ≡ (p → q) ∧ (q → p) ≡ (p ∧ q) ∨ (¬p ∧ ¬q) | |
| Absorption | p ∨ (p ∧ q) ≡ p; p ∧ (p ∨ q) ≡ p | |
| Exportation | (p ∧ q) → r ≡ p → (q → r) | confusing it with (p → q) → r |
When in doubt, build the 4-row or 8-row truth table. It always settles equivalence.
Check yourself
Which statement is equivalent to "If it rains, the match is cancelled"?
Exam notes (the dense version)
Two formulas are equivalent if they have the same truth table, i.e. p ↔ q is a tautology. Core laws: De Morgan ¬(p∧q) ≡ ¬p∨¬q; implication p→q ≡ ¬p∨q; contrapositive p→q ≡ ¬q→¬p; ¬(p→q) ≡ p∧¬q; p↔q ≡ (p→q)∧(q→p); distribution of ∧ over ∨ and ∨ over ∧. The converse q→p and inverse ¬p→¬q are NOT equivalent to p→q.
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.