集合论课件(离散数学).ppt

例5：在20个大学生中,有10个戴眼镜的,有8个爱吃口香糖,有6人即戴眼镜又爱吃口香糖,问不戴眼镜又不吃口香糖的人数是多少？ 解：设A是戴眼镜的大学生的集合， B是爱吃口香糖的大学生的集合。 由题意可知：|A|=10 |B|=8 |A∩B|=6 |A∪B|=|A|+|B|-|A∩B|=10+8-6=12 不戴眼镜又不爱吃口香糖的大学生数： 20-|A∪B|=8 * 定理：设 S 为有穷集，P1, P2, …, Pn 是 n种性质， Ai 是 S 中具有性质 Pi (i=1, 2,…,n)的元素构成的子集。则 S 中不具有性质 P1, P2, …, Pn 的元素数为： * 解：S ={ x | x?Z, 1? x ?1000 }, 如下定义 S 的 3 个子集 A, B, C： A={ x | x?S, 5 | x }， B={ x | x?S, 6 | x }， C={ x | x?S, 8 | x } 例6：求1到1000之间（包含1和1000在内）既不能被 5，6 整除，也不能被 8 整除的数有多少个？ * 对上述子集计数： |S|=1000, |A|= ?1000/5? =200, |B|=?1000/6?=133， |C|= ?1000/8? =125, |A?B|= ?1000/30? =33, |A?C| = ?1000/40? =25, |B?C|= ?1000/24? =41, |A?B?C| = ?1000/120? =8 根据包含排斥原理得： 既不能被 5和6 整除，也不能被 8 整除的数有N个， N = 1000?(200+133+125)+(33+25+41)?8=600 * 方法二：可以利用文氏图 |S|=1000 |A|=200 |B|=133 |C|=125 |A?B| =33 |A?C| =25 |B?C|=41 |A?B?C|=8 67 * 例7：某班有学生60人，其中有38人学习PASCAL，有16人学习C，有21人学习JAVA；有3人这三种语言都学习，有2人这三种语言都不学习，问仅学两门语言的学生数是多少？ 解： 设A为学习PASCAL的学生集合；B为学习C的集合；C为学习JAVA的学生集合。 由题意得： |A|=38 |B|=16 |C|=21 |A∩B∩C|=3 60-|A∪B∪C|=2 * 所以：|A∩B|+|A∩C|+|B∩C|=20 仅学习PASCAL和C的学生数应是： |A∩B|-|A∩B∩C|=|A∩B|-3 仅学习两门语言的人数是：|A∩B|+|A∩C|+|B∩C|-3|A∩B∩C|=11 |A∪B∪C| =|A|+|B|+|C|-|A∩B|-|A∩C|- |B∩C|+|A∩B∩C| * 三、广义并和广义交 定义（广义并）：设A为集合，A的元素的元素构成的集合称为A的广义并，记作:∪A e.g. * 定义（广义交）：设A为非空集合，A的所有元素的公共元素构成的集合称为A的广义交，记作:∩A e.g. * 四、集合运算的优先级 将广义并、广义交、幂集、绝对补称作一类运算；并、交、相对补、对称差称作二类运算。 一类运算的优先级高于二类运算； 一类运算之间由右向左进行； 二类运算之间由括号决定先后顺序。 * 6.3 集合恒等式 集合运算的算律 集合包含的证明 集合相等的证明 * 一、集合运算的算律 ? ? ? 交换 A?B=B?A A?B=B?A A?B=B?A 结合 (A?B)?C= A?(B?C) (A?B)?C= A?(B?C) (A?B)?C= A?(B?C) 幂等 A?A=A A?A=A * 分配 A?(B?C)=(A?B)?(A?C) A?(B?C)=(A?B)?(A?C) 吸收 A?(A?B)=A A?(A?B)=A 双重否定 ??A=A ? ? D.M 律 A?(B?C)=(A?B)?(A?C) A?(B?C)=(A?B)?(A?C) ?(B?C)=?B??C ?(B?C)=?B??C * ? E 补元律 A??A=?(矛盾律) A??A=E(排中律) 零律 A??=? A?E=E 同一律 A??=A A?E=A 否定 ??=E ?E=? * 第二部分 集合论 * * 集合论部分主要内容 第六章 集合代数 第七章 二元关系 第八章 函数 * 第六章 集合代数 3.1 集合的基本概念 3.2 集合的运算 3.3 集合恒等