第三章 集合与关系

1、第二篇 集合论集合与关系函数第三章 集合与关系2014-2015 学年第二学期陈磊3.1 集合的概念和表示法 把具有共同性质的一些东西, 汇集成一个整体, 就形成一个集合【例】1. 教室内的桌椅 2. 自然数的全体 3. 图书馆的藏书 通常用大写的英文字母表示集合的名称 组成集合的对象叫做集合的元素或成员, 常用小写的英文字母表示。 若元素a属于集合A, 记作aA, 也称为A包含a, a在A之中, a是A的成员 若元素a不属于集合A, 记作a A, 也称为A不包含a, a不在A之中, a不是A的成员 若组成集合的元素个数是有限个, 则称作有限集, 否则称作无限集【例】1. 集合A: 计算机专业

2、14级全体学生 2.集合B: 全体自然数 集合的性质 集合的元素必须是确定的。所谓确定的，是指任何一个对象是不是集合的元素是明确的、确定的，不能模棱两可。 集合的元素又是能区分的，能区分的是指集合中的元素是互不相同的。如果一个集合中有几个元素相同，算做一个。 集合的元素又是无序的，即1,2,3和3,1,2是同一集合。 集合的表示方法 列举法：在花括号“”中列举出该集合的元素，元素之间用逗号隔开。 【例】 I5=1,2,3,4,5 I+=1,2,3, I =0,1,-1,2,-2, S=T,F 描述法：用谓词界定集合的元素。【例】 Q=x | x是有理数 若用P(x)表示x是有理数，那么Q又可表

3、示为： Q=x | P(x) 集合的元素可以是一个集合【例】1. S = a, 1,2, p, q q q 但 q S 2. S =1, 2, 1,2 1, 2 S 且 1, 2 S 罗素悖论 设命题函数P(x)表示“x x”，现假设由性质P确定了一个类A, 也就是说“A=x|x x”。 那么现在的问题是：AA是否成立？ 首先，若AA，则A是A的元素，那么A具有性质P，由命题函数P知A A； 其次，若A A，也就是说A具有性质P，而A是由所有具有性质P的类组成的，所以AA。 理发师悖论 在某个城市中有一位理发师，他的广告词是这样写的：“本人的理发技艺十分高超，誉满全城。我将为本城所有不给自己刮

4、脸的人刮脸，我也只给这些人刮脸。我对各位表示热诚欢迎！”来找他刮脸的人络绎不绝，自然都是那些不给自己刮脸的人。可是，有一天，这位理发师从镜子里看见自己的胡子长了，他本能地抓起了剃刀，你们看他能不能给他自己刮脸呢？ 如果他不给自己刮脸，他就属于“不给自己刮脸的人”，他就要给自己刮脸，而如果他给自己刮脸呢？他又属于“给自己刮脸的人”，他就不该给自己刮脸。 子集 定义 3-1.1 设A，B是任意的集合，当A的每一元素都是B的元素时，则称A是B的子集，也称A包含在B内或B包含A。记为A B或B A。 当A不是B的子集时，记为A B。 AB用谓词公式表示为：A B (x)(xAxB) A B用谓词公式表

5、示为： A B (x)(xAxB)【例】设A=1，B=1,2，C=1,2,3 则 AA; AB，BC，AC ; C B 集合的包含有下列性质： 自反性。即对任意集合A，AA。 传递性。即对任意集合A、B、C，当AB和BC时，AC。 两个集合相等 外延性原理: 两个集合A和B是相等的, 当且仅当它们有相同的成员, 记为A = B. 如果两个集合不相等, 则记为A B 由集合相等的定义可以看出，集合相等有下列性质：自反性: 即对任意集合A，A=A。对称性: 即对任意集合A、B, 当A=B时，B=A。传递性: 即对任意集合A、B、C，当A=B和B=C时，A=C。 定理3-1.1 设A，B是集合，A与

6、B相等的充分必要条件为A B且B A. 集合相等也可用谓词公式表示为： A=BABBA (x)(xAxB)(x)(xBxA) (x)(xAxB) 证明两个集合相等, 主要利用上述定理中互为子集的判断条件 真子集 定义3-1.2 设A，B是集合，如果AB且AB，则称A是B的真子集。记为A B。如果A不是B的真子集，记为A B。 真子集用谓词公式表示为： ABABAB (x)(xAxB)(x)(xBxA)【例】1. 设 A=a，B=a,b，C=a,b,c 则 A B，BC，AC AA 2. 自然数集是整数集合的真子集，也是有理数集合和实数集合的真子集，即N I ，NQ，NR。 空集 定义3-1.3

7、 不包含任何元素的集合叫空集, 记为 空集可以表示为： =x | P(x)P(x) 其中，P(x)为任意谓词 注: 定理3-1.2 对于任意一个集合A, A 证明：设A是任意集合。对任意对象x，由空集的定义知，x为假，由条件联结词的定义知，xxA为真。根据全称推广规则有 (x)( xxA) 为真，故A 任意非空集合A至少有两个不同的子集，一个是空集，另一个是它本身A, 它们被称为平凡子集. 全集 定义3-1.4 在一定范围内, 如果所有集合均为某一个集合的子集, 则称该集合为全集, 记作E. 全集的谓词表示: E=x | P(x) P(x), P(x) 为任何谓词【例】全集E = a, b,

