离散数学 第5章 二元关系.ppt

《离散数学 第5章 二元关系.ppt》由会员分享，可在线阅读，更多相关《离散数学 第5章 二元关系.ppt（116页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散数学讲义之离散数学讲义之第二部分第二部分 集合论集合论集合论简介集合论简介集合是数学中最基本的概念，又是数学各分支、自然科学及社会科学各领域的最普遍采用的描述工具。集合论在开关理论、形式语言、有限状态机、编译原理、数据库原理等领域中有着广泛的应用。本篇介绍集合论的基础知识，主要内容包括集合的基本运算、序偶、关系、函数、基数等。2主要知识点关联图 有序化集合性质互异性无序性确定性集合关系集合闭包关系等价关系范式元素计数表示方法哈斯图集合运算笛卡尔积二元关系关系图序偶相容关系范式偏序关系合取范式集合分划商集关系性质等价式函数等价类集合基数等势优势函数性质不可数集合一满射可数集双射单射关系矩阵闭

2、包运算复合函数函数运算逆函数运算规律容斥原理特殊二元关系覆盖幂集3第二篇集合论目录第二篇集合论目录第第4 4章章 集合及其运算集合及其运算4.1 4.1 集合的概念及其表示集合的概念及其表示4.2 4.2 集合的基本运算集合的基本运算4.3 4.3 集合中元素的计数集合中元素的计数4.4 4.4 集合的应用集合的应用习习 题题 四四实验四实验四 集合的基本运算集合的基本运算第第5 5章章 二元关系二元关系5.1 5.1 集合的笛卡尔积集合的笛卡尔积5.2 5.2 二元关系二元关系5.3 5.3 等价关系与集合的划分等价关系与集合的划分5.4 5.4 相容关系与集合的覆盖相容关系与集合的覆盖*5

3、.5 5.5 偏序关系偏序关系5.6 5.6 关系的应用关系的应用习习 题题 五五实验五实验五 求关系的闭包求关系的闭包第第6 6章章 函数函数6.1 6.1 函数的概念函数的概念6.2 6.2 逆函数与复合函数逆函数与复合函数习习 题题 六六实验六实验六 函数的图形可视化函数的图形可视化第第7 7章章 集合的基数集合的基数*7.17.1集合的等势与优势集合的等势与优势7.27.2基数、可数集与不可数集基数、可数集与不可数集习习 题题 七七实验七：自然数性质的可视化表示实验七：自然数性质的可视化表示4第五章第五章 二元关系二元关系主要内容：主要内容：序偶与笛卡儿积；二元关系的定义和表示；关系的

4、运算；关系的性质；关系的闭包；等价关系与划分；相容关系与集合的覆盖；偏序关系；关系的应用。教学要求：教学要求：掌握序偶与笛卡尔积概念；掌握关系，关系矩阵和关系图；掌握关系的运算；掌握关系的性质；掌握关系的闭包运算；理解等价关系与等价类；理解偏序概念，会作哈斯图；了解相容关系与集合的覆盖、关系的应用。重点：重点：序偶与笛卡尔积；关系；关系的运算；关系的性质；关系的闭包运算；等价关系，偏序及哈斯图。难点：难点：关系的运算、性质、闭包运算；偏序及哈斯图。实践活动：实践活动：关系闭包运算的实现55.1 5.1 5.1 5.1 序偶与笛卡儿积序偶与笛卡儿积 定义5.1.1 由两个元素x和y（允许x=y）

5、按一定顺序排列成的二元组叫做一个有序对(ordered pair)或序偶，记作，其中x是它的第一元素，y是它的第二元素。有序对具有以下性质：（1）当xy时，。（2）的充分必要条件是xu且yv。说明说明q有序对中的元素是有序的有序对中的元素是有序的q集合中的元素是无序的集合中的元素是无序的6例例5.1.15.1.1例例5.1.1 5.1.1 已知已知 x+2,4，求求x x和和y y。由有序对相等的充要条件有由有序对相等的充要条件有 x+2x+25 52 2x+yx+y4 4 解得解得 x x3,y3,y-2-2。解答解答7定义5.1.2 设A，B为集合,用A中元素为第一元素，B中元素为第二元素

