Formal Logic - Lesson 5 - Logical Equivalence

Formal Logic - Logical Equivalence Presentation

1. z
FORMAL LOGIC
Discrete Structures I
FOR-IAN V. SANDOVAL

2. z
Lesson 5
LOGICAL EQUIVALENCE

3. z
LEARNING OBJECTIVES
❑Determine if the logical expression is logically equivalent

4. z
LOGICAL EQUIVALENT
❑Twostatementsaresaidtobelogicallyequivalent(or
equivalent)iftheyhavethesametruthvalueforeveryrow
ofthetruthtable,thatisifx↔yisatautology.
❑Symbolically,x≡y.
❑i.e.
❑Showthatp^(qvr)and(p^q)v(p^r)areequal.

5. z
LOGICAL EQUIVALENT
p q rq v rp ^ (q v r ) p ^ qp ^ r (p ^ q) v (p ^ r )
TTT
TTF
TFT
TFF
FTT
FTF
FFT
FFF

6. z
LOGICAL EQUIVALENT
p q rq v rp ^ (q v r ) p ^ qp ^ r (p ^ q) v (p ^ r )
TTTT
TTFT
TFTT
TFFF
FTTT
FTFT
FFTT
FFFF

7. z
LOGICAL EQUIVALENT
p q rq v rp ^ (q v r ) p ^ qp ^ r (p ^ q) v (p ^ r )
TTTT T
TTFT T
TFTT T
TFFF F
FTTT F
FTFT F
FFTT F
FFFF F

8. z
LOGICAL EQUIVALENT
p q rq v rp ^ (q v r ) p ^ qp ^ r (p ^ q) v (p ^ r )
TTTT T T
TTFT T T
TFTT T F
TFFF F F
FTTT F F
FTFT F F
FFTT F F
FFFF F F

9. z
LOGICAL EQUIVALENT
p q rq v rp ^ (q v r ) p ^ qp ^ r (p ^ q) v (p ^ r )
TTTT T T T
TTFT T T F
TFTT T F T
TFFF F F F
FTTT F F F
FTFT F F F
FFTT F F F
FFFF F F F

10. z
LOGICAL EQUIVALENT
p q rq v rp ^ (q v r ) p ^ qp ^ r (p ^ q) v (p ^ r )
TTTT T T T T
TTFT T T F T
TFTT T F T T
TFFF F F F F
FTTT F F F F
FTFT F F F F
FFTT F F F F
FFFF F F F F

11. z
LOGICAL EQUIVALENT
❑EnrichmentExercise
Determinewhetherthefollowingcompound
statementsarelogicallyequivalentusingtruthtables.
1.p→qand~q→~p
2.p↔qand(p→q)^(q→p)

12. z
LOGICAL EQUIVALENT
1.p→qand~q→~p
p q p →q ~q ~p ~q →~p
T T T
T F F
F T T
F F T

13. z
LOGICAL EQUIVALENT
1.p→qand~q→~p
p q p →q ~q ~p ~q →~p
T T T F
T F F T
F T T F
F F T T

14. z
LOGICAL EQUIVALENT
1.p→qand~q→~p
p q p →q ~q ~p ~q →~p
T T T F F
T F F T F
F T T F T
F F T T T

15. z
LOGICAL EQUIVALENT
1.p→qand~q→~p
p q p →q ~q ~p ~q →~p
T T T F F T
T F F T F F
F T T F T T
F F T T T T

16. z
LOGICAL EQUIVALENT
2.p↔qand(p→q)^(q→p)
p q p ↔ q p →q q →p (p →q) ^ (q →p)
T T T
T F F
F T F
F F T

17. z
LOGICAL EQUIVALENT
2.p↔qand(p→q)^(q→p)
p q p ↔ q p →q q →p (p →q) ^ (q →p)
T T T T
T F F F
F T F T
F F T T

18. z
LOGICAL EQUIVALENT
2.p↔qand(p→q)^(q→p)
p q p ↔ q p →q q →p (p →q) ^ (q →p)
T T T T T
T F F F T
F T F T F
F F T T T

19. z
LOGICAL EQUIVALENT
2.p↔qand(p→q)^(q→p)
p q p ↔ q p →q q →p (p →q) ^ (q →p)
T T T T T T
T F F F T F
F T F T F F
F F T T T T