8、c, 则其所有可能的子集有: S0= S1= a S2= b S3= c S4=a,b S5= b,c S6=c,a S7=a,b,c 幂集 定义3-1.5 设A是集合，A的所有子集构成的集合称为A的幂集合，记为P (A)【例】 A= a, b, c, 则其幂集为 P(A) =, a, b, c, a,b, b,c, c,a, a,b,cP ()= P (P () = , 定理3-1.3 设A为有n个元素的有限集合，则其幂集P (A)有2n个元素 证明: 设A有n个元素，A的子集有： 不含元素的子集一个，即 个。 含一个元素的子集n个，即 个。 含两个元素的子集 个。 含n个元素的子集 个。

9、|P (A)|= + + + =2n0nC1nC2nCnnC0nC1nCnnC 用二进制编码表示一个有限集的幂集【例】S=a, b, c S中每个元素与一个三位二进制数中一位对应，1表示该元素在幂集的一个集合中， 0表示不在 S100 = a, S011 = b, c 每个二进制数还可以化为一个十进制数 S4 = S100 = a, S3 = S011 = b, c P(S) = S0, S1, S2, S3, S4, S5, S6, S7 一般的， P(S) = S0, S1, , S2n-1 作业: (4) (6) a) (10) 3.2 集合运算 集合的交 定义3-2.1设A，B是任意两

10、个集合，由集合A与B的公共元素组成的集合S，称为A和B的交集，记为AB。 S = AB=x | (xA) (xB)【例】令A=a,b,c，B=d,e，C=a, e 则AB=，A和B是互不相交的 A C=a 集合的交运算具有以下性质 A A=A A = A E=A A B = B A (A B) C = A (B C) A B A, A B B【例】设A B, 求证A C B C 集合交运算有结合律, 故niinAAAAP121= 集合的并 定义3-2.2 设A，B是任意两个集合，由A中的元素或B中的元素组成的集合S，称为A和B的并集，记为AB S= AB =x | (xA)(xB)【例】设A=

11、1, 2, 3, 4, B=2, 4, 5 则A B=1,2,3,4,5 集合的并运算具有以下性质 A A=A A = A A E= E A B = B A (A B) C = A (B C) A A B, B A B【例】设A B,C D, 求证A C B D 集合并运算有结合律, 故niinAAAAW121= 定理3-2.1设A,B,C为三个集合, 则下列分配律成立 a) A (B C) = (A B) (A C) b) A (B C) = (A B) (A C) 定理3-2.2 设A,B为任意两个集合, 则下列关系式成立(吸收律) a) A (A B) = A b) A (A B) =

12、A 定理3-2.3 A B, 当且仅当A B=B或A B=A 集合的补 定义3-2.3 设A，B是任意两个集合，属于A的而不属于B的元素组成的集合S，称为B对于A的补集，也叫B对于A的相对补集。记为A-B S = A-B=x |xAxB【例】设A=2, 5, 6, B=1, 2, 4, 7, 9 则A-B=5, 6 定义3-2.4 设E是全集, 对任一集合A关于E的补E-A，称为集合A的绝对补，记为A。 A=E-A=x |xExA=x | xA 集合补运算的一些性质 (A)= AE= =EA A=EA A= 定理3-2.4 设A,B为任意两个集合, 则下列关系成立 a) (A B) = A B

13、 b) (A B) = A B 定理3-2.5 设A,B为任意两个集合, 则下列关系成立 a) A-B = A B b) A-B = A-(A B) 定理3-2.6 设A, B, C为三个集合, 则 A (B-C) = (A B) (A C) 定理3-2.7 设A, B为两个集合, 若A B, 则 a) B A b) (B-A) A=B 集合的对称差 定义3-2.5 设A，B是任意两个集合，由 A中元素或B中元素，但不是A与B的公共元素组成的集合S，称为A和B的对称差，记为A B。 S=A B=x |(xA) (xB) =(A-B) (B-A)=(AB)-(AB)【例】令A=1,2,3,4，

14、B= 1,2,5,6，则 A B=3,4,5,6 集合的对称差运算有如下性质 a) A B=B A b) A = A c) A A= d) A B = (A B) (B A) e) (A B) C = A (B C) 作业 (3) (4) (8) 3.3 包含排斥原理 有限个元素的计数问题 - 包含排斥原理 设A1,A2是两个有限集, 元素个数定义为|A1|和|A2|, 则 |A1 A2| |A1|+|A2| |A1 A2| min(|A1|, |A2|) |A1-A2| |A1|-|A2| | A1 A2 | = |A1|+|A2|-2 |A1 A2| l定理3-3.1 设A1,A2为有限集

15、合, 其元素个数分别为|A1|和|A2|, 则 |A1 A2| = |A1|+|A2|- |A1 A2| 【例】有100名程序员，其中47名熟悉Fortran语言，35名熟悉Pascal语言，23名熟悉这两种语言。问有多少人对这两种语言都不熟悉。 解: 设A、B分别表示熟悉Fortran和Pascal语言的程序员集合, 则 |A| = 47; |B| = 35; |A B| = 23 |A B| = |A|+|B|- |A B| = 47+35-23=59 | (A B)| = 100-59=41 三个集合有没有类似的结果? 对于任意三个集A1，A2，A3, 有： A1 A2 A3 A1 A2