6、构成有序对。所有这样的有序对组成的集合叫做A和B的笛卡儿积(Cartesian product)，记作AB。笛卡儿积的符号化表示为AB|xAyB 笛卡儿积笛卡儿积的定义的定义qA A表示某大学所有学生的集合，表示某大学所有学生的集合，B B表示大学开设的所有表示大学开设的所有课程的集合，课程的集合，则则A AB B可以用来表示该校学生选课的所有可能情况。可以用来表示该校学生选课的所有可能情况。q令令A A是直角坐标系中是直角坐标系中x x轴上的点集，轴上的点集，B B是直角坐标系中是直角坐标系中y y轴上的点集，轴上的点集，于是于是A AB B就和平面点集一一对应。就和平面点集一一对应。举例举

7、例8笛卡尔积举例设设A=a,b,B=0,1,2A=a,b,B=0,1,2，则则AB=,AB=,BA=,BA=,举例举例说明说明q如果如果|A|=m,|B|=n,A|=m,|B|=n,则则|A AB|=B|=mnmn。910笛卡儿积的运算性质(1)对任意集合A，根据定义有A,A(2)一般的说，笛卡儿积运算不满足交换律，即ABBA(当 A B AB 时)(3)笛卡儿积运算不满足结合律，即(AB)CA(BC)(当 A B C 时)11(4)笛卡儿积运算对并和交运算满足分配律，即A(BC)=(AB)(AC)(BC)A=(BA)(CA)A(BC)=(AB)(AC)(BC)A=(BA)(CA)(5)AC

8、BD AB CD12A(BC)=(AB)(AC)的证明任取 A(BC)xA yBC xA (yByC)(xAyB)(xAyC)AB AC (AB)(AC)所以 A(BC)=(AB)(AC)13关于ACBD ABCD的讨论该性质的逆命题不成立，可分以下情况讨论。（1）当A=B=时，显然有AC 和 BD 成立。（2）当A且B时，也有AC和BD成立，证明如下：任取xA，由于B,必存在yB,因此有 xAyB AB CD xCyD xC从而证明了 AC。同理可证 BD。14关于关于A A CBCB D D AB AB CDCD的讨论的讨论该性质的逆命题不成立，可分以下情况讨论。（3）当A而B时，有AC成

9、立，但不一定有BD成立。反例：令A,B1,C3,D4。（4）当A而B时，有BD成立，但不一定有AC成立。反例略。15例例5.1.25.1.2例例5.1.25.1.2 设设A=1,2,A=1,2,求求P(A)AP(A)A。P(A)AP(A)A ,1,2,1,21,2,1,2,1,21,2 ,2,解答解答16例例5.1.35.1.3例例5.1.35.1.3 设设A A，B B，C C，D D为任意集合，判断以下命题是否为真，为任意集合，判断以下命题是否为真，并说明理由。并说明理由。(1)(1)ABABAC AC B BC C(2)(2)A-(BC)A-(BC)(A-B)(A-C)(A-B)(A-C

10、)(3)(3)A ABCBCD D AC ACBDBD(4)(4)存在集合存在集合A A，使得使得A A AAAA(1)(1)不一定为真。当不一定为真。当A A，B B1,C1,C22时，有时，有 ABABACAC，但但BCBC。(2)(2)不一定为真。当不一定为真。当A=B=1,CA=B=1,C22时，有时，有 A-(BC)A-(BC)1111 (A-B)(A-C)A-B)(A-C)11(3)(3)为真。由等量代入的原理可证。为真。由等量代入的原理可证。(4)(4)为真。当为真。当A A时，有时，有 A AAA AA 成立。成立。解答解答175.2 二元关系(binary relation)

11、定义定义5.2.1 5.2.1 如果一个集合满足以下条件之一：如果一个集合满足以下条件之一：（1 1）集合非空，且它的元素都是）集合非空，且它的元素都是有序对有序对（2 2）集合是空集）集合是空集 则称该集合为一个则称该集合为一个二元关系二元关系，记作，记作R R。二元关系也可简称为二元关系也可简称为关关系系。对于二元关系。对于二元关系R R，如果如果 Rx,yR，可记作可记作xRyxRy；如果如果 x,y R R，则记作则记作xRxRy y。设设R R1 1,，R R2 2,a,b,a,b。则则R R1 1是二元关系，是二元关系，R R2 2不是二元关系，只是一个集合，不是二元关系，只是一个