20. z
LAWS OF LOGICAL EQUIVALENCE
❑Letp,q,andrstandsforanystatements.
❑LetTindicatestautologyandFindicatescontradiction.
Laws Logical Equivalence
Commutative
p ^ q ≡q ^ p
p v q ≡q v p
Associative
p ^ (q ^ r) ≡(p ^ q) ^ r
p v (q v r) ≡(p v q) v r
Distributive
p ^ (q v r) ≡(p ^ q) v (p ^ r)
p v (q ^ r) ≡(p v q) ^ (p v r)
Identity
p ^ T≡p
p v F≡p
Inverse
p ^ ~p ≡F
p v ~p ≡T

21. z
LAWS OF LOGICAL EQUIVALENCE
❑Letp,q,andrstandsforanystatements.
❑LetTindicatestautologyandFindicatescontradiction.
Laws Logical Equivalence
Double Negation
~(~p) ≡p
Idempotent
p ^ p ≡p
p v p ≡p
De Morgan’s
~(p ^ q) ≡~p v ~q
~(p v q) ≡~p ^ ~q
Universal Bound
p ^ F≡F
p v T≡T
Absorption
p ^ (p v q) ≡p
p v (p ^ q) ≡p

22. z
LAWS OF LOGICAL EQUIVALENCE
❑Additionallogicalequivalencesareasfollows.
Laws Logical Equivalence
Exportation Law
(p ^ q) →r ≡p →(q →r)
Contrapositive
p →q ≡~q →~p
ReductoAd Absurdum
p →q ≡(p ^ ~q) →F
Equivalence
p ↔q ≡(p →q) ^ ( q →p)
p ↔q ≡(~p v q) ^ ( p v ~q)
Implication
p →q ≡~p v q

23. z
LOGICAL EQUIVALENT EXAMPLE
❑Simplifythefollowingcompoundstatementsusingthelaws
ofequivalence.
1.[pv(~p^q)]v(pv~q)
2.[qv(~p^q)v(pv~q)]^~q

24. z
LOGICAL EQUIVALENT EXAMPLE
1.[pv(~p^q)]v(pv~q)
[pv(~p^q)]v(pv~q)≡[pv(~p^q)]v(pv~q)≡[(pv~p)^(pvq)]v(pv~q)
DistributiveLaw
[pv(~p^q)]v(pv~q)≡[(pv~p)^(pvq)]v(pv~q)
DistributiveLaw
[pv(~p^q)]v(pv~q)≡[T^(pvq)]v(pv~q)
InverseLaw
[pv(~p^q)]v(pv~q)≡(pvq)v(pv~q)
IdentityLaw
[pv(~p^q)]v(pv~q)≡(pvq)v(pv~q)
IdentityLaw
[pv(~p^q)]v(pv~q)≡pv(qv~q)
DistributiveLaw
[pv(~p^q)]v(pv~q)≡pv(qv~q)
DistributiveLaw
[pv(~p^q)]v(pv~q)≡pvT
InverseLaw
[pv(~p^q)]v(pv~q)≡T
UniversalBoundLaw

25. z
LOGICAL EQUIVALENT EXAMPLE
2.[qv(pv~q)v(~pv~q)]^~q
[qv(pv~q)v(~pv~q)]^~q≡[qv(pv~q)v(~pv~q)]^~q≡[qv(~qvp)v(~pv~q)]^~q
CommutativeLaw
[qv(pv~q)v(~pv~q)]^~q≡[qv(~qvp)v(~pv~q)]^~q
CommutativeLaw
[qv(pv~q)v(~pv~q)]^~q≡[(qv~q)vpv(~pv~q)]^~q
AssociativeLaw
[qv(pv~q)v(~pv~q)]^~q≡[(qv~q)vpv(~pv~q)]^~q
AssociativeLaw
[qv(pv~q)v(~pv~q)]^~q≡[Tvpv(~pv~q)]^~q
InverseLaw
[qv(pv~q)v(~pv~q)]^~q≡[Tvpv(~pv~q)]^~q
InverseLaw
[qv(pv~q)v(~pv~q)]^~q≡[(Tvp)v(~pv~q)]^~q
AssociativeLaw
[qv(pv~q)v(~pv~q)]^~q≡[(pvT)v(~pv~q)]^~q
CommutativeLaw

