Logical equivalence, laws of logic

Logical Equivalence
Laws of Logic
Proving logical equivalences using Laws of Logic and Truth Tables

1. Discrete Mathematical Structures
Fundamentals of Logic
BY,
Lakshmi R
Asst. Professor
Dept. of ISE

2. Logical Equivalence
•Two propositions uand vare said to be logically equivalent whenever
uand vhave the same truth value.
•Symbol used ⇔
•Eg: (p → q) ⇔(¬p ∨q)
Lakshmi R, Asst. Professor, Dept. Of ISE
¬ ∧∨⊻→ ↔
p q ¬p (p → q) (¬p ∨q)
0 0 1 1 1
0 1 1 1 1
1 0 0 0 0
1 1 0 1 1

3. Logical Equivalence contd.,
•Eg: [(p ∨q)∧(¬ p ∨¬ q) ] ⇔p ⊻q
Lakshmi R, Asst. Professor, Dept. Of ISE
¬ ∧∨⊻→ ↔
pq¬p¬q(p ∨q) (¬p ∨¬q)(p ∨q) ∧(¬ p ∨¬ q)p ⊻q
001 1 0 1 0 0
011 0 1 1 1 1
100 1 1 1 1 1
110 0 1 0 0 0

4. Logical Equivalence contd.,
•Eg: [p → (q ∧r) ] ⇔[(p → q) ∧(p → r)]
Lakshmi R, Asst. Professor, Dept. Of ISE
¬ ∧∨⊻→ ↔
pqr(q ∧r)(p → q)(p → r)p → (q ∧r)(p → q) ∧(p → r)
0000 1 1 1 1
0010 1 1 1 1
0100 1 1 1 1
0111 1 1 1 1
1000 0 0 0 0
1010 0 1 0 0
1100 1 0 0 0
1111 1 1 1 1

5. Logical Equivalence contd.,
•Eg: [p ∧(¬ q∨r) ] ⇔[p ∨(q∧¬r) ]
Lakshmi R, Asst. Professor, Dept. Of ISE
¬ ∧∨⊻→ ↔
pqr¬ q(¬ q ∨r) p ∧(¬ q ∨r) ¬r(q ∧¬r) p ∨(q ∧¬r)
0001 1 0 1 0 0
0011 1 0 0 0 0
0100 0 0 1 1 1
0110 1 0 0 0 0
1001 1 1 1 0 1
1011 1 1 0 0 1
1100 0 0 1 1 1
1110 1 1 0 0 1

6. Laws of Logic
Lakshmi R, Asst. Professor, Dept. Of ISE
¬ ∧∨⊻→ ↔
1. Law of double
negation
¬¬ p ⇔p
2. DeMorgan’s
Laws
i.¬ (p ∨q) ⇔¬p ∧¬q
ii.¬ (p ∧q) ⇔¬p ∨¬q
3. Commutative
Laws
i.(p ∧q) ⇔(q ∧p)
ii.(p ∨q) ⇔(q ∨p)
4. Associative
Laws
i.p ∨(q∨r) ⇔(p∨q ) ∨r
ii.p ∧(q ∧r) ⇔(p∧q ) ∧r
5. Distributive
Laws
i.p ∨(q∧r) ⇔(p∨q ) ∧(p ∨r )
ii.p ∧(q ∨r) ⇔(p ∧q ) ∨(p ∧r)
6. Idempotent
Laws
i.(p ∨p) ⇔p
ii.(p ∧p) ⇔p
7. Identity Laws
i.(p ∨F) ⇔p
ii.(p ∧T) ⇔p
8. Inverse Laws
i.(p ∨¬p) ⇔T
ii.(p ∧¬p) ⇔F
9. Domination
Laws
i.(p ∨T) ⇔T
ii.(p ∧F) ⇔F
10. Absorption
Laws
i.p ∨(p ∧q )⇔p
ii.p ∧(p ∨q ) ⇔p
Important p → q ⇔¬ p ∨q

7. Law of negation for a conditional
•Let x be a specific number. Write the negation of the following conditional.
“if x is an integer, then x is a rational number”
Lakshmi R, Asst. Professor, Dept. Of ISE
¬ ∧∨⊻→ ↔
Let
p: x is an integer
q: x is a rational number
The given statement can be symbolically
represented as
p → q
We need to find ¬ (p → q)
Important p → q ⇔¬ p ∨q
¬ (p → q) ⇔¬ (¬p ∨q)
⇔¬¬p ∧¬q(using DeMorgan’sLaw)
⇔p ∧¬q (using law of double negation)
¬ (p → q) is
“x is an integer and x is not a rational number”
Solution
Problem 9:

