离散数学-第6章(精品)

单击此处编辑母版标题样式,*,*,主要内容,集合的基本概念,属于、包含,幂集、空集,文氏图等,集合的基本运算,并、交、补、差等,集合恒等式,集合运算的算律、恒等式的证明方法,第二部分 集合论,第六章 集合代数,1,6.1,集合的基本概念,1.,集合定义,集合没有精确的数学定义,理解：由离散个体构成的整体称为,集合,，称这些个体为集,合的,元素,常见的数集：,N,Z,Q,R,C,等分别表示自然数、整数、有,理数、实数、复数集合,2.,集合表示法,枚举法,-,通过列出全体元素来表示集合,谓词表示法,-,通过谓词概括集合元素的性质,实例：,枚举法 自然数集合,N=0,1,2,3,谓词法,S,=,x,|,x,是实数，,x,2,1=0,2,元素与集合,1.,集合的元素具有的性质,无序性：元素列出的顺序无关,相异性：集合的每个元素只计,数一次,确定性：对任何元素和集合都,能确定这个元素是否,为该集合的元素,任意性：集合的元素也可以是,集合,2,元素与集合的关系,隶属关系：,或者,3,集合的树型层次结构,d,A,a,A,3,集合与集合,集合与集合之间的关系：,=,定义,6.1,A,B,x,(,x,A,x,B,),定义,6.2,A,=,B,A,B,B,A,定义,6.3,A,B,A,B,A,B,A,B,x,(,x,A,x,B,),思考：,和,的定义,注意,和,是不同层次的问题,4,空集、全集和幂集,1,定义,6.4,空集,：不含有任何元素的集合,实例：,x,|,x,R,x,2,+1=0,定理,6.1,空集是任何集合的子集。,证 对于任意集合,A,，,A,x,(,x,x,A,),T,(,恒真命题,),推论,是惟一的,3.,定义,6.6,全集,E,：包含了所有集合的集合,全集具有相对性：与问题有关，不存在绝对的全集,2.,定义,6.5,幂集,：,P,(,A,)=,x,|,x,A,实例：,P,(,)=,P,(,)=,计数：如果,|,A,|=,n,，则,|,P,(,A,)|=2,n,.,5,6.2,集合的运算,初级运算,集合的基本运算有,定义,6.7,并,A,B,=,x,|,x,A,x,B,交,A,B,=,x,|,x,A,x,B,相对补,A,B,=,x,|,x,A,x,B,定义,6.8,对称差,A,B,=(,A,B,),(,B,A,),定义,6.9,绝对补,A,=,E,A,6,文氏图,集合运算的表示,A,B,A,B,A,B,A,B,A,B,A,B,A,B,A,B,A,B,A,7,几点说明,并和交运算可以推广到有穷个集合上，即,A,1,A,2,A,n,=,x,|,x,A,1,x,A,2,x,A,n,A,1,A,2,A,n,=,x,|,x,A,1,x,A,2,x,A,n,A,B,A,B,=,A,B,=,A,B,=,A,8,广义运算,1.,集合的广义并与广义交,定义,6.10,广义并,A,=,x,|,z,(,z,A,x,z,),广义交,A,=,x,|,z,(,z,A,x,z,),实例,1,1,2,1,2,3=1,2,3,1,1,2,1,2,3=1,a,=,a,，,a,=,a,a,=,a,，,a,=,a,9,关于广义运算的说明,2.,广义运算的性质,(1),=,，,无意义,(2),单元集,x,的广义并和广义交都等于,x,(3),广义运算减少集合的层次（括弧减少一层）,(4),广义运算的计算：一般情况下可以转变成初级运算,A,1,A,2,A,n,=,A,1,A,2,A,n,A,1,A,2,A,n,=,A,1,A,2,A,n,3.,引入广义运算的意义,可以表示无数个集合的并、交运算，例如,x,|,x,R,=R,这里的,R,代表实数集合,.,10,运算的优先权规定,1,类运算：初级运算,，,优先顺序由括号确定,2,类运算：广义运算和,运算，,运算由右向左进行,混合运算：,2,类运算优先于,1,类运算,例,1,A,=,a,a,b,，计算,A,(,A,A,).,解：,A,(,A,A,),=,a,b,(,a,b,a,),=(,a,b,),(,a,b,),a,),=(,a,b,),(,b,a,)=,b,11,有穷集合元素的计数,1.,文氏图法,2.,包含排斥原理,定理,6.2,设集合,S,上定义了,n,条性质，其中具有第,i,条性质的,元素构成子集,A,i,那么集合中不具有任何性质的元素数为,推论,S,中至少具有一条性质的元素数为,12,实例,例,2,求,1,到,1000,之间（包含,1,和,1000,在内）既不能被,5,和,6,整,除，也不能被,8,整除的数有多少个？,解 方法一：文氏图,定义以下集合：,S,=,x,|,x,Z,1,x,1000,A,=,x,|,x,S,x,可被,5,整除,B,=,x,|,x,S,x,可被,6,整除,C,=,x,|,x,S,x,可被,8,整除,画出文氏图，然后填入相应的数字，解得,N=1000,(200+100+33+67),=600,13,实例,方法二,|,S,|=1000,|,A,|=,1000/5,=200,|,B,|=,1000/6,=166,|,C,|=,1000/8,=125,|,A,B,|=,1000/lcm(5,6),=,1000/33,=33,|,A,C,|=,1000/lcm(5,8),=,1000/40,=25,|,B,C,|=,1000/lcm(6,8),=,1000/24,=41,|,A,B,C,|=,1000/lcm(5,6,8),=,1000/120,=8,=1000,(200+166+125)+(33+25+41),8=600,14,6.3,集合恒等式,集合算律,1,只涉及一个运算的算律：,交换律,、,结合律,、,幂等律,交换,A,B,=,B,A,A,B,=,B,A,A,B,=,B,A,结合,(,A,B,),C,=,A,(,B,C,),(,A,B,),C,=,A,(,B,C,),(,A,B,),C,=,A,(,B,C,),幂等,A,A,=,A,A,A,=,A,15,集合算律,2,涉及两个不同运算的算律：,分配律、吸收律,与,与,分配,A,(,B,C,)=,(,A,B,),(,A,C,),A,(,B,C,)=,(,A,B,),(,A,C,),A,(,B,C,),=(,A,B,),(,A,C,),吸收,A,(,A,B,)=,A,A,(,A,B,)=,A,16,集合算律,3,涉及补运算的算律：,DM,律,，,双重否定律,D,.,M,律,A,(,B,C,)=(,A,B,),(,A,C,),A,(,B,C,)=(,A,B,),(,A,C,),(,B,C,)=,B,C,(,B,C,)=,B,C,双重否定,A,=,A,17,集合算律,4,涉及全集和空集的算律：,补元律,、,零律,、,同一律,、,否定律,E,补元律,A,A,=,A,A,=,E,零律,A,=,A,E,=,E,同一律,A,=,A,A,E,=,A,否定,=,E,E,=,18,集合证明题,证明方法：命题演算法、等式置换法,命题演算证明法的书写规范,(,以下的,X,和,Y,代表集合公式,),(1),证,X,Y,任取,x,，,x,X,x,Y,(2),证,X,=,Y,方法一 分别证明,X,Y,和,Y,X,方法二,任取,x,，,x,X,x,Y,注意：在使用方法二的格式时，必须保证每步推理都是充,分必要的,19,集合等式的证明,方法一：命题演算法,例,3,证明,A,(,A,B,)=,A,（吸收律）,证 任取,x,x,A,(,A,B,),x,A,x,A,B,x,A,(,x,A,x,B,),x,A,因此得,A,(,A,B,)=,A.,例,4,证明,A,B,=,A,B,证 任取,x,x,A,B,x,A,x,B,x,A,x,B,x,A,B,因此得,A,B,=,A,B,20,等式代入法,方法二：等式置换法,例,5,假设交换律、分配律、同一律、零律已经成立，证明吸,收律,.,证,A,(,A,B,),=(,A,E,),(,A,B,),（同一律）,=,A,(,E,B,),（分配律）,=,A,(,B,E,),（交换律）,=,A,E,（零律）,=,A,（同一律）,21,包含等价条件的证明,例,6,证明,A,B,A,B,=,B,A,B,=,A,A,B,=,证明思路：,确定问题中含有的命题：本题含有命题,确定命题间的关系（哪些命题是已知条件、哪些命题是要证明的结论）：本题中每个命题都可以作为已知条件，每个命题都是要证明的结论,确定证明顺序：,，,，,，,按照顺序依次完成每个证明（证明集合相等或者包含）,22,证明,证明,A,B,A,B,=,B,A,B,=,A,A,B,=,证 ,显然,B,A,B,，下面证明,A,B,B,.,任取,x,，,x,A,B,x,A,x,B,x,B,x,B,x,B,因此有,A,B,B,.,综合上述得证,.,A,=,A,(,A,B,),A,=,A,B,(,由知,A,B,=,B,，将,A,B,用,B,代入,),23,假设,A,B,即,x,A,B,，那么知道,x,A,且,x,B,.,而,x,B,x,A,B,从而与,A,B,=,A,矛盾,.,假设,A,B,不成立，那么,x,(,x,A,x,B,),x,A,B,A,B,与条件矛盾,.,证明,24,第六章 习题课,主要内容,集合的两种表示法,集合与元素之间的隶属关系、集合之间的包含关系的区别与联系,特殊集合：空集、全集、幂集,文氏图及有穷集合的计数,集合的,等运算以及广义,运算,集合运算的算律及其应用,25,基本要求,熟练掌握集合的两种表示法,能够判别元素是否属于给定的集合,能够判别两个集合之间是否存在包含、相等、真包含等关系,熟练掌握集合的基本运算（普通运算和广义运算）,掌握证明集合等式或者包含关系的基本方法,26,练习,1,1,判断下列命题是否为真,(1),(2),(3),(4),(5),a,b,a,b,c,a,b,c,(6),a,b,a,b,c,a,b,(7),a,b,a,b,a,b,(8),a,b,a,b,a,b,解,(1),、,(3),、,(4),、,(5),、,(6),、,(7),为真，其余为假,.,27,方法分析,(1),判断元素,a,与集合,A,的隶属关系是否成立基本方法：,把,a,作为整体检查它在,A,中是否出现，注意这里的,a,可,能是集合表达式,.,(2),判断,A,B,的四种方法,若,A,B,是用枚举方式定义的，依次检查,A,的每个元素是否在,B,中出现,.,若,A,B,是谓词法定义的，且,A,B,中元素性质分别为,P,和,Q,那么“若,P,则,Q,”,意味,A,B,，“,P,当且仅当,Q,”,意味,=,通过集合运算判断,A,B,，即,A,B,=,B,A,B,=,A,A,B,=,三个等式中有一个为真,.,通过文氏图判断集合的包含（注意这里是判断，而不是证明,28,练习,2,2,设,S,1,=1,2,8,9,，,S,2,=2,4,6,8,S,3,=1,3,5,7,9,S,4,=3,4,5,S,5,=3,5,确定在以下条件下,X,是否与,S,1,S,5,中某个集合相等？如果是，又与哪个集合相等？,（,1,）若,X,S,5,=,（,2,）若,X,S,4,但,X,S,2,=,（,3,）若,X,S,1,且,X,S,3,（,4,）若,X,S,3,=,（,5,）若,X,S,3,且,X,S,1,29,解答,解,(1),和,S,5,不交的子集不含有,3,和,5,，因此,X,=,S,2,.,(2),S,4,的子集只能是,S,4,和,S,5,.,由于与,S,2,不交，不能含有偶数，,因此,X,=,S,5,.,(3),S,1,S,2,S,3,S,4,和,S,5,都是,S,1,的子集，不包含在,S,3,的子集含有,偶数，因此,X,=,S,1,S,2,或,S,4,.,(4),X,S,3,=,意味着,X,是,S,3,的子集，因此,X,=,S,3,或,S,5,.,(5),由于,S,3,是,S,1,的子集，因此这样的,X,不存在,.,30,练习,3,3.,判断以下命题的真假，并说明理由,.,（,1,）,A,B,=,A,B,=,（,2