12、集合，除非将除非将a a和和b b定义为有序对。定义为有序对。根据上面的记法可以写根据上面的记法可以写1 1R R1 12 2，aRaR1 1b b，aRaR1 1c c等。等。举例举例18集合集合A A上的二元关系的数目依赖于上的二元关系的数目依赖于A A中的元素数。中的元素数。如果如果|A|=nA|=n，那么那么|A AA|=nA|=n2 2，A AA A的子集就有的子集就有 个。个。每一个子集代表一个每一个子集代表一个A A上的二元关系，所以上的二元关系，所以A A上有上有 个不个不同的二元关系。同的二元关系。例如例如|A|=3A|=3，则则A A上有上有 个不同的二元关系。个不同的二元

13、关系。定义定义5.2.25.2.2 设设A A，B B为集合，为集合，A AB B的任何子集所定义的二元关系叫的任何子集所定义的二元关系叫做做从从A A到到B B的二元关系的二元关系；特别当；特别当A=BA=B时，则叫做时，则叫做A A上的二元关系上的二元关系.A=0,1A=0,1，B=1,2,3B=1,2,3，那么那么 R R1 1=，R R2 2=A=AB B，R R3 3=，R R4 4=等都是从等都是从A A到到B B的二元关系，而的二元关系，而R R3 3和和R R4 4同时也是同时也是A A上的二上的二元关系。元关系。举例举例说明说明19定义5.6 设R是二元关系。(1)R中所有有

14、序对的第一元素构成的集合称为R的定义域(domain)，记为dom R。形式化表示为：dom R x|y(R)(2)R中所有有序对的第二元素构成的集合称为R的值域(range)，记作ran R。形式化表示为ran Ry|x(R)(3)R的定义域和值域的并集称为R的域(field)，记作fld R。形式化表示为fld Rdom R ran R 20例例5.2.1 5.2.1 求求R=,R=,的定义域、值域和域。的定义域、值域和域。解解domdom R R1,2,4 ran R1,2,4 ran R2,3,4 2,3,4 fldfld R R1,2,3,41,2,3,4 21常用的关系定义5.2.

15、3 对任意集合A，定义全域关系 EA=|xAyA=AA 恒等关系 IA=|xA空关系 设设 A=1,2A=1,2，那么那么E EA A=,=,IA A=,=,举例举例22其它常用的关系小于或等于关系：LA=|x,yAxy，其中 AR。整除关系：DB=|x,yBx整除y,其中 AZ*Z*是非零整数集包含关系：R|x,yAxy,其中 A是集合族。(1)(1)设设 A=1,2,3A=1,2,3，B Ba,ba,b则则 L LA A=,=,D DA A=,=,(2)(2)令令A=P(B)=A=P(B)=,a,b,a,b,a,b,a,b，则则A A上的包含关系是上的包含关系是 R R,a,b,举例举例2

16、3例5.2.2例5.2.2 设A=1,2,3,4，下面各式定义的R都是A上的关系，试用列元素法表示R。(1)R=|x是y的倍数(2)R=|(x-y)2A(3)R=|x/y是素数(4)R=|xy 解答解答(1)(1)R=,R=,(2)(2)R=,R=,(3)(3)R=,R=,(4)R=E(4)R=EA A-I-IA A=,=,24关系的表示方法关系的三种表示方法：集合表达式关系矩阵关系图关系矩阵和关系图可以表示有穷集上的关系。25关系矩阵和关系图的定义设设A=xA=x1 1,x,x2 2,x xn n,R,R是是A A上的关系。令上的关系。令 则则 是是R R的的关系矩阵关系矩阵，记作，记作M

17、MR R。设设A=xA=x1 1,x,x2 2,x xn n,R,R是是A A上的关系。令图上的关系。令图G=G=，其中顶点其中顶点集合集合V=AV=A，边集为边集为E E。对于对于 x xi i,x,xj jVV，满足满足 E E x xi iRxRxj j称图称图G G为为R R的的关系图关系图，记作，记作 G GR R。26关系矩阵和关系图的实例设设 A=1,2,3,4A=1,2,3,4，R=,R=,，则则R R的关系矩阵和的关系矩阵和关系关系图分别是图分别是 27关系的并、交、补、差、对称差等运算关系也是集合关系也是集合,故关系可以做并、交、补、差、对称差和故关系可以做并、交、补、差、

