《离散数学》浙大讲义 1.2.1 集合.ppt
S e t sS e t s集合集合集合集合 1.2 集合集合 Sets1.2.1 集合的根本概念集合的根本概念 Concepts of Sets3/5/20231S e t sS e t s集合集合集合集合 DEFINITION 1.DEFINITION 1.The objects in a set are also called the elements,or members,of the set.A set is said to contain its elements.Null Set:There are no anything in the set.=x|x P(x)(x P(x)3/5/20232S e t sS e t s集合集合集合集合 EXAMPLE 1 EXAMPLE 1 The set V of all vowels in the English alphabet can written as-V=a,e,i,o,u.3/5/20233S e t sS e t s集合集合集合集合 EXAMPLE 2 EXAMPLE 2 The set O of odd positive integers less than 10 can be expressed byO=1,3,5,7,9.O=x|x=1 x=10 x is odd number.A=a,b,c,n 枚举法枚举法A=x|x P(x)谓词公式法谓词公式法3/5/20234S e t sS e t s集合集合集合集合 DEFINTION 2.DEFINTION 2.Two sets are equal if and only if they have the same elements.Presented as A=B otherwise A BA=B x(x A x B)3/5/20235S e t sS e t s集合集合集合集合 EXAMPLE 5 EXAMPLE 5 The sets 1,3,5 and 3,5,1 are equal,since they have the same elements.Note that the order in which the elements of a set are listed does not matter.Note also that it does not matter if an element of a set is listed more than once,so that 1,3,3,3,5,5,5,5 is the same as the set 1,3,5 since they have the same elements.3/5/20236S e t sS e t s集合集合集合集合 EXAMPLE 5 EXAMPLE 5 1、集合中的元素互异、集合中的元素互异2、集合中的元素无次序和大小之分、集合中的元素无次序和大小之分3、集合中的元素不一定同类、集合中的元素不一定同类4、集合中的元素也可以是集合、集合中的元素也可以是集合3/5/20237S e t sS e t s集合集合集合集合 DEFINITION 3.DEFINITION 3.The set A is said to be a subset of B if and only if every element of A is also an element of B.We use the notation A B to indicate that A is a subset of the set B.A是是B的子集、的子集、B包含包含A、A包含在包含在B中中3/5/20238S e t sS e t s集合集合集合集合 The set A is said to be a proper subset of B if A B and there is a B and a AA是是B的真子集、的真子集、B真包含真包含A、A真包含在真包含在B中中3/5/20239S e t sS e t s集合集合集合集合 定理定理1：A=B 当且仅当当且仅当 A B B A 定理定理2：对任意的集合：对任意的集合A，A A 定理定理3：对任意的集合：对任意的集合A、B、C，如果如果 A B，B C，那么，那么 A C 定理定理4：对任意的集合：对任意的集合A，A 定理定理5：空集：空集 是唯一的是唯一的3/5/202310S e t sS e t s集合集合集合集合 DEFINITION 3.DEFINITION 3.The set U is said to be a universal set:U=x|x P(x)V (x P(x)全集全集3/5/202311S e t sS e t s集合集合集合集合 DEFINITION 4.DEFINITION 4.Let S be a set.If there are exactly n distinct elements in S where n is a nonnegative integer,we say that S is a finite set and that n is the cardinality of S.The cardinality of S is denoted by S.集合的基、势集合的基、势3/5/202312S e t sS e t s集合集合集合集合 EXAMPLE 7 EXAMPLE 7 Let A be the set of odd positive integers less than 10.Then A=53/5/202313S e t sS e t s集合集合集合集合 EXAMPLE 8 EXAMPLE 8 Let S be the set of letters in the English alphabet.Then S=263/5/202314S e t sS e t s集合集合集合集合 EXAMPLE 9 EXAMPLE 9 Since the null set has no elements,it follows that =03/5/202315S e t sS e t s集合集合集合集合 DEFINITION 5.DEFINITION 5.A set is said to be infinite if it is not finite.3/5/202316S e t sS e t s集合集合集合集合 EXAMPLE 10 EXAMPLE 10 The set of positive integers is infinite.3/5/202317S e t sS e t s集合集合集合集合 DEFINITION 6.DEFINITION 6.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).幂集幂集3/5/202318S e t sS e t s集合集合集合集合 EXAMPLE 11 EXAMPLE 11 What is the power set of the set 0,1,2?p(0,1,2)=,0,1,2,0,1,0,2,1,2,0,1,2.3/5/202319S e t sS e t s集合集合集合集合 EXAMPLE 12 EXAMPLE 12 What is the power set of the empty set?What is the power set of the set?P()=,.3/5/202320S e t sS e t s集合集合集合集合 DEFINITION 7.DEFINITION 7.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.有序有序n元组元组 或或 n元元有序组有序组(a1,a2,an)3/5/202321S e t sS e t s集合集合集合集合 DEFINITION 8.DEFINITION 8.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 aA and bB.Hence,A B=(a,b)aAbB.3/5/202322S e t sS e t s集合集合集合集合 EXAMPLE 14 EXAMPLE 14 What is the Cartesian product of A=1,2 and B=a,b,c?A B=(1,a),(1,b),(1,c),(2,a),(2,b),(2,c)3/5/202323S e t sS e t s集合集合集合集合 DEFINITION 9.DEFINITION 9.The Cartesian product of the sets A1,A2,An,denoted by A1 A2 An,is the set of ordered n-tuples(a1,a2,an),where ai belongs to Ai for i=1,2,.,n.In other wordsA1 A2 An=(a1,a2,an)aiAi for i=1,2,.,n.3/5/202324S e t sS e t s集合集合集合集合 EXAMPLE 16 EXAMPLE 16 What is the Cartesian product A x B x C,where A=0,1,B=1,2,and C=0,1,2?ABC=(0,1,0),(0,1,1),(0,1,2),(0,2,0),(0,2,1),(0,2,2),(1,1,0),(1,1,1),(1,1,2),(1,2,0),(1,2,1),(1,2,2).3/5/202325S e t sS e t s集合集合集合集合 Set Operations集合的运算集合的运算3/5/202326S e t sS e t s集合集合集合集合 DEFINITION 1.DEFINITION 1.Let A and B be sets.The union of the sets A and B,denoted by AB,is the set that contains those elements that are either in A or in B,or in both.集合的并集合的并3/5/202327S e t sS e t s集合集合集合集合 DEFINITION 2.DEFINITION 2.Let A and B be sets.The intersection of the sets A and B,denoted by AB,is the set containing those elements in both A and B.集合的交集合的交3/5/202328S e t sS e t s集合集合集合集合 DEFINITION 3.DEFINITION 3.Two sets are called disjoint if their intersection is the empty set.AB=A与与B不相交不相交3/5/202329S e t sS e t s集合集合集合集合 DEFINITION 4.DEFINITION 4.Let A and B be sets.The difference of A and B,denoted by A B,is the set containing those elements that are in A but not in B.The difference of A and B is also called the complement of B with respect to A.差集、补集、余集差集、补集、余集3/5/202330S e t sS e t s集合集合集合集合 DEFINITION 5.DEFINITION 5.Let U be the universal set.The complement of the set A,denoted by ,is the complement of A with respect to U.In other words,the complement of the set A is U A.3/5/202331S e t sS e t s集合集合集合集合 Table 1Table 13/5/202332S e t sS e t s集合集合集合集合 命题演算的根本等值定理命题演算的根本等值定理命题演算的根本等值定理命题演算的根本等值定理3/5/202333S e t sS e t s集合集合集合集合 EXAMPLE 11 EXAMPLE 11 Use set builder notation and logical equivalences to show that =3/5/202334S e t sS e t s集合集合集合集合 Table 2Table 23/5/202335S e t sS e t s集合集合集合集合 EXAMPLE 13 EXAMPLE 13 Let A,B,and C be sets.Show that3/5/202336S e t sS e t s集合集合集合集合 EXAMPLE 14 EXAMPLE 14 Let A=0,2,4,6,8,B=0,1,2,3,4,and C=0,3,6,9.What are ABC and ABC?ABC=0,1,2,3,4,6,8,9.ABC=0.3/5/202337S e t sS e t s集合集合集合集合 EXAMPLE 14 EXAMPLE 14 证明两个集合相等的方法：证明两个集合相等的方法：1、定义方法：谓词公式、定义方法：谓词公式2、相等定理：互相包含、相等定理：互相包含3、集合相等运算：根本相等定理、集合相等运算：根本相等定理4、Venn 图文氏图：图解图文氏图：图解5、特征函数、特征函数3/5/202338S e t sS e t s集合集合集合集合 DEFINITION 6.DEFINITION 6.The union of a collection of sets is the set that contains those elements that are members of at least one set in the collection.多个集合的并多个集合的并3/5/202339S e t sS e t s集合集合集合集合 DEFINITION 7.DEFINITION 7.The intersection of a collection of sets is the set that contains those elements that are members of all the sets in the collection.多个集合的交多个集合的交3/5/202340S e t sS e t s集合集合集合集合 EXAMPLE 18 EXAMPLE 18 The bit strings for the sets 1,2,3,4,5 and(1,3,5,7,9)are 11 1110 0000 and 10 1010 1010,respectively.Use bit strings to find the union and intersection of these sets.11 1110 000010 1010 1010=11 1110 1010,11 1101 000010 1010 1010=10 1010 0000,3/5/202341S e t sS e t s集合集合集合集合 小小 结结 1、一些特殊集合、一些特殊集合2、集合的运算、集合的运算3、两个集合相等的证明、两个集合相等的证明3/5/202342S e t sS e t s集合集合集合集合 进一步的思考进一步的思考 2、集合概念的拓广：、集合概念的拓广：有序集有序集(ordered sets)重集重集 (multisets)模糊集模糊集(fuzzy sets)可拓集可拓集(extension sets)1、集合概念的矛盾：、集合概念的矛盾：S=x x 3/5/202343S e t sS e t s集合集合集合集合 练练 习习 pp.45 7、12、15 pp.54 12(e)、31、36 其中其中12e用三种不同的方法证明用三种不同的方法证明3/5/202344更多资料请访问：更多资料请访问：更多资料请访问：更多资料请访问：3/5/202345