16、 A3 A1 A2 A1 A3 A2 A3 A1 A2A3【例】某工厂装配30辆汽车, 可供选择的设备有收音机, 空气调节器和对讲机. 现已知其中15辆汽车有收音机, 8辆有空气调节器, 6辆有对讲机, 而且其中3辆汽车这三样设备都有, 则至少有几辆汽车什么设备都没有? 推广到一般情况 定理3-3.2 设A1,A2, , An为有限集, 其元素个数分别为|A1|, |A2|,|An|, 则【例】求1到250之间能被2,3,5,7任何一个整除的整数个数=njijiniinAAAAAA1121|nkjikjiAAA1|) 1(211nnAAA 作业 (4) (5) 3.4 序偶与笛卡尔积 在日常生

17、活中, 许多事物是成对出现的, 且具有一定的顺序 【例】上,下; 左,右; 34; 平面上的点坐标 具有固定次序的客体组成一个序偶 序偶表达两个客体之间的关系【例】; ; ; 序偶可以看作有两个元素的集合, 但其具有次序, 即a,b=b,a 但 定义3-4.1两个序偶和相等, 当且仅当x=u, y=v 序偶的次序一旦确定就不能再变了.序偶中, a 称为第一元素, b 称为第二元素 序偶的推广 三元组 三元组是一个序偶, 其第一元素本身也是一个序偶, 表示为,z 两个三元组,z和,w相等, 当且仅当x=u, y=v, z=w 简记为 四元组 四元组是一个序偶, 其第一元素是一个三元组, 表示为,

18、w 两个四元组,w和,s相等, 当且仅当x=p, y=q, z=r, w=s 简记为 n元组 n元组是一个序偶, 其第一元素是一个n-1元组, 表示为,xn 两个n元组,xn和,yn相等, 当且仅当x1=y1, x2=y2, , xn=yn 简记为 序偶其元素可以属于两个不同的集合, 任给两个集合A,B, 可以定义一种序偶的集合 定义3-4.2 令A和B是任意两个集合, 若序偶的第一元素属于A, 而第二元素属于B, 所有这样的序偶构成的集合称为集合A和B的笛卡尔积或直积, 记作A B , A B= | (x A) (xB)【例】A=a,b, B=1,2,3, 则A B, B A, A A, B

19、 B 注 A B B A 若A= 或B= , 则A B = (A B ) C A ( B C) 定理3-4.1 设A,B,C为任意三个集合, 则 a) A (B C)=(A B ) (A C ) b) A (B C)=(A B ) (A C ) c) (A B) C= (A C) (B C) d) (A B) C= (A C) (B C) 定理3-4.2 若C , 则 A B (A C B C ) (C A C B) 定理3-4.3 设A,B,C,D为四个非空集合, 则 A B C D当且仅当A C, B D 两个集合的笛卡尔积仍然是集合，故可以和其它集合继续做笛卡尔积 约定 A1 A2 A3

20、= (A1 A2) A3; A1 A2 A3 A4= (A1 A2 A3) A4 一般地， A1 A2 An= (A1 A2 An-1) An = | (x1 A1) (x2 A2) (xn An) A1 A2 An可以看成是n元组构成的集合 AA简记为A2； 一般地，A A A简记为An 作业 (3) a)、b)、c) (4) 3.5 关系及其表示 日常生活中我们常用如：兄弟关系， 上下级关系等来表示集合中两个元素的关系 序偶可以表达两个客体，甚至n个客体间的关系 可以用序偶表示关系【例】电影票与座位之间的关系 X表示电影票集合 Y 座位集合 则对任意的x X和y Y, 必有x与y有 “对号

21、”关系或x与y无 “对号”关系 令R表示“对号”关系，则上述问题可表述为xRy或x y 对号关系是序偶的集合，也是X Y的子集R 定义3-5.1 任一序偶的集合S确定了一个二元关系R，R中任一序偶可记作 R或xRy. 不在S中的任一序偶可记作 R或x y【例】实数中“”关系可记作 | x,y是实数且xy 定义3-5.2 令R为二元关系，由 R的所有x组成的集合dom R称为R的前域，即 dom R= x | (y)( R) 使 R的所有y组成的集合ran R称为R的值域，即 ran R= y | (x)( R) R的前域和值域一起称作R的域，记作FLD R, 即 FLD R= dom R ra

22、n R R 【例】A=1,2,3,5, B=1,2,4, H=, 则 dom H=1,2,3 ran H=2,4 FLD H=1,2,3,4 定义 3-5.3 令X和Y是任意两个集合，直积X Y的子集R称为X到Y的关系 如R是X到Y的关系，则 dom R X ran R Y R X Y FLD R X Y 特例 R= ，则R称为空关系 R= X Y, 则R称为全域关系 当X=Y时，关系R是X X的子集，R称为在X上的二元关系【例】X=1,2,3,4, 求X上的关系 “” 所求的二元关系为, , , , , 定义3-5.4 设IX是X上的二元关系且满足Ix= | x X, 则称IX是X上的恒等关

23、系【例】A=1,2,3,4, 则IA=, , , 【例】设X=1,2,3,4，X上的二元关系H和S定义如下： H=x,y | 是整数 S=x,y | 是正整数 试求HS，HS，H，S-H 解：解：H=1,1,1,3,2,2,2,4,3,3,3,1,4,4,4,2 S=4,1 HS=1,1,1,3,2,2,2,4,3,3,3,1,4,4, 4,2,4,1 HS= H=X2- H=1,2,1,4,2,1,2,3,3,2,3,4, 4,3,4,1 SH=4,1 定理3-5.1 若Z和S是从集合X到集合Y的两个关系，则Z,S的并、交、补、差仍为X到集合Y的关系2yx 3yx 设R是从X到Y的一个二元关

