1
Logical equivalences
Tautology: A compound proposition that is always true, no matter what the truth value of the
proposition that occur in it is called tautology.
Self contradiction/ contradiction: A compound proposition that is always false is called
Self contradiction/ contradiction.
Contingency: A compound proposition that is neither true nor false is called contingency.
Example:
p ⇁p p ∨⇁ p p∧⇁ p
T F T F
F T T F
In the above example
p ∨⇁ pis a tautolgy and p∧⇁ p is contradiction.
Logical equivalence: Compound propositions that have the same truth values in all possible
cases are called logically equivalent.
The proposition p and q are logically equivalent if p↔q is a tautology.the notation p⇔q denotes
that p and q are logically equivalent.
Example: Show that ⇁ (p∨q)⇔ ⇁ p ∧ ⇁q
Note: this equivalence is one of De-morgan laws.
p q p∨q ⇁ (p∨ ⇁p ⇁q ⇁ p ∧⇁ q
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
Clearly from the column 4 and column 7 ⇁ (p∨q) and ⇁ p ∧⇁ q have same truth values so
these propositions are logically equivalent.
Example: Show that propositions p∨ (q ∧ r ¿ and (p∨q)∧ (p∨r) arte logically equivalent.
Note:This is distributive law of disjunction over conjunction.
2
p q r (q ∧ r ¿ p∨ ( p∨q p∨r (p∨q)∧ (p∨r)
q∧r¿
T T T T T T T T
T T F F T T T T
T F T F T T T T
T F F F T T T T
F T T T T T T T
F T F F F T F F
F F T F F F T F
F F F F F F F F
Clearly from the column 5 and column 8
p∨ (q ∧ r ¿ ⇔(p∨q)∧ (p∨r)
Logical equivalences:
Logical equivalences
Equivalence Name
p ∧T ⇔ p Identity Laws
p ∨F ⇔ p
p ∨T ⇔ T Domination Laws
p∧F⇔F
p∨ p ⇔ p Idempotent Laws
p∧ p⇔ p
⇁ (⇁ p ¿ ⇔ p Double negation Law
p ∨q ⇔ q ∨ p Commutative laws
p ∧q ⇔ q ∧ p
( p ∨q ) ∨ r ⇔ p ∨(q ∨ r) Associative Laws
( p ∧q ) ∧ r ⇔ p ∧(q ∧ r)
p ∨( q ∧r ) ⇔ ( p ∨ q ) ∧(p ∨ r) Distributive Laws
p ∧( q ∨r ) ⇔ ( p ∧ q ) ∨(p ∧ r)
⇁ (p ∧ q)⇔ ⇁ p ∨⇁ q De Morgan’s Laws
⇁ (p ∨ q)⇔ ⇁ p ∧⇁ q
Example:Show that ⇁ (p ∨ ( ⇁ p∧ q )) ⇔⇁ p ∧⇁ q
Solution: ⇁ (p ∨ ( ⇁ p∧ q ))⇔ ⇁ p ∧⇁ ( ⇁ p ∧ q ) (DeMorgan’s law)
⇔ ⇁ p ∧ ¿) (DeMorgan’s law)
⇔ ⇁ p ∧ ( p ∨⇁ q ) (Double negation law)
3
⇔ ( ⇁ p ∧ p ) ∨(⇁ p ∧⇁ q) (Distributive law)
⇔ F ∨(⇁ p ∧⇁ q) since⇁ p ∧ p ⇔F
⇔ (⇁ p ∧⇁ q)∨ F (Commutative law)
⇔ (⇁ p ∧⇁ q) since p ∨ F ⇔ p
Consequently ⇁ (p ∨ ( ⇁ p∧ q )) ⇔⇁ p ∧⇁ q
Example: Show that(p⋀ q)→ (p∨q) is a tautology.
Solution: To prove the required result we will construct the truth table
p q (p⋀q) (p∨q) (p⋀q)→ (p∨q)
T T T T T
T F F T T
F T F T T
F F F F T
Clearly from last column (p⋀q)→ (p∨q) is a tautology.
Exercise 1.2
Q1 :Use truth table to verify
a) p ∧T ⇔ p
Solution:
p T p∧T
T T T
F T F
Clearly from 1st and 3rd column p ∧T ⇔ p
b) p ∨F ⇔ p
Solution:
p F p∨F
T F T
F F F
Clearly from 1st and 3rd column p ∨F ⇔ p
c) p ∧ F ⇔ F
Solution:
4
P F p∧F
T F F
F F F
Clearly from 1st and 3rd column p ∧ F ⇔ F
d) p ∨T ⇔ T
Solution:
p T p∨T
T T T
F T T
Clearly from 1st and 3rd column p ∨T ⇔ T
e) p ∨ p ⇔ p
Solution:
p P p∨p
T T T
F F F
Clearly from 1st and 3rd column p ∨p ⇔ p
f) p ∧ p ⇔ p
Solution:
p p p∧p
T T T
F F F
Clearly from 1st and 3rd column p ∧ p ⇔ p
5
Q2: Show that⇁ (⇁ p ¿ ⇔ p
Solution:
p ⇁p ⇁ (⇁ p ¿
T F T
F T F
Clearly from 1 and 3 column⇁ (⇁ p ¿ ⇔ p
st rd
Q3:Use truth tables to verify
a) p ∨q ⇔ q ∨ p
Solution:
p q (p∨q) (q∨p)
T T T T
T F T T
F T T T
F F F F
Clearly from 3rd AND 4thcolumn p ∨q ⇔ q ∨ p
b) p ∧q ⇔ q ∧ p
Solution:
p q p ∧q q∧ p
T T T T
T F F F
F T F F
F F F F
Clearly from 3rd AND 4thcolumn p ∧q ⇔ q ∧ p
Q4:Use truth table to verify
a ¿ ( p ∨q ) ∨ r ⇔ p ∨(q ∨ r)
Solution:
p q r p∨q (p∨ q∨r p∨(q∨r)
q¿∨r
T T T T T T T
T T F T T T T
T F T T T T T
T F F T T F T
F T T T T T T
F T F T T T T
6
F F T F T T T
F F F F F F F
Clearly from 5th and 7thcolumn ( p ∨q ) ∨ r ⇔ p ∨(q ∨ r)
b)( p ∧q ) ∧ r ⇔ p ∧(q ∧ r)
Solution:Try yourself
Q5:Use truth table to verify p ∧( q ∨r ) ⇔ ( p ∧ q ) ∨(p ∧ r)
Solution: Try yourself same as example done already.
Q6: Use truth table to verify the equivalence ⇁ (p ∧ q)⇔ ⇁ p ∨⇁ q
Solution: Try yourself same as example done already.
Q7:show that following implication is a tautology
d)[( p ∨q)∧( p→ r )∧(q → r )]→r
p q r p∨q (p→ r) (q→ ¿)∧ ( p → r ) [( p ∨q)
r) ∧(q → r) ∧( p→ r )∧(q → r )]→
r
T T T T T T T T
T T F T F F F T
T F T T T T T T
T F F T F T F T
F T T T T T T T
F T F T T F F T
F F T F T T F T
F F F F T T F T
7
Clearly from the column 8th [( p ∨q)∧( p→ r )∧(q → r )]→r is a tautology.
Try other parts yourself.
Q11:Verify the following equivalences which are known as the absorption laws.
a)[ p ∨( p ∧ q)]⇔p
Solution:
p q p ∧q p ∨ ( p ∧q ¿
T T T T
T F F T
F T F F
F F F F
Clearly from column 4 [ p ∨( p ∧ q)]⇔p
th
b)[ p ∧( p ∨ q)¿ ⇔ p
Solution: Try yourself
Q10(a,b,c parts),Q16,20,25 (page 35) Try yourself
