离散数学ppt课件第六章 集合代数.ppt

《离散数学ppt课件第六章 集合代数.ppt》由会员分享，可在线阅读，更多相关《离散数学ppt课件第六章 集合代数.ppt（58页珍藏版）》请在三一办公上搜索。

1、希帕索斯悖论与第一次数学危机,毕达哥拉斯：欧多克索斯：,贝克莱悖论与第二次数学危机,牛顿、莱布尼兹：贝克莱：,第6章 集合代数,本章说明,本章的主要内容集合的基本概念集合、相等、(真)包含、子集、空集、全集、幂集集合运算交、并、(相对和绝对)补、对称差、广义交、广义并文氏图有穷集计数问题集合恒等式本章与后续各章的关系是集合论后面各章的基础是典型的布尔代数系统,6.1 集合的基本概念,集合(Set)是不能精确定义的基本概念。所谓集合，是指我们无意中或思想中将一些确定的、彼此完全不同的客体的总和而考虑为一个整体。这些客体叫做该集合的元素。(康托)直观地说，把一些事物汇集到一起组成一个整体就叫集合，

2、而这些事物就是这个集合的元素或成员。例如：方程x210的实数解集合：26个英文字母的集合；坐标平面上所有点的集合；集合通常用大写的英文字母来标记。,常见的数的集合,N自然数集合Z整数集合Q有理数集合R实数集合C复数集合,集合的表示方法,表示一个集合的方法主要有两种：列元素法和谓词表示法。列元素法(roster)是列出集合的所有元素，元素之间用逗号隔开，并把它们用花括号括起来。Aa，b，c，zZ0，1，2，C桌子,灯泡,老虎,自然数 谓词表示法(defining predicate)是用谓词来概括集合中元素的属性。Bx|xRx210许多集合可以用两种方法来表示，如B也可以写成-1，1。但是有些集

3、合不可以用列元素法表示，如实数集合。,集合的元素,集合的元素是彼此不同的，如果同一个元素在集合中多次出现应该认为是一个元素。例如：1，1，2，2，31，2，3集合的元素是无序的。例如：1，2，33，1，2在本书所采用的体系中规定：集合的元素都是集合。,元素和集合之间的关系,元素和集合之间的关系是隶属关系，即属于或不属于，属于记作，不属于记作。例如：Aa，b，c，d，daA，b，cA，dA，dA，bA，dA。b和d是A的元素的元素。可以用一种树形图表示集合与元素的隶属关系。,说明,隶属关系可以看作是处在不同层次上的集合之间的关系。规定：对任何集合A都有AA。,A,子集（subset）,定义6.1

4、 设A，B为集合，如果B中的每个元素都是A中的元素，则称B是A的子集合，简称子集。这时也称B被A包含，或A包含B，记作 BA。包含的符号化表示为BA x(xBxA),显然对任何集合A都有 AA。,隶属和包含的说明,隶属关系和包含关系都是两个集合之间的关系，对于某些集合可以同时成立这两种关系。例如 Aa，a和a既有aA，又有aA。前者把它们看成是不同层次上的两个集合，后者把它们看成是同一层次上的两个集合。,集合相等(equal),定义6.2 设A，B为集合，如果 AB 且 BA，则称A与B相等，记作AB。相等的符号化表示为：AB AB BA 如果A与B不相等，则记作AB。,真子集,定义6.3 设

5、A，B为集合，如果 BA 且 BA，则称B是A的真子集，记作BA。真子集的符号化表示为BA BA BA如果B不是A的真子集，则记作B A。例如：N N,空集(empty set),定义6.4 不含任何元素的集合叫做空集，记作。空集的符号化表示为：x|xx。例如:x|xRx2+1=0是方程x2+1=0的实数解集，因为该方程无实数解，所以是空集。,空集的性质,推论 空集是唯一的。证明：假设存在空集1和2，由定理6.1有1 2，2 1。根据集合相等的定义，有 1 2。,定理6.1 空集是一切集合的子集。证明：任给集合A，由子集定义有 A x(x xA)右边的蕴涵式因前件假而为真命题，所以 A也为真。