26. z
LOGICAL EQUIVALENT EXAMPLE
2.[qv(pv~q)v(~pv~q)]^~q
[qv(pv~q)v(~pv~q)]^~q≡[Tv(~pv~q)]^~q
UniversalBoundLaw
[qv(pv~q)v(~pv~q)]^~q≡[Tv(~pv~q)]^~q
[qv(pv~q)v(~pv~q)]^~q≡[(~pv~q)vT]^~q
CommutativeLaw
[qv(pv~q)v(~pv~q)]^~q≡T^~q
UniversalBoundLaw
[qv(pv~q)v(~pv~q)]^~q≡T^~q
UniversalBoundLaw
[qv(pv~q)v(~pv~q)]^~q≡~q^T
CommutativeLaw
[qv(pv~q)v(~pv~q)]^~q≡~q
IdentityLaw

27. z
LOGICAL EQUIVALENT EXAMPLE
2.[qv(pv~q)v(~pv~q)]^~q
[qv(pv~q)v(~pv~q)]^~q≡[qv(~qvp)v(~pv~q)]^~q
CommutativeLaw
[qv(pv~q)v(~pv~q)]^~q≡[(qv~q)vp)v(~pv~q)]^~q
AssociativeLaw
[qv(pv~q)v(~pv~q)]^~q≡[(qv~q)vp)v(~pv~q)]^~q
InverseLaw
[qv(pv~q)v(~pv~q)]^~q≡[(Tvp)v(~pv~q)]^~q
AssociativeLaw
[qv(pv~q)v(~pv~q)]^~q≡[Tvpv(~pv~q)]^~q
InverseLaw

28. z
LOGICAL EQUIVALENT EXAMPLE
2.[qv(pv~q)v(~pv~q)]^~q
[qv(pv~q)v(~pv~q)]^~q≡[Tv(~pv~q)]^~q
UniversalBoundLaw
[qv(pv~q)v(~pv~q)]^~q≡~q
IdentityLaw
[qv(pv~q)v(~pv~q)]^~q≡[Tv(~pv~q)]^~q
UniversalBoundLaw
[qv(pv~q)v(~pv~q)]^~q≡T^~q
UniversalBoundLaw

29. z
Group Enrichment Exercises
❑Simplifythefollowingcompoundstatementsusingthelaws
ofequivalence.
1.[(p^r)v(q^r)]v~q
2.[pv(~pvq)v(pv~q)]^~q
3.~(p→q)^(p↔q)

