If two propositions are semantically identical then we say those two propositions are “equivalent”. If two propositions P(p,q,r,.…) and Q(p,q,r,….) where p,q,r,… are propositional variables have the same truth values in every possible case, the propositions are called logically equivalent and denoted as, P(p,q,r,.…) ≡ Q(p,q,r,….)
To test whether two propositions P and Q are logically equivalent, the following steps are followed:
- Construct truth table for P.
- Construct truth table for Q using same propositional values.
- Check each combination of truth values of propositional variables to see whether the value of P is same as value of Q or not.
- If truth value of P is same as value of Q then P and Q are logically equivalent.
Examples:
Prove ￢(A ∨ B) and [(￢A) ∧ (￢B)] are equivalent.
The compound propositions p and q are logically equivalent, denoted by p≡q or p q, if proposition p↔q is a tautology.
Exercise:
- Show that the conditional statement is logically equivalent to its contrapositive.
- Show that the inverse and converse of conditional statement are logically equivalent.
- Show that neither inverse nor converse is logically equivalent to implication.
Translate the following paragraphs into logical expression.
“When the system software is being upgraded, users can’t access the file system. If users can access the file system then, they can save new files. If users can’t save new files then, system software isn’t being upgraded.”
State as an “if . . . then . . .” sentence:
(1) Where there’s smoke, there’s fire.
(2) Beer sales end after the 7th inning.
(3) People who go to college make more money than people who have not.
(4) You may purchase beer provided you are 21 or older.
(5) One gets wiser with age.
Some important logical equivalences:
Example:
Show that (p∧q)→(p∨q) is a tautology.
Solution: To show that this statement is a tautology, we will use logical equivalences to demonstrate that it is logically equivalent to T.
(p∧q)→(p∨q) ≡ ¬(p∧q)∨(p∨q)
≡ (¬p∨¬q)∨(p∨q) [Demorgan’s law]
≡ (¬p∨p)∨(¬q∨q) [Commutative law]
≡ T∨T [Negation law]
≡ T [Domination law]
Show that (p→r)∧(q→r) and (p∨q)→r are logically equivalent using law of equivalent.
Solution: Here given first expression,
L.H.S (p→r)∧(q→r) = (¬p∨r)∧(¬q∨r) [Implication]
Let A represent ¬p, B represent ¬q and C represent r
Then, (A∨C)∧(B∨C) ≡ (C∨A)∧(C∨B) [Commutative law]
≡ C∨(A∧B) [Distribution law]
≡ (A∧B)∨C [Commutative law]
≡ (¬p∧¬q)∨r [Substitution law]
≡ ¬(p∨q)∨r [Demorgan’s law]
≡ (p∨q)→r [Implication]
Exercise:
Show that ¬(p→¬q)∧p and (p∧q) are logically equivalent using law of equivalent.