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

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