8. Law of negation for a conditional
•Let x be a specific number. Write the negation of the following conditional.
“if x is not a real number, then it is not a rational number and not an
irrational number”
Lakshmi R, Asst. Professor, Dept. Of ISE
¬ ∧∨⊻→ ↔
Let
p: x is a real number
q: x is a rational number
r: x is an irrational number
The given statement can be symbolically
represented as
¬p →( ¬q ∧¬r)
We need to find ¬ (¬p →( ¬q ∧¬r))
¬ (¬p →( ¬q ∧¬r)) ⇔¬ (¬¬ p ∨(¬q ∧¬r))
⇔¬ ( p ∨(¬q ∧¬r))(using law of double
negation)
⇔¬p ∧¬(¬q ∧¬r)(using DeMorgan’sLaw)
⇔¬ p ∧(¬ ¬q ∨¬ ¬r) (using DeMorgan’sLaw)
⇔¬ p ∧(q ∨r) (law of double negation)
¬ (¬p →( ¬q ∧¬r)) is
“x is not a real number and it is a rational number or an
irrational number”
Solution

9. 1.Prove the following logical equivalences without using truth tables.
i. p ∨[p ∧(p ∨q) ] ⇔p
ii. [p ∨q ∨(¬ p ∧¬ q ∧r) ] ⇔(p ∨q ∨r)
iii. [(¬ p ∨¬ q) → (p ∧q ∧r) ] ⇔p ∧q
Compulsorily you have to use laws of logic to solve
Lakshmi R, Asst. Professor, Dept. Of ISE
¬ ∧∨⊻→ ↔

10. Solution i:
To prove that, p ∨[p ∧(p ∨q) ] ⇔p
p ∨[p ∧(p ∨q) ]
⇔ p ∨[ p ] ----Absorption law
⇔ p ----Idempotent Law
Lakshmi R, Asst. Professor, Dept. Of ISE
¬ ∧∨⊻→ ↔

11. Solution ii:
To prove that, [p ∨q ∨(¬ p ∧¬ q ∧r) ] ⇔(p ∨q ∨r)
[(p ∨q) ∨(¬ p ∧¬ q ∧r) ]
⇔[(p ∨q)∨(¬ (p ∨q) ∧r)] -----DeMorgan’sLaw –eq(1)
Let P = (p ∨q) and Q = ¬ (p ∨q), eq(1) becomes
⇔[P ∨(Q ∧r ) ]
⇔[ (P ∨Q) ∧(P ∨r) ] ---Distributive Law -eq(2)
SubstitutingP = (p ∨q) and Q = ¬ (p ∨q) in eq(2)
⇔[{(p ∨q) ∨¬ (p ∨q)} ∧(p ∨q∨r) ]
⇔[ T ∧(p ∨q ∨r) ] ----Inverse Law
⇔(p ∨q ∨r) ----Identity Law
Lakshmi R, Asst. Professor, Dept. Of ISE
5. Distributive
Laws
8. Inverse Laws
i.(p ∨¬p) ⇔T
ii.(p ∧¬p) ⇔F
i.p ∨(q∧r) ⇔(p∨q ) ∧(p ∨r )
ii.p ∧(q ∨r) ⇔(p ∧q ) ∨(p ∧r)
5. Distributive
Laws
7. Identity Laws
i.(p ∨F) ⇔p
ii.(p ∧T) ⇔p

12. Exercise
iii. [(¬ p ∨¬ q) → (p ∧q ∧r) ] ⇔p ∧q
iv. [(p∨q) ∧(p ∨¬ q)] ∨q ⇔p ∨q
Lakshmi R, Asst. Professor, Dept. Of ISE

