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

第三章集合与关系3-3包含与排斥原理讲课人：李朔Email:chn.nj.ls@1第1页

一、有限集计数一个集合若其组成集合元素个数是有限，则称作有限集。设A1.A2为有限集，其元素个数分别记为|A1|，|A2|P96有限集记数有以下几个性质：a）|A1∪A2|≤|A1|+|A2|b）|A1∩A2|≤min(|A1|,|A2|)c）|A1―A2|≥|A1|―|A2|d）|A1⊕A2|=|A1|+|A2|―2|A1∩A2|以上公式能够经过文氏图直接得到说明2第2页

二、容斥原理定理3-3.1设A1,A2为有限集合,其元素个数分别为|A1|,|A2|,则

|A1∪A2|=|A1|+|A2|―|A1∩A2|

A2A1EA1∩A23第3页

二、容斥原理定理设A1,A2,A3为有限集合,其元素个数分别为|A1|,|A2|,|A3|则有

|A1∪A2∪A3|=|A1|+|A2|+|A3|―|A1∩A2|―|A1∩A3|―|A2∩A3|+|A1∩A2∩A3|

4第4页

二、容斥原理A1A2A3A1∩A2A1∩A3A2∩A3A1∩A2∩A35第5页

二、容斥原理例一个学校只有三门课程：数学、物理、化学。已知修这三门课学生分别有170、130、120人；同时修数学、物理两门课学生45人；同时修数学、化学20人；同时修物理化学22人。同时修三门3人。问这学校共有多少学生？6第6页

二、容斥原理例一个学校只有三门课程：数学、物理、化学。已知修这三门课学生分别有170、130、120人；同时修数学、物理两门课学生45人；同时修数学、化学20人；同时修物理化学22人。同时修三门3人。问这学校共有多少学生？解：令M为修数学学生集合；P为修物理学生集合；C为修化学学生集合；则：书例P96例题1.27第7页

二、容斥原理定理设A1,A2,A3,A4为有限集合,其元素个数分别为|A1|,|A2|,|A3|,|A4|,则

|A1∪A2∪A3∪A4|=|A1|+|A2|+|A3|+|A4|

―|A1∩A2|―|A1∩A3|―|A1∩A4|

―|A2∩A3|―|A2∩A4|―|A3∩A4|

+|A1∩A2∩A3|+|A2∩A3∩A4|

+|A1∩A3∩A4|+|A1∩A2∩A4|

―|A1∩A3∩A2∩A4|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|证实:P989第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。设Ai为不超出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=3015第15页

本课小结有限集计数包容排斥原理16第16页

作业P100（3）17第17页