集合的基本概念和运算.ppt

3.3集合中元素的计数AnIntroductiontoDatabaseSystenm01容斥原理02容斥原理实例3.3.1容斥原理AnIntroductiontoDatabaseSystenm集合A含有n个元素，可以说集合A的基数是n，记作cardA=n。所谓基数就是表示集合中所含元素多少的量。如果集合A的基数是n，也可以记为|A|=n。显然空集的基数是0，即|?|=0。定义设为集合，若存在自然数n（0也是自然数），使得|A|=cardA=n，则称A为有穷集，否则就称A为无穷集。例3.3.1有100名程序员，其中47名熟悉C语言，35名熟悉C++语言，23名熟悉这两种语言。问有多少人对这两种语言都不熟悉？解：设A，B分别表示熟悉C和C++语言的程序员的集合，则该问题可以用图的文氏图表示。将熟悉两种语言的对应人数23填入A∩B的区域内，不难得到A-B和B-A的人数分别为|A-B|=|A|-|A∩B|=47-23=24|B-A|=|B|-|A∩B|=35-23=12从而得到|A∪B|=24+23+12=59,故，|~(A∪B)|=100-59=41，即两种语言都不熟悉的有41人。3.3.1容斥原理AnIntroductiontoDatabaseSystenm设S是有穷集，P1和P2分别表示两种性质，对于S中的任何一个元素x，只能处于以下四种情况之一：（1）只具有性质P1；（2）只具有性质P2；（3）具有P1和P2两种性质；（4）两种性质都没有。令A1和A2分别表示S中具有性质P1和P2的元素的集合。为了使表达式简洁，对任何集合B，用代替~B。由文氏图不难得到以下公式这就是容斥原理的一种简单形式。如果涉及到三条性质，容斥原理的公式则变成3.3.1容斥原理AnIntroductiontoDatabaseSystenm定理S中不具有性质P1,P2,…,Pm的元素数是定理证明略。推论在S中至少具有一条性质的元素数是3.3集合中元素的计数AnIntroductiontoDatabaseSystenm01容斥原理02容斥原理实例3.3.2容斥原理实例AnIntroductiontoDatabaseSystenm例3.3.4某班学生150人。数学考试成绩90分以上的有80人，语文考试成绩90分以上的有75人，两门课程均在90分以上的有50人，问（1）只有一门课程成绩90分以上的学生有多少人？（2）两门课程成绩均不在90分以上的学生有多少人？解：全集为该班学生组成的集合。设由题意可知，，，（1）即需求。因为所以，，即3.3.2容斥原理实例续AnIntroductiontoDatabaseSystenm即需求AnIntroductiontoDatabaseSystenm华中师范大学计算机科学系

离散数学第三章集合的基本概念和运算第三章集合的基本概念和运算AnIntroductiontoDatabaseSystenm输入标题集合的基本概念输入标题输入标题输入标题笛卡尔乘积2集合的基本运算集合中元素的计数1433.1集合的基本概念AnIntroductiontoDatabaseSystenm集合是不能精确定义的基本的数学概念，直观地讲，集合是由某些可以相互区别的事物汇集在一起所组成的整体。对于给定的集合和事物，应该可以断定这个特定的事物是否属于这个集合。如果属于，就称它为这个集合的元素。集合通常用大写的英文字母来表示。集合有两种表示方法：枚举法和谓词表示法。前一种方法是将集合中的所有元素罗列出来，元素之