Week 07& 08 Set Operations Discrete Structures.pptx

Week 07& 08 Set Operations Discrete Structures

1. ( MA-216) - Discrete Structures (Discrete Mathematics) Spring 2025 Set Operations Week- 07 & 08

2. Outline Set operations Set Union Set Intersection Set Difference Complement of Set Cartesian Product Set Identities

3. In Discrete Mathematics, set operations are basic ways to combine or compare sets to create new sets. Set theory rules and are important in logic, probability, and computing. Two sets can be combined in many different ways. Set Operations

4. Let A and B be sets. The union of A and B, denoted by A ⋃ B, is the set containing those elements that are either in A or in B, or in both. A ⋃ B = {x | x ∈ A ˅ x ∈ B} Union

5. Let A and B be sets. The intersection of A and B, denoted by A ∩ B, is the set containing those elements in both A and B. A ∩ B = {x | x ∈ A ˄ x ∈ B} Intersection

6. Let A = {1,2,3} B = {2,4,6,8} A ⋃ B = {1,2,3,4,6,8} Let A = {x | x ∈ Z ˄ x is even} B = {x |x ∈ Z ˄ x is odd} A ⋃ B = Z Union (example)

7. Let A = {1,2,3} B = {2,4,6,8} A ∩ B = { 2 } Let A = Z B = {x |x ∈ Z ˄ x is odd} A ∩ B = {x |x ∈ Z ˄ x is odd} Intersection (example)

8. Two sets are called disjoint if their intersection is empty. Let A = {x | x ∈ Z ˄ x is even} B = {x |x ∈ Z ˄ x is odd} A ∩ B = Ø Disjoint Sets

9. |A ⋃ B|=? Solution: Let A = {1,2,3} B = {2,3,4} A ⋃ B = {1,2,3,4} |A| = 3 |B| = 3 |A ⋃ B|=4 |A ⋃ B| = |A| + |B| - |A ∩ B| Cardinality of the Union of Sets

10. Let A and B be sets. The difference of A and B, denoted by A - B , is the set containing those elements that are in A but not in B. (also called complement of B with respect to A ). A - B = {x | x ∈ A ˄ x ∉ B} Difference

11. Let A = {1,2,3} B = {2,4} A – B = {1,3} Let A = Z B = { x | x ∈ Z ˄ x is odd } A – B = { x | x ∈ Z ˄ x is even } Difference (example)

12. Let U be the universal set and A be a set. The complement of A, denoted by A , is the complement of A with respect to U (which is U - A). Complement

13. Let A = { a, b, c, d } and U is the set of English alphabet A = { e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z } Let A = { x | x ∈ Z ˄ x is odd } and U is Z A = { x | x ∈ Z ˄ x is even } Complement (example)

14. The Cartesian product of n number of sets A 1 , A 2 ,… A n denoted as A 1 × A 2 ⋯× A n can be defined as all possible ordered pairs ( x 1 , x 2 ,… x n ) Where x 1 ∈ A 1 , x 2 ∈ A 2 ,… x n ∈ A n Example : If we take two sets A ={ a , b } and B ={1,2} 14 Cartesian Product / Cross Product

15. The Cartesian product of A and B is written as: A × B ={( a ,1),( a ,2),( b ,1),( b ,2)} The Cartesian product of B and A is written as: B × A ={(1, a ),(1, b ),(2, a ),(2, b )} 15 Cartesian Product / Cross Product (Cont.)

16. Operation Notation Union A ⋃ B = {x | x ∈ A ˅ x ∈ B} Intersection A ∩ B = {x | x ∈ A ˄ x ∈ B} Difference A - B = {x | x ∈ A ˄ x ∉ B} Complement (U - A) A = x x ∉ A} Summary Set Operations

17. Set Identities Set identities are fundamental rules that describe how sets interact with each other using set operations. These identities help simplify expressions and prove relationships between sets.

18. Set Identities Laws Identity A∪∅=A Identity Law A∩U=A A∪U=U Domination Law A∩∅=∅ A∪A=A Idempotent Law A∩A=A A = A Complementation Law A∪A=U Complement Law A ∩ A =∅

