离散数学集合(精品).ppt

《离散数学集合(精品).ppt》由会员分享，可在线阅读，更多相关《离散数学集合(精品).ppt（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、3.1 3.1 集合的基本概念集合的基本概念一、集合：一些可确定的可分辨可确定的可分辨的事物构成的整体。用大写字母A,B,C,标记。如：(1)26个英文字母的集合；(2)坐标平面上所有点的集合。规定：(i)元素之间彼此相异；(ii)没有次序关系。组成一个集合的每一个特定的事物，叫做集合的元素，用小写字母a,b,c,标记。常用集合记号：常用集合记号：N：自然数集(包括0)；Z：代表整数集；Q：有理数集；R：实数集；C：复数集；：空集(不含任何元素)；U：全集二、常用集合三、集合的表示方法：(1)列举法：A=a,b,c,d 可以看出aA，但eA(2)描述法：用谓词概括该集合中元素的属性，即：A=x

2、|P(x)如：A=x|xZ 3x6(1)子集：如果B中每个元素都是A中元素，则BA。(2)相等集：如果A B且B A，则A=B。符号化：B A(x)(xBxA)，显然：(i)S S，(ii)对任意集合A，A。符号化：A=B A B B A四、集合之间的关系(3)真子集：如果B A A 且 B A，则 B A。(4)幂 集：集合A的全体子集构成的集合，记作P(A)。符号化：P(A)=B|B A，n元集A的幂集P(A)中含2n个元素。例例例例3.13.1 计算以下幂集(1)P()(2)P(,)(3)P(1,2,3)解：解：解：解：(1)P()=(为什么不是?)(2)P(,)=,(3)P(1,2,3

3、)=,方法：先写方法：先写 子集；再写含一个元素的子集；子集；再写含一个元素的子集；再写含二个元素的子集；再写含二个元素的子集；,1,2,3,1,2,33.2 3.2 集合的基本运算集合的基本运算 并：A B=x|xA xB交：AB=x|xA xB，若AB=，则称A与B不交相对补：A B=x|xA xB绝对补：A对全集U的相对补集，记作：A或对称差：A B=(A B)(B A)=(A B)(AB)一、几种常见的运算集合运算的直观表示集合运算的直观表示：文氏图画法画法：(1)用大矩形表示全集U；(2)用一些圆圈(矩形内)表示不同的集合及其关系；(3)用阴影线表示运算结果。二、文氏图如：ABABA

4、BA B三、集合算律：(1)幂等律幂等律 AA=A AA=A(2)结合律结合律 (AB)C =A(BC)(3)交换律交换律 AB=BA AB=BA(4)分配律分配律 A(BC)=(AB)(AC)(AB)C =A(BC)A(BC)=(AB)(AC)(9)吸收律吸收律 A(AB)=A(7)排中律排中律 A =U(8)矛盾律矛盾律 A =A(AB)=A(5)同一律同一律 A=A AU=A(6)零零 律律 AU=U A=(10)德德.摩根律摩根律A (BC)=(A B)(A C)A(BC)=(A B)(A C)(11)互补律互补律 A =U (排中律排中律)=U (德德 摩根律摩根律)=(德德 摩根律

5、摩根律)(12)双重否定律双重否定律A =(矛盾律矛盾律)常常用用运运算算性性质质(1)AB A AB B(2)A AB B AB(3)A B A(5)AB=B A B AB=A A B=(证明包含关系的各种方法)(4)(补变交)(7)(A B)C=A(B C)(8)A =A(9)A A=(6)A B=B A(10)A B=A C B=C (消去律)例例例例3.23.2 化简(ABC)(AB)(A(BC)A)解题思想：解题思想：解：解：解：解：因为AB ABC A A(BC)所以(ABC)(AB)=AB(A(BC)A=A所以原式是：(AB)A=BA利用算律和运算性质四、应用3.3 3.3 集合

6、中元素的计数集合中元素的计数容斥原理：对任意两个有限集A和B，有|AB|=|A|+|B|AB|：集合的基数(元素个数)一、集合计数的基本原理证明：证明：证明：证明：AB=B(AB)且B(AB)=又 A=(AB)(AB)且(AB)(AB)=从而|AB|=|B|+|AB|A|=|A B|+|AB|即|AB|=|B|+|A|AB|ABC|A|B|C|AB|AC|BC|ABC|推推 广广例例例例3.3.3 3 某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有两人会打这三种球，而6个会打网球的人都会打另外一种球(指篮球和排球)，求不会打这三种球的人数？二

7、、实例 =|A|+|B|+|C|AB|AC|BC|+|ABC|先求：先求：=12+6+146 5+2|AB|=23|AB|解：解：解：解：用A、B、C分别表示会打排球、网球、篮球的学生集合，则有：|A|=12，|AC|=6，|B|=6，|U|=25|C|=14，|BC|=5，|ABC|=2|ABC|又因为6个会打网球的人都会打另外一种球，=6 (5 2)=3 例例例例3.43.4 一个班里有50个学生，在第一次考试中有26人得5分，在第二次考试中有21人得5分。如果两次考试中都没得5分的有17人，那么在两次考试都得5分的有多少人？解：解：解：解：设A、B、分别表示第一和第二次考试中得5分学生的集合，那么有 又因为|AB|=|A|+|B|AB|所以|AB|=|A|+|B|AB|=26+21 33=14知=33小结与学习要求小结与学习要求熟练掌握空集，子集，幂集，并，熟练掌握空集，子集，幂集，并，熟练掌握空集，子集，幂集，并，熟练掌握空集，子集，幂集，并，交，补，差等概念，善于应用各种运交，补，差等概念，善于应用各种运交，补，差等概念，善于应用各种运交，补，差等概念，善于应用各种运算的性质，要特别掌握好容斥原理在算的性质，要特别掌握好容斥原理在算的性质，要特别掌握好容斥原理在算的性质，要特别掌握好容斥原理在集合计数中的应用。集合计数中的应用。集合计数中的应用。集合计数中的应用。