6、,n元集,含有n个元素的集合简称n元集，它的含有m(mn)个元素的子集叫做它的m元子集。例6.1 A1,2,3，将A的子集分类：,0元子集（空集）,1元子集（单元集）,1，2，3,2元子集,1,2，1,3，2,3,3元子集,1,2,3,幂集(power set),一般地说，对于n元集A，它的0元子集有 个，1元子集有 个，m元子集有 个，n元子集有 个。子集总数为,定义6.5 设A为集合，把A的全部子集构成的集合叫做A的幂集，记作P(A)(或PA，2A)。幂集的符号化表示为P(A)x|xA 若A是n元集，则P(A)有 2n 个元素。,全集,定义6.6 在一个具体问题中，如果所涉及的集合都是某个

7、集合的子集，则称这个集合为全集，记作E。,说明,全集是有相对性的，不同的问题有不同的全集，即使是同一个问题也可以取不同的全集。例如，在研究平面上直线的相互关系时，可以把整个平面(平面上所有点的集合)取作全集，也可以把整个空间(空间上所有点的集合)取作全集。一般地说，全集取得小一些，问题的描述和处理会简单些。,6.2 集合的运算,定义6.7 设A，B为集合，A与B的并集AB，交集AB，B对A的相对补集AB分别定义如下：ABx|xAxB(union set)ABx|xAxB(intersection set)ABx|xAxB(difference set),举例,设 Aa，b，c，Ba，Cb，d

8、则有 ABa，b，c，ABa，ABb，c，BA，BC,说明,如果两个集合的交集为，则称这两个集合是不相交的。例如B和C是不相交的。,n个集合的并和交,两个集合的并和交运算可以推广成n个集合的并和交：A1A2Anx|xA1xA2xAnA1A2Anx|xA1xA2xAn上述的并和交可以简记为：,A1A2An,A1A2An,两个集合的并和交运算可以推广到无穷多个集合的情况：,A1A2,A1A2,对称差集,定义6.8 设A，B为集合，A与B的对称差集 AB定义为：AB(AB)(BA)对称差运算的另一种定义是AB(AB)(AB)例如:Aa，b，c，Bb，d，则 ABa，c，d,绝对补集,定义6.9 AE

9、Ax|xExA 因为E是全集，xE是真命题，所以A可以定义为：Ax|x A 例如:Ea，b，c，d，Aa，b，c Ad,文氏图(Venn Diagram),集合之间的关系和运算可以用文氏图给予形象的描述。文氏图的构造方法如下：画一个大矩形表示全集E(有时为简单起见可将全集省略)。在矩形内画一些圆(或任何其它的适当的闭曲线)，用圆的内部表示集合。不同的圆代表不同的集合。如果没有关于集合不交的说明，任何两个圆彼此相交。图中阴影的区域表示新组成的集合。可以用实心点代表集合中的元素。,文氏图的实例,有穷集的计数问题,使用文氏图可以很方便地解决有穷集的计数问题。首先根据已知条件把对应的文氏图画出来。一般

10、地说，每一条性质决定一个集合。有多少条性质，就有多少个集合。如果没有特殊说明，任何两个集合都画成相交的然后将已知集合的元素数填入表示该集合的区域内。通常从n个集合的交集填起，根据计算的结果将数字逐步填入所有的空白区域。如果交集的数字是未知的，可以设为x。根据题目中的条件，列出一次方程或方程组，就可以求得所需要的结果。,例6.2,例6.2 对24名会外语的科技人员进行掌握外语情况的调查。其统计结果如下：会英、日、德和法语的人分别为13，5，10和9人，其中同时会英语和日语的有2人，会英、德和法语中任两种语言的都是4人。已知会日语的人既不懂法语也不懂德语，分别求只会一种语言(英、德、法、日)的人数

