离散数学第3章(1-6)(新教材).pptVIP

第二篇 集合论基础 第三章 集合与关系 第一节 集合的基本概念 一般教科书中都把若干有某种共同性质、彼此 不同的东西(元素)放在一起就构成一个集合.实际上 没有共同性质的若干个对象放在一起也可认为作成 一个集合。集合是数学中不能精确定义的少数概念 之一.若元素a属于集合A, 记作aA, 若元素a不属于 集合A, 记作aA. (注)为了避免出现悖论,我们应该避免使用诸如“所 有的集合组成的集合”这一类的术语. 例1.下面是集合的几个例子: (1)S=1,2,3,4; (2)T=(xR)(x4-10x3+35x2-50x+24=0) (3)W=z|(zZ)(x,y,u,vZ)(x2+y2+u2+v2=z) 集合可以用列举法和描述法这两种方法加以表达.列 举法通常适用于元素个数较少的有限集合,而描述法则通 常适用于元素个数较多以及无限的集合. 集合具有如下四个重要的性质: (i)集合元素的确定性:即对具体一个集合的元素而 言, 一个元素或在此集合中, 或不在此集合中, 二 者必居其一; (ii)集合元素的无重复性:即集合的元素彼此不同, 没有重复的元素在同一个集合中重复出现; (iii)集合元素的无序性:例如我们认为1, 2=2, 1; (iv)集合元素的抽象性:集合中的元素不必是具体的事物, 也可以是抽象的对象,甚至集合也可以作为集合的元素. 定义1.1(集合相等的定义): 两个集合A和B是相等的 , 当且仅当A和B有相同的元素, 记作A=B; 集合A与 集合B不相等,记作AB; 例如上面例1中的(1)和(2)中的两个集合S和T, 不难 看出它们实际上是两个相同的集合,也即有S=T. 再看上面例1中的(3),根据数论中著名的 Lagrange四平方定理(该定理的结论是:每个自然数 都可以表示成四个整数的平方数之和)可以看出:这 个例子中的集合W与全体自然数组成的集合N也是 相等的集合。 常用的以数作为元素的集合及其符号表示: N自然数作成的集合, Z整数作成的集合, Z+正整数作成的集合, Q有理数作成的集合, R实数作成的集合, C复数作成的集合; kZk的整数倍组成的集合, Zk0,1,k-1,整数模k的剩余类作成的集 合。 定义1.2(有限集和无限集) 如果一个集合中只有限多个元素,则称之为一个 有限集;反之则称之为一个无限集. 第二节 子集和幂集 定义2.1(子集和真子集)。 设A、B是任意两个集合, 任取 xA, 都有xB, 则称A是B的子集, 或A包含在B内, 记作 AB, 或BA.即如果有AB,但AB,也就是说,至少存在一 个元素bB,使得bA,则称A是B的一个真子集,记为A B 或者BA. 根据上述定义不难看出:任何一个集合A都有两个特殊的子 集合,一是空集,用符号表示;另一个是集合A自身.它们称 为集合A的平凡子集. 对于给定的非空集合A,如果除了这两个平凡的子集合之外 , 它还有其他的子集合,则称之为集合A的非平凡子集. 下面的图(称为Venn图)表达了集合B与其子集合A 之间的关系: 例如, A=1, 2, B=1, 2, 3, 则AB,且也有A B. B A 例如, 设 Z是整数集合, 2Z是偶数集合, 则2ZZ; 1, 2, 3a, 1, 2, 3, 1, a, a, 1, 2, 3a, 1, 2, 3, 1, a, 但, 1, 2, 3a, 1, 2, 3, 1, a, 注意“”与“” 的意义完全不同. “”显然有性质: (1) AA; 自反性 (2) AB且BC, 则AC; 传递性 (注)在每个问题中如果所有出现的集合都是某一集 合的子集, 称此集合为该问题中的全集, 记作E;全集 是一个相对唯一确定的集合, 根据问题的不同, 我 们有时需要取不同的集合作为全集。 定理2.1集合A和B相等的充分必要条件是A和B 互为子集。 证明:1设A=B, 则(x)(xAxB)为真, 且(x)(xBxA)为真, 即AB, 且BA; 2反之(用反证法), 若AB, 且BA, 假设 AB,即A与B的元素不完全相同. 不妨设有某一元素xA, 但xB, 与AB矛盾, 若有某xB, 但xA, 同样与BA矛盾, 故A=B. 要避免使用“包罗一切的集合”或“由一切集合组成的 集合”等术语, 否则会导致集合论中的悖论。 集合论中的悖论: 定义: 寻常集-不包含自身作为元素的集合, 不寻常集-包含自身作为元素的集合, 再定义T是由所有寻常集组成的集合, 即, T=A|A是寻常集, 现在问T是寻常集还是不寻常集? 如果: (1)若T是寻常集, 它不包含自身作为元素;但根据T的定义, T又应该包含自身作为元素.这就与T是寻常集的假设矛 盾; (2)若T是不寻常集, 则根据不寻常集的定义, TT, 与T是 寻常集的集合这一原来的定义相矛盾。 定义2.2(幂集) 假设A是一个给定的集合, 将集合A的每个 子集看成一个元素,则集合A的所有子集为元素所作成的新 的集合称为集合A的幂集,记为(A). 例1.求空集的幂集. 解由于空集只有一个子集，也就是空集自己,从而它的 幂集为 ()= . (注)请注意将空集与区别开来: 中没有任何元素,而 中恰好有一个元素。 例2.设A=1,2,3, 试求它的幂集(A)。 解:集合A有8个子集,从而不难看出它的幂集为 (A). =,1,2,3,1,2,1,3,2,3,1,2,3. 显然,对于任何一个有三个元素的集合S,它的幂集 (S)都有与例中的集合A的幂集(A)同样的构造. 这个结果可以推广成下面一般性的结果: 定理2.2 如果A有n个元素, 则幂集(A)有2n个元素. 证明: (A)所含元素的个数, 即为A的子集个数N, 对A的所有子集按所含元素的个数排序, 而由A 的k个元素组成的子集数为: Cnk=n(n-1)(n-2) (n-k+1)/(k!) 故, N=Cn0+Cn1+Cn2+.+Cnk+Cnn = Cnk 又, (x+y)n = Cnkxkyn-k, 令x=y=1, 则2n= Cnk, 故N=2n. 下面来引进一种表示有限集合的子集和幂集的编码 方法, 以S=a, b, c为例: 记, S011=b, c, S000=, S111=a, b, c, 则, (S)=Si | iJ, 其中J=i | 000 i 111. 一般地, (S)=S0, S1, S2n1=Si|iJ, 其中J=i | 0000 i 1111. 注: J恰好是全体n位二进制数,也就是集合 0,1,2, 的二进制表示. 第三节 集合的运算 1. 集合的并 定义3.1 A和B是集合, 所有属于A或属于B 的元素组成的集合S, 称为A和B的并集, 记作 AB, 即, S=AB=x |(xA)(xB) A AB AB B 例:设O是奇数集合, 2Z是偶数集合, Z是整数集合, 则Z=O2Z; 例: A=1, 2, 3, B=2, 3, 4, 则 AB=1, 2, 3, 4; 定理3.1(集合的并的性质) (1)AB=BA(交换律), (2)(AB)C=A(BC)(结合律), (3)AA=A(等幂性), (4)A=A(同一律), (5)AE=E(零律), (6)AAB, BAB. 例1.A表示整个中国大陆部分的领土作成的集合 ,B表示中国的所有海域以及所有岛屿(含海南岛 、台湾岛、黄海、东海以及南海诸岛例如包括 钓鱼岛、东沙群岛以及南沙群岛等一切自古以来 属于中国的领海以及岛屿在内),C表示因历史原 因有自主独立的行政管理权或其管理权尚不属于 大陆政府的中国的其他领土(包括香港特别行政 区、台湾地区等). 那么,ABC恰好就是中国全部领土的集合. 2. 集合的交 定义3.2 假设A和B是两个给定的集合, 由A和B 的所有共同元素组成的集合S, 称为A和B的交集, 记作AB, 即, S=AB=x|(xA)(xB). E A AB B 例1. A=1, 2, 3, 4, 5, 6, 7, B=x|4的符号称为一个二元序偶.或者简称为 一个序偶.x称为这个序偶的第一元素,y称为这个序 偶的第二元素。 注意: 一般集合中的元素间是没有次序的, 故 序偶用 表示 由定义容易看出:两个序偶相等, 当且仅当对 应的元素相等, 即=,当且仅当x=u, y=v. 定义5.2(笛卡尔积) 设A和B是任意的 集合, 所有可能的序偶作成的集合|(xA)(yB)称为集合A和B的笛卡 尔积或直积, 记作AB.即 AB=|(xA)(yB). (注)如果|A|=m, |B|=n, 则 |AB|=mn=|A|B|, 显然, 当A=, 或B=, 有AB=, 此 时 |AB|=0. 定义5.2(三元序偶) 设A,B,C是三个集合,x,y,z是分别从这三个 集合取来的任意三个元素.我们把形如 ,z的符号称为一个三元序偶.为了简 便起见,三元序偶,z通常简写为 . 定义5.3(n元序偶的递归定义) 设 是n个集合(n3),从每个集 合中任取一个元素,记为 ,我们称 符号 是一个n元序偶,如 果 是一个n-1元序偶.通常我们将n元序偶 简记为 . 定义5.4(多重笛卡尔积) 设 是n个集合(n3),由一切n元序偶 ( ) 组成的集合称为这n个集合的n重笛卡尔积,记为 . 为简单起见我们将它记为 .特别地,如 果 是一个给定的集合,则记 笛卡尔积有如下性质: 定理5.1 设A, B, C,D均为集合, 则有下列结 论成立: (1)A(BC)=(AB)(AC), (BC)A=(BA)(CA), (2)A(BC)=(AB)(AC), (BC)A=(BA)(CA), (3)A(B-C)=(AB)-(AC), (B-C)A=(BA)-(CA), (4)若C,那么 1AB ACBC,2AB CACB. (5)设A,B,C,D均为非空集合,则有 ABCD (AC)(BD). 证明:我们只给出(1)和(3)的第一式以及(5)的 证明. (1)的第一式的证明: A(BC) (xA)(yBC) (xA)(yB)(yC) (xA)(yB)(xA)(yC) (AB)(AC) (AB)(AC), 同理可证其余. (3)的第一式的证明: 只证明A(B-C)(AB)-(AC). A(BC) (xA)(yBC) (xA)(yB)(yC) (xA)(yB)(xA)(yC) (AB)(AC) (AB)(AC), 同理可证其余. (5)式的证明: 1证明 ABCD (AC)(BD). 证明: xA,yB AB. ABCD CD (xC)(yD) (AC)(BD) . 相反的包含关系可以类似地加以证明. 第六节 关系及其表示 在科学以及人类社会活动中，到处都有各种各 样的关系存在。 在数学中当然充满了关系，例如在整数之间对 于取定的一个除数有余数相同的同余关系；在实 数之间有大小关系；集合之间有包含关系；在三 角形之间有全等关系以及相似关系；即便在人类 社会中也有数不清的关系存在，例如家庭中的长 幼关系、学校中的师生关系、工作单位里的同事 关系以及上下级关系等等等等。 如何确切地表达“关系”这个概念，并对它进行 深入的研究，是我们这一部分的一个重点内容。 本书中重点讨论两个对象之间的“二元关系”，而 不涉及多个对象之间的“多元关系”。 定义6.1 任意的序偶集合RAB称 为集合A到B的一个二元关系(relation) ， 若是关系R中的任意一个元素, 则记作R, 或xRy, 若不是关 系R中的元素, 则记为R, 或者记 作xRy,或者记为 ；当A=B时,称R 为集合A上的一个二元关系. 例1. (整数集合上的同余关系) 取定一个正整数k(通常取k为大于1的整数, 这样的数k在数论中称之为“模”,它的含义实 际上是除法中的除数),将全体整数的集合 中的每一个整数被k除，取非负最小余 数.容易看出,可能得到的不同的余数一共有 以下k个:0,1,k-1.现在定义 上的一个 二元关系 如下: , 这里 的含义是 整除 .通常 我们把 表示成下面的形式 , 这个式子可以读成“ 和 关于模 同余 ”.之所以这样说,其原因在于:当且仅当 成立时, 和 被模 除显然有相同的余 数. 例2.给定任意一个非空集合A,可以作出它的 幂集(A).在(A)上定义一个二元关系R如 下: S,T(A),R S T. 例3.给定集合A=a,b,c,d,在集合A上定义如 下几两个二元关系R1,R2: R1=, R2=,. 例4.给定集合A=1,2,3,4,5,定义A上两个关系 如下: 经过计算,它们实际上就是如下的两个关系 , . 由于任何非空集合都有两个平凡的子 集:空集和它自己.同样地,给定任意一个非空 集合A,笛卡尔积A2=AA也有两个平凡的子 集:空集和它自己AA.根据定义, 和AA 也都是集合A上的二元关系,分别称它们是A 上的空关系以及全域关系.此外,任何非空集 合上都有如下定义的一个特殊的关系 IA=|xA, 我们始终用符号IA来记这样一个特殊的 关系,并称它是集合A上的恒等关系. 定义6.2(关系的前域、值域以及域) 设R是集合A到B的二元关系, dom R=x |(y)(R)称为R的前域, (domain) ran R=y |(x)(R)称为R的值域, (range) fldR=domRranR称为R的域。 (field) 显然, domRA, ranRB, RAB , filR=domRranR, 例如, 设A=1, 2, 3, 5, B=a, b, c, R=, , , ; 求: dom R, ran R, fld R . 解: dom R =1, 2, 3, ran R =b, c, fld R =domRranR=1, 2, 3, b, c. 关系除了可以用通常集合的表示方法(描述法 以及列举法)表示以外, 还可以用关系矩阵和关系图 来表示. 设有限集合A=x1, x2,xm, B=y1, y2,yn, R是A到B的关系, 则对应的关系矩阵M(R