set identities and their examples outlined.pptx

set identities and their examples outlined.pptx

1. SET IDENTITIES Lecture # 09

2. Let A , B , C be subsets of a universal set U . Idempotent Laws a. A  A = A b. A  A = A Commutative Laws a. A  B = B  A b. A  B = B  A Associative Laws a. A  (B  C) = (A  B)  C b. A  (B  C) = (A  B)  C SETS IDENTITIES

3. Distributive Laws a. A  (B  C) = (A  B)  (A  C) b. A  (B  C) = (A  B)  (A  C) Identity Laws a. A   = A b. A   =  c. A  U = U d. A  U = A Complement Laws a. A  A c = U b. A  A c =  c. U c =  d.  c = U

4. Double Complement Law (A c ) c = A De-Morgan’s Laws a. (A  B) c = A c  B c b. (A  B) c = A c  B c Alternative Representation for Set Difference A – B = A  B c

5. Subset Laws a. A  B  C iff A  C and B  C b. C  A  B iff C  A and C  B Absorption Laws a. A  (A  B) = A b. A  (A  B) = A

6. EXERCISE Let A , B & C be subsets of a universal set U . Show that: A  A  B A – B  A If A  B and B  C then A  C A  B if, and only if , B c  A c

7. SOLUTION A – B  A Solution: Let x  A – B  x  A and x  B (by definition of A – B)  x  A (in particular) But x is an arbitrary element of A – B  A – B  A (proved)

8. SOLUTION If A  B and B  C , then A  C Solution: Suppose that A  B and B  C Consider x  A  x  B (as A  B)  x  C (as B  C) But x is an arbitrary element of A  A  C (proved)

9. SOLUTION Prove that A  B iff B c  A c Solution: Suppose A  B {To prove B c  A c } Let x  B c  x  B (by definition of B c )  x  A (A  B  if x  A then x  B contrapositive : if x  B then x  A)  x  A c (by definition of A c ) Thus if we show for any two sets A and B, if x  B then x  A . But x is an arbitrary element of B c  B c  A c

10. Cont… Conversely, Suppose B c  A c {To prove A  B} Let x  A  x  A c (by definition of A c )  x  B c (  B c  A c )  x  B (by definition of B c ) But x is an arbitrary element of A.  A  B (proved)

11. SOLUTION A  A  B Solution: Let x be the arbitrary element of A, that x  A  x  A or x  B  x  A  B But x is an arbitrary element of A.  A  A  B (proved)

12. EXERCISE Let A , B & C be subsets of a universal set U . Prove that: A – B = A  B c EQUAL SETS: Two sets are equal if first is subset of second and second is subset of first .  A – B  A  B c and A  B c  A – B

13. SOLUTION Let x  A – B x  A and x  B (definition of set difference) x  A and x  B c (definition of complement) x  A  B c (definition of intersection) But x is an arbitrary element of A – B So we can write:  A – B  A  B c ………….(1)

14. Cont… Conversely,  Let y  A  B c  y  A and y  B c (definition of intersection)  y  A and y  B (definition of complement)  y  A – B (definition of set difference) But y is an arbitrary element of A  B c  A  B c  A – B…………. (2) From (1) and (2) it follows that A – B = A  B c (as required)

15. DEMORGAN’S LAW (A  B) c = A c  B c EQUAL SETS: Two sets are equal if first is subset of second and second is subset of first .  (A  B) c  A c  B c and A c  B c  (A  B) c

16. PROOF First we show that (A  B) c  A c  B c Let x  (A  B) c  x  AB (definition of complement )  x  A and x  B ( DeMorgan’s Law of Logic)  x  A c and x  B c (definition of complement)  x  A c  B c (definition of intersection) But x is an arbitrary element of (A  B) c so we have proved that:  (A  B) c  A c  B c ………(1)

17. Cont… Conversely,  Let y  A c  B c  y  A c and y  B c (definition of intersection)  y  A and y  B (definition of complement)  y  A  B (definition of set difference)  y  (A  B) c (definition of complement) But y is an arbitrary element of A c  B c  A c  B c  A  B…………. (2) From (1) and (2) it follows that (A  B) c = A c  B c ( Demorgans Law)

18. ASSOCIATIVE LAW A  (B  C) = (A  B)  C PROOF: First we show that A  (B  C)  (A  B)  C Consider x  A  (B  C)  x  A and x  B  C (definition of intersection)  x  A and x  B and x  C (definition of intersection)  x  A  B and x  C (definition of intersection)  x  (A  B)  C (definition of intersection) But x is an arbitrary element of A  (B  C)  A  (B  C)  (A  B)  C……(1)

19. Cont… Conversely, Let y  (A  B)  C  y  A  B and y  C (definition of intersection)  y  A and y  B and y  C (definition of intersection)  y  A and y  B  C (definition of intersection)  y  A  (B  C) (definition of intersection) But y is an arbitrary element of (A  B)  C  (A  B)  C  A  (B  C)……..(2) From (1) & (2), we conclude that A  (B  C) = (A  B)  C (proved)

20. USING SET IDENTITIES For all subsets A and B of a universal set U, prove that (A – B)  (A  B) = A PROOF : LHS: = (A – B)  (A  B) = (A  B c )  (A  B) (Alternative representation for set difference) = A  ( B c  B) Distributive Law = A  U Complement Law = A Identity Law = RHS (proved)

21. The result can also be proved through Venn diagram. A B A - B A  B A – B  A  B

22. EXERCISE A – (A – B) = A  B PROOF: LHS = A – (A – B) = A – (A  B c ) Alternative representation for set difference = A  (A  B c ) c Alternative representation for set difference = A  ((A c  ( B c ) c ) DeMorgan’s Law = A  (A c  B) Double Complement Law = (A  A c )  (A  B) Distributive Law =   (A  B) Complement Law = A  B Identity Law = RHS (proved)

23. EXERCISE (A – B) – C = (A – C) – B PROOF: LHS = (A – B) – C = (A  B c ) – C Alternative representation for set difference = (A  B c )  C c Alternative representation for set difference = A  ( B c  C c ) Associative Law = A  (C c  B c ) Commutative Law = (A  C c )  B c Associative Law = (A – C)  B c Alternative representation of set difference = (A – C) – B Alternative representation of set difference = RHS (proved)

24. EXERCISE Simplify ( B c  ( B c – A)) c Solution: ( B c  ( B c – A)) c = ( B c  ( B c  A c )) c Alternative representation for set difference = ( B c ) c  ( B c  A c ) c DeMorgan’s Law = B  ( B c  A c ) c Double Complement Law = B  (( B c ) c  (A c ) c ) DeMorgan’s Law = B  (B  A) Double Complement Law = B Absorption Law

25. PROVING SET IDENTITIES BY MEMBERSHIP TABLE Prove the following using Membership Table : A – ( A – B ) = A  B ( A  B ) c = A c  B c A – B = A  B c

26. SOLUTION A – (A – B) = A  B A B A - B A - (A - B) A  B 1 1 1 1 1 1 1

27. SOLUTION (A  B) c = A c  B c A B A  B (A  B) c A c B c A c  B c 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

28. SOLUTION A – B = A  B c A B A – B B c A  B c 1 1 1 1 1 1 1 1