18、对称差和包含等运算。包含等运算。2829关系的复合运算说明说明q可以把二元关系看作一种作用，可以把二元关系看作一种作用，x,yRR可以解释为可以解释为x x通过通过R R的作用变到的作用变到y y。qR R S S表示两个作用的连续发生。表示两个作用的连续发生。303132333435363738关系与集合的说明关系是集合，集合运算对于关系也是适用的。规定：关系运算中逆运算优先于其它运算所有的关系运算都优先于集合运算，优先权的运算以括号决定运算顺序。例如：ran F-1FGFH39例题设A表示是学校的所有学生的集合，B表示学校的所有课程的集合，并设R1由所有有序对组成，其中a是选修课程b的学生

19、。R2由所有的有序对构成，其中课程b是a的必修课。则关系R1R2、R1R2、R1R2、R1R2、R2R1的含义分别为：R1R2：a是一个学生，他或者选修了课程b，或者课程b是他的必修课。R1R2：a是一个学生，他选修了课程b并且课程b也是a的必修课。40R1R2：学生a已经选修了课程b，但课程b不是a的选修课，或者课程b是a的必修课，但是a没有选修它。R1R2：学生a已经选修了课程b，但课程b不是a的选修课。R2R1：课程b是学生a的必修课，但是a没有选修它。41关系的性质自反性反自反性对称性反对称性传递性42自反性和反自反性定义5.2.5 设R为A上的关系，(1)若x(xAR)，则称R在A上

20、是自反(reflexivity)的。(2)若x(xAR)，则称R在A上是反自反(irreflexivity)的。例如 全域关系EA，恒等关系IA，小于等于关系LA，整除关系DA都是为A上的自反关系。包含关系R是给定集合族A上的自反关系。小于关系和真包含关系都是给定集合或集合族上的反自反关系。43例5.2.4例例5.2.4 5.2.4 设设A=1,2,3A=1,2,3，R R1 1，R R2 2，R R3 3是是A A上的关系，其中上的关系，其中 R R1 1,R R2 2,R R3 3说明说明R R1 1，R R2 2和和R R3 3是否为是否为A A上的自反关系和反自反关系。上的自反关系和反

21、自反关系。解答解答 R R1 1既不是自反的也不是反自反的，既不是自反的也不是反自反的，R R2 2是自反的，是自反的，R R3 3是反自反的。是反自反的。44对称性和反对称性对称性和反对称性定义5.2.6 设R为A上的关系，（1）若xy(x,yARR)，则称R为A上对称(symmetry)的关系。（2）若xy(x,yARRx=y)，则称R为A上的反对称(antisymmetry)关系。例如 A上的全域关系EA，恒等关系IA和空关系都是A上的对称关系。恒等关系IA和空关系也是A上的反对称关系。但全域关系EA一般不是A上的反对称关系，除非A为单元集或空集。45例5.2.5例5.2.5 设A1,2

22、,3，R1，R2，R3和R4都是A上的关系，其中 R1,;R2,;R3,;R4,说明R1，R2，R3和R4是否为A上对称和反对称的关系。解答 R1既是对称也是反对称的。R2是对称的但不是反对称的。R3是反对称的但不是对称的。R4既不是对称的也不是反对称的。46传递性定义5.2.7 设R为A上的关系，若 xyz(x,y,zARRR)则称R是A上的传递(transitivity)关系。例如 A上的全域关系EA,恒等关系IA和空关系都是A上的传递关系。小于等于关系，整除关系和包含关系也是相应集合上的传递关系。小于关系和真包含关系仍旧是相应集合上的传递关系。47例5.2.6例5.2.6 设A1,2,3