24、系，如果X和Y都是有限集，则除了用序偶集合表示之外，还有如下两种表示法 矩阵表示法 如果X，Y是有限集， X=a1,a2,am， Y=b1,b2,bn， R是X到Y的二元关系，R的关系矩阵定义为： MR= rijmn 其中，RRbbaarjjiiij=,01【例】设A=a1,a2,a3,a4，B=b1,b2,b3，R是A到B的二元关系，定义为： R=a1,b1,a1,b3,a2,b2,a2,b3,a3,b1,a4,b1,a4,b2 则R的关系矩阵为MR= 011001110101【例】设A=1,2,3,4，R是A的二元关系，定义为：R=1,1,1,2,2,1,3,2,3,1,4,3,4,2,4

25、,1则R的关系矩阵为： 上例中的二元关系R是A上的二元关系，只需看成A到A的二元关系，利用上述定义，就可以方便地写出它的关系矩阵。A上的二元关系和A到B的二元关系的关系矩阵的定义是相同的。=0111001100010011RM 图表示法 如果A和B是有限集，R是A到B二元关系，还可以用图表示二元关系R。表示二元关系R的图叫做R的关系图。A到B二元关系的关系图和A上的二元关系的关系图的定义是不一样的。分别描述如下： A到B二元关系R的关系图 设A=a1,a2,am，B=b1,b2,bn，R是A到B二元关系，R的关系图的绘制方法如下： 画出m个小圆圈表示A的元素，再画出n个小圆圈表示B的元素。这些

26、小圆圈叫做关系图的结点。 如果ai,bj R，则从ai到bj画一根有方向(带箭头)的线。这些有方向(带箭头)的线叫做关系图的弧。 【例】设A=a1,a2,a3,a4，B=b1,b2,b3，R是A到B的二元关系，定义为： R=a1,b1,a1,b3,a2,b2,a2,b3,a3,b1,a4,b1,a4,b2 则R的关系图如下图所示A上的二元关系R的关系图设A=a1,a2,am，R是A上的二元关系，其关系图如下绘制:画出m个小圆圈表示A的元素。如果ai,ajR，则从ai到aj画一根有方向(带箭头)的线。【例】设A=1,2,3,4，R是A的二元关系，定义为：R=1,1,1,2,2,1,3,2,3,1

27、,4,3,4,2,4,1则R的关系图为： 作业 (5) b)、d) (6) (7) 3.6 关系的性质 有些关系具有比较特别的性质, 如恒等关系1. 自反的 定义3-6.1 设R为定义在集合X上的二元关系, 如果对于每个xX, 有 R, 则称R是自反的 R是自反的当且仅当(x)(xXx,xR) 自反关系R的关系矩阵和关系图 R的关系矩阵MR的主对角线全为1 R的关系图中每一个结点上都有自回路。【例】设X=1,2,3，X上的二元关系 R=1,1,2,2,3,3,1,2R是自反的,它的关系图如下图所示，关系矩阵如下： 注意：对于自反关系R, 必须是对于每个xA,都去检验是否有 R 定理 设R是X上

28、的二元关系，R是自反的当且仅当IXR。1000100112. 对称的 定义3-6.2 设R为定义在集合X上的二元关系, 如果对于每个x,yX, 每当 R, 就有 R, 则称R是对称的。 R在X上对称当且仅当 (x)(y)(xXyXx,yRy,xR) 对称关系R的关系矩阵和关系图 R的关系矩阵MR是对称矩阵 在R的关系图中，如果两个不同的结点间有弧，一定有方向相反的弧【例】设X=1,2,3，X上的二元关系R=1,2,2,1,3,3，R是对称的。它的关系图如下图所示，关系矩阵如下：【例】设A=1,3,5,7，定义A上的二元关系如下： R=a,b|(ab)/2是整数 试证明R在A上是自反的和对称的。

29、1000010103. 传递的 定义3-6.3 设R为定义在集合X上的二元关系, 如果对于任意x,y,zX, 每当 R和 R, 就有 R, 则称R是传递的。 R在X上是传递的当且仅当 (x)(y)(z)(xXyXzXx,yRy,zR x,zR)【例】设R是实数集合， S=x,y|xRyRxy 是实数集合上的大于关系。 证明实数集合上的大于关系是传递的。4. 反自反 定义3-6.4 设R为定义在集合X上的二元关系, 如果对于每个xX, 有 R, 则称R是反自反的 R是反自反的当且仅当(x)(xXx,xR) 反自反关系R 的关系矩阵和关系图 R的关系矩阵MR的主对角线全为0 在R的关系图中每一个结

30、点上都没有自回路【例】设X=1,2,3，X上的二元关系R=1,2,2,3,3,1，R是反自反的,它的关系图如下图所示，关系矩阵如下：【例】设R是实数集合， =x,y| xRyRxy是实数集合上的小于关系。证明实数集合上的小于关系是反自反的。001100010 注 一个关系若是自反的，则一定不是反自反。反之亦然。 一个关系可以既不是自反的，也不是反自反的。 定理 设R是X上的二元关系, R是反自反的当且仅当RIX=。【例】设A=1,2,3，定义A上的二元关系如下： R=1,1,2,2,3,3,1,3 S=1,3 T=1,1试说明R，S，T是否是A上的自反关系或反自反关系。自反的反自反的不是自反的

