离散数学包含与排斥原理省公开课一等奖全国示范课微课金奖PPT课件.pptx

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第三章 集合与关系,1,第1页,一、有限集计数,一个集合若其组成集合元素个数是有限，则称作,有限集,。,设,A,1,、A,2,为素个数分别记为|,A,1,|，|A,2,|,P96,有限集记数有以下几个性质：,a）|A,1,A,2,|,|A,1,|+|A,2,|,b）|A,1,A,2,|,min(,|A,1,|,|A,2,|),c）|A,1,A,2,|,|A,1,|,|A,2,|,d）|A,1,A,2,|,=,|A,1,|+|A,2,|,2,|A,1,A,2,|,以上公式能够经过文氏图直接得到说明,2,第2页,二、容斥原理,定理3-3.1,设,A,1,，,A,2,为有限集合，其元素个数分别为|,A,1,|，|A,2,|，,则|,A,1,A,2,|,=,A,2,|,|A,1,A,2,|,A,2,A,1,E,A,1,A,2,3,第3页,二、容斥原理,定理,设,A,1,，,A,2,，A,3,为有限集合，其元素个数分别为|,A,1,|，|A,2,|，|A,3,|,则有,|A,1,A,2,A,3,|,=,|A,1,|+|A,2,|A,2,|,|A,1,A,3,|,|A,2,A,3,|,+|A,1,A,2,A,3,|,4,同时修数学、化学20人；同时修物理化学22人。,同时修三门3人。问这学校共有多少学生？,解：,令,M,为修数学学生集合；,P,为修物理学生集合；,C,为修化学学生集合；则：,书例,P96,例题1、2,7,第7页,二、容斥原理,定理,设,A,1,，,A,2,，,A,3,，,A,4,为有限集合，其元素个数分别为|,A,1,|，|A,2,|，|A,3,|，|A,4,|，,则,|,A,1,A,2,A,3,A,4,|,=,|A,1,|+|A,2,|+|A,3,|+|A,4,|,|A,1,A,2,|,|A,1,A,3,|,|A,1,A,4,|,|A,2,A,3,|,|A,2,A,4,|,|A,3,A,4,|,+,|A,1,A,2,A,3,|,+,|A,2,A,3,A,4,|,+,|A,1,A,3,A,4,|,+,|A,1,A,2,A,4,|,|A,1,A,3,A,2,A,4,|,8,第8页,二、容斥原理,P97,定理3-3.,(推广到,n,个有限集情况）设,A1,A2,An,为有限集合，其元素个数分别为|,A1|，|A2|,|An|，,则|,A1,A2,An|,=,|Ai|,|Ai,Aj|,+,|Ai,Aj,Ak|+,+(-1),n-1,|A1,A2,An|,证实：,P98,9,第9页,练习,例,求从1到500整数中能被3或5除尽数个数。,10,第10页,练习,例,求从1到500整数中能被3或5除尽数个数。,解：,令,A,为从1到500整数中被3除尽数集合，,B,为被5除尽数集合,被3或5除尽数个数为,11,第11页,练习,P99,书例3,例 求不超出120素数个数。,提醒,：因 ，故不超出120合数是2、3、5、7倍数，而且不超出120合数因子不可能都超出11。设,A,i,为不超出120数,i,倍数集，,i=2，3，5，7。,12,第12页,练习,例 求不超出120素数个数。,解：,13,第13页,练习,14,第14页,练习,注意：,27并非就是不超出120素数个数，因为这里排除了2，3，5，7着四个数，又包含了1这个非素数。2，3，5，7本身是素数。故所求不超出120素数个数为：,27+4-1=30,15,第15页,本课小结,有限集计数,包容排斥原理,16,第16页,作业,P100（3）,17,第17页,