第6章 集合代数,离 散 数 学,大学本科生课程,计算机系,本章说明,本章的主要内容集合的基本概念集合、相等、(真)包含、子集、空集、全集、幂集集合运算交、并、(相对和绝对)补、对称差、广义交、广义并文氏图有穷集计数问题集合恒等式本章与后续各章的关系是集合论后面各章的基础是典型的布尔代数系统,6.1 集合的基本概念,集合(Set)是不能精确定义的基本概念所谓集合，是指我们无意中或思想中将一些确定的、彼此完全不同的客体的总和而考虑为一个整体这些客体叫做该集合的元素康托)直观地说，把一些事物汇集到一起组成一个整体就叫集合，而这些事物就是这个集合的元素或成员例如：方程x210的实数解集合：26个英文字母的集合；坐标平面上所有点的集合； 集合通常用大写的英文字母来标记常见的数的集合,N自然数集合Z整数集合Q有理数集合R实数集合C复数集合,集合的表示方法,表示一个集合的方法主要有两种：列元素法和谓词表示法列元素法(roster)是列出集合的所有元素，元素之间用逗号隔开，并把它们用花括号括起来Aa，b，c，zZ0，1，2，C桌子,灯泡,老虎,自然数 谓词表示法(defining predicate)是用谓词来概括集合中元素的属性。
Bx|xRx210许多集合可以用两种方法来表示，如B也可以写成-1，1但是有些集合不可以用列元素法表示，如实数集合集合的元素,集合的元素是彼此不同的，如果同一个元素在集合中多次出现应该认为是一个元素例如：1，1，2，2，31，2，3集合的元素是无序的例如：1，2，33，1，2在本书所采用的体系中规定：集合的元素都是集合元素和集合之间的关系,元素和集合之间的关系是隶属关系，即属于或不属于，属于记作，不属于记作例如：Aa，b，c，d，daA，b，cA，dA，dA，bA，dAb和d是A的元素的元素可以用一种树形图表示集合与元素的隶属关系说明,隶属关系可以看作是处在不同层次上的集合之间的关系规定：对任何集合A都有AAA,子集（subset）,定义6.1 设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 设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也为真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 在一个具体问题中，如果所涉及的集合都是某个集合的子集，则称这个集合为全集，记作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 则有 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 AEAx|xExA 因为E是全集，xE是真命题，所以A可以定义为：Ax|x A 例如: Ea，b，c，d，Aa，b，c Ad,文氏图(Venn Diagram),集合之间的关系和运算可以用文氏图给予形象的描述。
文氏图的构造方法如下：画一个大矩形表示全集E(有时为简单起见可将全集省略)在矩形内画一些圆(或任何其它的适当的闭曲线)，用圆的内部表示集合不同的圆代表不同的集合如果没有关于集合不交的说明，任何两个圆彼此相交图中阴影的区域表示新组成的集合可以用实心点代表集合中的元素文氏图的实例,有穷集的计数问题,使用文氏图可以很方便地解决有穷集的计数问题首先根据已知条件把对应的文氏图画出来一般地说，每一条性质决定一个集合有多少条性质，就有多少个集合如果没有特殊说明，任何两个集合都画成相交的然后将已知集合的元素数填入表示该集合的区域内通常从n个集合的交集填起，根据计算的结果将数字逐步填入所有的空白区域如果交集的数字是未知的，可以设为x根据题目中的条件，列出一次方程或方程组，就可以求得所需要的结果例6.2,例6.2 对24名会外语的科技人员进行掌握外语情况的调查其统计结果如下：会英、日、德和法语的人分别为13，5，10和9人，其中同时会英语和日语的有2人，会英、德和法语中任两种语言的都是4人已知会日语的人既不懂法语也不懂德语，分别求只会一种语言(英、德、法、日)的人数和会三种语言的人数 解：令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中不具有性质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|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 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)(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)(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互换，把与互换，得到式子称为原式的对偶式。
对欧原理：对偶式同真假或者说，集合恒等式的对偶式还是恒等式集合恒等式的证明方法,逻辑演算法利用逻辑等值式和推理规则集合演算法利用集合恒等式和已知结论,逻辑演算法的格式,题目：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。