31、,也不是反自反的5. 反对称 定义3-6.5 设R为定义在集合X上的二元关系, 如果对于每个x,yX, 每当 R和 R,必有x=y, 则称R是反对称的。 R在X上反对称当且仅当 (x)(y)(xXyXx,yRy,xR(x=y)x,yRy,xR(x=y) (x=y)(x,yRy,xR) (x=y)(x,yRy,xR) (x=y)x,yR)y,xR (xy)x,yR)y,xR (xy)x,yRy,xR x,yR(xy)y,xR由此，反对称的定义又可以等价的描述为： (x)(y)(xXyXx,yR(xy)y,xR) 反对称关系R 的关系矩阵和关系图 在R的关系矩阵MR中以主对角线为轴的对称位置上不能

32、同时为1(主对角线除外) 在R的关系图中每两个不同的结点间不能有方向相反的两条弧【例】设X=1,2,3，X上的二元关系R=1,2,2,3,3,3，R是反对称的。它的关系图如下图所示，关系矩阵如下：100100010 注 一个关系可以既是对称的，又是反对称的。 一个关系可以既不是对称的，又不是反对称的。 【例】 设A=1,2,3，定义A上的二元关系如下： R=1,1,2,2 S=1,1,1,2,2,1 T=1,2,1,3 U=1,3,1,2,2,1试说明R，S，T，U是否是A上的对称关系和反对称关系。既是对称的,也是反对称的对称的,不是反对称的反对称的,不是对称的既不是对称的,也不是反对称的【例

33、】设R，S是X上的二元关系，证明 若R，S是自反的，则RS和RS也是自反的。 若R，S是对称的，则RS和RS也是对称的。 若R，S是传递的，则RS也是传递的。 注若R，S是传递的，则RS不一定是传递的。【例】 X=1,2,3,4 S=, , R=, , 则R，S是传递的，但RS不是传递的 作业 (1) (6) 3.7 复合关系和逆关系 二元关系是以序偶为元素的集合 对其进行集合的运算（并、交、补、对称差等）可以得到新的集合，即可得到新的二元关系 对于二元关系还可以进行其它运算关系的复合关系的逆关系的复合运算 定义 3-7.1 设R为X到Y的关系，S为从Y到Z的关系，则R S称为R和S的复合关系

34、，表示为 R S =x,zxXzZ(y)(yYx,yRy,zS)【例】 X=1,2,3,4,5，X上的二元关系R和S定义如下： R=1,2,3,4,2,2 S=4,2,2,5,3,1,1,3试求R S，S R可以类推得到两个以上关系的复合, 并有结合律, 即(R S) P = R (S P) 【例】 求上例的R (S R)，(R S) R，R R，S S，R R R 注 复合运算不满足交换律，即R SS R 关系R本身所组成的复合关系可以写成： R R， R R R，, 简记为R(2), R(3), R(m), 一般地，R(m-1) R=R(m)mRRR 复合关系用矩阵表示设R是从X=x1,x

35、2, ,xm到Y=y1,y2, ,yn的一个二元关系，则其关系矩阵MR=uij为设S是从Y=y1,y2, ,yn到Z=z1,z2, ,zP的一个二元关系，则其关系矩阵MS=vij为RRyyxxujjiiij=,01SSzzyyvjjiiij=,01R S表示R和S的复合关系，表示从X到Z的二元关系，其关系矩阵 MR S =wijwij和uij、vij的关系如下：将上述关系用矩阵符号记为： MR S =MR MS 矩阵运算“ ”叫做关系矩阵MR和MS的布尔乘法。SSRRzzxxwjjiiij=,01)(1kjiknkijvuw= 代表逻辑乘，满足： 0 0=0， 01=0， 10=0， 11=1

36、 代表逻辑加，满足 0 0=0， 0 1=1， 1 0=1， 1 1=1 把关系矩阵的布尔乘法公式 与线性代数中的矩阵乘法公式相比，发现，只要把矩阵乘法公式中的数乘改为逻辑乘，把数加改为逻辑加，就得到了关系矩阵的布尔乘法公式。)(1kjiknkijvuw=【例】A=1,2,3,4,5，A上的二元关系R和S定义如下： R=1,2,2,2,3,4 S=1,3,2,5,3,1,4,2试求MR S和MR MS，它们是否相等 ? 解：按照R 和S的定义，求出 R S=1,5,3,2,2,5 写出R 、S和R S关系矩阵如下： MR= MS= MR S=00000000000100000010000100

37、0000000100000110000001000000000000000101000010000 MR MS= = M R S =所以MR S=MR MS 00000000000100000010000100000000010000011000000100000000000000010100001000000000000000001010000100002. 关系的逆 定义 3-7.2 设R为从X到Y的二元关系，如将R中每一序偶的元素顺序互换，所得到的集合称为R的逆关系，记为Rc, 即 Rc =y,xx,yR【例】1. 自然数集合上的关系“” 2. 设X=1,2,3,4，Y=a,b,c，X到

38、Y二元关系 R=1,a,2,b,4,c， 则 Rc=a,1,b,2,c,4注 (Rc)c = R 定理 3-7.1 设R,R1,R2是从A到B的二元关系，则下列各式成立 a) (R1R2)c = R1c R2c b) (R1R2)c = R1c R2c c) (AB)c = BA d) , 其中 e) (R1-R2)c = R1c - R2c 定理 3-7.2 设T为从X到Y的关系，S为从Y到Z的关系，证明(T S)c = Sc TcccRR=)(RBAR= 定理 3-7.3 设R为X上的二元关系，则 a) R是对称的，当且仅当R = Rc b) R是反对称的，当且仅当RRc IX 关系的逆用

