Introduction
In Mathematical Logic, two propositions are said to be logically equivalent if they always have the same truth values, regardless of the truth values of their individual components. Logical equivalences help in simplifying complex logical expressions, proving theorems, and optimizing logical circuits in digital electronics.
For example, the statements:
- “If it rains, then the ground will be wet.”
- “The ground is not dry if it rains.”
Both express the same idea but in different forms.
Definition
Two propositions p and q are logically equivalent, denoted as p ≡ q, if their truth tables are identical, meaning they always yield the same truth value for every possible input combination.
Types of Logical Equivalences
1. Identity Laws
Identity laws state that:
- p ∧ T ≡ p (AND-ing with true does not change the statement)
- p ∨ F ≡ p (OR-ing with false does not change the statement)
Example:
- “Sachin Tendulkar is a cricketer AND 1=1.” (Same truth value as just “Sachin Tendulkar is a cricketer.”)
2. Domination Laws
- p ∨ T ≡ T (Anything OR-ed with true is always true)
- p ∧ F ≡ F (Anything AND-ed with false is always false)
Example:
- “Narendra Modi is the Prime Minister OR 2+2=5.” (This is always true because 2+2=5 is false, but the first statement is true.)
3. Idempotent Laws
Applying the same operation twice does not change the result:
- p ∨ p ≡ p
- p ∧ p ≡ p
Example:
- “Virat Kohli is a cricketer OR Virat Kohli is a cricketer.” (Repeating the same statement does not add any value.)
4. Double Negation Law
- ¬(¬p) ≡ p (Negation cancels itself out)
Example:
- “It is NOT the case that Rahul Dravid is NOT a cricketer.” (Simply means “Rahul Dravid is a cricketer.”)
5. Commutative Laws
The order of operands does not matter in AND/OR operations:
- p ∨ q ≡ q ∨ p
- p ∧ q ≡ q ∧ p
Example:
- “Delhi is the capital of India OR Mumbai is a financial hub.” (Same meaning if reversed.)
6. Associative Laws
Grouping of terms does not matter:
- (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
- (p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
Example:
- “Rajasthan is hot OR (Punjab is fertile OR Kerala is humid)” is the same as “(Rajasthan is hot OR Punjab is fertile) OR Kerala is humid.”
7. Distributive Laws
Similar to multiplication and addition in algebra:
- p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
- p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
Example:
- “I will buy a mobile OR (laptop AND tablet)” is the same as “(I will buy a mobile OR laptop) AND (I will buy a mobile OR tablet).”
8. De Morgan’s Laws
Fundamental in Boolean algebra and circuit design:
- ¬(p ∨ q) ≡ ¬p ∧ ¬q (Negation distributes and changes OR to AND)
- ¬(p ∧ q) ≡ ¬p ∨ ¬q (Negation distributes and changes AND to OR)
Example:
- “It is NOT the case that (I will watch a movie OR I will read a book).”
- Equivalent to “I will NOT watch a movie AND I will NOT read a book.”
9. Absorption Laws
- p ∨ (p ∧ q) ≡ p
- p ∧ (p ∨ q) ≡ p
Example:
- “I will go to school OR (I will go to school AND take my books).” (Clearly, just “I will go to school” is sufficient.)
10. Implication and Contrapositive
Implication can be rewritten as:
- p → q ≡ ¬p ∨ q
- Contrapositive: (p → q) ≡ (¬q → ¬p)
Example:
- “If it rains, then the ground is wet.”
- Equivalent to “Either it does not rain OR the ground is wet.”
11. Exclusive OR (XOR) Laws
- p ⊕ q ≡ (p ∨ q) ∧ ¬(p ∧ q)
- XOR means one is true but not both.
Example:
- “Either I will play cricket OR football, but not both.”
Truth Tables of Important Equivalences
Truth Table for De Morgan’s Laws
| p | q | p ∨ q | ¬(p ∨ q) | ¬p | ¬q | ¬p ∧ ¬q |
|---|---|---|---|---|---|---|
| T | T | T | F | F | F | F |
| T | F | T | F | F | T | F |
| F | T | T | F | T | F | F |
| F | F | F | T | T | T | T |
Since ¬(p ∨ q) ≡ ¬p ∧ ¬q, both columns match.
Practice Questions
- Prove p → q ≡ ¬p ∨ q using a truth table.
- Simplify ¬(p ∧ (q ∨ ¬r)) using De Morgan’s laws.
- Find a real-life example of the absorption law.
- Show that (p → q) ∧ (q → r) ≡ (p → r) using logical equivalences.
Conclusion
Understanding propositional equivalences is crucial in logic, computer science, and circuit design. These equivalences allow us to simplify logical expressions, optimize algorithms, and make better logical deductions.