章集合论 第 数学历史上出现过三次危机: 第一次数学危机:发现了“无理数”。毕达哥拉斯是公元前五世纪古希腊的著名数学 家与哲学家,创立了毕达哥拉斯学派,提出了著名命题“万物皆数”,该数均可表示成整数 或整数之比。毕达哥拉斯的一个弟子发现边长为1的正方形的对角线是不能用任何比例 来表示的,对于毕氏学派来说,这是天大的罪过,结果他被扔进海里喂了鲨鱼。 第二次数学危机:关于微积分。在牛顿和莱布尼茨发现微积分的年代里,总是有人 跟他们作对,其中有一位爱尔兰的大主教贝克莱就讥讽牛顿的无穷小量是“已死量的幽 灵”。经过柯西(微积分收官人)用极限的方法定义了无穷小量,微积分理论得以发展和完 善,从而使数学大厦变得更加辉煌美丽。 第三次数学危机:康托尔创立了著名的集合论。在集合论刚产生时,曾遭到许多人 的猛烈攻击,但不久这一开创性成果就为广大数学家所接受了,并且获得广泛而高度的赞 誉。“一切数学成果可建立在集合论基础上”这一发现使数学家们为之陶醉。1903 年,一 个震惊数学界的消息传出:集合论是有漏洞的! 这就是英国数学家罗素提出的著名的罗 素悖论。危机产生后,数学家纷纷提出自己的解决方案,人们希望能够对康托尔的集合论 进行改造。1908 年,策梅洛在自己这一原则基础上提出第一个公理化集合论体系,后来 经其他数学家改进,称为ZF 系统。这一公理化集合系统很大程度上弥补了康托尔朴素 集合论的缺陷。除ZF 系统外,集合论的公理系统还有多种,如冯·诺依曼等人提出的 NBG 系统等。公理化集合系统成功排除了集合论中出现的悖论。 3.集合与表示 1 前两章我们学习了命题公式及谓词公式,其中谓词公式是对命题公式的一个量上的 约束,在约束时,提供了论域。本章开始,我们学习如何限定这个论域,或者称之为集合。 下面我们给出集合的定义: 定义3-1(集合) 若一类互异事物具有某一组规定的属性A,那么这类事物称之为 一个具有属性 A 的集合S,记作S={|e,其中每一个满足属性的 e 称之为集合 元素,简单谓词公式V(A) eV(A)}, e,表示的是 e 具有属性A。 定义3-1中需要注意的是 A 是一组规定的属性,它是将至少一个属性可以通过合取 或者析取形成的表达式,或者就是一个属性。同时也发现集合的定义中并没有给定元素 的顺序,因而集合内元素是无序的,而且,定义中规定元素必须互异,所以集合中的元素是 唯一的。 如果一个集合的元素数量有限,我们称它为有限集合,否则称为无限集合。集合可以 用两种方式表示:枚举方式和属性方式。定义3-1给的就是属性方式。当然,如果集合 是有限集合,就可以使用枚举方式①。例如,我们可以把一年中的月份枚举表示成{1,2, 3,4,5,6,7,8,9,10,11,12}或者属性表示成{m|m∈Z+∧1≤m≤12}, 具体选择使用哪种 表示方法看使用需要。 日常生活中的集合与数学中定义的集合在理解上有一定的细微差别,比如中学阶段 学习的:自然数全部是正整数或表示成N={x|x∈Z+}, 这里包含了同时具有正负的零。 但是我们有时把这样的一类看似没有任何同一属性的也称之为集合,例如:{ a,1,±0, .,@}这个集合被称之为目标选择集合,即其中的事物均具有被选择进这个集合中的属 性。因而定义3-1也可以应用到这个集合上,只是属性变成了随意被选择的。当然集合 内还可以嵌套集合,例如{1,2,{3,4}}, 还有一个集合是比较特别的,那就是空集,记作., 我们给出它的定义: 定义3-2(空集) 若集合内剔除所有元素得到的集合称为空集,记作.= {}。 由于.是一个集合而不是一个元素,因而对于集合内嵌套空集{.}≠.,这是因为 {.}相当于{{}}。我们可以把空集想象成里面有一个属于空集的特殊元素,这个特殊元 素是组成集合的基本元素,它无法剔除,我们把它称为集合基底。 下面我们定义集合的相等与从属关系: 定义3-3(集合相等) 如果两个集合A, B 相等,当且仅当A, B 里的元素全部相等, 记作A=B;若两个集合中存在不同的元素,那么称这两个集合不等,记作A≠B。 定义3-4(元素从属) 若 x 是集合 S 里的任一元素,那么称元素 x 属于集合S,记作 x∈S,读作 x 属于集合S,或读作 x 取自集合S;若 x 不属于集合S,那么记作x.S,读 作 x 不属于集合S,或读作 x 不是取自集合S。 定义3-5(集合从属) 若集合 A 的任意元素 x 也是集合 B 的元素,那么称集合 A 为 集合 B 的子集,记作A.B,读作集合 A 包含于集合B,或读作集合 B 包含集合A,或者 集合 A 是集合 B 的子集;若此时A≠ B 且A. B 那么称集合 A 是集合 B 的真子集,记作 A.B。 集合还有这样的性质: (传递性)若集合A,B,C,它们满足A.B,B. C 那么A.C。 (自反性)集合 A 对其自身有A.A。 定理3-1(空集从属) 对于任意一个集合A,空集..A。 对于空集从属的定理3-1,我们可以从空集的定义中看出,对于一个集合 A 可以剔除 其中的所有元素得到空集,自然我们可以认为空集中那个不存在的集合基底元素既属于 空集也属于任何其他集合。 ① 枚举是指将集合中的元素一个个列举出来。 38离散数学(第 2 版) 第3 章 集合论 定理3-2(集合等价的充要条件) 若两个集合A ,B 相等,当且仅当A .B∧B.A 。 定义3-6(全集) 若给定一组限定属性A ,由所有满足这组属性的元素所组成的集 合称为条件A 下的全集E,简称全集E,或论域E。 需要注意的是,全集的定义与集合的定义有相似之处,区别在于定义3-6将所有满足 条件的元素都包含在集合内,而定义3-1只是指出满足条件的元素组成的集合。 定义3-7(幂集) 给定集合S,由S 的所有子集为元素组成的集合称为集合S 的幂 集,记作P(S)。 例如,集合S={a,b,c},那么它的幂集: P(S)={.,{a},{b},{c},{a,b},{b,c},{c,a},{a,b,c}} 这里需要关注两点:第一,空集符号.与其他集合性质一样是一个集合,且为幂集的 一个元素;第二,在实际生成幂集时可以按照先选一个,再选两个,等等依次选择。 定理3-3(幂集中元素个数) 有限集合A 包含n 个元素,那么幂集P (A )中包含的 元素个数为2n 。 证明 根据幂集的定义,从集合A 的n 个元素中挑选出k 个不同的元素组成一个幂 集中的元素,显然空集单独一个,那么从A 挑选出k 个不同元素共 Ckn =n(n-1)(n-2)…(n-k+1) k! 种不同结果,那么幂集的元素个数可以表示成 N =1+C1n +C2n + … +Ckn + … +Cnn =Σn k=0Ckn 根据二项式定理: (x +y)n =Σn k=0Ck nxkyn-k 我们令x=y=1,那么得到 N =(1+1)n =2n 证毕。 3.2 集合运算 作为一个集合,如果给定一个研究域,或者给定一个论域,可以在这个论域内进行有 限的加减等集合运算。这种集合的运算是按照一定的规则进行的,在介绍集合运算前,先 介绍文氏图①。 文氏图是在平面图形上的论域内对所研究的集合进行标识,其中阴影部分是所需要 的区域,每个集合用闭曲线表示,独立元素用点表示。例如图3-1所示,阴影部分为所研 39 ① J.Venn(1834—1923)英国逻辑学家,于1881年在《符号逻辑》一书中,首先使用相交区域的图解来说明类与 类之间的关系。后来人们以他的名字命名这种用图形表示集合间的关系和集合的基本运算的方法,称为文氏图(Venn Diagram)。 究的部分,这表示了一个交集,其中E是研究的论域,集 合A,B的公共部分。一般情况下论域 E 不需要特别指 明,默认出现的集合都满足随机选择属性的要求。 下面开始定义集合的基本运算: 定义3-8(交集) E 内给定两个集合A,B,那么由 A, B 共同元素组成的集合称之为A, B 的交集,记作 图3-1 集合的交A∩B①,属性定义为S=A∩B={x|x∈A∧x∈B}。 文氏图如图3-1所示,其中 C 就是A, B 的交集。 -a,3,d,b,=, 【例31】计算集合的交集S,其中A={b,6,0},B={h,s,0}。 解选择公共的元素, b, 那么S=A∩B={0}。 【例3-2】求证,当A. B 时,有A∩S.B∩S。 证明由于 S 未给定,我们按照默认, S 与A, B 在同一个选择属性集合里,那么, 元素x∈A,必然由A.B.x∈B,那么也必然存在x∈ A ∩S,这个式子等价于(.x)(设) (x∈A∧x∈S), 可以得到.x(x∈S), 由x∈ B 与.x(x∈S)共同得到x∈B∩S,那么 可以根据集合从属的定义得到A∩S.B∩S。 证毕 。 可以利用前面所学得到交的这些运算性质 : (1)A.B.A∩B= A (2)A∩B=B∩ A (3)(A∩B)∩C=A∩(B∩C) (4)A∩B.A,A∩B. B 当有很多个集合交时,可以采用一种符号来表示。当集合 P 表 示 P=A1∩A2∩…∩An 那么可以使用符号表示 P=∩(n) Ai = 定义3-9(并集)E内给定两个集合A,B(1) (i) ,那么由A, B 的全部元素组成的集合称之 为A, B 的并集或A, B 的和,记作 A ∪B,属性定义为 S=A∪B={x|x∈A∨x∈B}。 文氏图如图3-2所示,其中公共阴影就是A, B 的 并集。 【例3-计算集合的并集S, ={b,6, 3】其中Aa,3, d,0},B={h,s,0}。 b,=, 解选择全部的元素,并去除重复的,那么S=A∪B= 图3-2 集合的并 {a,b,6,0,=, 3,d,h,s,} 。 并的运算性质 : (1)A.B.A∪B= B (2)A∪B=B∪ A B。 ① 部分计算机专业程序设计教材和概率论上通常将A∩B.AB,A∪B.A+B,A-B.A.. 40离散数学(第 2 版) (3)(A∪B)∪C=A∪(B∪C) (4)A.A∪B,B.A∪ B 当有很多个集合并时,我们可以采用一种符号来表示。当集合 P 表 示 P=A1∪A2∪…∪An 那么我们可以使用符号表示 P=∪(n) Ai =1 定理3-4(集合的分配律) 设E下的三个(i) 集合A,B,C,那么 有 A∪(B∩C)=(A∪B)∩(A∪C) A∩(B∪C)=(A∩B)∪(A∩C) 我们只证其中一个,另外一个可以自行推导。 证明设x∈A∪(B∩C), 那么x∈A∨x∈B∩C.x∈A∨(x∈B∧x∈C)。 根据命题逻辑的分配律有 x∈A∪(B∩C).(x∈A∨x∈B)∧(x∈A∨x∈C) .x∈(A∨B)∧x∈(A∨C) 证毕。 .x∈(A∪B)∩(A∪C) 同样我们还可以得 到 (1)A∪(A∩B)= A (2)A∩(A∪B)= A 定理3-5(从属判定) 若要得到A.B,当且仅当A∪B= B 或A∩B=A。 定义3-10(相对补集) 设 E 下的任意集合A,B,将所有属于集合 A 但不属于集合 B 的元素组成的新的集合 S 称为 B 对于 A 的相对补集,或 B 对于 A 的差集,记作S=A-B, 属性定义为S={x|x∈A∧x.B}。 文氏图如图3-3所示,其中公共阴影就是A-B。 定义3-11(绝对补集) 设 E 下的任意集合A,将所 有不属于集合 A 但属于集合 E 的元素组成的新的集合 称为 A 的绝对补集,记作..属性定义为..{ A∧x∈E}。 A, A =x|x. 显然定义3-10 与定义3-11 的差别在于范围的选 取,相对差相对于A,绝对补相对于全集E。图3-3 集合的相对差 根据它的定义,我们可以得到这些补集公式: 1)..3)A∪..4)A∩.. ( A = A (2).=..( A = E ( EA =. (5)A∪B=..(6)A∩B=..(B=A∩.. A∩BA ∪ B 7)A- B (8)A-B=A-(A∩B) (9)A∩(B-C)=A∩B-A∩ C -6( B, A, 定理3补的逆从属) 若 E 下任意两个集合A,且A.B,那么B.....且还有 (B-A)∪A=B。 证明第一个结论部分。设x∈A,已知A.B,那么x∈B,当x. B 必然在 A 中也 找不到x,或x.A, B 中存在x∈..则在范围更大的 A ,也能有 那么显然在补集较小的..B, .. 第 3 章集合论 x∈.. A,因而得证A.B 。 第二个结论部分 。 B∩.. .. (B-A)∪A.(A)∪A.(B∪A)∩( A ∪A).B∪ A 由于A.B,所以B∪A=B。 证毕。 定义3-12(集合的对称差或异或) E 下任意两个集合A,B,那么A, B 的对称差为 集合S,其中 S 中的元素或属于A,或属于B,但不同时 属于 A 和B,记作 S = A ..B,属性定义为 A .. B = {x|x∈A..x∈B}。 文氏图如图3-4所示,其中阴影部分就是A..B。 对称差有很多可以推导的公式: 1)A..B=B.. A 2)A...= A 3)A..A=. 图3-4 集合的对称差 ( A∩.. ( .. ( (4)A..B=(B)∪(A∩B) (5)(A..B)..C=A..(B..C) (对称差奇偶步差应用)对称差还有一个在计算机作图软件上常用的功能,从直观上 来说,如果一个共同的区域被重叠奇数次,那么最终的集合包含该区域,如果是重叠偶数 次,那么最终的集合不包含该区域,下面用图3-5说明。 图3-5 对称差的奇偶步差应用 【例3-4】证明表达式A∩(B..C)=(A∩B)..(A∩C)成立。 证明 (A∩B)..(A∩C)=((A∩B)∩(A∩C))∪((A∩B)∩(A∩C)) .... A ∪.. =((A∩B)∩( A ∪C))∪((B)∩(A∩C)) A∩B∩..A∩C∩..A∩C∩.. =((A)∪(A∩B∩C))∪((A)∪(B)) A∩C∩..C∩..B..C) 证毕 = 。 (A∩B∩C)∪(B)=A∩((B∩C)∪(B))=A∩( 在集合的运算中还有一类特殊的集合,它们的元素均为一对有序序列,通常这个序列 中包含两个元素,例如表示坐标的,<3,4>, 它们是有序的,调换前后顺序会表达不 同的意义,所以我们通常把有两个量的序列称之为序偶,或者序对。 定义3-13(序偶) 当用两个量x, y 来表示有序关系时,我们把这种关系称之为序 偶,记作其中 x 称之为第一元素, x,, y 称之为第二元素。 42离散数学(第 2 版) 定义3-序偶相等) x,与 当且仅当x=y=v。 14( 若序偶 u,相等, u, 序偶描述了两个量之间的关系,我们现在把它进行扩展。 定义3- n 元组) x2,…,将最后一个元素作为第二元素, 15(若对有序序列x1,xn 将 剩余的有序序列作为第一元素,这样再对第一元素重复划分得到的序偶称之为 n 元组。 记作<或简写为, 称 <…x3>xn-1>xn , x1,xn 其中第 i 个元素xi 之为 n 元组的第 i 个坐标, n 元组本身称之为 n 维坐标。 举例来说,一个三元组可以表示成或<,x3>,四元组可以表示成 ,x4> ,,由于我们限定了第一元素和 x1,x2,x4> ,或 第二元素的大小,所以不是三元组。 x3> 对于二元组的序偶,我们称之为二维坐标,由于二维坐标的序偶的第一元素 可以来自任意给定的集合A,第二元素来自集合B,这样就可以定义一个概念。 定义3-16(笛卡儿积①) 给定任意两个集合 A 和B,若序偶的第一元素来自集合A, 第二元素来自集合B,将所有满足条件的序偶组成的集合 S 称之为集合 A 和 B 的笛卡儿 积或直积,记作S=A×B,x∈A∧y∈B}。 属性定义为A×B={x,| 【例3-若A={b},B={2,求A×B,B×A,A×A,(A×B)∩(B×A)。 5】a,1,3}, 解笛卡儿积计算时,直接选定其中一个,然后从第二个集合中依次挑选组成 A×B={<1><2><3><1>,b,,b,} a,,a,,a,,b,<2><3> 1,,1,,2,,3,,3, B×A={,2,} A×A={,b,} a,,a,,b, 显然(A×B)∩(B×A)=. 。 我们约定若A=. 或B=.,那么A×B=.,另外,我们还可以知 道 (A×B)x∈A∧y∈B∧z∈C} A×(B×C)<|x∈A∧y∈B∧z∈C} ={x,y,> 显然(A×B)×C≠A×(B×C), 因为后一项并不是序偶。 (直积的几个等式)设任意三个集合A,B,C,那么存在 (1)A×(B∪C)=(A×B)∪(A×C)(2)A×(B∩C)=(A×B)∩(A×C) (3)(A∪B)×C=(A×C)∪(B×C)(4)(A∩B)×C=(A×C)∩(B×C) 我们对其中的第三个进行证明,其余读者可以参照证明。 证明 ∈(A(若) ∪B)×C. x ∈( x ∈ A ∨ x ∈B)∧( A ∪B)∧ y ∈C.( y ∈C) .( x ∈ A ∧ y ∈C)∨( x ∈ B ∧ y ∈C) .∈ A ×C ∨∈ B ×C y>∈(( B ×C)) 证毕。 .∈( .(x∈A∧y∈C).(x∈B∧y∈C) .(A×C).(B×C) (2)证明反过程,若已知y∈C,C≠.,由(A×C).(B×C)得 到 A×C).B×C) .(x∈A∧y∈C).(x∈B∧y∈C) .[(x∈A).(x∈B)]∧y∈ C .[(x∈A).(x∈B)]∧T .A. B 证毕。 其中第三步中由于已知y∈C,C≠. 必定为真,那么就转化为T,定理的第二部分可 以用同样的办法。 定理3-8(直积的对应从属) 设四个非空集合A,B,C,D,那么 A ×B.C×D 的充 要条件是A.C,B.D。 证明充分性:若A×B.C×D,那么 (x∈A∧y∈B) .A×B).C×D) .(x∈C∧y∈D) 由对应关系可以知道A. C 且B.D 。 必要性:若A.C,B.D,那 么 A×B) .(x∈A∧y∈B).(x∈C∧y∈D) .C×D) .A×B.C×D 证毕 。 3.集合的计数与划分 3 集合的运算可以用在有限元素集合的计数上,计数问题常常运用在概率统计和一些 小规模的问题上,下面我们做具体介绍。 44离散数学(第 2 版) 定义3-17(集合的规模或基数) 我们将一个集合 A 所包含的元素个数 n 称为集合 的基数,或称为势,记作|A|= n 或card(A)=n。 显然根据这个定义我们可以得到集合规模的一些关系: (1)|A∪B|≤|A|+|B| (2)|A∩B|≤min(|A|,|B|) (3)|A-B|≥|A|-|B| (4)|A..B|=|A|+|B|-2|A∩B| 定理39(包含排斥) 若有限集合A1,A2,…,,其中的元素个数分别为|A1|, |A2|,…, - 那么 An n≥2, |An|, n …=(0Σ 1Σ1≤i,<0,1,2>,<1,0,1>,<1, 0,2> }。( ) 3- 2 单选题。 1.设A=.,B={.,{.}}, 则B- A 是( ) 。 A.{{.}} B.{.,{.}} C.{.} D. . 2.下列是假命题的有( )。 a,{{a}} C.a}.{{{a}} a}} a,{{a}} a,{ A.a∈{B.a}∈{D.a}.{ 3.下列结果正确的是( ) 。 A.(A∪B)-A= B B.(A∩B)-A= . C.(A-B)∪B= A D..∪{.}= . 4.下列结论正确的是( )。 A.若A∪B=A∪C,则B= C B.若A∪B.A∩B,则B= A C.若A∩B=A∩C,则B= C D.若A. B 且C.D,则A∩C.B∩ D 5.下列结论正确的是( ) 。 A..∩{.}={.} B..∪{.}= . C.(A∩B)-A=. D.A..A= A 6.设A,B, C 是集合,则下述论断正确的是( )。 A.若A.B,B∈C,则A∈ C B.若A.B,B∈C,则A. C C.若A∈B,B.C,则A∈ C D.若A∈B,B.C,则A. C 7.幂集P(P(P(.))) 为( ) 。 A.{{.},{.,{.}}} B.{.,{.,{.}},{.} } C.{.,{.,{.}},{{.}},{.}} D.{.,{.,{.}} } 8.设 A ( 、B、C、 D 是任意的集合。以下说法正确的是( ) 。 A.A∩B)×(C∩D)=(A×C)∩(B×D) B.(A∪B)×(C∪D)=(A×C)∪(B×D) C.(A-B)×(C-D)=(A×C)-(B×D) D.(A..B)×(C..D)=(A×C)..(B×D) 3- 3 不定项选择。 1.设A={.},B=P(P(A)), 下列() 表达式成立。 {{.}}.BA... B B.{.}. B C.{.}∈ B D. E.{{.}}∈ B 2.下列式子正确的是( ) 。 A.(A-B)-C=A-(B∪C) 05 离散数学(第 2 版) B.A-B=B- A C.(A..B)∩C=(A∩C)..(B∩C) D.A∩(B..C)=(A∩B)..(A∩C) E.A∪(B..C)=(A∪B)..(A∪C) 3.设A1=.,A2={.},A3=P({.}),A4=P(.), 以下命题为真的是( )。 A.A2∈A4B.A1.A3C.A4.A2D.A4∈A3 E.A2∈A3 4.A,B, C 是三个集合,则下列推理不正确有( )。 A.若A.B,B.C,则A. C B.若A.B,B.C,则A∈ C C.若A.B,B∈C,则A∈ C D.若A∈B,B.C,则A. C E.若A.B,B∈ C 则A. C 5.以下说法正确的有( ) 。 A.(A-B)-C=A-(B∪C) B.A-(B∪C)=(A-B)∪ C C.A∩(B..C)=(A∩B)..(A∩C) D.(A∩B)×(C∩D)=(A×C)∩(B×D) E.(A..B)×C=(A×C)..(B×C) 6.以下说法正确的有( )。 A.若A∈ B 且B.C,则A. C B.若A. B 且B∈C,则A. C C.若A. B 且B∈C,则A. C D.A∩(B..C)=(A∩B)..(A∩C) E.(A-B)×C=(A×C)-(B×C) 3- 4 解答题。 1.在30 个学生中有18 个爱好音乐,12 个爱好美术,15 个爱好体育,10 个既爱好音 乐又爱好体育,8个既爱好美术又爱好体育,11 个既爱好音乐又爱好美术,但有6个学生 这三种爱好都没有,试求这三种爱好都有的人数。 2.某年级共有200 名学生,喜欢打篮球的有134 人,喜欢打排球的有101 人,喜欢打 乒乓球的有90 人,篮球、乒乓球都不喜欢的23 人,篮球、排球都喜欢的54 人,喜欢排球但 不喜欢乒乓球的有48 人,三样都喜欢的有12 人。 求:(1)三样运动都不喜欢的有多少人? (2)只喜欢一项运动的有多少人 ? 3- 5 设A,B, C 是任意集合,利用集合恒等式,证明下列结论 : 1.A∪B=A- B 当且仅当B=. 。 2.A∩B=A- B 当且仅当A=. 。 3.A∪B=A∩ B 当且仅当A=B。 第 3 章集合论 15 4.A-B=B- A 当且仅当A=B。 5.P(A)∩P(B)=P(A∩B)。 6.P(A)∪P(B).P(A∪B)。 7.(A∩B)∪C=A∩(B∪C)当且仅当C.A。 8.若A∪B=A∪ C 且A∩B=A∩C,则B=C。 3- 6 设A,B,C, D 为任意集合,判断下列结论是否成立? 成立的给出证明,不成立 的说明理由或者举出反例。 1.如果A×B=A×C,那么B=C。 2.A-(B×C)=(A-B)×(A-C)。 3.如果A= B 且C=D,那么A×C=B×D。 4.存在集合A,使得A.A×A。 5.(A∪B)×(C∪D)=(A×C)∪(B×D)。 6.(A-B)×(C-D)=(A×C)-(B×D)。 7.若A∪B=A∪C,则B=C。 8.若A∩B=A∩C,则B=C。 25 离散数学(第 2 版)