39、矩阵表示和图表示 Rc的关系矩阵 是R的关系矩阵MR的转置矩阵，即 将R关系图中的弧线的箭头反置，就可以得到Rc关系图。【例】设X=1,2,3,4，Y=a,b,c，X到Y二元关系 R=1,a,2,b,4,c， 试求Rc，写出MR和 ，验证cRMTRRMMc=CRMTRRMMc=R和Rc的关系矩阵是：R和Rc的关系图是：=100000010001RM=100000100001cRM 作业 (1) (3) (6) 3.8 关系的闭包运算 给定一个集合上的关系，扩充一些序偶可以得到一些具有特殊性质的关系 闭包运算 定义 3-8.1 设R是X上的二元关系，如果有另一个关系R满足： a) R是自反的(对

40、称的，可传递的) b) R R c) 对于任何自反的(对称的，可传递的)关系R ，如果有R R, 就有R R 则称关系R 为R的自反(对称，传递)闭包，记为 r(R) (s(R), t(R) 对于一个不是自反的(对称的，可传递的)二元关系，可以通过扩充序偶的方法得到它的自反(对称，传递)闭包 自反(对称，传递)闭包是包含R的最小的自反(对称，传递)闭包 当二元关系R是自反(对称，传递)的，求R的自反(对称，传递)闭包方法由下面的定理给出了。 定理3-8.1 设R是X上的二元关系，那么 a) R是自反的，当且仅当r(R) = R b) R是对称的，当且仅当s(R) = R c) R是传递的，当且

41、仅当t(R) = R 当二元关系R不是自反的时候，下面的定理给出了求其自反闭包的方法 定理3-8.2 设R是集合X上的二元关系，则 r(R) = R IX 当二元关系R不是对称的时候，下面的定理给出了求其对称闭包的方法 定理3-8.3 设R是集合X上的二元关系，则 s(R) = R Rc 当二元关系R不是传递的时候，下面的定理给出了求其传递闭包的方法 定理3-8.4 设R是集合X上的二元关系，则 t(R) =RR(2)R(3)=R+【例】设A=1,2,3，定义A上的二元关系R为： R=1,2,2,3,3,1 试求：r(R)，s(R)，t(R) 解：r(R)= RIA=1,2,2,3,3,1,1

42、,1,2,2,3,3 s(R)=RRc=1,2,2,3,3,1,2,1,3,2,1,3 R(2)= R R=1,3,2,1,3,2 R(3)= R(2) R =1,1,2,2,3,3=IA R(4)= R3 R = IA R=R t(R)= RR(2) R(3) = 1,1,1,2,1,3,2,1,2,2,2,3, 3,1,3,2,3,3 定理3-8.5 设X是含有n个元素的集合，R是X上的二元关系，则存在一个整数kn，使得 t(R) =RR(2)R(3) R(k) 求一个二元关系R的传递闭包可以简单的求RR(2)R(3) R(n)【例】设A=1,2,3，定义A上的二元关系R为：R=1,2,2

43、,3,3,1试用关系矩阵求传递闭包t(R)。=001100010RM=010001100001100010001100010)2(RRRMMM=100010001001100010010001100)2()3(RRRMMM=111111111)3()2()(RRRRtMMMM其中，表示矩阵的对应元素进行析取运算。 求传递闭包的简易算法置新矩阵A:=M;置i:=1;对所有j如果Aj,i = 1, 则对k=1,2,n Aj,k:=Aj,kAi,k i加1;1.如果in, 转步骤3, 否则停止【例】已知关系矩阵 求t(R)=0010100001010010M001010000111001001111

44、0000111011111111000111111111111111111111111 定理3-8.6 设X是集合，R是X上的二元关系，则 a) rs(R)=sr(R) b) rt(R)=tr(R) c) st(R)ts(R) 作业 (2) (5) c) (7) 3.9 集合的划分和覆盖 对集合的研究，有时要把一个集合分成若干子集进行讨论 定义3-9.1 若把一个集合A分成若干个叫做分块的非空子集，使得A中每个元素至少属于一个分块，那么这些分块的全体构成的集合叫做A的一个覆盖。如果A中每个元素属于且仅属于一个分块，那么这些分块的全体构成的集合叫做A的一个划分(或分划)【例】A=1,2,3,4,

45、5,6,7,8,9 S1=1,2,3 S2=2,3,4,5,6 S3=4,5,6,7 S4=6,7,8 S5=8,9 则 S1,S2,S3,S4,S5是A的一个覆盖 而S1,S3,S5是A的一个划分 形式化定义 定义3-9.1 令A为给定非空集合，S=S1,S2,Sm, 其中Si A, Si(i=1,2,m)且 , 集合S称为集合A的覆盖 如果附加条件SiSj=(ij), 则称S是A的划分(或分划)【例】A=a,b,c S=a,b, b,c Q=a, a,b, a,c D=a, b,c G=a,b,c E=a, b, c F=a, a,c 则S,Q,D,G,E是A的覆盖 其中D,G,E是A的划

