What is Logical Equivalence?
Two compound propositions are logically equivalent if they have the same truth value in all possible cases. We denote logical equivalence with the symbol ≡ or ⇔.
In other words, p ≡ q means that p and q are logically equivalent.
How to Prove Logical Equivalence?
- Using Truth Tables: Show that both propositions have identical truth values for all combinations
- Using Logical Laws: Apply known equivalence laws to transform one proposition into another
Fundamental Logical Equivalences
These are the most important laws you must memorize for exams:
1. Identity Laws
- p ∧ T ≡ p
- p ∨ F ≡ p
Explanation: ANDing with True doesn’t change p; ORing with False doesn’t change p.
Example:
- “It is raining AND the statement is true” = “It is raining”
- “It is raining OR the statement is false” = “It is raining”
2. Domination Laws
- p ∨ T ≡ T
- p ∧ F ≡ F
Explanation: ORing with True always gives True; ANDing with False always gives False.
Example:
- “It is raining OR it’s definitely true” = Always True
- “It is raining AND it’s definitely false” = Always False
3. Idempotent Laws
- p ∨ p ≡ p
- p ∧ p ≡ p
Explanation: Combining something with itself doesn’t change it.
Example:
- “It is raining OR it is raining” = “It is raining”
- “It is raining AND it is raining” = “It is raining”
4. Double Negation Law
- ¬(¬p) ≡ p
Explanation: Negating twice brings you back to the original.
Example:
- “It is NOT the case that it is NOT raining” = “It is raining”
- “NOT(NOT True)” = “True”
5. Commutative Laws
- p ∨ q ≡ q ∨ p
- p ∧ q ≡ q ∧ p
Explanation: Order doesn’t matter in AND/OR operations.
Example:
- “It is raining OR it is sunny” = “It is sunny OR it is raining”
- “I study AND I pass” = “I pass AND I study”
6. Associative Laws
- (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
- (p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
Explanation: Grouping doesn’t matter in AND/OR operations.
Example:
- “(A OR B) OR C” = “A OR (B OR C)“
7. Distributive Laws
- p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
- p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
Explanation: Similar to algebraic distribution: a × (b + c) = (a × b) + (a × c)
Example: Let p = “I like coffee”, q = “It’s morning”, r = “I’m tired”
“I like coffee OR (It’s morning AND I’m tired)” = “(I like coffee OR It’s morning) AND (I like coffee OR I’m tired)“
8. De Morgan’s Laws ⭐ (Very Important)
- ¬(p ∧ q) ≡ ¬p ∨ ¬q
- ¬(p ∨ q) ≡ ¬p ∧ ¬q
Explanation: When negating AND, it becomes OR of negations. When negating OR, it becomes AND of negations.
Example 1: “It is NOT the case that (it is raining AND it is cold)” = “It is NOT raining OR it is NOT cold”
Example 2: “It is NOT the case that (I study OR I play)” = “I do NOT study AND I do NOT play”
Proof using Truth Table:
| p | q | p ∧ q | ¬(p ∧ q) | ¬p | ¬q | ¬p ∨ ¬q |
|---|---|---|---|---|---|---|
| T | T | T | F | F | F | F |
| T | F | F | T | F | T | T |
| F | T | F | T | T | F | T |
| F | F | F | T | T | T | T |
Columns 4 and 7 are identical, proving the equivalence.
9. Absorption Laws
- p ∨ (p ∧ q) ≡ p
- p ∧ (p ∨ q) ≡ p
Explanation: If p is true, the rest doesn’t matter.
Example: “I pass the exam OR (I pass the exam AND I get a scholarship)” = “I pass the exam” (Because if I pass, the whole statement is true regardless of scholarship)
10. Negation Laws
- p ∨ ¬p ≡ T (Law of Excluded Middle)
- p ∧ ¬p ≡ F (Law of Contradiction)
Explanation: Something is either true or false (never both, never neither).
Example:
- “It is raining OR it is NOT raining” = Always True
- “It is raining AND it is NOT raining” = Always False (Impossible)
Conditional Statement Equivalences
11. Conditional-Disjunction Equivalence
- p → q ≡ ¬p ∨ q
Explanation: “If p then q” is the same as “NOT p OR q”
Example: “If it rains, then the ground is wet” = “It does NOT rain OR the ground is wet”
Proof:
| 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 |
12. Contrapositive Equivalence
- p → q ≡ ¬q → ¬p
Explanation: A conditional statement is equivalent to its contrapositive.
Example: “If it rains, then the ground is wet” = “If the ground is NOT wet, then it is NOT raining”
13. Biconditional Equivalences
- p ↔ q ≡ (p → q) ∧ (q → p)
- p ↔ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q)
Explanation: “p if and only if q” means both have the same truth value.
Important Non-Equivalences
Be careful! These are NOT equivalent:
1. Conditional vs. Converse
- p → q NOT≡ q → p
Example: “If it rains, then the ground is wet” ≠ “If the ground is wet, then it rains” (Ground could be wet from sprinkler)
2. Conditional vs. Inverse
- p → q NOT≡ ¬p → ¬q
Example: “If you study, you pass” ≠ “If you don’t study, you don’t pass” (You might pass even without studying)
Special Equivalences
Exportation Law
- (p ∧ q) → r ≡ p → (q → r)
Example: “If (you study AND you attend class), then you pass” = “If you study, then (if you attend class, then you pass)“
Material Implication
- ¬(p → q) ≡ p ∧ ¬q
Example: The negation of “If you study, you pass” = “You study AND you don’t pass”
Solving Problems Using Equivalences
Example 1: Simplify ¬(p ∨ ¬q)
Step 1: Apply De Morgan’s Law ¬(p ∨ ¬q) ≡ ¬p ∧ ¬(¬q)
Step 2: Apply Double Negation ¬p ∧ ¬(¬q) ≡ ¬p ∧ q
Answer: ¬p ∧ q
Example 2: Prove (p → q) ∧ (p → r) ≡ p → (q ∧ r)
Left Side: (p → q) ∧ (p → r) ≡ (¬p ∨ q) ∧ (¬p ∨ r) [Conditional equivalence] ≡ ¬p ∨ (q ∧ r) [Distributive law] ≡ p → (q ∧ r) [Conditional equivalence]
Answer: Proved! ✓
Example 3: Simplify ¬(¬p ∧ q) ∨ (p ∧ ¬q)
Step 1: Apply De Morgan’s Law ¬(¬p ∧ q) ∨ (p ∧ ¬q) ≡ (¬(¬p) ∨ ¬q) ∨ (p ∧ ¬q)
Step 2: Apply Double Negation ≡ (p ∨ ¬q) ∨ (p ∧ ¬q)
Step 3: Apply Absorption Law ≡ p ∨ ¬q
Answer: p ∨ ¬q
Example 4: Show that p → q and ¬p ∨ q are equivalent
Truth Table Method:
| 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 are identical → They are equivalent! ✓
Tautologies and Contradictions
Tautology
A compound proposition that is always TRUE.
Examples:
- p ∨ ¬p
- p → p
- (p ∧ q) → p
- ¬(p ∧ ¬p)
Contradiction
A compound proposition that is always FALSE.
Examples:
- p ∧ ¬p
- (p ↔ q) ∧ (p ↔ ¬q)
Testing for Tautology
Example: Is (p → q) ∨ (q → p) a tautology?
| p | q | p → q | q → p | (p → q) ∨ (q → p) |
|---|---|---|---|---|
| T | T | T | T | T |
| T | F | F | T | T |
| F | T | T | F | T |
| F | F | T | T | T |
Answer: Yes, it’s a tautology! ✓
Key Points for Exams
- Memorize all fundamental laws - they are frequently used
- De Morgan’s Laws are crucial - flip AND to OR (or vice versa) and negate each term
- p → q ≡ ¬p ∨ q is one of the most used equivalences
- Contrapositive is equivalent, but converse and inverse are NOT
- Always simplify step by step, citing the law used
- Use truth tables when in doubt to verify equivalences
- Practice transforming complex expressions using laws
- Check your answer by substituting simple propositions
Practice Problems
-
Simplify: ¬(p ∧ ¬q) ∨ (p ∧ q)
-
Prove using laws: (p ∨ q) ∧ ¬p ≡ q ∧ ¬p
-
Show that p → (q → r) ≡ (p ∧ q) → r
-
Is ¬(p → q) ≡ p ∧ ¬q? Prove it.
-
Simplify: (p → q) ∧ (¬p → q)
-
Determine if (p ∧ q) → (p ∨ q) is a tautology.
-
Write the contrapositive, converse, and inverse of: “If it’s sunny, then I go to the beach.”
-
Simplify using De Morgan’s Laws: ¬((p ∨ q) ∧ (r ∨ s))