13. Prove that (p → q)∧[(¬ q ∧(r ∨¬ q)] ⇔¬ (q ∨p)
Solution:
(p → q)∧[(¬ q ∧(r ∨¬ q)]
⇔ (p → q)∧[(¬ q ∧(¬ q ∨r)] ---Commutative Law
⇔ (p → q)∧¬ q --------------------Absorption Law
⇔ (¬p ∨q) ∧¬ q ------------------Factp → q ⇔¬ p ∨q
⇔ ¬ q ∧(¬p ∨q) -----------------Commutative Law
⇔ (¬ q ∧¬p) ∨(¬ q ∧q) ---------Distributive Law
⇔ (¬ q ∧¬p) ∨F ------------------Inverse Law
⇔ (¬ q ∧¬p) -----------------------Identity Law
⇔ ¬(q∨p) -------------------------DeMorgan’sLaw
Lakshmi R, Asst. Professor, Dept. Of ISE

14. Prove that [¬p ∧(¬ q ∧r ) ] ∨(q ∧r) ∨( p ∧r) ⇔r
Solution:
[¬p ∧(¬ q ∧r ) ] ∨(q ∧r) ∨( p ∧r)
⇔ [¬p ∧(¬ q ∧r ) ] ∨(r ∧q) ∨( r ∧p) -----Commutative Law
⇔ [(¬p ∧¬ q ) ∧r ] ∨(r ∧q) ∨( r ∧p) -----Associative Law
⇔ [¬(p ∨q ) ∧r ] ∨(r ∧q) ∨( r ∧p) -------DeMorgan’sLaw
⇔ [¬(p ∨q ) ∧r] ∨r ∧(q ∨p) --------------Distributive Law
⇔ [r ∧¬(p ∨q ) ] ∨[r ∧(p ∨q)] -------------Commutative Law
Let A = ¬(p ∨q ) and B = (p ∨q)
⇔ [r ∧A] ∨[r ∧B]
⇔ r ∧[ A ∨B ] ------------------------------------Distributive Law
Substituting A = ¬(p ∨q ) and B = (p ∨q) in the above equation
⇔ r ∧[¬(p ∨q )∨(p ∨q)] ⇔r ∧T ---------------Inverse Law
⇔ r --------------Identity Law
Lakshmi R, Asst. Professor, Dept. Of ISE

15. Prove that
[ ( p ∨q) ∧¬ {¬p ∧(¬ q ∨¬r ) } ] ∨(¬ p ∧¬q )∨(¬ p ∧¬r )
is a tautology without using truth tables.
Solution:
To prove that
[ ( p ∨q) ∧¬ {¬p ∧(¬ q ∨¬r ) } ] ∨(¬ p ∧¬q ) ∨(¬ p ∧¬r ) = T
Lakshmi R, Asst. Professor, Dept. Of ISE

16. [ ( p ∨q) ∧¬ {¬p ∧(¬ q ∨¬r ) } ] ∨(¬ p ∧¬q )∨(¬ p ∧¬r )
⇔ [ ( p ∨q) ∧¬ {¬p ∧¬ ( q ∧r ) }] ∨(¬ p ∧¬q ) ∨(¬ p ∧¬r )
-----DeMorgan’sLaw
⇔ [ ( p ∨q) ∧{¬ ¬p∨¬ ¬ ( q ∧r )} ] ∨(¬ p ∧¬q ) ∨(¬ p ∧¬r )
-----DeMorgan’sLaw
⇔ [ ( p ∨q) ∧{p ∨( q ∧r ) } ] ∨(¬ p ∧¬q ) ∨(¬ p ∧¬r )
-----Law of Double Negation
⇔ [ p ∨(q ∧( q ∧r ))] ∨(¬ p ∧¬q ) ∨(¬ p ∧¬r ) ------------Distributive Law
⇔ [ p ∨((q ∧q) ∧r )] ∨(¬ p ∧¬q ) ∨(¬ p ∧¬r ) -------------Associative Law
⇔ [ p ∨(q ∧r )] ∨(¬ p ∧¬q )∨(¬ p ∧¬r ) -------------Idempotent Law
⇔ [ p ∨(q ∧r )] ∨¬ (p ∨q ) ∨¬ ( p ∨r ) -------------DeMorgan’sLaw
⇔ [ p ∨(q ∧r )] ∨¬ [ (p ∨q ) ∧( p ∨r ) ] -------------DeMorgan’sLaw
⇔ [ p ∨(q ∧r )] ∨¬ [ (p ∨( q ∧r ) ] -------------Distributive Law
Let u = p ∨(q ∧r )
⇔ [ p ∨(q ∧r )] ∨¬ [ (p ∨( q ∧r ) ] ⇔u ∨¬u ⇔T --------Inverse Law
Lakshmi R, Asst. Professor, Dept. Of ISE

17. Application to switching networks
•We can relate switches and their states with propositions and their truth
values.
•Value 0 ----> when switch is open
•Value 1 ----> when switch is closed
•Laws of logic –simplify the complex switching networks.
Lakshmi R, Asst. Professor, Dept. Of ISE

18. Application to switching networks
1. Simplify the switching network.
Lakshmi R, Asst. Professor, Dept. Of ISE
Solution:
We write the given network as:
[p ∧(¬ r ∨q ∨¬ q )] ∨[(r∨t V ¬ r) ∧¬ q ]
r
t
¬ r
¬ r
q
¬q
p
T1 T2
¬q

19. Lakshmi R, Asst. Professor, Dept. Of ISE
[p ∧(¬ r ∨q ∨¬ q)] ∨[(r∨t V ¬ r) ∧¬ q ]
⇔ [p ∧(¬ r ∨T)] ∨[(t V T)∧¬ q ] ---Inverse Law
⇔ [p ∧(T)] ∨[(T) ∧¬ q] ---Domination Law
⇔ [p ∨¬ q ] ---Identity Law
p
¬q
T1 T2
The simplified network is

20. Application to switching networks
2. Simplify the switching network.
Lakshmi R, Asst. Professor, Dept. Of ISE
p
q
r
p
t
¬q
p
¬ t
r
T1 T2
Solution:
We write the given network as:
(p ∨q ∨r) ∧(p ∨t ∨¬ q ) ∧(p ∨¬ t V r)

21. Lakshmi R, Asst. Professor, Dept. Of ISE
(p ∨q ∨r) ∧(p ∨t ∨¬ q ) ∧(p ∨¬ t V r)
⇔[p ∨((q ∨r) ∧( t ∨¬ q) )] ∧(p ∨¬ t V r)
Distributive Law
⇔ p ∨[((q ∨r) ∧( t ∨¬ q)) ∧(¬ t V r) ]Distributive Law
⇔p ∨[((q ∨r) ∧(¬ t V r)) ∧( t ∨¬ q)]Associative law
⇔p ∨[((r ∨q) ∧(r V ¬ t))∧( t ∨¬ q)]Commutative law
⇔p ∨[r ∨( q ∧¬ t)] ∧( t ∨¬ q)]Distributive Law

22. Lakshmi R, Asst. Professor, Dept. Of ISE
⇔ p ∨[r ∨( q ∧¬ t)] ∧( t ∨¬ q)]
⇔ p ∨[( t ∨¬ q) ∧[r ∨( q ∧¬ t)]]Commutative Law
⇔ p ∨[[( t ∨¬ q) ∧r] ∨[( t ∨¬ q) ∧( q ∧¬ t)]] -Distributive Law
⇔ p ∨[[( t ∨¬ q) ∧r] ∨[( t ∨¬ q) ∧(¬ t ∧q)]] -Commutative law
⇔ p ∨[[( t ∨¬ q) ∧r] ∨[( t ∨¬ q) ∧¬(t ∨¬q)]] -DeMorgan’sLaw
⇔ p ∨[[( t ∨¬ q) ∧r] ∨[( t ∨¬ q) ∧¬ (t ∨¬ q)]]
⇔ p ∨[( t ∨¬ q) ∧r] ∨F] -Inverse Law
⇔ p ∨[( t ∨¬ q) ∧r] -Identity Law
p
t
¬q
rT1
T2

23. Lakshmi R, Asst. Professor, Dept. Of ISE
p
q
r
p
t
¬q
p
¬ t
r
T1 T2
Simplified circuit is
p
t
¬q
rT1
T2
Given circuit is

24. Exercise
Prove the following logical equivalences without using truth tables.
i.[(¬ p ∨¬ q) → (p ∧q ∧r) ] ⇔p ∧q
ii.[(p ∨q) ∧(p ∨¬ q)] ∨q ⇔p ∨q
iii.p → (q → r) ⇔(p ∧q) → r
iv.¬ [{(p ∨q) ∧r} → ¬q] ⇔¬ (¬ {(p ∨q) ∧r} ∨¬q) ⇔q ∧r

25. Exercise
¬ p
p
q
r r
T1 T2
¬q
r
Simplify the following switching networks
¬ p¬qr
p r
q r
T1 T2
2
1

26. Converse, Inverse, and Contrapositive
Consider a conditional p → q. then,
i.q →pis called the converse of p → q
ii.¬p → ¬q is called the inverse of p → q
iii.¬q → ¬p is called the contrapositive of p → q
Lakshmi R, Asst. Professor, Dept. Of ISE
pq¬p¬qp → qq →p¬p → ¬q ¬q →¬p
0011 1 1 1 1
0110 1 0 0 1
1001 0 1 1 0
1100 1 1 1 1
p → qq →p¬p → ¬q ¬q →¬p
1 1 1 1
1 0 0 1
0 1 1 0
1 1 1 1
p → q ⇔¬q→¬p
q→ p ⇔¬p→ ¬q
Conditional ⇔Contrapositive
Converse ⇔Inverse

27. Converse, Inverse, and Contrapositive cont.,
State converse, inverse, and contrapositive of the following implication.
“If a triangle is not isosceles, then it is not equilateral”
Solution: The given implication p → q is If a triangle is not isosceles, then it is
not equilateral
Let p: Triangle is not isosceles
q: Triangle is not equilateral
Converse: q →p : If a triangle is not equilateral, then it is not isosceles
Inverse: ¬p → ¬q : If a triangle is isosceles, then it is equilateral.
Contrapositive: ¬q→ ¬p: If a triangle is equilateral, then it is isosceles.
Lakshmi R, Asst. Professor, Dept. Of ISE