19. A ∪ B = B ∪ A A ∩ B = B ∩ A A ∪ (B ∪ C) = (A ∪ B) ∪ C A ∩ (B ∩ C) = (A ∩ B) ∩ C A ∪ (A ∩ B) = A A ∩ (A ∪ B) = A Commutative Laws Associative Laws Absorption Laws Set Identities (Cont.)

20. De Morgan’s Law A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) Distributive Law Set Identities (Cont.)

21. Four methods: Use the basic set identities Use membership tables Prove each set is a subset of each other Use set builder notation and logical equivalences How to Prove a Set Identity

22. Basic set identities are rules in set theory that describe how sets interact with union (∪), intersection (∩), and Cartesian product (×). They help simplify and manipulate set expressions . Prove the basic set identities

23. Set Identities (example) Show A ∪ (B ∩ C) = (C ∪ B) ∩ A Solution: We Know that:

24. Membership tables show all the combinations of sets an element can belong to 1 means the element belongs, 0 means it does not Consider the following membership table: A B A ∪ B A ∩ B A - B 1 1 1 1 1 1 1 1 1 What is a membership table

25. A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) Distributive Law A B C B ∩ C A ∪ (B ∩ C) A ∪ B A ∪ C (A ∪ B) ∩ (A ∪ C) 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Membership Table

26. Proof by showing each set is a subset of the other Assume that an element is a member of one of the identities Then show it is a member of the other

27. Example

28. Example

29. First, translate both sides of the set identity into set builder notation Then use one side (or both) to make it identical to the other Do this using logical equivalences Proof by set builder notation and logical equivalences

30. A×(B∪C)=(A×B)∪(A×C) Solution: Left-Hand Side (LHS): A×(B∪C) Means the Cartesian product of A with B∪C So, every pair ( x,y ) will have: x∈A y∈B o r y∈C Thus, A×(B∪C) are: ( x,y ) where  x∈A  and  y∈B∪C Using set builder notation for set identities (Example)

31. A×(B∪C)=(A×B)∪(A×C) Solution: Right-Hand Side (RHS): (A×B)∪(A×C) The union means we take all elements from both sets:  A×B={( x,y )∣ x∈A,y∈B } A×C={( x,y )∣ x∈A,y∈C } Now, taking their union: (A×B)∪(A×C)={( x,y )∣ x∈A,y∈B }∪{( x,y )∣ x∈A,y∈C } x∈A and either y∈B or y∈C . Using set builder notation for set identities (Example) ( Cont .)

32. A×(B∪C)=(A×B)∪(A×C) Solution: Step 2: Compare LHS and RHS Both sides contain the same pairs ( x,y ), where x∈A and y∈B∪C . Since both expressions give the same set of elements, the identity is proved ✅. Using set builder notation for set identities (Example) (Cont.)

33. Show That: A ∩ B = A ∪ B Solution: Using set builder notation for set identities (Example) (Cont.)

34. |A ⋃ B| = |A| + |B| - |A ∩ B| |A ⋃ B ⋃ C | = |A| + |B| +|C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C | 2 and 3 - Set Venn Diagram

35. Suppose a list A contains the 30 students in a mathematics class, and a list B contains the 35 students in an English class, and suppose there are 20 names on both lists. Find the number of students: only on list A only on list B on list A or B (or both), on exactly one list. Example

36. Solution: 30 − 20 = 10 names are only on list A . 35 − 20 = 15 are only on list B . |A ∪ B| = |A| + |B| − |A ∩ B| = 30 + 35 − 20 = 45 . 10 + 15 = 25 names are only on one list; that is, |A ⊕ B| = 25. Example

37. Consider the following data for 120 mathematics students at a college concerning the languages French, German, and Russian: 65 study French, 42 study Russian , 45 study German, 20 study French and German, 25 study French and Russian, 15 study German and Russian. 8 study all three languages. Determine how many students study exactly 1 subject and fill the correct numbers of students in each eight region of Venn diagram shown in figure. Example

38. Total number of students exactly registered in one course = 28+18+10=56 Example

39. Chapter Reading Chapter # 2 , Kenneth H. Rosen, Discrete Mathematics and Its Applications, Section 2.2 Exercise Questions Topic # 2.2 Question # 1, 2, 3,4,5,6,15,16,17,18, 19,20,21,22,23,24,25

40. Thanks ...?