23、，R1，R2，R3是A上的关系，其中 R1,R2,R3说明R1，R2和R3是否为A上的传递关系。解答 R1和R3是A上的传递关系，R2不是A上的传递关系。48关系性质的等价描述 定理5.2.6 设R为A上的关系，则 （1）R在A上自反当且仅当 IA R （2）R在A上反自反当且仅当 RIA （3）R在A上对称当且仅当 RR-1 （4）R在A上反对称当且仅当 RR-1 IA （5）R在A上传递当且仅当 RRR 说明说明q利用该定理可以从关系的集合表达式来判断或证明关利用该定理可以从关系的集合表达式来判断或证明关系的性质。系的性质。分析分析关系性质的证明方法关系性质的证明方法49定理5.2.6(1

24、)的证明（1）R在A上自反当且仅当 IA R必要性。任取，有 IA x,yA xy R 所以 IA R充分性。充分性。任取任取x x，有有 xA xA IIA A RR 所以所以 R R在在A A上是自反的。上是自反的。50定理定理5.2.6(2)5.2.6(2)的证明的证明（2）R在A上反自反当且仅当 RIA充分性。充分性。任取任取x x，有有 xA xA I IA A R(RIR(RIA A=)所以所以 R R在在A A上是反自反的。上是反自反的。必要性。用反证法。必要性。用反证法。假设假设RIRIA A，必存在必存在 RIx,yRIA A。由于由于I IA A是是A A上恒等关系，上恒等

25、关系，可知可知 xAxA且且 Rx,xR。这与这与R R在在A A上是反自反的相矛盾。上是反自反的相矛盾。51定理定理5.2.6(3)5.2.6(3)的证明的证明（3）R在A上对称当且仅当 RR-1必要性。任取，有 R R(因为R在A上对称)R-1 所以 RR-1充分性。充分性。任取任取 x,y，由由 R RR R-1-1 得得 Rx,yR RR-1-1 RR 所以所以 R R在在A A上是对称的。上是对称的。52定理定理5.2.6(4)5.2.6(4)的证明的证明（4）R在A上反对称当且仅当 RR-1 IA必要性。任取，有 RR-1 R R-1 R R xy(R是反对称的)IA所以 RR-1

26、 IA充分性。充分性。任取任取,x,y,则有则有 R Rx,yR R R R R R-1-1 RR RR-1-1 I IA A (RR (RR-1-1 I IA A)x xy y所以所以 R R在在A A上是反对称的。上是反对称的。53定理定理5.2.6(5)5.2.6(5)的证明的证明（5）R在A上传递当且仅当 RRR必要性。任取，有 RR t(RR)R(因为R在A上是传递的)所以 RRR。充分性。任取,R，则 RR RR R (因为RRR)所以 R在A上是传递的。54关系性质的特点自反性反自反性对称性反对称性传递性集合表达式IA RRIARR-1RR-1 IARRR关系矩阵主对角线元素全是

27、1主对角线元素全是0 矩阵是对称矩阵 若rij1，且ij，则rji0 对M2中1所在位置，M中相应的位置都是1 关系图每个顶点都有环每个顶点都没有环 如果两个顶点之间有边，一定是一对方向相反的边(无单边)如果两点之间有边，一定是一条有向边(无双向边)如果顶点xi到xj有边，xj到xk有边，则从xi到xk也有边 55例5.2.7例5.2.7 判断下图中关系的性质，并说明理由。（1 1）对称的，不是自反的，不是反自反的，不是反对称的，）对称的，不是自反的，不是反自反的，不是反对称的，不是传递的。不是传递的。（2 2）是反自反的，不是自反的，是反对称的，不是对称的，）是反自反的，不是自反的，是反对称

28、的，不是对称的，是传递的是传递的。（3 3）是自反的，不是反自反的，是反对称的，不是对称的，是自反的，不是反自反的，是反对称的，不是对称的，不是传递的。不是传递的。56关系的性质和运算之间的关系自反性反自反性对称性反对称性传递性R1-1R1R2R1R2R1R2R1 R257关系的闭包(closure)闭包的定义闭包的构造方法闭包的性质闭包的相互关系58闭包的定义 定义5.2.8 设R是非空集合A上的关系，R的自反（对称或传递）闭包是A上的关系R,使得 R满足以下条件：（1）R是自反的（对称的或传递的）（2）RR（3）对A上任何包含R的自反（对称或传递）关系R有R R。一般将R的自反闭包记作r(

29、R)，对称闭包记作s(R)，传递闭包记作t(R)。59闭包的主要性质60闭包的构造方法定理5.2.8 设R为A上的关系，则有（1）r(R)RR0（2）s(R)RR-1（3）t(R)RR2R3 证明思路(1)和(2)：证明右边的集合满足闭包定义的三个条件。(3)采用集合相等的证明方法。证明左边包含右边，即t(R)包含每个Rn。证明右边包含左边，即RR2具有传递的性质。61定理5.2.8(1)的证明（1）r(R)RR0证明证明由由I IA AR R0 0 RRRR0 0，可知可知RRRR0 0是自反的，是自反的，R R RRRR0 0。设设R R是是A A上包含上包含R R的自反关系，的自反关系，

30、则有则有R R R R和和I IA A R R。任取任取 x,y，必有必有 RRx,yRR0 0 RIRIA A RRRRR R 所以所以 RRRR0 0 R R。综上所述，综上所述，r(R)r(R)RRRR0 0。62定理定理5.2.8(2)5.2.8(2)的证明的证明（2）s(R)RR-1证明证明 R R RRRR-1-1。证明证明RRRR-1-1是对称的，是对称的，任取任取 x,y，有有 RRx,yRR-1-1 RRRR-1-1 RR-1-1RR RRy,xRR-1-1 所以所以 RRRR-1-1 是对称的是对称的。综上所述，综上所述，s(R)s(R)RRRR-1-1。设设R R是包含是

31、包含R R的的对称关系，对称关系，任取任取 x,y，有有 RRx,yRR-1-1 RRRR-1-1 RRRR RRRR RRRR Rx,yR 所以所以 RRRR-1-1 R R。63定理定理5.2.8(3)5.2.8(3)的证明的证明（3）t(R)RR2R3 证明证明先证先证RR2RR2 t(R)t(R)成立，为此只需证明对任意的正成立，为此只需证明对任意的正整数整数n n有有 R Rn n t(R)t(R)即可。用归纳法。即可。用归纳法。n n1 1时，有时，有 R R1 1R R t(R)t(R)。假设假设R Rn n t(R)t(R)成立，那么对任意的成立，那么对任意的 x,y有有 Rx

32、,yRn+1n+1R Rn n R R t(t(R Rn nR)R)t(t(R)t(R)t(t(R)t(R)t(R)t(R)（因为因为t(R)t(R)是传递的）是传递的）这就证明了这就证明了R Rn+1 n+1 t(R)t(R)。由归纳法命题得证。由归纳法命题得证。64定理定理5.2.8(3)5.2.8(3)的证明的证明（3）t(R)RR2R3 证明证明再证再证t(R)t(R)RRRR2 2成立，为此只须证明成立，为此只须证明RRRR2 2是传是传递的。递的。任取任取,x,y,，则则 RRx,yRR2 2 RR RR2 2 t(t(R Rt t)s(s(R Rs s)t t s(s(R Rt

33、t R Rs s)t t s(s(R Rt t R Rs s)t t s(s(R Rt+st+s)RR RR2 2 从而证明了从而证明了RRRR2 2是传递的。是传递的。65推论推论推论 设R为有穷集A上的关系，则存在正整数r使得t(R)=RR2Rr例题 求整数集合Z上的关系R|ab的自反闭包和对称闭包。解答 r(R)RR0|ab|ab|ab s(R)RR-1|ab|ba|ab66通过关系矩阵求闭包的方法设关系R，r(R)，s(R)，t(R)的关系矩阵分别为M，Mr，Ms和Mt，则Mr ME(对角线上的值都改为1)Ms MM(若aij1，则令aji1)Mt MM2M3(沃舍尔算法)其中E是和M

34、同阶的单位矩阵，M是M的转置矩阵。注意在上述等式中矩阵的元素相加时使用逻辑加。67通过关系图求闭包的方法 设关系R，r(R)，s(R)，t(R)的关系图分别记为G，Gr，Gs，Gt，则Gr，Gs，Gt的顶点集与G的顶点集相等。除了G的边以外，以下述方法添加新的边。1)考察G的每个顶点，如果没有环就加上一个环。最终得到的是Gr。2)考察G的每一条边，如果有一条xi到xj的单向边，ij，则在G中加一条边xj到xi的反方向边。最终得到Gs。3)考察G的每个顶点xi，找出从xi出发的所有2步，3步，n步长的路径（n为G中的顶点数）。设路径的终点为 。如果没有从xi到 (l=1,2,k)的边，就加上这条

35、边。当检查完所有的顶点后就得到图Gt。68例例5.2.85.2.8 例5.2.8 设A=a,b,c,d，R=,，则R和r(R)，s(R)，t(R)的关系图如下图所示。其中r(R)，s(R)，t(R)的关系图就是使用上述方法直接从R的关系图得到的。69Warshall 算法输入：M（R的关系矩阵）输出：MT（t(R)的关系矩阵）1.MTM2.for k 1 to n do3.for i 1 to n do4.for j 1 to n do5.MTi,jMTi,j+MTi,k*MTk,j注意：算法中矩阵加法和乘法中的元素相加都使用逻辑加(即1+11,1+00+11,0+00)。70Warshall

36、 算法 举例例 设A=a,b,c,d，R=,，求t(R)。分析分析 k k1 1 时，时，M MT Ti,jMi,jMT Ti,j+Mi,j+MT Ti,1*Mi,1*MT T1,j1,j M MT T1,jM1,jMT T1,j+M1,j+MT T1,1*M1,1*MT T1,j1,j M MT T2,jM2,jMT T2,j+M2,j+MT T2,1*M2,1*MT T1,j 1,j 将第将第1 1行加到第行加到第2 2行上行上 M MT T3,jM3,jMT T3,j+M3,j+MT T3,1*M3,1*MT T1,j1,j M MT T4,jM4,jMT T4,j+M4,j+MT T4

37、,1*M4,1*MT T1,j1,j 得到得到M M1 1。71Warshall 算法 举例k k1 1时，时，第第1 1列中只有列中只有M2,1M2,11 1，将第将第1 1行加到第行加到第2 2行上。行上。k k2 2时，时，第第2 2列中列中M1,2M1,2 M2,2M2,2M4,2M4,21 1，将第将第2 2行分别加到第行分别加到第1,2,41,2,4行上。行上。72WarshallWarshall 算法算法 举例举例k k3 3时，时，第第3 3列中列中M1,3M1,3M2,3M2,3M4,3M4,31 1，将第将第3 3行分别加到行分别加到第第1,2,41,2,4行上。行上。k

38、k4 4时，时，第第4 4列中列中M1,4M1,4 M2,4M2,4M3,4M3,4M4,4M4,41 1，将第将第4 4行分别加到第行分别加到第1,2,3,41,2,3,4行上。行上。73闭包的复合闭包的复合 74757677785.3 等价关系与集合的划分A2A5A3A4A1798081 定义5.3.4 设R为非空集合上的关系。如果R是自反的、对称的和传递的，则称R为A上的等价关系(equivalent relation)。设R是一个等价关系，若R，称x等价于y，记做x y。举例(1)平面上三角形集合中，三角形的相似关系。(2)人群中的同性关系。82例5.3.2例5.3.2 设A1,2,8

39、，如下定义A上的关系R：R|x，yAxy(mod 3)其中xy(mod 3)叫做x与y模3相等，即x除以3的余数与y除以3的余数相等。不难验证R为A上的等价关系，因为xA，有xx(mod 3)x,yA，若xy(mod 3)，则有yx(mod 3)x,y,zA，若xy(mod 3)，yz(mod 3)，则有xz(mod 3)83等价类定义5.3.5 设R为非空集合A上的等价关系，xA，令 xR=y|yAxRy称xR为x关于R的等价类，简称为x的等价类，简记为x或 x。qx x的等价类是的等价类是A A中所有与中所有与x x等价的元素构成的集合。等价的元素构成的集合。q例例5.3.25.3.2中的

40、等价类是：中的等价类是：1144771,4,71,4,72255882,5,82,5,833663,6 3,6 84等价类的性质定理5.3.3 设R是非空集合A上的等价关系，则（1）xA，x是A的非空子集。（2）x,yA，如果xRy，则xy。（3）x,yA，如果R，则x与y不交。（4）x|xAA。证明（1）由等价类的定义可知，xA有xA。又由于等价关系的自反性有xx，即x非空。85（2）x,yA，如果xRy，则x=y。任取z，则有 zx R R(因为R是对称的)R R R(因为R是传递的)R (因为R是对称的)zy。所以 xy；同理可证 yx。因此，x=y。86（3）x,yA，如果R，则x与y

41、不交。假设 xy，则存在 zxy，从而有 zxzy，即RR成立。根据R的对称性和传递性，必有R，与R矛盾，即假设错误，原命题成立。87（4）x|xAA。先证 x|xAA任取y，yx|xA x(xAyx)yA (因为xA)从而有x|xA A。再证 Ax|xA 任取y，yA yyyA yx|xA从而有Ax|xA成立。综上所述得 x|xAA。88商集定义5.3.6 设R为非空集合A上的等价关系，以R的所有等价类作为元素的集合称为A关于R的商集(quotient set)，记做A/R，即A/R=xR|xA例5.3.2中的商集为1,4,7,2,5,8,3,6整数集合Z上模n等价关系的商集是 nz+i|z

42、Z|i=0,1,n-189商集与划分商集就是A的一个划分，并且不同的商集将对应于不同的划分。反之，任给A的一个划分，如下定义A上的关系R：R=|x,yAx与y在的同一划分块中则不难证明R为A上的等价关系，且该等价关系所确定的商集就是。由此可见，A上的等价关系与A的划分是一一对应的。90例5.3.3例5.3.3 给出A1,2,3上所有的等价关系这些划分与这些划分与A A上的等价关系之间的一一对应是：上的等价关系之间的一一对应是：1 1对应于全域关系对应于全域关系E EA A，5 5的对应于恒等关系的对应于恒等关系I IA A，2 2，3 3和和4 4分别对应于等价关系分别对应于等价关系R R2

43、2，R R3 3和和R R4 4。其中其中 R R2 2=,I=,IA A R R3 3=,I=,IA A R R4 4=,I=,IA A91相容关系与集合的覆盖*92相容关系与相容类 9394955.5 偏序(partial order)关系定义5.5.1 设R为非空集合A上的关系。如果R是自反的、反对称的和传递的，则称R为A上的偏序关系，记作。序偶称为偏序集。设为偏序关系，如果，则记作xy，读作“x小于或等于y”。注意 这里的“小于或等于”不是指数的大小，而是在偏序关系中的顺序性。x“小于或等于”y的含义是：依照这个序，x排在y的前边或者x就是y。根据不同偏序的定义，对序有着不同的解释。9

44、697偏序集的哈斯（Hasse）图 9899100偏序集中的特殊元 101102103可比 (1)x,yA，xy xyxy。(2)x,yA，x与y可比 xyyx。其中xy读作x“小于”y。这里所说的“小于”是指在偏序中x排在y的前边。在具有偏序关系的集合A中任取两个元素x和y，可能有下述几种情况发生：xy(或yx)，xy，x与y不是可比的。例如A1，2，3，是A上的整除关系，则有 12，13，1=1，2=2，3=3，2和3不可比。104全序关系及其应用 定义5.5.5 设R为非空集合A上的偏序关系，如果x,yA，x与y都是可比的，则称R为A上的全序关系(或线序关系)。例如数集上的小于或等于关系

45、是全序关系，因为任何两个数总是可比大小的。整除关系一般来说不是全序关系，如集合1,2,3上的整除关系就不是全序关系，因为2和3不可比。105106107注意：定理中的“有限”条件非常重要，如果是无限全序集，如负整数集Z-，对数的小于等于关系，不构成良序集，因为,-4,-2Z-对数的小于等于关系，不存在最小元。108关系的应用 等价关系在计算机中的应用 序关系在项目管理中的应用 109例题补充例 画出偏序集和的哈斯图。110例题补充例 已知偏序集的哈斯图如右图所示，试求出集合A和关系R的表达式。解答解答A=a,b,c,d,e,f,g,hA=a,b,c,d,e,f,g,hR=R=,IIA A 11

46、1偏序集中的特殊元素363242126B最大元最小元极大元极小元2,3,6,12,24,366,122,3,66无无 无无 24,26 2,312 12 6 6 12 6 6 6 无无 6 2,3 6 6 6 6 6 6112例 设偏序集如右图所示，求A的极小元、最小元、极大元、最大元。解答解答极小元：极小元：a,b,c,ga,b,c,g极大元：极大元：a,f,ha,f,h。没有最小元与最大元没有最小元与最大元说说明明哈斯图中的孤立顶点既是极小元也是极大元。哈斯图中的孤立顶点既是极小元也是极大元。113上界与下界举例363242126B上界下界上确界下确界2,3,6,12,24,366,122

47、,3,66 无无 无无 无无 无无12,24,36 2,3,612,24,36 2,3,6 12 6 12 66,12,24,36 6,12,24,36 无无 6 6 无无6,12,24,366,12,24,36 2,3,6 6 6 2,3,6 6 6q考虑右考虑右图图中的偏序集。令中的偏序集。令B Bbb，c c，dd，则则B B的下界和最大下界都的下界和最大下界都不存在，上界有不存在，上界有d d和和f f，最小上界最小上界为为d d。114作业：习题五1、3、4、7、8、12、13、14、15、16、20、21 115实验五 求关系的闭包运算求关系的闭包运算 1.实验目的:熟悉关系的自反、对称、传递等闭包的求法。2.实验内容 编程求关系的自反、对称、传递闭包。3.实验要求 列出实验目的、实验内容、实验步骤、源程序和实验结果。4.实验参考116