《離散數(shù)學(xué)》ch(3)

1、整理課件2.1 SetsIntroductionDefinition 1 A set is an unordered collection of objects.(2) Definition 21. The objects in a set are also called the elements or members, of the set. A set is said to contain its elements整理課件(3) How to describe a set? The first way -listing all the members of a set Examples (

2、page 112) (a) The set V of all vowels (元音字母元音字母) in the English alphabet V=a, e, i, o, u (b) The set of odd positive integers less than 10 O=1, 3, 5, 7, 9整理課件 (c) A set can contain some unrelated elements a, 2, Fred, New Jersey (d) The set of positive integers less than 100 1, 2, 3, , 99 (e) Some im

3、portant sets (page 112) N, Z, Z+, Q, R整理課件(4) The equation of two sets Definition 3 (page 113) Two sets are equal if and only if they have the same elements. Example 6 (page 113) 1, 3, 5 = 3, 5, 1 = 1, 3, 3, 3, 5, 5, 5, 5整理課件(5) How to describe a set? The second way -Using set builder notation Examp

4、le: the set of all odd positive integers less than 10 O=x | x is an odd positive integer less than 10整理課件(6) Venn diagram(文氏圖）文氏圖） Universal set U (全集全集)-containing all the objects under consideration Example: Venn diagram for the set of vowels (page 113114) Solution: See blackboard.整理課件(7) Empty se

5、t or How about ?(8) Subset Definition 4 (page 114) The set A is said to be a subset of B if and only if every element of A is a also an element of B. We use the notation to indicate that A is a subset of the set B. A B iff x (xA xB )整理課件Example8(Page 115) The set of all odd positive integers less th

6、an 10 is a subset of the set of all positive integers less than 10, the set of rational numbers is a set of the set of real numbers, the set of all computer science majors at your school is a subset of the set of all students at your school the set of all people in China is a subset of all people in

7、 China.整理課件(9) Theorem 1 (page 115) For any set S, (a) S (b) S S(10) Proper subset (真子集真子集) A is a proper subset of B if and only if A is a subset of B but that AB. The notation-ABIt must be the case that A is a subset of B and there must exist an element x of B that is not an element of A. (Logical

8、ly Expression) 整理課件(11) One way to show that two sets are equal A=B iff AB and BA(12) Cardinality (基數(shù)基數(shù)) Definition 5 (page 116) Let S be a set. If there are exactly n distinct elements in S where n is nonnegative integer, we say that S is a finite set and that n is the cardinality of S. The cardina

9、lity of S is denoted by |S|.整理課件 Example 9 (page 116) Let A be the set of odd positive integers less than 10. Then |A|=5.Example 10 Let S be the set of letters in the English alphabet. Then |S|=26.Example 11 | |=? Definition 6 (page 116) A set is said to be infinite if it is not finite. Example12 (p

10、age 116) The set of positive integers is infinite.整理課件2. The power set (冪集冪集)Definition 7 (page 116) Given a set S, the power set of S is the set of all subsets of the set S. The power set of S is denoted by P(S).(2) Example 13 What is the power set of 0, 1, 2? Solution:(1) See page 116. 整理課件Example

11、 14:What is power set of the empty set? What is the power set of the set ? Solution: See page 117.整理課件3. Cartesian product (笛卡兒乘積笛卡兒乘積)Ordered n-tuple (a1, a2, , an) Definition 8 (page 83) The ordered n-tuple (a1, a2, , an) (有序有序n元組元組) is the ordered collection that has a1 as its first element, a2 a

12、s its second element, , an as its nth element.(2) Equality of two ordered n-tuples (a1, a2, , an) = (b1, b2, , bn) iff(1) ai = bi for i=1,2,n整理課件(3) Cartesian product of two sets AB = (a,b) | aA / bB Example 15(page 118)Let A represent the set of all students at a university, and let B represent the

13、 set of all courses offered at the university. What is the Cartesian product AB? Example 16 (page118 ) A=1, 2 and B=a, b, c How about AB and BA? Solution: See page 118.整理課件(4) Cartesian product of A1, A2, , An A1A2 An = (a1, a2, , an) | aiAi for i=1, 2, n Example 18 (page 118) A=0,1 B=1,2 C=0,1,2 Ho

14、w about ABC?整理課件4 Using set notation with quantifiersPage 119 xS P(x)-the universe of discourse is the set S Example 19 (page 119) What do the statements xR (x2 0) and xZ (x2 1) mean? Solution: See book.整理課件Truth Sets of Quantifiers Given a predicate P and a domain D, we define the truth set of P to be the set of elements x in D for which P(x) is true. The truth set of P(x) is denoted by x D|P(x)整理課件Example 20(page 119)What are the truth sets of the predicates P(X),Q(X) and R(x), where the domain is the set of integers and P(X) is “|X|=1”, Q(X)= “x2 =2” , R(X)