Intro to Discrete Structures Lecture 9 Pawel M Wocjan School of Electrical Engineering and Computer Science University of Central Florida wocjan eecs ucf edu Intro to Discrete StructuresLecture 9 p 1 26 Sets Definition 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 notation x A to indicate that x is an element of the set A Intro to Discrete StructuresLecture 9 p 2 26 Example of Sets Intro to Discrete StructuresLecture 9 p 3 26 Sets Definition 3 Two sets are equal if and only if they have the same elements That is if A and B are sets then A and B are 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 26 Subset Definition 4 The set A is said to be a subset of B iff every element of A is also an element of B We use A B to 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 26 Venn Diagrams Intro to Discrete StructuresLecture 9 p 6 26 Sets Theorem 1 For every set S we have S and S S Intro to Discrete StructuresLecture 9 p 7 26 Proper Subset When we wish to emphasize that a set A is a subset of the set B but A 6 B we write A B and say that A is a proper subset of B x x A x B x x B x 6 A Intro to Discrete StructuresLecture 9 p 8 26 Infinite Sets Definition 6 A set is said to be infinite if it is not finite Intro to Discrete StructuresLecture 9 p 9 26 The Power Set Definition 7 Given a set S the power set is the set of all subsets 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 26 Cartesian Products Definition 8 The ordered n tuple a1 a2 an is the ordered collection that has a1 as its first element a2 as its second element and an as its nth element Intro to Discrete StructuresLecture 9 p 11 26 Cartesian Products Definition 9 Let A and B be sets The Cartesian product of 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 An be sets The Cartesian product of A1 A2 An is the set A1 A2 An a1 a2 an ai A for i 1 2 n Intro to Discrete StructuresLecture 9 p 12 26 Union Definition 1 The union of the sets A and B is the set A B x x A x B Intro to Discrete StructuresLecture 9 p 13 26 Intersection Definition 1 The intersection of the sets A and B is the set A B x x A x B Intro to Discrete StructuresLecture 9 p 14 26 Venn Diagrams Intro to Discrete StructuresLecture 9 p 15 26 Disjoint Sets Definition 3 Two set A and B are called disjoint iff their intersection is empty that is A B Intro to Discrete StructuresLecture 9 p 16 26 Difference Definition 4 The difference of the sets A and B is the set A B x x A x 6 B The difference of A and B is also called the complement of B respect to A Definition 5 Let U be the universal set The complement of A is the set A U A We have A x x 6 A Intro to Discrete StructuresLecture 9 p 17 26 Set Identities I Intro to Discrete StructuresLecture 9 p 18 26 Set Identities II Intro to Discrete StructuresLecture 9 p 19 26 Set Identities III Intro to Discrete StructuresLecture 9 p 20 26 Example B A B Prove De Morgan law A B A Intro to Discrete StructuresLecture 9 p 21 26 Membership Table A B C B C A B C A B A C A B A C Intro to Discrete StructuresLecture 9 p 22 26 Generalized Union Definition 6 The union of a collection of sets is the set that contains those element that are members of at least one set in the collection We use the notation A1 A2 An n Ai i 1 to denote the union of the sets A1 A2 An Intro to Discrete StructuresLecture 9 p 23 26 Generalized Intersection Definition 6 The intersection of a collection of sets is the set that contains those element that are members of all sets in the collection We use the notation A1 A2 An n Ai i 1 to denote the intersection of the sets A1 A2 An Intro to Discrete StructuresLecture 9 p 24 26 Functions Intro to Discrete StructuresLecture 9 p 25 26 Intro to Discrete StructuresLecture 9 p 26 26
View Full Document
Unlocking...