离散数学-第六章的课件

1,主要内容集合的基本概念属于、包含幂集、空集文氏图等集合的运算有穷集的计数集合恒等式集合运算的算律、恒等式的证明方法,第二部分集合论,第六章集合代数,2,6.1集合的基本概念,1.集合定义集合没有精确的数学定义理解：由离散个体构成的整体称为集合，称这些个体为集合的元素常见的数集：N,Z,Q,R,C等分别表示自然数、整数、有理数、实数、复数集合,2.集合表示法列元素法-列出集合的所有元素，所有元素之间用逗号隔开，并把它们用花括号括起来谓词表示法-用谓词来概括集合中元素的性质实例：列元素法自然数集合N=0,1,2,3,谓词表示法S=x|xRx21=0,3,元素与集合,1.集合的元素具有的性质无序性：元素列出的顺序无关相异性：集合的每个元素只计数一次确定性：对任何元素和集合都能确定这个元素是否为该集合的元素任意性：集合的元素也可以是集合2元素与集合的关系隶属关系：或者3集合的树型层次结构例如：集合A=a,b,c,d,d,规定：AA,4,集合与集合,集合与集合之间的关系：,=,定义6.1设A，B为集合，如果B中的每个元素都是A中的元素，则称B是A的子集合，简称子集。这时也称B被A包含，或A包含B，记作BA。如果B不被A包含，则记作BA。符号化表示为：BAx(xBxA)BAx(xBxA)例如NZQRC，但ZN。显然对任何集合A都有AA。定义6.2设A，B为集合，如果AB且BA，则称A与B相等，记作AB。如果A与B不相等，则记作AB。符号化表示为：A=BABBA定义6.3设A，B为集合，如果BA且BA，则称B是A的真子集，记作BA。如果B不是A的真子集，则记作BA。符号化表示为：BABABA例如NZQRC，但NN。注意：和是不同层次的问题，如A=a,a和a,5,空集、全集和幂集,定义6.4空集：不含有任何元素的集合符号化表示为：=x|xx实例：x|xRx2+1=0定理6.1空集是任何集合的子集。证对于任意集合A，Ax(xxA)1(恒真命题)推论是惟一的证明：假设存在空集1和2，由定理6.1有：12和21根据集合相等的定义，有1=2所以得出结论：是惟一的。,6,空集、全集和幂集,含有n个元素的集合简称n元集，它的含有m（mn）个元素的子集叫做它的m元子集。任给一个n元集，怎样求出它的全部子集呢？,例6.1A1,2,3，将A的子集分类：解：0元子集，也就是空集，只有一个：；1元子集，即单元集：1，2，3；2元子集：1,2，1,3，2,3；3元子集：1,2,3。,7,空集、全集和幂集,定义6.5幂集：设A为集合，把A的全部子集构成的集合叫做A的幂集，记作P(A)(或PA，2A)。符号化表示为：P(A)=x|xA实例：P()=,P()=,计数：如果|A|=n，则|P(A)|=2n.,定义6.6全集E：包含了所有集合的集合全集具有相对性：与问题有关，不存在绝对的全集,8,6.2集合的运算,初级运算集合的基本运算有并，交，相对补和对称差定义6.7设A，B为集合，A与B的并集AB，交集AB，B对A的相对补集AB分别定义如下：并AB=x|xAxB交AB=x|xAxB相对补AB=x|xAxB例如：A=a,b,c，B=a，C=b,dAB=a,b,c,AB=a,AB=b,c,B-A=,BC=若两个集合的交集为，则称这两个集合是不交的,9,6.2集合的运算,定义6.8设A，B为集合，A与B的对称差集AB定义为：对称差AB=(AB)(BA)另一种定义是：AB=(AB)(AB)例如：A=a,b,c，B=b,d,AB=a,c,d定义6.9在给定全集E以后，AE，A的绝对补集A定义如下：绝对补A=EA=x|xExA=x|xA例如：Ea，b，c，d，Aa，b，c，则Ad。,10,文氏图,集合运算的表示,A,B,A,B,A,B,A,B,A,E,AB,AB,AB,AB,A,11,几点说明,并和交运算可以推广到有穷个集合上，即A1A2An=x|xA1xA2xAnA1A2An=x|xA1xA2xAnABAB=AB=AB=A,12,广义运算,1.集合的广义并与广义交定义6.10设A为集合，A的元素的元素构成的集合称为A的广义并，记为A。符号化表示为广义并A=x|z(zAxz)定义6.11设A为非空集合，A的所有元素的公共元素构成的集合称为A的广义交，记为A。符号化表示为广义交A=x|z(zAxz)例6.2设Aa,b,c,a,c,d,a,e,fBaCa,c,d则Aa,b,c,d,e,f,Ba，Cac,dAa，Ba，Cac,d,13,广义运算,1.集合的广义并与广义交定义6.10设A为集合，A的元素的元素构成的集合称为A的广义并，记为A。符号化表示为广义并A=x|z(zAxz)定义6.11设A为非空集合，A的所有元素的公共元素构成的集合称为A的广义交，记为A。符号化表示为广义交A=x|z(zAxz)练习:A=1,1,2,1,2,3,B=a,C=a解:A=1,2,3,A=1B=a，B=aC=a，C=a,14,关于广义运算的说明,2.广义运算的性质(1)=，无意义(2)单元集x的广义并和广义交都等于x(3)广义运算减少集合的层次（括弧减少一层）(4)广义运算的计算：一般情况下可以转变成初级运算A=A1,A2,An=A1A2AnA=A1,A2,An=A1A2An3.引入广义运算的意义可以表示无数个集合的并、交运算，例如x|xR=R这里的R代表实数集合.,15,运算的优先权规定,一类运算：广义并，广义交，幂集，绝对补运算运算由右向左顺序进行(右结合)二类运算：并，交，相对补，对称差优先顺序由括号确定混合运算：一类运算优先于二类运算。,例A=a,a,b，计算A(AA).,解：A(AA)=a,b(a,ba)=(ab)(ab)a)=(ab)(ba)=b,16,例6.5设Aa,a,b计算A，A和A(AA)。解:Aa,bAaAabAaAabAaA(AA)(ab)(ab)a)(ab)(ba)b所以Aab，Aa，A(AA)b。,17,作业,书本97页第8题的第（4）小题第9题的第（1）、（3）、（5）三个小题书本98页第18题的第（1）、（3）两个小题,18,有穷集合元素的计数,1.文氏图法2.包含排斥原理定理6.2设集合S上定义了n条性质，其中具有第i条性质的元素构成子集Ai,那么集合中不具有任何性质的元素数为,推论S中至少具有一条性质的元素数为,19,实例,例6.5求1到1000之间（包含1和1000在内）既不能被5和6整除，也不能被8整除的数有多少个？,解方法一：文氏图定义以下集合：S=x|xZ1x1000A=x|xSx可被5整除B=x|xSx可被6整除C=x|xSx可被8整除画出文氏图，然后填入相应的数字，解得N=1000(200+100+33+67)=600,20,实例,方法二|S|=1000|A|=1000/5=200,|B|=1000/6=166,|C|=1000/8=125|AB|=1000/lcm(5,6)=1000/33=33|AC|=1000/lcm(5,8)=1000/40=25|BC|=1000/lcm(6,8)=1000/24=41|ABC|=1000/lcm(5,6,8)=1000/120=8=1000(200+166+125)+(33+25+41)8=600,21,6.3集合恒等式,下面的恒等式给出了集合运算的主要算律，其中A，B，C代表任意集合。幂等律AAAAAA结合律(AB)CA(BC)(AB)CA(BC)交换律ABBAABBA分配律A(BC)(AB)(AC)A(BC)(AB)(AC)同一律AAAEA零律AEEA排中律AAE矛盾律AA吸收律A(AB)AA(AB)A德摩根律A(BC)(AB)(AC)A(BC)(AB)(AC)(BC)=BC(BC)=BCEE双重否定律(A)A,22,除了以上算律以外，还有一些关于集合运算性质的重要结果。例如：ABA，ABB(6.24)AAB，BAB(6.25)ABA(6.26)ABAB(6.27)ABBABABAAB(6.28)ABBA(6.29)(AB)CA(BC)(6.30)AA(6.31)AA(6.32)ABACBC(6.33),23,书本88页,例6.5设Aa,a,b计算A，A和A(AA)。解:Aa,bAaAabAaAabAaA(AA)(ab)(ab)a)(ab)(ba)b所以Aab，Aa，A(AA)b。,24,6.4集合恒等式（P92）,集合算律1只涉及一个运算的算律：交换律、结合律、幂等律,25,集合算律,2涉及两个不同运算的算律：分配律、吸收律,26,集合算律,3涉及补运算的算律：德摩根律，双重否定律,27,集合算律,4涉及全集和空集的算律：补元律、零律、同一律、否定律,28,集合证明题,证明方法：命题演算法、等式置换法命题演算证明法的书写规范(以下的X和Y代表集合公式)(1)证XY任取x，xXxY(2)证X=Y方法一分别证明XY和YX都为真。方法二任取x，xXxY注意：在使用方法二的格式时，必须保证每步推理都是充分必要的（等值）,29,集合等式的证明,方法一：命题演算法例1证明A(AB)=A（吸收律）证任取x,xA(AB)xAxABxA(xAxB)xA因此得A(AB)=A.,例2证明(6.27)AB=AB证任取x,xABxAxBxAxBxAB因此得AB=AB,30,等式置换法,方法二：等式置换法例3假设交换律、分配律、同一律、零律已经成立，证明吸收律A(AB)=A.证A(AB)=(AE)(AB)（同一律）=A(EB)（分配律）=A(BE)（交换律）=AE（零律）=A（同一律）,31,包含等价条件的证明,例4证明(6.28)ABAB=BAB=AAB=证明思路：确定问题中含有的命题：本题含有命题,确定命题间的关系（哪些命题是已知条件、哪些命题是要证明的结论）：本题中每个命题都可以作为已知条件，每个命题都是要证明的结论确定证明顺序：，按照顺序依次完成每个证明（证明集合相等或者包含）,32,证明,证明ABAB=BAB=AAB=证显然BAB，下面证明ABB.任取x，xABxAxBxBxBxB因此有ABB.综合上述得证.AB=A(AB)=A(由知AB=B，将AB代入B，并结合吸收律得证),33,证明ABAB=BAB=AAB=AB=AB=(AB)B=A(BB)=A=假设AB不成立，那么x(xAxB)xABAB与条件矛盾.因此，结论AB成立。,证明,34,式（6.28）在化简集合公式中的应用,例6.14化简(ABC)(AB)(A(BC)A)解：由于ABABC，AA(BC)因此有：(ABC)(AB)(A(BC)A)=(AB)A（由式子（6.28）=(AB)A（由式子（6.27）=(AA)(BA)（分配律）=(BA)（矛盾律）=(BA)（交换律）=BA（同一律）=BA（由式子（6.27）,35,对称差运算算律式（6.33）的证明,例6.15已知AB=AC，证明B=C证已知AB=AC，所以有A(AB)=A(AC)(AA)B=(AA)C（由式子（6.30）B=C（由式子（6.32）B=C（由式子（6.29）B=C（由式子（6.31）,36,练习题,练习：证明下列集合恒等式（1）（AB）C=（AC）B证明：左边=（AB）C=（AB）C（由式子（6.27）=（AC）B（交换律和结合律）=（AC）B（由式子（6.27）=右边（2）（AB）A）=A证明：左边=（AB）A）=（AB）A）（德摩根律）=（AB）A（德摩根律）=A（吸收律）=右边,37,第六章练习作业,书本第100页第32题的第（1）小题第33题的第（1）小题第50题,38,第六章总结,主要内容集合的两种表示法集合与元素之间的隶属关系、集合之间的包含关系的区别与联系特殊集合：空集、全集、幂集文氏图及有穷集合的计数集合的,等运算以及广义,运算集合运算的算律及其应用,39,第六章习题课,主要内容集合的两种表示法集合与元素之间的隶属关系、集合之间的包含关系的区别与联系特殊集合：空集、全集、幂集文氏图及有穷集合的计数集合的,等运算以及广义,运算集合运算的算律及其应用,40,基本要求,熟练掌握集合的两种表示法能够判别元素是否属于给定的集合能够判别两个集合之间是否存在包含、相等、真包含等关系熟练掌握集合的基本运算（普通运算和广义运算）掌握证明集合等式或者包含关系的基本方法,41,练习1,1判断下列命题是否为真(1)(2)(3)(4)(5)a,ba,b,c,a,b,c(6)a,ba,b,c,a,b(7)a,ba,b,a,b(8)a,ba,b,a,b,解(1)、(3)、(4)、(5)、(6)、(7)为真，其余为假.,42,方法分析,(1)判断元素a与集合A的隶属关系是否成立基本方法：把a作为整体检查它在A中是否出现，注意这里的a可能是集合表达式.(2)判断AB的四种方法若A,B是用枚举方式定义的，依次检查A的每个元素是否在B中出现.若A,B是谓词法定义的，且A,B中元素性质分别为P和Q,那么“若P则Q”意味AB，“P当且仅当Q”意味=通过集合运算判断AB，即AB=B,AB=A,AB=三个等式中有一个为真.通过文氏图判断集合的包含（注意这里是判断，而不是证明,43,练习2,2设S1=1,2,8,9，S2=2,4,6,8S3=1,3,5,7,9S4=3,4,5S5=3,5确定在以下条件下X是否与S1,S5中某个集合相等？如果是，又与哪个集合相等？（1）若XS5=（2）若XS4但XS2=（3）若XS1且XS3（4）若XS3=（5）若XS3且XS1,44,解答,解(1)和S5不交的子集不含有3和5，因此X=S2.(2)S4的子集只能是S4和S5.由于与S2不交，不能含有偶数，因此X=S5.(3)S1,S2,S3,S4和S5都是S1的子集，不包含在S3的子集含有偶数，因此X=S1,S2或S4.(4)XS3=意味着X是S3的子集，因此X=S3或S5.(5)由于S3是S1的子集，因此这样的X不存在.,45,练习3,3.判断以下命题的真假，并说明理由.（1）AB=AB=（2）A(BC)=(AB)(AC)（3）AA=A（4）如果AB=B，则A=E.（5）A=xx，则xA且xA.,46,解题思路,先将等式化简或恒等变形.查找集合运算的相关的算律，如果与算律相符，结果为真.注意以下两个重要的充要条件AB=AAB=AB=ABAB=BAB=A如果与条件相符，则命题为真.如果不符合算律，也不符合上述条件，可以用文氏图表示集合，看看命题是否成立.如果成立，再给出证明.试着举出反例，证明命题为假.,47,解答,解(1)B=是AB=A的充分条件，但不是必要条件.当B不空但是与A不交时也有AB=A.(2)这是DM律，命题为真.(3)不符合算律，反例如下：A=1，AA=，但是A.(4)命题不为真.AB=B的充分必要条件是BA，不是A=E.(5)命题为真，因为x既是A的元素，也是A的子集,48,练习4,4证明AB=ACAB=ACB=C,解题思路分析命题：含有3个命题：AB=AC,AB=AC,B=C证明要求前提：命题和结论：命题证明方法：恒等式代入反证法利用已知等式通过运算得到新的等式,49,解答,方法一：恒等变形法B=B(BA)=B(AB)=B(AC)=(BA)(BC)=(AC)(BC)=(AB)C=(AC)C=C,方法二：反证法.假设BC，则存在x(xB且xC),或存在x(xC且xB).不妨设为前者.若x