11、和会三种语言的人数。解：令A，B，C，D分别表示会英、法、德、日语的人的集合。根据题意画出文氏图。设同时会三种语言的有x人，只会英、法或德语一种语言的分别为y1，y2和y3人。将x和y1，y2，y3填入图中相应的区域，然后依次填入其它区域的人数。,例6.2,2,5-2,y1+2(4-x)+x+213y2+2(4-x)+x9y3+2(4-x)+x10y1+y2+y3+3(4-x)+x24-5,包含排斥原理,定理6.2 设S为有穷集，P1,P2,Pm是m个性质。S中的任何元素x或者具有性质Pi，或者不具有性质Pi(i=1,2,m),两种情况必居其一。令Ai表示S中具有性质Pk的元素构成的子集，则S

12、中不具有性质P1,P2,Pm的元素为,推论,S中至少具有一条性质的元素数为,例6.3,例6.3 求1到1000之间(包含1和1000在内)既不能被5和6，也不能被8整除的数有多少个。解答 设Sx|xZ1x1000 A x|xSx可被5整除 B x|xSx可被6整除 C x|xSx可被8整除|T|表示有穷集T中的元素数x表示小于等于x的最大整数lcm(x1,x2,xn)表示x1,x2,xn的最小公倍数,例6.3,|A|1000/5200|B|1000/6166|C|1000/8125|AB|1000/lcm(5,6)33|AC|1000/lcm(5,8)25|BC|1000/lcm(6,8)41

13、|ABC|1000/lcm(5,6,8)8 将这些数字依次填入文氏图，得到,例6.3,根据包含排斥原理，所求不能被5，6和8整除的数应为,由文氏图也可得知，不能被5，6和8整除的数有1000(200+1003367)600个。,广义并和广义交,定义6.10 设A为集合，A的元素的元素构成的集合称为A的广义并，记为A。符号化表示为Ax|z(zAxz)定义6.11 设A为非空集合，A的所有元素的公共元素构成的集合称为A的广义交，记为A。符号化表示为 Ax|z(zAxz),例6.4,例6.4 设 Aa,b,c,a,c,d,a,e,f Ba Ca,c,d则 Aa,b,c,d,e,f Ba Cac,d

14、Aa Ba Cac,d,广义并与广义交的说明,若AA1,A2,An，则AA1A2An若AA1,A2,An，则AA1A2An在后面的叙述中，若只说并或交，则这都是指集合的初级并或初级交；如果在并或交前边冠以“广义”两个字，则指集合的广义并或广义交。为了使得集合表达式更为简洁，我们对集合运算的优先顺序做如下规定：称广义并、广义交、幂集、绝对补运算为一类运算并、交、相对补、对称差运算为二类运算。一类运算优先于二类运算一类运算之间由右向左顺序进行二类运算之间由括号决定先后顺序。,例6.5,例6.5 设 Aa,a,b计算A，A，A(AA)解答 Aa,bAaAabAaA(AA)(ab)(aba)(ab)(

15、b-a)b,6.3 集合恒等式,下面的恒等式给出了集合运算的主要算律，其中A，B，C代表任意集合。幂等律 AAA(6.1)AAA(6.2)结合律(AB)CA(BC)(6.3)(AB)CA(BC)(6.4)交换律 ABBA(6.5)ABBA(6.6)分配律 A(BC)(AB)(AC)(6.7)A(BC)(AB)(AC)(6.8)同一律 AA(6.9)AEA(6.10),6.3 集合恒等式,零律 AEE(6.11)A(6.12)排中律 AAE(6.13)矛盾律 AA(6.14)吸收律 A(AB)A(6.15)A(AB)A(6.16)德摩根律 A(BC)(AB)(AC)(6.17)A(BC)(AB)

