离散数学第六章 集合-包含与排斥原理.ppt

第六章 集合 6.1 集合的基本概念 6.2 集合的基本运算 6.3 全集和集合的补 6.4 自然数与自然数集 6.5 包含与排斥原理 6．5 包含与排斥原理 定义 一个集合A，如果它所包含的元素个数是有限个，比如n个，我们说A是有限集，且记为 │A│=n 加法公式 令A1，A2是两个有限集，则： │A1∪A2│=│A1│+│A2│–│A1∩A2│ 有限加法公式 定理 设集合A1,A2,…,Ar是r个有限集。则 例 (p71-72) 求出在1和300之间，不能被2、3、5、7中任意一个整除的整数的个数。 分析： A1表示1和300之间能被2整除的整数集合 A2表示1和300之间能被3整除的整数集合 A3表示1和300之间能被5整除的整数集合 A4表示1和300之间能被7整除的整数集合 │A1∪A2∪A3∪A4 │=? 例 (p71-72)求出在1和300之间，不能被2、3、5、7中任意一个整除的整数的个数。 解：设A1,A2,A3,A4分别表示1和300之间能被2整除的、能被3整除的、能被5整除的和能被7整除的整数集合。故有： │A1│=150，│A2│=100，│A3│=60，│A4│=42， │A1∩A2│=50，│A1∩A3│=30，│A1∩A4│=21 │A2∩A3│=20，│A2∩A4│=14，│A3∩A4│=8 │A1∩A2 ∩A3 │=10，│A1∩A2 ∩A4 │=7 │A1∩A3 ∩A4 │=4， │A2∩A3 ∩A4 │=2 │A1∩A2 ∩A3 ∩A4 │=1 于是，我们有： │A1∪A2∪A3∪A4 │ =150+100+60+42– (50+30+21+20+14+8)+(10+7+4+2)–1 =231 因此, 所求个数为 300-231=69. 第六章 集合 6.1 集合的基本概念 6.2 集合的基本运算 6.3 全集和集合的补 6.4 自然数与自然数集 6.5 包含与排斥原理 第七章 关系 本节所涉及的集合一般均为有限集。 例 某班第一次英语测验有12个同学得优，第二次测验有18个同学得优，有5个同学两次测验都得优。至少有一次测验得优的同学数目为多少? │A1∪A2│=│A1│+│A2│–│A1∩A2│ = 12+18-5 = 25 可以用对集合的个数用归纳法来证明。 显然，当r=2时，结论成立。归纳假定r时结论成立,于是 │A1∪┅∪Ar∪Ar+1│=│ A1∪┅∪Ar │+│Ar+1│–│ (A1∪┅∪Ar)∩Ar+1│ 对第一项与第三项分别运用归纳假设即可以得到定理的证明。 │(A1 ∩Ar )∪┅∪(Ar-1∩Ar)│