46、分 F既不是划分也不是覆盖ASmii=1 注 若是划分则必是覆盖 一个集合的最小划分是由这个集合的全部元素组成的一个分块集合 一个集合的最大划分是由每个元素构成一个单元素分块的集合 一个集合的划分不唯一 定义3-9.2 若A1,A2,Ar与B1,B2,Bs是同一个集合A的两种划分，则其中所有AiBj组成的集合，称为是原来两种划分的交叉划分。【例】所有生物的集合X，可分割为P,A, 其中P表示植物的集合，A表示动物的集合。 X也可分割为E,F, 其中E表示史前生物的集合，F表示史后生物的集合。 则它们的交叉划分为P E, P F, A E, A F, 其中 P E：史前植物的集合 P F：史后植

47、物的集合 A E：史前动物的集合 A F：史后动物的集合 定理3-9.1设A1,A2,Ar与B1,B2,Bs是同一集合X的两种划分，则其交叉划分也是X的一种划分 定义3-9.3 给定X的任意两个划分A1,A2,Ar与B1,B2,Bs，若对于每个Aj均有Bk使得Aj Bk，则A1,A2,Ar称为是B1,B2,Bs的加细【例】X=a,b,c,d,e,f,g S = a,b,c, d,e, f,g 和 D = a,b, c, d,e, f, g 是X的两 个划分 则D是S的加细 定理3-9.2 任何两种划分的交叉划分，都是原来划分的一种加细 作业 (2) (5) 3.10 等价关系与等价类 等价关系

48、是最重要、最常见的二元关系之一。它有良好的性质。在计算机科学和计算机技术、信息科学和信息工程中都有广泛的应用。 定义3-10.1 设R为定义在集合A上的一个关系，若R是自反的，对称的和传递的，则R称为等价关系 等价关系的关系矩阵和关系图 关系矩阵主对角线全为1且是对称阵； 关系图每一个结点上都有自回路且每两个结点间如果有弧，一定有方向相反的两条弧。 【例】设A=1,2,3,4,5，R是A上的二元关系， R=1,1,1,2,2,1,2,2,3,3,3,4,4,3,4,4,5,5， 证明R是A上的等价关系。 证法一：用关系矩阵说明R是等价关系 R的关系矩阵MR如下： MR的主对角线全为1且是对称阵

49、，所以R是自反的和对称的；还可以用二元关系传递性的定义证明R是传递的。故R是A上的等价关系。=1000001100011000001100011RM证法二：用关系图说明R是等价关系 在R的关系图中每一个结点上都有自回路；每两个结点间如果有弧，一定有方向相反的两条弧。所以R是自反的和对称的。与前面一样，也可以用二元关系传递性的定义证明R是传递的。故R是A上的等价关系等价关系R的关系图被分为三个互不连通的部分。每部分中的结点两两都有关系，不同部分中的任意两个结点则没有关系。【例】 设R=x,y xIyIx y mod k是整数集合I上的二元关系。证明R是等价关系。 证明：设a,b,c是任意的整数。

50、 因为 a-a=k0，所以 aa mod k，a,aR。故R是自反的。 若a,bR，a b mod k，a-b = kt，tI，b-a =-(a-b)=k(t)，tI，ba mod k，b,aR。故R是对称的。 若a,bR且b,cR， a-b = kt1，t1I，b-c = kt2， t2 I， a-c=(a-b)+(b-c)=kt1+kt2=k(t1+t2)，t1+t2I，a,cR，故R是传递的。 所以R是整数集合I上的等价关系。 定义3-10.2 设R是集合A上的等价关系，对任何aA，集合aR = x xAaRx 称为元素a形成的R等价类 任意一个元素的等价类非空，包含该元素【例】设A=1

51、,2,3,4,5，R是A上的二元关系， R=1,1,1,2,2,1,2,2,3,3,3,4,4,3,4,4,5,5， R是A上的一个等价关系 其等价类为1R=2R=1,2; 3R=4R=3,4; 5R=5【例】 设R=x,y xIyIx y mod 3是整数集合I上的二元关系。 R是等价关系, 其等价类为 0R=,-6,-3,0,3,6, 1R=,-5,-2,1,4,7, 2R=,-4,-1,2,5,8, 定理3-10.1设给定集合A上的等价关系R，对于a,b A有 R当且仅当aR=bR 定义3-10.3 集合A上的等价关系R, 其等价类集合aR | a A称作A关于R的商集，记作A/R【例】

52、设A=1,2,3,4,5，R是A上的二元关系， R=1,1,1,2,2,1,2,2,3,3,3,4,4,3,4,4,5,5， R是A上的一个等价关系 A的关于R的商集A/R为1R, 3R, 5R【例】 设R=x,y xIyIx y mod 3是整数集合I上的二元关系。 R是等价关系,I关于R的商集I/R为0R,1R, 2R 在商集I/R中，0R 1R,2R=I, 且任意两个等价类的交为 定理3-10.2 集合A上的等价关系R，决定了A的一个划分，该划分就是商集A/R 定理3-10.3 集合A的一个划分确定A的元素间的一个等价关系【例】设X=1,2,3,4，X的划分S=1，2,3，4，试写出S导

53、出的等价关系R。 解：R=1,1,2,2,2,3,3,2,3,3,4,4 =112,32,344可以验证R是X上的等价关系。 定理3-10.4 设R1和R2为非空集合A上的等价关系, 则R1=R2当且仅当A/R1=A/R2【例】设X=1,2,3，写出集合X上的所有等价关系。 解：先写出集合X上的所有划分，它们是： S1=1,2,3， S2=1,2,3， S3=1,3,2 S4=2,3,1, S5=1,2,3 对应的等价关系为： R1=1,2,31,2,3 R2=1,21,233 =1,1,1,2,2,1,2,2, 3,3 R3=1,31,322 =1,1,1,3,3,1,3,3,2,2 R4=

