离散数学 第六章.doc

第二部分集合论 引言集合是数学中最为基本的概念，又是数学各分支、自然科学及社会科学各领域的最普遍采用的描述工具。集合论是离散数学的重要组成部分，是现代数学中占有独特地位的一个分支。G.康托尔是作为数学分支的集合论的奠基人。1870年前后，他关于无穷序列的研究导致集合论的系统发展。1874年他发表了关于实数集合不能与自然数集合建立一一对应的有名的证明。1878年，他引进了两个集合具有相等的“势”的概念。然而，朴素集合论中包含着悖论。第一个悖论是布拉利-福尔蒂的最大序数悖论。1901年罗素发现了有名的罗素悖论。1932年康托尔也发表了关于最大基数的悖论。 集合论的现代公理化开始于1908年E.策梅罗所发表的一组公理，经过A.弗兰克尔的加工，这个系统称为策梅罗-弗兰克尔集合论（ZF），其中包括1904年策梅罗引入的选择公理。另外一种系统是冯*诺伊曼-伯奈斯-哥德尔集合论。公理集合论中一个有名的猜想是连续统假设（CH）。K.哥德尔证明了连续统假设与策梅罗-弗兰克尔集合论的相容性，P.J.科恩证明了连续统假设与策梅罗-弗兰克尔集合论的独立性。现在把策梅罗-弗兰克尔集合论与选择公理一起称为ZFC系统。 本部分主要介绍朴素集合论的主要内容，其中包括集合代数（第六章）、二元关系（第七章）、函数（第八章）、集合的基数（第九章）等。 本部分的先行知识及各部分的关系如下图所示：6.1 集合的基本概念 一集合的表示 集合是不能精确定义的基本概念。直观地说，把一些事物汇集到一起组成一个整体就叫集合，而这些事物就是这个集合的元素或成员。例如：方程x210的实数解集合；26个英文字母的集合；坐标平面上所有点的集合；集合通常用大写的英文字母来标记，例如自然数集合N(在离散数学中认为0也是自然数)，整数集合Z，有理数集合Q，实数集合R，复数集合C等。表示一个集合的方法有两种：列元素法和谓词表示法，前一种方法是列出集合的所有元素，元素之间用逗号隔开，并把它们用花括号括起来。例如A=a，b，c，zZ=0，1，2，都是合法的表示。谓词表示法是用谓词来概括集合中元素的属性，例如集合Bx|xRx210表示方程x210的实数解集。许多集合可以用两种方法来表示，如B也可以写成-1，1。但是有些集合不可以用列元素法表示，如实数集合。 集合的元素是彼此不同的，如果同一个元素在集合中多次出现应该认为是一个元素，如1，1，2，2，31，2，3集合的元素是无序的，如1，2，33，1，2在本书所采用的体系中规定集合的元素都是集合。元素和集合之间的关系是隶属关系，即属于或不属于，属于记作，不属于记作，例如Aa，b，c，d，d这里aA，b，cA，dA，dA，但bA，dA. b和d是A的元素的元素。可以用一种树形图来表示这种隶属关系，该图分层构成，每个层上的结点都表示一个集合，它的儿子就是它的元素。上述集合A的树形图如图6.1所示。图中的a，b，c，d也是集合，由于所讨论的问题与a，b，c，d的元素无关，所以没有列出它们的元素。鉴于集合的元素都是集合这一规定，隶属关系可以看作是处在不同层次上的集合之间的关系。为了体系上的严谨性，我们规定：对任何集合A都有AA。 二集合之间的关系 下面考虑在同一层次上的两个集合之间的关系。定义6.1 设A，B为集合，如果B中的每个元素都是A中的元素，则称B是A的子集合，简称子集。这时也称B被A包含，或A包含B，记作BA。如果B不被A包含，则记作BA。包含的符号化表示为BAx(xBxA) 例如NZQRC，但ZN。显然对任何集合A都有AA。隶属关系和包含关系都是两个集合之间的关系，对于某些集合可以同时成立这两种关系。例如Aa，a和a既有aA，又有aA。前者把它们看成是不同层次上的两个集合，后者把它们看成是同一层次上的两个集合，都是正确的。定义6.2 设A，B为集合，如果AB且BA，则称A与B相等，记作AB。如果A与B不相等，则记作AB。相等的符号化表示为ABABBA 定义6.3 设A，B为集合，如果BA且BA，则称B是A的真子集，记作BA。如果B不是A的真子集，则记作BA。真子集的符号化表示为BABABA 例如NZQRC，但NN。定义6.4 不含任何元素的集合叫做空集，记作。空集可以符号化表示为x|xx。例如x|xRx2+1=0是方程x2+1=0的实数解集，因为该方程无实数解，所以是空集。定理6.1 空集是一切集合的子集。证：任何集合A，由子集定义有Ax(xxA) 右边的蕴涵式因前件假而为真命题，所以A也为真。推论 空集是唯一的。证：假设存在空集1和2，由定理6.1有12 ，21。 根据集合相等的定义，有12。含有n个元素的集合简称n元集，它的含有m(mn)个元素的子集叫做它的m元子集。任给一个n元集，怎样求出它的全部子集呢？举例说明如下。例6.1 A1,2,3，将A的子集分类：0元子集，也就是空集，只有一个：；1元子集，即单元集：1，2，3；2元子集：1,2，1,3，2,3；3元子集：1,2,3。一般地说，对于n元集A，它的0元子集有个，1元子集有个，m元子集有个，n元子集有个。子集总数为+2n 个。 定义6.5 设A为集合，把A的全部子集构成的集合叫做A的幂集，记作P(A)(或PA，2A)。幂集的符号化表示为P(A)x|xA 对于例6.1中的集合A有P(A)，1，2，3，1，2，1，3，2，3，1，2，3 不难看出，若A是n元集，则P(A)有2n个元素。定义6.6 在一个具体问题中，如果所涉及的集合都是某个集合的子集，则称这个集合为全集，记作E。全集是有相对性的，不同的问题有不同的全集，即使是同一个问题也可以取不同的全集。例如在研究平面上直线的相互关系时，可以把整个平面(平面上所有点的集合)取作全集，也可以把整个空间(空间上所有点的集合)取作全集。一般地说，全集取得小一些，问题的描述和处理会简单些。6.2 集合的运算 一集合的基本运算 集合的基本运算有并，交，相对补和对称差。定义6.7 设A，B为集合，A与B的并集AB，交集AB，B对A的相对补集AB分别定义如下：ABx|xAxB ABx|xAxB ABx|xAxB 由定义可以看出，AB是由A或B中的元素构成，AB由A和B中的公共元素构成，AB由属于A但不属于B的元素构成。例如 Aa，b，c，Ba，Cb，d 则有ABa，b，c，ABa，ABb，c，BA，BC 如果两个集合的交集为，则称这两个集合是不相交的。例如B和C是不相交的。 两个集合的并和交运算可以推广成n个集合的并和交：A1A2Anx|xA1xA2xAnA1A2Anx|xA1xA2xAn上述的并和交可以推广成n个集合的并和交：A1A2AnA1A2An并和交运算还可以推广到无穷多个集合的情况：A1A2A1A2 定义6.8 设A，B为集合，A与B的对称差集AB定义为：AB(AB)(BA) 例如Aa，b，c，Bb，d，则ABa，c，d。对称差运算的另一种定义是AB(AB)(AB) 可以证明这两种定义是等价的，证明可留作练习。在给定全集E以后，AE，A的绝对补集A定义如下：定义6.9 AEAx|xExA 因为E是全集，xE是真命题，所以A可以定义为Ax|xA 例如Ea，b，c，d，Aa，b，c，则Ad。以上集合之间的关系和运算可以用文氏图(Venn Diagram)给予形象的描述。文氏图的构造方法如下： 首先画一个大矩形表示全集E(有时为简单起见可将全集省略)，其次在矩形内画一些圆(或任何其它的适当的闭曲线)，用圆的内部表示集合。不同的圆代表不同的集合。如果没有关于集合不交的说明，任何两个圆彼此相交。图中阴影的区域表示新组成的集合。图6.2就是一些文氏图的实例。二有穷计数集 使用文氏图可以很方便地解决有穷集的计数问题。首先根据已知条件把对应的文氏图画出来。一般地说，每一条性质决定一个集合。有多少条性质，就有多少个集合。如果没有特殊说明，任何两个集合都画成相交的，然后将已知集合的元素数填入表示该集合的区域内。通常从n个集合的交集填起，根据计算的结果将数字逐步填入所有的空白区域。如果交集的数字是未知的，可以设为x。根据题目中的条件，列出一次方程或方程组，就可以求得所需要的结果。例6.2 对24名会外语的科技人员进行掌握外语情况的调查。其统计结果如下：会英、日、德和法语的人分别为13，5，10和9人，其中同时会英语和日语的有2人，会英、德和法语中任两种语言的都是4人。已知会日语的人既不懂法语也不懂德语，分别求只会一种语言(英、德、法、日)的人数和会三种语言的人数。解 令A，B，C，D分别表示会英、法、德、日语的人的集合。根据题意画出文氏图如图6.3所示。设同时会三种语言的有x人，只会英、法或德语一种语言的分别为y1，y2和y3人。将x和y1，y2，y3填入图中相应的区域，然后依次填入其它区域的人数。根据已知条件列出方程组如下： 解得x1，y14，y22，y33。例6.3 求1到1000之间(包含1和1000在内)既不能被5和6，也不能被8整除得数有多少个。 解 设Sx|xZ1x1000A x|xSx可被5整除B x|xSx可被6整除C x|xSx可被8整除 用|T|表示有穷集T中得元素数，表示小于等于x的最大整数，lcm(x1,x2,xn)表示x1,x2,xn的最小公倍数，则有 |A|=200|B|=166|C|=125|AB|33|AC|25|BC|41|ABC|8 将这些数字依次填入文氏图，得到图6.4.由图可知，不能被5，6和8整除的数有1000(200+1003367)600个。 三广义交和广义并 以上定义的并和交运算称为初级并和初级交。下面考虑推广的并和交运算，即广义并和广义交。定义6.10 设A为集合，A的元素的元素构成的集合称为A的广义并，记为A。符号化表示为Ax|z(zAxz)。例6.4 设Aa,b,c,a,c,d,a,e,fBaCa,c,d则Aa,b,c,d,e,fBaCac,d根据广义并定义不难证明，若A A1,A2,An，则AA1A2An。类似地可以定义集合的广义交。定义6.11 设A为非空集合，A的所有元素的公共元素构成的集合称为A的广义交，记为A。符号化表示为Ax|z(zAxz) 考虑例6.4中的集合，有Aa，Ba，Cac，d 细心的读者一定会注意到在定义6.11中特别强调了A是非空集合。对于空集可以进行广义并，即。但空集不可以进行广义交，因为不是集合，在集合论中是没有意义的。和广义并类似，若AA1,A2,An，则AA1A2An。在后面的叙述中，若只说并或交，则这都是指集合的初级并或初级交；如果在并或交前边冠以“广义”两个字，则指集合的广义并或广义交。为了使得集合表达式更为简洁，我们对集合运算的优先顺序做如下规定：称广义并，广义交，幂集，绝对补运算为一类运算，并，交，相对补，对称差运算为二类运算。一类运算优先于二类运算。一类运算之间由右向左顺序进行。二类运算之间由括号决定先后顺序。例如下面的集合公式：AB，P(A)，P(A)B，(AB)都是合理的公式。例6.5 设 Aa,a,b计算A，A和A(AA)。解 Aa,b Aa Aab Aa Aab Aa A(AA)(ab)(ab)a)(ab)(ba)b所以Aab，Aa，A(AA)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)零律 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)我们只选证其中的一部分。例6.9 证明等式6.27，即ABAB。证对于任意的x，xABxAxB xAxB xAB所以ABAB。等式6.27把相对补运算转换成交运算，这在证明有关相对补的恒等式中是很有用的。例6.10 证明(AB)BAB证 (AB)B(AB)B(AB)(BB)(AB)EAB二证明技巧 证明技巧一除了以上算律以外，还有一些关于集合运算性质的重要结果。 例如：ABA，ABB(6.24)AAB，BAB(6.25)ABA(6.26)ABAB (6.27)我们只选证其中的一部分。例6.9 证明等式6.27，即ABAB。证对于任意的x，xABxAxB xAxB xAB所以ABAB。等式6.27把相对补运算转换成交运算，这在证明有关相对补的恒等式中是很有用的。例6.10 证明(AB)BAB证 (AB)B(AB)B(AB)(BB)(AB)EAB证明技巧二 ABBABAAB (6.28)例6.11 证明命题6.28是真命题。证先证ABBAB对于任意的x，xAxAxBxABxB(因为ABB)所以AB。再证ABABA。显然有ABA，下面证AAB。对于任意的x，xAxAxAxAxB(因为AB)xAB由集合相等的定义有ABA。然后证ABAAB。ABAB(AB)B(因为ABA)A(BB)A最后证ABABB。由例6.10及AB有ABB(AB)BB 式6.28给出了AB的另外三种等价的定义，这不仅为证明两个集合之间的包含关系提供了新方法，同时也可以用于集合公式的化简。例6.12 化简(ABC)(AB)(A(BC)A)。解因为ABABC，AA(BC)，由式6.28有(ABC)(AB)(A(BC)A)(AB)ABA证明技巧三ABBA (6.29)(AB)CA(BC) (6.30)AA (6.31)AA (6.32)ABACBC (6.33)式6.296.33是关于对称差运算的算律，前四条可通过对称差的定义加以证明，最后一条叫做消去律，它的证明给在下面。例6.13 已知ABAC，证明BC。证 已知ABAC，所以有 A(AB)A(AC)(AA)B(AA)C (由式6.30)BC (由式6.32)BC (由式6.29)BC (由式6.31) 主要内容 1. 集合，相等，（真）包含，子集，空集，全集，幂集2. 交，并，（相对和绝对）补，对称差，广义交，广义并3. 文氏图，有穷集计数问题4. 集合恒等式（等幂律，交换律，结合律，分配律，德摩根律，吸收律，零律，同一律，排中律，矛盾律，余补律，双重否定律，补交转换律等） 学习要求 1. 熟练掌握集合的子集、相等、空集、全集、幂集等概念及其符号化表示2. 熟练掌握集合的交、并、（相对和绝对）补、对称差、广义交、广义并的定义及其性质3. 掌握集合的文氏图的画法及利用文氏图解决有限集的计数问题的方法4. 牢记基本的集合恒等式（等幂律、交换律、结合律、分配律、德摩根律、收律、零律、同一律、排中律、矛盾律、余补律、双重否定律、补交转换律）5. 准确地用逻辑演算或利用已知的集合恒等式或包含式证明新的等式或包含式典型习题 1. 证明 A-B=A AB= 。2. 证明 A-B= AB AB=B AB=A 。3. 设A,B为集合，试确定下列各式成立的充分必要条件：4. 判断下列命题是否为真。5. 设A=,B=PP(A)，问下列各题是否为真。6. 判断下列命题的真假。7. 在下列各题中，如果命题为真，请给出证明；如果命题为假，请给出反例。8. 证明(A-B)-C = (A-C)-(B-C)。9. 对60个学生参加课外活动的情况进行调查。结果发现，25人参加物理小组，26人参加化学小组，26人参加生物小组。9人既参加物理小组又参加生物小组，11人既参加物理小组又参加化学小组，8人既参加化学小组又参加生物小组。8人什么小组也没参加，回答下列各问题： 内容与要求典型习题1.证明 A-B=A AB= 。提示 参看基本集合恒等式，集合恒等式证明技巧。答案 必要性。假设AB，必有x属于AB，则x属于A同时属于B，即x属于A但是x不属于A-B。与A-B=A矛盾。 充分性。显然A-BA。任取xA，则如果x属于B，则x属于AB，与AB=矛盾。因此x必不属于B，即x属于A-B。从而证明了AA-B。命题得证。分析 参看答案。提示答案分析返回上一道下一道2.证明 A-B= AB AB=B AB=A 。提示 参看基本集合恒等式，集合恒等式证明技巧。答案 证明过程如下： A-B= AB AB=B AB=A A-B= 。 假设AB，即存在x属于A但不属于B，则x属于A-B，与A-B=矛盾。 显然BAB，反之，任取x， xAB xAxB xBxB xB因此ABB。命题得证。 显然ABA，任取x， xA xAB xB 因此xA xAxB xAB。从而有AAB。命题得证。 假设存在xA-B，xAxB，即xAxAB，与矛盾。分析 参看答案。提示答案分析返回上一道下一道3.设A,B为集合，试确定下列各式成立的充分必要条件：（1）A-B=B（2）A-B=B-A（3）AB=AB（4）AB=A提示 参看集合的基本运算，包含，文氏图。答案 (1) A=B=; (2) A=B; (3) A=B; (4) B=.分析 与前面求解的问题不同，找出集合等式成立的充分必要条件的问题是比较灵活的应用问题。求解这类问题可能用到集合的算律、不同集合之间的包含关系、甚至文氏图等。具体求解过程可以说明如下。 （1）由A-B=B得 (AB)B = BB化简得B=。再将这个结果代入已知等式得A=。从而得到必要条件A=B=。 下面验证充分性。如果A=B=成立，则A-B =B也成立。 （2）充分性是显然的，下面验证必要性。由A-B = B-A得 (A-B)A = (B-A)A从而有A=AB，即AB。同理可证BA。 （3）充分性是显然的，下面验证必要性。由AB=AB得 A(AB) = A(AB)化简得 A=AB，从而有AB。类似可以证明BA。 （4）充分性是显然的，下面验证必要性。由AB=A得 A(AB) = AA根据结合律有 (AA)B = AA即 B=，就是B=。提示答案分析返回上一道下一道习题 1.选择适当的谓词表示下列集合：答案(1)小于5的非负整数(2)奇整数集合(3)10的整倍数的集合2.用列元素法表示下列集合：答案(1)S1x|x是十进制的数字(2)S2x|x2x5(3)S3x|xxZ3x3(5)S5|x，yZ0x2-1y03.设F表示一年级大学生的集合，S表示二年级大学生的集合，M表示数学专业学生的集合，R表示计算机专业学生的集合，T表示听离散数学课学生的集合，G表示星期一晚上参加音乐会的学生的集合，H表示星期一晚上很迟才睡觉的学生的集合。问下列各句子所对应的集合表达式分别是什么？请从备选的答案中挑出来。答案 (1)所有计算机专业二年级的学生在学离散数学课。(2)这些且只有这些学离散数学课的学生或者星期一晚上去听音乐会的学生在星期一晚上很迟才睡觉。(3)听离散数学课的学生都没参加星期一晚上的音乐会。(4)这个音乐会只有大学一、二年级的学生参加。(5)除去数学专业和计算机专业以外的二年级学生都去参加了音乐会。备选答案：TGH GHT SRTHGT TG FSGGFS S-(RM)G GS-(RM)4.确定下列命题是否为真：答案(1)(2)(3)(4)(5)a，ba，b，c，a，b，c(6)a，ba，b，c，a，b (7)a，ba，b，a，b(8)a，ba，b，a，b5.设S11，2，3，8，9，S22，4，6，8，S31，3，5，7，9，S43，4，5，S53，5.确定在以下条件下X可能与S1，S5中哪个集合相等？答案(1)若XS5(2)若XS4但XS2(3)XS1且XS3(4)若XS3(5)若XS3，且XS16.求下列集合的幂集：答案(1)a，b，c(2)1，2，3(3)(4)，(5)1，2，2，1，1，2，1，1，2(6)，2，27.设E1，2，3，4，5，6，A1，4，B1，2，5，C2，4。求下列集合：答案(1)AB(2)(AB)C(3)(AB)(4)P(A)P(B)(5)P(A)P(B)8.设A，B，C，D是Z的子集，其中 A1，2，7，8 Bx2|x250xZ Cx|xZ0x30x可以被3整除 Dx|x2kkZ0k6用列元素法表示下列集合：答案(1)ABCD(2)ABCD(3)B(AC)(4)(AB)D 9.化简下列集合表达式：答案(1)(AB)B)(AB)(2)(ABC)(BC)A(3)(B(AC)(ABC)(4)(AB)(C(AB)10.画出下列集合的文氏图：答案(1)AB(2)(A(BC)(BC)A)(3)A(BC)11.用公式表示图6.5中阴影部分的集合。答案 12.对60个人的调查表明有25人阅读每周新闻杂志，26人阅读时代杂志，