1、Chapter 2 (Part 1): Sets and Set OperationsElements of Discrete StructuresCSCI-235Basic Definitions Set: unordered collection of objects The objects in a set are called the elements, or members of the set A set is said to be finite if it has finite number of elements. Otherwise it is called infinite
2、 The notation a A denotes that a is an element of the set A. If a is not a member of A, write a ABasic Definitions The cardinality(基数 ) of a finite set S is the number of distinct elements in S, and is denoted by S A set with no elements is an empty set, denoted by or A set that contains all the obj
3、ects under consideration is called the universal set, denoted by UCommon Universal SetsN = natural numbers = 0, 1, 2, 3.Z = integers = , -3, -2, -1, 0, 1, 2, 3, Z = positive integers = 1, 2, 3, .R = set of real numbersR+ = set of positive real numbersQ = set of rational numbersSet-Builder Notation1.
4、 Specify the property or properties that all members must satisfy:N = x | x is 0 or positive integerS = x | x is a positive integer less than 100O10 = x | x is an odd positive integer less than 10O10 = x Z | x is odd and x 102. Use of predicate: S = x | P(x)Examples: P = x | Prime(x), Prime(x): x is
5、 a prime.Positive rational numbers:Q+ = x R | p q (p N q Z+ x = p/q)Denotation of a Set List or enumerate all the members. Examples,V = a, e, i, o, uO = 1, 3, 5, 7, 9 = 1, 7, 5, 3, 9, 9 Set builder notationV = x | x is a vowel in the English alphabetO = x | x is smaller than 10 and an odd number Use
6、 the graphical Venn diagram: Universal set in a rectangle that contains circles for sets and dots for elementsVenn Diagrams for Example VUniversal Set U = 26 English lettersMore Definitions Two sets are equal if and only if they have the same elements Subset: the set S is a subset of T if every elem
7、ent of S is also an element of T, denoted by S T (S is contained in T) (Subset definition by proposition with quantifiers? How about equality of two sets?) T is said to be the super set of S Any set S always has and S itself as its subsets (Theorem 1) S is a proper subset of T, denoted by S T (S is
8、properly contained in T), if S T and S T (denotation by proposition with quantifiers?)More Definitions The power set of a set S is the set of all subsets of S, denoted by P(S)Example: If A = a, b, c then P(A) = If a set has n elements, then the cardinality of the power set is 2. (In Chapters 5 and 6
9、, we will discuss different ways to prove this.), a, b, c, a, b, a, c, b, c, a, b, cMore Definitions The Cartesian product of two sets A and B, denoted by A B, is defined as (a, b) a A b BExample: A = a, b, B = 1, 2, 3A B = (a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3) |A B| = ? when |A| = m and |B| = n? Tuples(元组 ): the ordered n-tuple (a1, a2, ., an) is the ordered collection that has a1 as its first element and a2 as its second element and so on until an as its last element Two n-tuples are equal if and only if their corresponding elements are equal (order is important)