54、2,32,311 =2,2,2,3,3,2,3,3,1,1 R5=112233=1,1,2,2,3,3 作业 (3) (4) (10) 3.11 相容关系 定义3-11.1 给定集合A上的关系r，若r是自反的，对称的，则称r是相容关系 所有的等价关系都是相容关系 相容关系的关系矩阵和关系图 相容关系的关系矩阵主对角线全为1且是对称阵。 相容关系的关系图每一个结点上都有自回路且每两个结点间如果有边，一定有方向相反的两条边。【例】设A=316,347,204,678,770，A上的二元关系r定义为：r=x,y| xAyAx和y有相同数码，证明r是A上的相容关系。写出关系矩阵和关系图。用关系矩阵和关

55、系图验证r是A上的相容关系。 证明证明: (1) 集合A中的每个数自己和自己有相同数码，故r是自反的； (2) 对于集合A中任意x和y，如果x和y有相同数码，则y和x也有相同数码。故r是对称的。于是，r是相容关系。 令a=316，b=347，c=204，d=678，e=770 用列举法将R表示为： r=a,a,a,b,a,d,b,a,b,b,b,c,b,d, b,e,c,b,c,c,c,e,d,a,d,b,d,d, d,e,e,b,e,c,e,d,e,er的关系矩阵Mr如下：Mr是一个对角线全为1的对称矩阵，所以r是相容关系r的关系图如上图：关系图每一个结点上都有自回路且每两个结点间如果有边，

56、一定有方向相反的两条边。所以r是相容关系=1111011011101101111101011RM 对于相容关系的关系矩阵一般用梯形表示，如上例中的相容关系r的关系矩阵就可表示为 1111011011101101111101011111011110101111 对于相容关系的关系图也可简化 省去每一个结点上的自回路，将两个结点间方向相反的两条有向边改为一条无向边，得到一个简化图。此图叫做R的相容关系图。 如上例中的相容关系r的关系图可表示为 定义3-11.2 设r是集合A上的相容关系，若C A, 如果对于C中任意两个元素a1和a2，有a1ra2，则称C是由相容关系r产生的相容类 注 相容类C一定

57、是A的子集。 aA，因为相容关系r是自反的，a,ar，所以a是由相容关系r产生的一个相容类。即A中的任何元素组成的单元素集是由相容关系r产生的一个相容类。【例】相容关系r=a,a,a,b,a,d,b,a,b,b,b,c,b,d, b,e,c,b,c,c,c,e,d,a,d,b,d,d, d,e,e,b,e,c,e,d,e,e a,a,b,b,c,b,d,e都是R产生的相容类。 a,bd=a,b,d和b,ce=b,c,e也是R产生的相容类。 但b,d,e与任何非空集合的并集都不再是R产生的相容类 定义 3-11.3 设r是集合A上的相容关系，不能真包含在任何其它相容类中的相容类，称为最大相容类，

58、记为Cr 注 Cr中任意元素x与Cr中的所有元素都有相容关系r。 X-Cr中没有一个元素与Cr中的所有元素都有相容的关系r。 利用相容关系的简化关系图可以求最大相容类，方法如下： (1) 最大完全多边形的顶点构成的集合是最大相容类。 (2) 孤立点构成的集合是最大相容类。 (3) 如果一条边不是任何完全多边形的边，则它的两个端点构成的集合是最大相容类。 【例】设X=1,2,3,4,5,6，r是X上的相容关系，它的相容关系图如下图所示，试找出所有最大相容类。1. 最大完全3边形的顶点构成的集合：2,3,5和2,3,4。2. 孤立点构成的集合：6。3. 不是任何完全多边形的边的两个端点构成的集合1

59、,5。最大相容类为:2,3,5，2,3,4，1,5和6。 定理3-11.1 设r是有限集A上的相容关系，C是一个相容类，那么比存在一最大相容类Cr，使得C Cr A的任意元素a可以组成相容类a，所以由上述定理可知一定存在一个最大相容类包含a A的所有最大相容类组成的集合构成A的一个覆盖 定义3-11.4 在集合A上给定相容关系r，其最大相容的集合称作集合A的完全覆盖，记作Cr(A)【例】设X=1,2,3,4,5,6，r是X上的相容关系，它的相容关系图如下图所示，最大相容类为:2,3,5，2,3,4，1,5和6。这些集合也是X的一个覆盖，即为集合X的完全覆盖 定理3-11.2 给定集合A的覆盖A

60、1,A2,An，由它确定的关系R=A1A1A2A2 AnAn是相容关系【例】设X=1,2,3,4，S1=1,2,3,3,4，S2=1,2,2,3,1,3,3,4是X的两个覆盖。试写出S1和S2 导出的相容关系R1和R2。 解：R1=1,2,31,2,33,43,4 =1,1,1,2,1,3,2,1,2,2,2,3, 3,1,3,2,3,3,3,4,4, 3,4,4 R2=1,21,22,32,3 1,31,33,43,4 =1,1,1,2,2,1,2,2,2,3,3,2, 3,3,1,3,3,1,3,4,4, 3,4,4 在上例中，S1S2，但是R1=R2。这说明不同的覆盖可以导出相同的相容关