sets.pptx set operations set notation of sets

aset

1. Set Operators Goals Show how set identities are established Introduce some important identities.

2. Copyright © Peter Cappello 2 Union Let A & B be sets. A union B, denoted A  B , is the set A  B = { x | x  A  x  B }. Draw a Venn diagram to visualize this. Example O = { x  N | x is odd }. S = { s  N |  x  N s = x 2 }. Describe O  S.

3. Copyright © Peter Cappello 3 Intersection Let A & B be sets. A intersection B, denoted A  B , is the set A  B = { x | x  A  x  B }. Draw a Venn diagram to visualize this. Example O = { x  N | x is odd }. S = { s  N |  x  N s = x 2 }. Describe O  S. A & B are disjoint when A  B =  .

4. Copyright © Peter Cappello 4 Difference Let A & B be sets. The difference of A & B, denoted A – B , is A – B = { x | x  A  x  B }. Draw a Venn diagram to visualize this. Example O = { x  N | x is odd }. S = { s  N |  x s = x 2 }. Describe O – S.

5. Copyright © Peter Cappello 5 Complement Let A be a set. The complement of A is { x | x  A } = U – A. Draw a Venn diagram to visualize this. Example O = { x  N | x is odd}. Describe the complement of O. Since I cannot overline in Powerpoint , I denote the complement of A as A .

6. Copyright © Peter Cappello 6 Set Identities Identity Name of laws A   = A A  U = A Identity A  U = U A   =  Domination A  A = A A  A = A Idempotent Complement of A = A Complementation A  B = B  A A  B = B  A Commutative

7. Copyright © Peter Cappello 7 Identity Name of laws A  (B  C)= (A  B)  C A  (B  C)= (A  B)  C Associative A  (B  C) = (A  B)  (A  C) A  (B  C) = (A  B)  (A  C) Distributive A  B = A  B A  B = A  B De Morgan A  (A  B) = A A  (A  B) = A Absorption A  A = U A  A =  Complement

8. Think like a mathematician How much is new here? Logic Set x  S S False  True Universe      complement  = Can you mechanically produce set identities from propositional identities via this translation? Example: ( x  A  x   )  x  A A   = A Copyright © Peter Cappello 8

9. Copyright © Peter Cappello 9 Prove A  B = A  B Venn diagrams Draw the Venn diagram of the LHS. Draw the Venn diagram of the RHS. Explain that the regions match.

10. Copyright © Peter Cappello 10 Prove A  B = A  B Use set operator definitions A  B = { x | x  A  B } ( defn . of complement) = { x |  (x  A  B) } ( defn . of  ) = { x |  (x  A  x  B) } ( defn . of  ) = { x | (x  A  x  B) } ( Propositional De Morgan) = { x | (x  A  x  B ) } ( defn . of complement ) = A  B ( defn . of  )

11. Copyright © Peter Cappello 11 Prove A  B = A  B Membership Table A B A  B A  B A B A  B F F F T T T T F T T F T F F T F T F F T F T T T F F F F 1 2 3 4 A B Let x be an arbitrary member of the Universe. In the table below, each column denotes the proposition function “ x is a member of this set.”

12. Think like a mathematician Is membership table the analog of truth table? With 3 propositional variables , a truth table has 2 3 rows. With 3 sets , do we have 2 3 regions? Does this generalize to n sets? What is the analog of modus ponens? What is the set analog of p  q? What is the set analog of a tautology? If interested, see chapter 12 of textbook. Copyright © Peter Cappello 12

13. Analogy between logic & sets In logic: p  q ≡  p  q Its set analog is P  Q Set analog of modus ponens ( p  ( p  q ) )  q is Complement[ P  ( P  Q ) ]  Q Copyright © Peter Cappello 13

14. Copyright © Peter Cappello 14 Computer Representation of Sets There are many ways to represent sets. Which is best depends on the particular sets & operations. Bit string: Let | U | = n , where n is not “too” large: U = { a 1 , …, a n }. Represent set A as an n -bit string. If ( a i  A ) bit i = 1; else bit i = 0. Operations  ,  , _ are performed bitwise. In Java, Set is the name of an interface . Consider a Java set class (e.g., BitStringSet ), where | U | is a constructor parameter. What data structures might be useful to implement the interface? What public methods might you want? How would you implement them?