COSC 50A - Lecture #6 PDF

Set Operations College of Engineering and Information Technology  Recap A Set is an unordered collection of objects, called elements. Roster Method is used to present elements inside the bracket. Example: 𝐴 = {𝑎, 𝑏, 𝑐, … , 𝑧} Ellipses (…) are used when the general p...

Set Operations College of Engineering and Information Technology  Recap A Set is an unordered collection of objects, called elements. Roster Method is used to present elements inside the bracket. Example: 𝐴 = {𝑎, 𝑏, 𝑐, … , 𝑧} Ellipses (…) are used when the general pattern of the elements is obvious. Set Former Notation describes the set by its property. Example: 𝐴 = 𝑎 ∈ 𝐴 𝑎 𝑖𝑠 𝑎 𝑙𝑜𝑤𝑒𝑟𝑐𝑎𝑠𝑒 𝑎𝑙𝑝ℎ𝑎𝑏𝑒𝑡} Subset is where set A is also an element of set B. 𝐴⊆𝐵 College of Engineering and Information Technology  Recap Cardinality is the size of a set. A limited number of set is called finite set otherwise it is called infinite set. Power set is the set of all subsets of the set S. Denoted by 𝑃(𝑆). Cardinality of a power set is 𝑃 𝑆 = 2|𝑆| Cartesian product is the set of all ordered pairs (𝑎, 𝑏) denoted by 𝐴 × 𝐵 where 𝑎 ∈ 𝐴 and 𝑏 ∈ 𝐵. College of Engineering and Information Technology  Set Operations Definition 1. Let 𝐴 and 𝐵 be sets. The union of the sets 𝐴 and 𝐵, denoted by 𝐴 ∪ 𝐵, is the set that contains those elements that are either in 𝐴 or in 𝐵, or in both. An element 𝑥 belongs to the union of the sets 𝐴 and 𝐵 if and only if 𝑥 belongs to 𝐴 or 𝑥 belongs to 𝐵. This tells us that 𝐴 ∪ 𝐵 = {𝑥|𝑥 ∈ 𝐴 ∨ 𝑥 ∈ 𝐵} Example 𝐴 = {1,3,5} and 𝐵 = {1,2,3}; the union of the two is 1,3,5 ∪ 1,2,3 = {1,2,3,5} College of Engineering and Information Technology  Set Operations Definition 2. Let 𝐴 and 𝐵 be sets. The intersection of the sets 𝐴 and 𝐵, denoted by 𝐴 ∩ 𝐵, is the set containing those elements in both 𝐴 and 𝐵. An element 𝑥 belongs to the intersection of the sets 𝐴 and 𝐵 if and only if 𝑥 belongs to 𝐵. This tells us that 𝐴 ∩ 𝐵 = {𝑥|𝑥 ∈ 𝐴 ∧ 𝑥 ∈ 𝐵} Example: 𝐴 = {1,3,5} and 𝐵 = {1,2,3}; the union of the two is 1,3,5 ∩ 1,2,3 = {1,3} College of Engineering and Information Technology  Set Operations Definition 3. Two sets are called disjoint if their intersection is the empty set. Example: 𝐴 = {1,3,5,7,9} and 𝐵 = {2,4,6,8,10}. Because 𝐴 ∩ 𝐵 = ∅, 𝐴 and 𝐵 are disjoint. Definition 4. Let 𝐴 and 𝐵 be sets. The difference of 𝐴 and 𝐵, denoted by 𝐴 − 𝐵, is the set containing those elements that are in 𝐴 but not in 𝐵. The difference of 𝐴 and 𝐵 is also called the 𝑐𝑜𝑚𝑝𝑙𝑒𝑚𝑒𝑛𝑡 𝑜𝑓 𝐵 𝑤𝑖𝑡ℎ 𝑟𝑒𝑠𝑝𝑒𝑐𝑡 𝑡𝑜 𝐴. College of Engineering and Information Technology  Set Operations An element 𝑥 belongs to the difference of 𝐴 and 𝐵 if and only if 𝑥 ∈ 𝐴 and 𝑥 ∉ 𝐵. This tells us that 𝐴 − 𝐵 = {𝑥|𝑥 ∈ 𝐴 ∧ 𝑥 ∉ 𝐵} Example: 𝐴 = {1,3,5} and 𝐵 = {1,2,3}; the difference 𝐴 − 𝐵 = {5}. College of Engineering and Information Technology  Set Operations Definition 5. Let 𝑈 be the universal set. The complement of the set 𝐴, denoted by 𝐴,ҧ is the complement of 𝐴 with respect to 𝑈. Therefore, the complement of the set 𝐴 is 𝑈 − 𝐴. An element belongs to 𝐴ҧ if and only if 𝑥 ∉ 𝐴. This tells us that 𝐴ҧ = {𝑥 ∈ 𝑈|𝑥 ∉ 𝐴} Example Let 𝐴 − {𝑎, 𝑒, 𝑖, 𝑜, 𝑢} where 𝑈 = 𝑥 𝑙𝑒𝑡𝑡𝑒𝑟𝑠 𝑜𝑓 𝐸𝑛𝑔𝑙𝑖𝑠ℎ 𝐴𝑙𝑝ℎ𝑎𝑏𝑒𝑡}, then 𝐴ҧ = {𝑥|𝑐𝑜𝑛𝑠𝑜𝑛𝑎𝑛𝑡𝑠 𝑓𝑟𝑜𝑚 𝐸𝑛𝑔𝑙𝑖𝑠ℎ 𝐴𝑙𝑝ℎ𝑎𝑏𝑒𝑡} College of Engineering and Information Technology  Set Identities Let 𝐴, 𝐵, 𝑎𝑛𝑑 𝐶 be sets, and consider them to be subsets of a universal set 𝑈. In proving sets, for all sets 𝐴, 𝐵, … some fact is true. College of Engineering and Information Technology  Set Identities Identity Laws (Proof) 𝐴∪∅=𝐴 𝐴∩𝑈 =𝐴 Proof a) 𝐴∪∅=𝐴 We understand that 𝑥 ∈ ∅ is b) 𝐴∪∅= 𝑥 𝑥 ∈𝐴∨𝑥 ∈∅ false. Hence, we can replace 𝑥 ∈ c) 𝐴 ∪ ∅ = {𝑥|𝑥 ∈ 𝐴 ∨ 𝐹} ∅=𝐹 d) 𝐴 ∪ ∅ = {𝑥|𝑥 ∈ 𝐴} e) 𝐴∪∅=𝐴 𝑥 ∈ 𝐴 ∨ 𝐹 = 𝑥 ∈ 𝐴 (identity law from Logical Equivalence) College of Engineering and Information Technology  Set Identities Identity Laws (Proof) 𝐴∪∅=𝐴 𝐴∩𝑈 =𝐴 Proof a) 𝐴∩𝑈 =𝐴 We know that every element is b) 𝐴∩𝑈 = 𝑥 𝑥 ∈𝐴∧𝑥 ∈𝑈 contained in the universal set 𝑈, c) 𝐴 ∩ 𝑈 = {𝑥|𝑥 ∈ 𝐴 ∧ 𝑇} therefore 𝑥 ∈ 𝑈 is always True. d) 𝐴 ∩ 𝑈 = {𝑥|𝑥 ∈ 𝐴} e) 𝐴∩𝑈 =𝐴 𝑥 ∈ 𝐴 ∧ 𝑇 = 𝑥 ∈ 𝐴 (identity law from Logical Equivalence) College of Engineering and Information Technology  Set Identities Domination Laws (Proof) Both proofs uses domination law (from 𝐴∪𝑈 =𝑈 Logical Equivalence) 𝐴∩∅=∅ Similarly, uses the same idea from identity laws 𝑥 ∈ ∅ = 𝐹 & 𝑥 ∈ 𝑈 = 𝑇 Proof a) 𝐴∪𝑈 =𝑈 a) 𝐴∩∅=∅ b) 𝐴 ∪ 𝑈 = {𝑥|𝑥 ∈ 𝐴 ∨ 𝑥 ∈ 𝑈} b) 𝐴 ∩ ∅ = {𝑥|𝑥 ∈ 𝐴 ∧ 𝑥 ∈ ∅} c) 𝐴 ∪ 𝑈 = {𝑥|𝑥 ∈ 𝐴 ∨ 𝑇} c) 𝐴 ∩ ∅ = {𝑥|𝑥 ∈ 𝐴 ∧ 𝐹} d) 𝐴 ∪ 𝑈 = {𝑥|𝑇} d) 𝐴 ∩ ∅ = {𝑥|𝐹} e) 𝐴 ∪ 𝑈 = {𝑥|𝑥 ∈ 𝑈} e) 𝐴 ∩ ∅ = {𝑥|𝑥 ∈ ∅} f) 𝐴∪𝑈 =𝑈 f) 𝐴∩∅=∅ College of Engineering and Information Technology  Set Identities Idempotent Laws (Proof) Both proofs uses Idempotent laws (from 𝐴∪𝐴 =𝐴 Logical Equivalence) 𝐴∩𝐴 =𝐴 Proof a) 𝐴∪𝐴 =𝐴 a) 𝐴∩𝐴 =𝐴 b) 𝐴 ∪ 𝐴 = {𝑥|𝑥 ∈ 𝐴 ∨ 𝑥 ∈ 𝐴} b) 𝐴 ∩ 𝐴 = {𝑥|𝑥 ∈ 𝐴 ∧ 𝑥 ∈ 𝐴} c) 𝐴 ∪ 𝐴 = {𝑥|𝑥 ∈ 𝐴} c) 𝐴 ∩ 𝐴 = {𝑥|𝑥 ∈ 𝐴} d) 𝐴∪𝐴 =𝐴 d) 𝐴∩𝐴 =𝐴 College of Engineering and Information Technology  Set Identities Complementation Laws (Proof) 𝐴′ ′ =𝐴 Proof 𝐴′ represents complement. 𝐴′ ′ =𝐴 𝑥 ∉ 𝐴′ = ¬(𝑥 ∈ 𝐴′ ). This means 𝐴′ ′ = 𝑥 𝑥 ∉ 𝐴′ 𝐴′ ′ = {𝑥|¬ 𝑥 ∈ 𝐴′ } that we just re-write the not 𝐴′ ′ = {𝑥|¬(𝑥 ∉ 𝐴} element of as element of w/ 𝐴′ 𝐴′ ′ = {𝑥|¬ ¬ 𝑥 ∈ 𝐴 } We used Double Negation Law 𝐴′ ′ = {𝑥|𝑥 ∈ 𝐴} from Logical Equivalence. (𝐴′ )′ = 𝐴 College of Engineering and Information Technology  Set Identities Commutative Laws (Proof) Both proofs uses Commutative laws 𝐴∪𝐵 =𝐵∪𝐴 (from Logical Equivalence) 𝐴∩𝐵 =𝐵∩𝐴 Proof a) 𝐴∪𝐵 =𝐵∪𝐴 a) 𝐴∩𝐵 =𝐵∩𝐴 b) 𝐴∪𝐵 = {𝑥|𝑥 ∈ 𝐴 ∨ 𝑥 ∈ 𝐵} b) 𝐴∩𝐵 = {𝑥|𝑥 ∈ 𝐴 ∧ 𝑥 ∈ 𝐵} c) 𝐴∪𝐵 = {𝑥|𝑥 ∈ 𝐵 ∨ 𝑥 ∈ 𝐴} c) 𝐴∩𝐵 = {𝑥|𝑥 ∈ 𝐵 ∧ 𝑥 ∈ 𝐴} d) 𝐴∪𝐵 =𝐵∪𝐴 d) 𝐴∩𝐵 =𝐵∩𝐴 College of Engineering and Information Technology  Set Identities Associative Laws (Proof) 𝐴∪ 𝐵∪𝐶 = 𝐴∪𝐵 ∪𝐶 𝐴∩ 𝐵∩𝐶 = 𝐴∩𝐵 ∩𝐶 Proof Both proofs uses 1st and 2nd a) 𝐴∪ 𝐵∪𝐶 = 𝐴∪𝐵 ∪𝐶 Associative Law from Logical b) 𝐴∪ 𝐵∪𝐶 = {𝑥|𝑥 ∈ 𝐴 ∨ 𝑥 ∈𝐵∨𝑥 ∈𝐶 } Equivalence ( 𝑝 ∨ 𝑞 ∨ 𝑟 = 𝑝 ∨ c) 𝐴∪ 𝐵∪𝐶 = 𝑥 𝑥 ∈𝐴∨𝑥 ∈𝐵 ∨𝑥 ∈𝐶 (𝑞 ∨ 𝑟)) and ( 𝑝 ∧ 𝑞 ∧ 𝑟 = 𝑝 ∧ d) 𝐴∪ 𝐵∪𝐶 = 𝐴∪𝐵 ∪𝐶 (𝑞 ∧ 𝑟)) a) 𝐴 ∩ 𝐵 ∩ 𝐶 = 𝐴 ∩ 𝐵 ∩ 𝐶 b) 𝐴 ∩ 𝐵 ∩ 𝐶 = 𝑥 𝑥 ∈ 𝐴 ∧ (x ∈ 𝐵 ∧ 𝑥 ∈ 𝐶)} c) 𝐴 ∩ 𝐵 ∩ 𝐶 = {𝑥| 𝑥 ∈ 𝐴 ∧ 𝑥 ∈ 𝐵 ∧ 𝑥 ∈ 𝐶} College of Engineering and d) 𝐴 ∩ 𝐵Technology Information ∩𝐶 = 𝐴∩𝐵 ∩𝐶  Set Identities Distributive Laws (Proof) From 1st Distributive Law, we 𝐴 ∩ 𝐵 ∪ 𝐶 = 𝐴 ∩ 𝐵 ∪ (𝐴 ∩ 𝐶) applied it to the set. 𝐴 ∪ 𝐵 ∩ 𝐶 = 𝐴 ∪ 𝐵 ∩ (𝐴 ∪ 𝐶) Proof: a) 𝐴∩ 𝐵∪𝐶 = 𝐴 ∩ 𝐵 ∪ (𝐴 ∩ 𝐶) b) 𝐴∩ 𝐵∪𝐶 = 𝑥 𝑥 ∈𝐴∧ 𝑥 ∈𝐵∨𝑥 ∈𝐶 c) 𝐴∩ 𝐵∪𝐶 = {𝑥| 𝑥 ∈ 𝐴 ∧ 𝑥 ∈ 𝐵 ∨ 𝑥 ∈ 𝐴 ∧ 𝑥 ∈ 𝐶 } d) 𝐴∩ 𝐵∪𝐶 = {𝑥|𝑥 ∈ 𝐴 ∩ 𝐵 ∨ 𝑥 ∈ A ∩ 𝐶 } e) 𝐴∩ 𝐵∪𝐶 = 𝐴 ∩ 𝐵 ∪ (𝐴 ∩ 𝐶) College of Engineering and Information Technology  Set Identities Distributive Laws (Proof) 𝐴 ∩ 𝐵 ∪ 𝐶 = 𝐴 ∩ 𝐵 ∪ (𝐴 ∩ 𝐶) From 2nd Distributive Law, we 𝐴 ∪ 𝐵 ∩ 𝐶 = 𝐴 ∪ 𝐵 ∩ (𝐴 ∪ 𝐶) applied it to the set. Proof: a) 𝐴∪ 𝐵∩𝐶 = 𝐴∪𝐵 ∩ 𝐴∪𝐶 b) 𝐴∪ 𝐵∩𝐶 = {𝑥|𝑥 ∈ 𝐴 ∨ (𝑥 ∈ 𝐵 ∧ 𝑥 ∈ 𝐶)} c) 𝐴∪ 𝐵∩𝐶 = 𝑥 𝑥 ∈ 𝐴 ∨ 𝑥 ∈ 𝐵 ∧ (𝑥 ∈ 𝐴 ∨ 𝑥 ∈ 𝐶)} d) 𝐴∪ 𝐵∩𝐶 = {𝑥|𝑥 ∈ 𝐴 ∪ 𝐵 ∧ 𝑥 ∈ 𝐴 ∪ 𝐶 } e) 𝐴∪ 𝐵∩𝐶 = 𝐴 ∪ 𝐵 ∩ (𝐴 ∪ 𝐶) College of Engineering and Information Technology  Set Identities De Morgan’s Laws (Proof) 𝐴∪𝐵 ′ = 𝐴′ ∩ 𝐵′ 𝐴∩𝐵 ′ = 𝐴′ ∪ 𝐵′ Proof By using 1st De Morgan’s Law from a) 𝐴 ∪ 𝐵 ′ = 𝐴′ ∩ 𝐵′ logical equivalence. b) 𝐴 ∪ 𝐵 ′ = {𝑥|𝑥 ∉ 𝐴 ∪ 𝐵 } We extracted not in not element of to create element of (𝑥 ∉ 𝐴 ∪ 𝐵 = c) 𝐴 ∪ 𝐵 ′ = 𝑥|¬ 𝑥 ∈ 𝐴 ∪ 𝐵 ¬(𝑥 ∈ 𝐴 ∪ 𝐵 )) d) 𝐴 ∪ 𝐵 ′ = {𝑥|¬ 𝑥 ∈ 𝐴 ∨ 𝑥 ∈ 𝐵 } e) 𝐴 ∪ 𝐵 ′ = {𝑥| 𝑥 ∉ 𝐴 ∧ 𝑥 ∉ 𝐵 } f) 𝐴 ∪ 𝐵 ′ = {𝑥| 𝑥 ∈ 𝐴′ ∧ 𝑥 ∈ 𝐵′ } g) 𝐴 ∪ 𝐵 ′ = 𝑥 𝑥 ∈ 𝐴′ ∩ 𝐵′ h) 𝐴 of College 𝐵 ′ = 𝐴′ ∩and ∪ Engineering 𝐵′ Information Technology  Set Identities De Morgan’s Laws (Proof) 𝐴∪𝐵 ′ = 𝐴′ ∩ 𝐵′ 𝐴∩𝐵 ′ = 𝐴′ ∪ 𝐵′ Proof By using 2nd De Morgan’s Law from a) 𝐴 ∩ 𝐵 ′ = 𝐴′ ∪ 𝐵′ logical equivalence. b) 𝐴 ∩ 𝐵 ′ = {𝑥|𝑥 ∉ 𝐴 ∩ 𝐵 } We extracted not in not element of to create element of (𝑥 ∉ 𝐴 ∪ 𝐵 = c) 𝐴 ∩ 𝐵 ′ = 𝑥|¬ 𝑥 ∈ 𝐴 ∩ 𝐵 ¬(𝑥 ∈ 𝐴 ∪ 𝐵 )) d) 𝐴 ∩ 𝐵 ′ = {𝑥|¬ 𝑥 ∈ 𝐴 ∧ 𝑥 ∈ 𝐵 } e) 𝐴 ∩ 𝐵 ′ = {𝑥| 𝑥 ∉ 𝐴 ∨ 𝑥 ∉ 𝐵 } f) 𝐴 ∩ 𝐵 ′ = {𝑥| 𝑥 ∈ 𝐴′ ∨ 𝑥 ∈ 𝐵′ } g) 𝐴 ∩ 𝐵 ′ = 𝑥 𝑥 ∈ 𝐴′ ∪ 𝐵′ h) 𝐴 of College 𝐵 ′ = 𝐴′ ∪and ∩ Engineering 𝐵′ Information Technology  Set Identities Absorption Laws (Proof) 𝐴∪ 𝐴∩𝐵 =𝐴 We want to prove that 𝐴 ∪ 𝐴∩ 𝐴∪𝐵 =𝐴 𝐴∩𝐵 ⊆𝐴 Proof: a) 𝐴 ∪ 𝐴 ∩ 𝐵 = 𝐴 b) Let 𝑥 ∈ 𝐴 ∪ 𝐴 ∩ 𝐵 = 𝑥 ∈ 𝐴 ∨ (𝑥 ∈ 𝐴 ∧ 𝑥 ∈ 𝐵) c) Then 𝑥 ∈ 𝐴 by using 1st absorption law of logical equivalence (𝑝 ∨ 𝑝 ∧ 𝑞 = 𝑝) d) Therefore, 𝐴 ∪ 𝐴 ∩ 𝐵 ⊆ 𝐴 College of Engineering and Information Technology  Set Identities Absorption Laws (Proof) 𝐴∪ 𝐴∩𝐵 =𝐴 We will be using 2nd absorption 𝐴∩ 𝐴∪𝐵 =𝐴 law of logical equivalence 𝑝 ∧ 𝑝∨𝑞 =𝑝 Proof a) Let 𝑥 ∈ 𝐴 ∧ 𝑥 ∈ (𝐴 ∪ 𝐵) b) Then 𝐴 ∩ 𝐴 ∪ 𝐵 = 𝑥 𝑥 ∈ 𝐴 ∧ 𝑥 ∈ 𝐴 ∨ 𝑥 ∈ 𝐵 c) By 2nd absorption law, we will get {𝑥|𝑥 ∈ 𝐴} d) Therefore, 𝐴 ∩ 𝐴 ∪ 𝐵 = {𝑥|𝑥 ∈ 𝐴} e) 𝐴 = 𝐴 College of Engineering and Information Technology  Set Identities Complement Laws (Proof) 𝐴 ∪ 𝐴′ = 𝑈 𝐴 ∩ 𝐴′ = ∅ Proof a) Let 𝐴 ∪ 𝐴′ = {𝑥|𝑥 ∈ 𝐴 ∨ 𝑥 ∈ 𝐴′ } b) Understandably, we know that 𝑥 ∈ 𝐴 ∨ 𝑥 ∈ 𝐴′ = 𝑈 c) Hence, 𝐴 ∪ 𝐴′ = 𝑈 a) Let 𝐴 ∩ 𝐴′ = {𝑥|𝑥 ∈ 𝐴 ∧ 𝑥 ∈ 𝐴′ } b) Similarly, we know that 𝑥 ∈ 𝐴 ∧ 𝑥 ∈ 𝐴′ = ∅ c) Hence, 𝐴 ∩ 𝐴′ = ∅ College of Engineering and Information Technology  Set Identities Example #1 Let 𝐴 𝑎𝑛𝑑 𝐵 be sets, then solve 𝐴 − 𝐵 = 𝐴 ∩ 𝐵′ Solution: 𝐴 − 𝐵 = {𝑥|𝑥 ∈ 𝐴 ∧ 𝑥 ∉ 𝐵} 𝐿𝐻𝑆 = {𝑥|𝑥 ∈ 𝐴 ∧ ¬ 𝑥 ∈ 𝐵 } 𝐿𝐻𝑆 = {𝑥|𝑥 ∈ 𝐴 ∧ 𝑥 ∈ 𝐵′ } 𝐿𝐻𝑆 = {𝑥|𝑥 ∈ 𝐴 ∩ 𝐵′ } 𝐴 ∩ 𝐵′ = 𝑅𝐻𝑆 College of Engineering and Information Technology  Set Identities Example #2 Let 𝐴 𝑎𝑛𝑑 𝐵 be sets, then solve 𝐴 − 𝐵 − 𝐵 − 𝐶 = 𝐴 − 𝐵 Solution: 𝐴 − 𝐵 = {𝑥|𝑥 ∈ 𝐴 ∧ 𝑥 ∉ 𝐵} 𝐴 − 𝐵 = {𝑥|𝑥 ∈ 𝐴 ∧ ¬ 𝑥 ∈ 𝐵 } College of Engineering and Information Technology