30. z
Group Enrichment Exercises
1.[(p^r)v(q^r)]v~q
[(p^r)v(q^r)]v~q≡
[(p^r)v(q^r)]v~q≡[(pvq)v~q]^(rv~q)
DistributiveLaw
[(p^r)v(q^r)]v~q≡[(pv(qv~q)]^(rv~q)
AssociativeLaw
[(p^r)v(q^r)]v~q≡[(pvq)^r]v~q
DistributiveLaw
[(p^r)v(q^r)]v~q≡[(pvq)^r]v~q
DistributiveLaw
[(p^r)v(q^r)]v~q≡[(pvq)v~q]^(rv~q)
DistributiveLaw
[(p^r)v(q^r)]v~q≡[(pv(qv~q)]^(rv~q)
AssociativeLaw
[(p^r)v(q^r)]v~q≡[(pvT)]^(rv~q)
InverseLaw
[(p^r)v(q^r)]v~q≡[(pvT)]^(rv~q)
InverseLaw
[(p^r)v(q^r)]v~q≡T^(rv~q)
UniversalBoundLaw
[(p^r)v(q^r)]v~q≡rv~q
IdentityLaw
[(p^r)v(q^r)]v~q≡rv~q
IdentityLaw

31. z
Group Enrichment Exercises
1.[(p^r)v(q^r)]v~q
[(p^r)v(q^r)]v~q≡~qvr
CommutativeLaw

32. z
Group Enrichment Exercises
2.[pv(~pvq)v(pv~q)]^~q
[pv(~pvq)v(pv~q)]^~q≡[pv(~pvq)v(pv~q)]^~q≡[pv(~pvq)v(pv~q)]^~q≡[(pv~p)vqv(pv~q)]^~q
AssociativeLaw
[pv(~pvq)v(pv~q)]^~q≡[(pv~p)vqv(pv~q)]^~q
AssociativeLaw
[pv(~pvq)v(pv~q)]^~q≡[Tvqv(pv~q)]^~q
InverseLaw
[pv(~pvq)v(pv~q)]^~q≡[Tvqv(pv~q)]^~q
InverseLaw
[pv(~pvq)v(pv~q)]^~q≡[(Tvq)v(pv~q)]^~q
AssociativeLaw
[pv(~pvq)v(pv~q)]^~q≡[(qvT)v(pv~q)]^~q
CommutativeLaw
[pv(~pvq)v(pv~q)]^~q≡[Tv(pv~q)]^~q
UniversalBoundLaw
[pv(~pvq)v(pv~q)]^~q≡[Tv(pv~q)]^~q
UniversalBoundLaw
[pv(~pvq)v(pv~q)]^~q≡[(pv~q)vT]^~q
CommutativeLaw
[pv(~pvq)v(pv~q)]^~q≡T^~q
UniversalBoundLaw

33. z
Group Enrichment Exercises
2.[pv(~pvq)v(pv~q)]^~q
[pv(~pvq)v(pv~q)]^~q≡~q
IdentityLaw

34. z
Group Enrichment Exercises
3.~(p→q)^(p↔q)
~(p→q)^(p↔q)≡~(p→q)^(p↔q)≡~(p→q)^(p↔q)≡~(~pvq)^(p↔q)
ImplicationLaw
~(p→q)^(p↔q)≡~(~pvq)^(p↔q)
ImplicationLaw
~(p→q)^(p↔q)≡[~(~p)^~q)]^(p↔q)
DeMorgan’sLaw
~(p→q)^(p↔q)≡[~(~p)^~q)]^(p↔q)
DeMorgan’sLaw
~(p→q)^(p↔q)≡(p^~q)^(p↔q)
DoubleNegationLaw
~(p→q)^(p↔q)≡(p^~q)^(p↔q)
DoubleNegationLaw
~(p→q)^(p↔q)≡(p^~q)^[(~pvq)^(pv~q)]
EquivalenceLaw
~(p→q)^(p↔q)≡(p^~q)^(pv~q)^(~pvq)
CommutativeLaw
~(p→q)^(p↔q)≡(p^~q)^(pv~q)^(~pvq)
CommutativeLaw
~(p→q)^(p↔q)≡[(p^~q)^(pv~q)]^(~pvq)
CommutativeLaw
~(p→q)^(p↔q)≡{(p^[~q^(pv~q)]}^(~pvq)
AssociativeLaw
~(p→q)^(p↔q)≡{(p^[~q^(pv~q)]}^(~pvq)
AssociativeLaw

35. z
Group Enrichment Exercises
3.~(p→q)^(p↔q)
~(p→q)^(p↔q)≡{(p^[~q^(~qvp)]}^(~pvq)
CommutativeLaw
~(p→q)^(p↔q)≡{(p^[~q^(~qvp)]}^(~pvq)
CommutativeLaw
~(p→q)^(p↔q)≡(p^~q)^(~pvq)
AbsorptionLaw
~(p→q)^(p↔q)≡(p^~q)^(~pvq)
AbsorptionLaw
~(p→q)^(p↔q)≡p^[~q^(~pvq)]
AssociativeLaw
~(p→q)^(p↔q)≡p^[(~q^~p)v(~q^q)]
DistributiveLaw
~(p→q)^(p↔q)≡p^[(~q^~p)v(~q^q)]
DistributiveLaw
~(p→q)^(p↔q)≡p^[(~q^~p)v(q^~q)]
CommutativeLaw
~(p→q)^(p↔q)≡p^[(~q^~p)vF]
InverseLaw
~(p→q)^(p↔q)≡p^(~q^~p)
IdentityLaw
~(p→q)^(p↔q)≡p^(~q^~p)
IdentityLaw
~(p→q)^(p↔q)≡p^[(~q^~p)vF]
InverseLaw

36. z
Group Enrichment Exercises
3.~(p→q)^(p↔q)
~(p→q)^(p↔q)≡p^(~p^~q)
CommutativeLaw
~(p→q)^(p↔q)≡p^(~p^~q)
CommutativeLaw
~(p→q)^(p↔q)≡(p^~p)^~q
AssociateLaw
~(p→q)^(p↔q)≡F^~q
InverseLaw
~(p→q)^(p↔q)≡~q^F
CommutativeLaw
~(p→q)^(p↔q)≡F
UniversalBoundLaw

37. z
•Levin, O. (2019). Discrete Mathematics: An Open Introduction 3
rd
Edition. Colorado: School of Mathematics Science
University of Colorado.
•Aslam, A. (2016). Proposition in Discrete Mathematics retrieved from https://www.slideshare.net/AdilAslam4/chapter-1-
propositions-in-discrete-mathematics
•Operator Precedence retrieved from http://intrologic.stanford.edu/glossary/operator_precedence.html
REFERENCES