SetsExample of SetsSetsSubsetVenn DiagramsSetsProper SubsetInfinite SetsThe Power SetCartesian ProductsCartesian ProductsUnionIntersectionVenn DiagramsDisjoint SetsDifferenceSet Identities ISet Identities IISet Identities IIIExampleMembership TableGeneralized UnionGeneralized IntersectionFunctionsIntro to Discrete StructuresLecture 9Pawel M. WocjanSchool of Electrical Engineering and Computer ScienceUniversity of Central [email protected] to Discrete StructuresLecture 9 – p. 1/26SetsDefinition 1: A set is an unordered collection of objects.Definition 2: The objects of a set are called the elements,or members, of the set.A set is said to contain its elements.We use the notationx ∈ Ato indicate that x is an element of the set A.Intro to Discrete StructuresLecture 9 – p. 2/26Example of SetsIntro to Discrete StructuresLecture 9 – p. 3/26SetsDefinition 3: Two sets are equal if and only if they have thesame elements. That is, if A and B are sets, then A and Bare equal iff∀x(x ∈ A ↔ x ∈ B) .We write A = B if A and B are equal sets.Intro to Discrete StructuresLecture 9 – p. 4/26SubsetDefinition 4: The set A is said to be a subset of B iff everyelement of A is also an element of B.We useA ⊆ Bto indicate that A is a subset of B.We see that A ⊆ B iff the quantification∀x(x ∈ A → x ∈ B)is true.Intro to Discrete StructuresLecture 9 – p. 5/26Venn DiagramsIntro to Discrete StructuresLecture 9 – p. 6/26SetsTheorem 1: For every set S, we have∅ ⊆ S andS ⊆ S .Intro to Discrete StructuresLecture 9 – p. 7/26Proper SubsetWhen we wish to emphasize that a set A is a subset of theset B but A 6= B, we write A ⊂ B and say that A is a propersubset of B.∀x(x ∈ A → x ∈ B) ∧ ∃x(x ∈ B ∧ x 6∈ A)Intro to Discrete StructuresLecture 9 – p. 8/26Infinite SetsDefinition 6: A set is said to be infinite if it is not finite.Intro to Discrete StructuresLecture 9 – p. 9/26The Power SetDefinition 7: Given a set S, the power set is the set of allsubsets of S. The power set of S is denoted by P (S).Example 13: What is the power set of {0, 1, 3}?The power set P ({0, 1, 3}) is the set of all subset of {0, 1, 3}.Hence,Intro to Discrete StructuresLecture 9 – p. 10/26Cartesian ProductsDefinition 8: The ordered n-tuple (a1, a2, . . . , an) is theordered collection that has a1as its first element, a2as itssecond element, ..., and anas its nth element.Intro to Discrete StructuresLecture 9 – p. 11/26Cartesian ProductsDefinition 9: Let A and B be sets. The Cartesian productof A and B, denoted by A × B, is the set of all ordered pairs(a, b) where a ∈ A and b ∈ B. Hence,A × B = {(a, b) | a ∈ A ∧ b ∈ B} .More generally, let A1, A2, . . . , Anbe sets. The Cartesianproduct of A1, A2, ..., Anis the setA1×A2×. . .×An= {(a1, a2, . . . , an) | ai∈ A for i = 1, 2, . . . , n} .Intro to Discrete StructuresLecture 9 – p. 12/26UnionDefinition 1: The union of the sets A and B is the setA ∪ B = {x | x ∈ A ∨ x ∈ B} .Intro to Discrete StructuresLecture 9 – p. 13/26IntersectionDefinition 1: The intersection of the sets A and B is the setA ∩ B = {x | x ∈ A ∧ x ∈ B} .Intro to Discrete StructuresLecture 9 – p. 14/26Venn DiagramsIntro to Discrete StructuresLecture 9 – p. 15/26Disjoint SetsDefinition 3: Two set A and B are called disjoint iff theirintersection is empty, that is,A ∩ B = ∅.Intro to Discrete StructuresLecture 9 – p. 16/26DifferenceDefinition 4: The difference of the sets A and B is the setA − B = {x | x ∈ A ∧ x 6∈ B} .The difference of A and B is also called the complementof B respect to A.Definition 5: Let U be the universal set. The complementof A is the set¯A = U − A .We have¯A = {x | x 6∈ A} .Intro to Discrete StructuresLecture 9 – p. 17/26Set Identities IIntro to Discrete StructuresLecture 9 – p. 18/26Set Identities IIIntro to Discrete StructuresLecture 9 – p. 19/26Set Identities IIIIntro to Discrete StructuresLecture 9 – p. 20/26ExampleProve De Morgan law¯A ∩ B =¯A ∪¯B.¯A ∩ B ========Intro to Discrete StructuresLecture 9 – p. 21/26Membership TableA B C B ∪ C A ∩ (B ∪ C) A ∩ B A ∩ C (A ∩ B) ∪ (A ∩ C)Intro to Discrete StructuresLecture 9 – p. 22/26Generalized UnionDefinition 6: The union of a collection of sets is the set thatcontains those element that are members of at least oneset in the collection.We use the notationA1∪ A2∪ . . . ∪ An=n[i=1Aito denote the union of the sets A1, A2, . . . , An.Intro to Discrete StructuresLecture 9 – p. 23/26Generalized IntersectionDefinition 6: The intersection of a collection of sets is theset that contains those element that are members of all setsin the collection.We use the notationA1∩ A2∩ . . . ∩ An=n\i=1Aito denote the intersection of the sets A1, A2, . . . , An.Intro to Discrete StructuresLecture 9 – p. 24/26FunctionsIntro to Discrete StructuresLecture 9 – p. 25/26Intro to Discrete StructuresLecture 9 – p.
View Full Document
Unlocking...