16、(AC)(6.18)(BC)BC(6.19)(BC)BC(6.20)E(6.21)E(6.22)双重否定律(A)A(6.23),集合运算性质的一些重要结果,ABA，ABB(6.24)AAB，BAB(6.25)ABA(6.26)ABAB(6.27)ABB AB ABA AB(6.28)ABBA(6.29)(AB)CA(BC)(6.30)AA(6.31)AA(6.32)ABAC BC(6.33),对偶(dual)原理,对偶(dual)式：一个集合表达式，如果只含有、E、，那么同时把与互换，把与E互换，把与互换，得到式子称为原式的对偶式。对欧原理：对偶式同真假。或者说，集合恒等式的对偶式还是恒等式。

17、,集合恒等式的证明方法,逻辑演算法利用逻辑等值式和推理规则集合演算法利用集合恒等式和已知结论,逻辑演算法的格式,题目：AB证明：x，xA xB所以 AB或证 PQ QP,题目：AB证明：x，xA xB所以 AB,集合演算法的格式,题目：AB证明：A B所以 AB,题目：AB证明：A B所以 AB,例6.6,例6.6 证明式6.17，即 A(BC)(AB)(AC)证明 对任意的x，有xA(BC)xA xBCxA(xBxC)xA(xBxC)xA(xB xC)(xAxB)(xAxC)xAB xAC x(AB)(AC)所以 A(BC)(AB)(AC),例6.7,例6.7 证明式6.10，即 AEA证明

18、 对任意的x，有xAExA xExA(因为xE是恒真命题)所以 AEA,例6.8,例6.8 假设已知等式6.16.14，试证等式6.15，即 A(AB)A。证明 A(AB)(AE)(AB)(由等式6.10)A(EB)(由等式6.8)A(BE)(由等式6.5)AE(由等式6.11)A(由等式6.10),例6.9,例6.9 证明等式6.27，即 ABAB证明 对于任意的x，有xAB xA xB xA xB xAB 所以 ABAB。,说明,等式6.27把相对补运算转换成交运算，这在证明有关相对补的恒等式中是很有用的。,例6.10,例6.10 证明(AB)BAB证明(AB)B(AB)B(AB)(BB)

19、(AB)E AB,例6.11,例6.11 证明命题6.28是真命题。ABB AB ABA AB说明 式6.28给出了AB的另外三种等价的定义，这不仅为证明两个集合之间的包含关系提供了新方法，同时也可以用于集合公式的化简。证明思路 ABB AB ABA AB ABB,例6.11,证明 ABB AB对于任意的x，有 xA xAxB xAB xB(因为ABB)所以 AB。,例6.11,证明 AB ABA显然有 AB A，下面证 A AB。对于任意的x，有 xA xAxA xAxB(因为AB)xAB 所以 A AB 由集合相等的定义有 ABA。,例6.11,证明 ABA AB AB AB(AB)B(因

20、为ABA)A(BB)A,例6.11,证明 AB ABB。由例6.10(AB)BAB 及 AB 有 AB B(AB)B B,例6.12,例6.12 化简(ABC)(AB)(A(BC)A)解答 因为 AB ABC，AA(BC)，由式6.28有：(ABC)(AB)(A(BC)A)(AB)ABA,例6.13,例6.13 已知 ABAC，证明BC。证明 已知 ABAC，所以有A(AB)A(AC)(AA)B(AA)C(由式6.30)BC(由式6.32)BC(由式6.29)BC(由式6.31),学习要求,熟练掌握集合的子集、相等、空集、全集、幂集等概念及其符号化表示熟练掌握集合的交、并、（相对和绝对）补、对称差、广义交、广义并的定义及其性质掌握集合的文氏图的画法及利用文氏图解决有限集的计数问题的方法牢记基本的集合恒等式（等幂律、交换律、结合律、分配律、德摩根律、收律、零律、同一律、排中律、矛盾律、余补律、双重否定律、补交转换律）准确地用逻辑演算或利用已知的集合恒等式或包含式证明新的等式或包含式,作业,习题六5，6，7，8，17，23，25，28,典型题,判断元素与集合的隶属关系以及集合之间的包含关系集合的基本运算题有关集合运算性质的分析题集合相等或者包含的证明题有穷集合的计数问题,