1、离离 散散 数数 学学 周周 塔塔计算机教研室计算机教研室 年年9 9月月江苏科技大学本科生必修课程江苏科技大学本科生必修课程第第7 7章章 二元关系二元关系1/921本章说明本章说明q本章主要内容本章主要内容有序对与笛卡儿集有序对与笛卡儿集二元关系定义和表示法二元关系定义和表示法关系运算关系运算关系性质关系性质关系闭包关系闭包等价关系与划分等价关系与划分偏序关系偏序关系q本章与后续各章关系本章与后续各章关系本章是图论基础本章是图论基础 2/922本章内容7.1有序对与笛卡儿积7.2二元关系7.3关系运算7.4关系性质7.5关系闭包7.6等价关系与划分7.7偏序关系本章小结习题作业3/9237
2、.1 7.1 有序对与笛卡儿积有序对与笛卡儿积 定义定义7.1由两个元素x和y（允许x=y）按一定次序排列成二元组叫做一个有序对有序对(orderedpair)或序偶序偶，记作，其中x是它第一元素，y是它第二元素。有序对有序对含有以下性质：含有以下性质：（1）当xy时，。（2）充分必要条件是xu且yv。说明说明q有序有序对中元素是有序中元素是有序q集合中元素是无序集合中元素是无序4/924例例7.17.1例例7.17.1 已知已知 x+2,4，求求x x和和y y。由有序对相等充要条件有由有序对相等充要条件有 x+2x+25 52 2x+yx+y4 4 解得解得 x x3,y3,y-2-2。解
3、答解答5/925定义定义7.2设A，B为集合,用A中元素为第一元素，B中元素为第二元素组成有序对。全部这么有序对组成集合叫做A和B笛卡儿积笛卡儿积(Cartesianproduct)，记作AB。笛卡儿积符号化表示为AB|xAyB笛卡儿积定义笛卡儿积定义qA A表示某大学全部学生集合，表示某大学全部学生集合，B B表示大学开设全部课程表示大学开设全部课程集合，集合，则则ABAB能够用来表示该校学生选课全部可能情况。能够用来表示该校学生选课全部可能情况。q令令A A是直角坐标系中是直角坐标系中x x轴上点集，轴上点集，B B是直角坐标系中是直角坐标系中y y轴轴上点集，上点集，于是于是ABAB就和
4、平面点集一一对应。就和平面点集一一对应。举例举例6/926笛卡尔积举例设设A=a,b,B=0,1,2A=a,b,B=0,1,2，则则AB=,AB=,BA=,BA=,举例举例说明说明q假如假如|A|=m,|B|=n,则|AB|=mn。7/927笛卡儿积运算性质(1)对任意集合A，依据定义有A,A(2)普通说，笛卡儿积运算不满足交换律，即ABBA(当ABAB时)(3)笛卡儿积运算不满足结合律，即(AB)CA(BC)(当ABC时)(4)笛卡儿积运算对并并和交交运算满足分配律，即A(BC)=(AB)(AC)(BC)A=(BA)(CA)A(BC)=(AB)(AC)(BC)A=(BA)(CA)8/928A
5、(BC)=(AB)(AC)证实任取A(BC)xAyBCxA(yByC)(xAyB)(xAyC)ABAC(AB)(AC)所以A(BC)=(AB)(AC)9/929例例7.27.2例7.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,解答解答10/9210例例7.37.3例7.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)(
6、A-C)(3)(3)A ABCBCD D AC ACBDBD(4)(4)存在集合存在集合A A，使得使得A A AA AA(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 成立。成立。解答解答11/92117.2 二元关系(binary re
7、lation)定义定义7.37.3 假如一个集合满足以下条件之一：假如一个集合满足以下条件之一：（1 1）集合非空，且它元素都是有序对）集合非空，且它元素都是有序对（2 2）集合是空集）集合是空集 则称该集合为一个则称该集合为一个二元关系二元关系，记作，记作R R。二元关系也可简称为二元关系也可简称为关关系系。对于二元关系。对于二元关系R R，假如假如 Rx,yR，可记作可记作xRyxRy；假如假如 x,y R R，则记作则记作xRyxRy。设设R R1 1,，R R2 2,a,b,a,b。则则R R1 1是二元关系，是二元关系，R R2 2不是二元关系，只是一个集合，不是二元关系，只是一个集
8、合，除非将除非将a a和和b b定义为有序对。定义为有序对。依据上面记法能够写依据上面记法能够写1 1R R1 12 2，aRaR1 1b b，aRaR1 1c c等。等。举例举例R R,是否为二元关系？是否为二元关系？12/9212集合集合A A上二元关系数目依赖于上二元关系数目依赖于A A中元素数。中元素数。假如假如|A|=nA|=n，那么那么|AA|=nAA|=n2 2，AA AA子集就有子集就有 个。个。每一个子集代表一个每一个子集代表一个A A上二元关系，所以上二元关系，所以A A上有上有 个不一个不一样二元关系。样二元关系。比如比如|A|=3A|=3，则则A A上有上有 个不一样二
9、元关系。个不一样二元关系。7.2 7.2 二元关系二元关系定义定义7.47.4 设设A A，B B为集合，为集合，ABAB任何子集所定义二元关系叫做任何子集所定义二元关系叫做从从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=AB=AB，R R3 3=，R R4 4=等都是从等都是从A A到到B B二元关系，而二元关系，而R R3 3和和R R4 4同时也是同时也是A A上二元关上二元关系。系。举例举例说明说明13/9213惯用关系定义定义7.
10、5对任意集合A，定义全域关系全域关系EA=|xAyA=AA恒等关系恒等关系IA=|xA空关系空关系设设 A=1,2A=1,2，那么那么E EA A=,=,I IA A=,=,举例举例14/9214其它惯用关系o小于或等于关系:LA=|x,yAxy，其中AR。o整除关系:DB=|x,yBx整除y，其中AZ*Z*是非零整数集o包含关系: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上包含关系是上包含关系是
11、R R,a,b,举例举例15/9215例7.4例7.4设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=,=,16/9216关系表示方法o关系三种表示方法：n集合表示式n关系矩阵n关系图o关系矩阵和关系图能够表示有穷集上关系。17/9217关系矩阵和关系图定义设设A=xA=x1 1,x,x2 2,x,xn n,R,R是是A A上关系。令上关系。令 则则 是是R R
12、关系矩阵关系矩阵，记作，记作M 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。18/9218关系矩阵和关系图实例设设 A=1,2,3,4A=1,2,3,4，R=,R=,，则则R R关系矩阵和关系图分别是关系矩阵和关系图分别是 19/92197.3 关系运算定义7.6设R是二元关系。(1)R中全部有序对第一元素组成集合称为R定
13、义域定义域(domain)，记为domR。形式化表示为：domR x|y(R)(2)R中全部有序正确第二元素组成集合称为R值域值域(range)，记作ranR。形式化表示为:ranRy|x(R)(3)R定义域和值域并集称为R域域(field)，记作fldR。形式化表示为:fldRdomRranR例例7.57.5 求求R=,R=,定义域、值域和域。定义域、值域和域。解答解答:dom Rdom R1,2,4 ran R1,2,4 ran R2,3,4 fld R2,3,4 fld R1,2,3,4 1,2,3,4 20/9220关系逆和右复合运算定义7.7设R为二元关系，R逆关系，简称R逆逆(in
14、verse)，记作R-1,其中R-1|R定义7.8设F,G为二元关系，G对F右复合右复合(composite)记作FG，其中FG|t(FG)例7.6设F,G=，则F-1,FGGF说明说明能够把二元关系看作一个作用，能够把二元关系看作一个作用，x,yRR能够解释为能够解释为x x经过经过R R作用变到作用变到y y。F F G G表示两个作用连续发生。表示两个作用连续发生。21/9221关系限制和像定义7.9设R为二元关系，A是集合(1)R在A上限制限制(restriction)记作RA，其中RA=|xRyxA(2)A在R下像像(image)记作RA，其中RA=ran(RA)说明说明 R R在在
15、A A上限制上限制RARA是是R R子关系。子关系。A A在在R R下像下像RARA是是ran Rran R子集。子集。22/9222例7.7设设R R，RR11，RR RR2,32,3，RR112,32,3RR RR332223/9223关系逆和右复合运算定义7.7设R为二元关系，R逆关系，简称R逆逆(inverse)，记作R-1,其中R-1|R定义7.8设F,G为二元关系，G对F右复合右复合(composite)记作FG，其中FG|t(FG)例7.6设F,G=，则F-1,FGGF说明说明q能够把二元关系看作一个作用，能够把二元关系看作一个作用，x,yRR能够解释为能够解释为x x经过经过R
16、 R作用变到作用变到y y。qF F G G表示两个作用连续发生。表示两个作用连续发生。24/9224关系与集合说明o关系是集合，集合运算对于关系也是适用。o要求：n关系运算中逆运算优先于其它运算n全部关系运算都优先于集合运算，n优先权运算以括号决定运算次序。o比如：nranF-1nFGFHnran(FA)25/9225例题o设A表示是学校全部学生集合，B表示学校全部课程集合，并设R1由全部有序对组成，其中a是选修课程b学生。R2由全部有序对组成，其中课程b是a必修课。则关系R1R2、R1R2、R1R2、R1R2、R2R1含义为oR1R2：a是一个学生，他或者选修了课程b，或者课程b是他必修课
17、。oR1R2：a是一个学生，他选修了课程b而且课程b也是a必修课。oR1R2：学生a已经选修了课程b，但课程b不是a选修课，或者课程b是a必修课，不过a没有选修它。oR1R2:学生a已经选修了课程b，但课程b不是a选修课。oR2R1：课程b是学生a必修课，不过a没有选修它。26/9226定理7.1定理定理7.1设F是任意关系，则(1)(F-1)-1F(2)domF-1ranF，ranF-1domF(1)(1)任取任取 x,y，由逆定义有由逆定义有 x,y(F(F-1-1)-1-1 F F-1-1 F F (2)(2)任取任取x x x xdom dom F F-1-1 y y(x,(FF-1-
18、1)y y(F),xF)xran F xran F 所以有所以有 dom Fdom F-1-1ran Fran F证实证实27/9227定理7.2定理7.2设F，G，H是任意关系，则(1)(FG)HF(GH)(2)(FG)-1G-1 F-1证实证实(1)(1)任取任取 x,y，x,y(F F G)G)H H t t(x,(FF G(G(t t,y)H),y)H)t t(s s(x,(FFG)G)H),yH)t t s s(x,(FFGGH),yH)s s(x,(FF t t(GGH),yH)s s(x,(FFG,yG H)H)x,yF F(G G H)H)28/9228定理定理7.27.2定理
19、定理7.2设F，G，H是任意关系，则(1)(FG)HF(GH)(2)(FG)-1G-1F-1证实证实(2)(2)任取任取 x,y，x,y(F(F G)G)-1-1 FF G G t t(y,(FFG),xG)t t(F,yF-1-1x,GG-1-1)G G-1-1 F F-1-129/9229定理定理7.37.3定理定理7.3设R为A上关系，则RIAIARR证实证实(1)(1)任取任取 x,y，x,y R R I IA A t(x,t(R(R(t t,y)I,y)IA A)t(x,t(RRt ty)y)R R x,yR R RyARyA RI RIA A)R R I IA A总而言之，有总而言
20、之，有 R R I IA AR R同理可证同理可证 I IA A R RR R30/9230定理定理7.47.4定理7.4设F，G，H是任意关系，则(1)F(GH)FGFH(2)(GH)FGFHF(3)F(GH)F GF H(4)(GH)FGFHF证实证实(3)(3)x,yF F(GH)GH)t t(x,(F(F(t t,y)GH),y)GH)t t(x,(F(F(t t,y)G(,y)G(t t,y)H),y)H)t t(x,F(F(t t,y)G,y)G)(x,F(F(t t,y)H,y)H)t t(x,(F(F(t t,y)G),y)G)t t(x,(F(F(t t,y)H),y)H)F
21、 F G G F F H H x,yF F GFGF H H31/9231定理7.4推论o由数学归纳法不难证实定理7.4结论对于有限多个关系并和交也是成立，即有R(R1R2Rn)RR1RR2RRn(R1R2Rn)RR1RR2RRnRR(R1R2Rn)RR1RR2RRn(R1R2Rn)RR1RR2RRnR32/9232定理定理7.57.5定理7.5设F为关系，A,B为集合，则(1)F(AB)FAFB(2)FABFAFB(3)F(AB)FAFB(4)FAB FAFB33/9233定理定理7.5(1)7.5(1)证实证实(1)F(AB)FAFB证实证实任取任取 x,y，F(AB)F(AB)F x(A
22、B)F x(AB)F (xAxB)F (xAxB)(FxA)(FxB)(FxA)(FxB)F FA FA FB B F FAFAFB B 所以有所以有 F(AB)F(AB)FAFBFAFB。34/9234定理定理7.5(4)7.5(4)证实证实(4)FAB FAFB证实证实任取任取y y，yFAB yFAB x x(F,yFx xAB)AB)x x(F,yFx xAAx xB)B)x x(F,yFx xA)(A)(F,yFx xB)B)x x(F,yFx xA)A)x x(F,yFx xB)B)yFA yFB yFA yFB yFAFByFAFB所以有所以有 FABFABFAFB FAFB 注
23、意注意(1)(1)和和(4)(4)证实区分证实区分35/9235关系幂运算定义定义7.10设R为A上关系，n为自然数，则Rn次幂定义为：（1）R0|xAIA（2）Rn+1RnR说明说明对于对于A A上任何关系上任何关系R R1 1和和R R2 2都有都有R R1 10 0R R2 20 0I IA A 即：即：A A上任何关系上任何关系0 0次幂都相等，都等于次幂都相等，都等于A A上恒等关系上恒等关系I IA A。对于对于A A上任何关系上任何关系R R都有都有R R1 1R R，因为因为R R1 1R R0 0 R RI IA A R RR R36/9236Rn计算o给定A上关系R和自然数
24、n，怎样计算Rn呢？o若n是0或1，结果是很简单。下面考虑n2情况。n假如R是用集合表示式给出，能够经过n-1次右复合计算得到Rn。n假如R是用关系矩阵M给出，则Rn关系矩阵是Mn，即n个矩阵M之积。与普通矩阵乘法不一样是，其中相加是逻逻辑加辑加，即1+11，1+00+11，0+00n假如R是用关系图G给出，能够直接由图G得到Rn关系图G。G顶点集与G相同。考查G每个顶点xi，假如在G中从xi出发经过n步长路径抵达顶点xj，则在G中加一条从xi到xj边。当把全部这么便都找到以后，就得到图G。37/9237例7.8例7.8设Aa,b,c,d，R,，求R各次幂，分别用矩阵和关系图表示。解答解答38
25、/9238例7.8所以M4M2，即R4R2。所以能够得到R2R4R6R3R5R739/9239定理7.7定理7.7设R是A上关系，m,nN，则(1)RmRnRm+n(2)(Rm)nRmn证实证实(1)(1)对于任意给定对于任意给定mN,mN,主要归纳于主要归纳于n n。若若n=0n=0，则有则有所以对一切所以对一切m,nNm,nN有有 R Rm m R Rn nR Rm+nm+n。R Rm m R R0 0 R Rm m I IA A R Rm m R Rm+0m+0假设假设R Rm m R Rn n=R=Rm+nm+n，则有则有R Rm m R Rn+1n+1 R Rm m (R(Rn n
26、R)R)(R(Rm m R Rn n)R R R Rm+n+1m+n+1，40/9240定理定理7.77.7定理7.7设R是A上关系，m,nN，则(1)RmRnRm+n(2)(Rm)nRmn证实证实(2)(2)对于任意给定对于任意给定mN,mN,主要归纳于主要归纳于n n。若若n=0n=0，则有则有所以对一切所以对一切m,nN m,nN 有有(R Rm m)n n=R=Rmnmn。(R Rm m)0 0 I IA A R R0 0 R Rm0m0假设假设(R Rm m)n nR Rmnmn，则有则有(R Rm m)n+1n+1(R(Rm m)n n R Rm m R Rmn+mmn+m R R
27、m(n+1)m(n+1)41/92417.4 关系性质o自反性o反自反性o对称性o反对称性o传递性42/9242自反性和反自反性定义定义7.11设R为A上关系，(1)若x(xAR)，则称R在A上是自反(reflexivity)。(2)若x(xA R)，则称R在A上是反自反(irreflexivity)。比如全域关系EA，恒等关系IA，小于等于关系LA，整除关系DA都是为A上自反关系。包含关系R是给定集合族A上自反关系。小于关系和真包含关系都是给定集合或集合族上反自反关系。43/9243例7.10例例7.107.10 设设A=1,2,3A=1,2,3，R R1 1，R R2 2，R R3 3是是
28、A A上关系，其中上关系，其中R R1 1,R R2 2,R R3 3说明说明R R1 1，R R2 2和和R R3 3是否为是否为A A上自反关系和反自反关系。上自反关系和反自反关系。解答解答 R R1 1既不是自反也不是反自反，既不是自反也不是反自反，R R2 2是自反，是自反，R R3 3是反自反。是反自反。44/9244对称性和反对称性对称性和反对称性定义7.12设R为A上关系，（1）若xy(x,yARR)，则称R为A上对称(symmetry)关系。（2）若xy(x,yARxy R)，则称R为A上反对称(antisymmetry)关系。比如A上全域关系EA，恒等关系IA和空关系都是A上
29、对称关系。恒等关系IA和空关系也是A上反对称关系。但全域关系EA普通不是A上反对称关系，除非A为单元集或空集。45/9245例7.11例例7.11设A1,2,3，R1，R2，R3和R4都是A上关系，其中R1,R2,R3,R4,说明R1，R2，R3和R4是否为A上对称和反对称关系。解答解答 R1既是对称也是反对称。R2是对称但不是反对称。R3是反对称但不是对称。R4既不是对称也不是反对称。46/9246传递性定义定义7.13设R为A上关系，若xyz(x,y,zARRR)则称R是A上传递传递(transitivity)关系。比如比如A上全域关系EA,恒等关系IA和空关系都是A上传递关系。小于等于关
30、系，整除关系和包含关系也是对应集合上传递关系。小于关系和真包含关系依旧是对应集合上传递关系。47/9247例7.12例例7.12设A1,2,3，R1，R2，R3是A上关系，其中R1,R2,R3说明R1，R2和R3是否为A上传递关系。解答解答 R1和R3是A上传递关系，R2不是A上传递关系。48/9248关系性质等价描述 定理7.9设R为A上关系，则（1）R在A上自反当且仅当IAR（2）R在A上反自反当且仅当RIA（3）R在A上对称当且仅当RR-1（4）R在A上反对称当且仅当RR-1IA（5）R在A上传递当且仅当RRR说明说明利用该定理能够从关系集合表示式来判断或证实关系性利用该定理能够从关系集
31、合表示式来判断或证实关系性质。质。分析分析关系性质证实方法关系性质证实方法49/9249定理7.9(1)证实（1）R在A上自反当且仅当IAR必要性。任取，有IAx,yAxyR所以IAR充分性充分性。任取任取x x，有有 x xAA IIA A RR 所以所以 R R在在A A上是自反。上是自反。50/9250定理定理7.9(2)7.9(2)证实证实（2）R在A上反自反当且仅当RIA充分性。充分性。任取任取x x，有有 xA xA I IA A R(RIR(RIA A=)所以所以 R R在在A A上是反自反。上是反自反。必要性。用反证法。必要性。用反证法。假设假设RIRIA A，必存在必存在 R
32、Ix,yRIA A。因为因为I IA A是是A A上恒等关系，上恒等关系，可知可知 xAxA且且 Rx,xR。这与这与R R在在A A上是反自反相矛盾。上是反自反相矛盾。51/9251定理定理7.9(3)7.9(3)证实证实（3）R在A上对称当且仅当RR-1必要性。必要性。任取，有RR(因为R在A上对称)R-1所以RR-1充分性。充分性。任取任取 x,y，由由 R RR R-1-1 得得 Rx,yR RR-1-1 RR 所以所以 R R在在A A上是对称。上是对称。52/9252定理定理7.9(4)7.9(4)证实证实（4）R在A上反对称当且仅当RR-1IA必要性。任取，有RR-1RR-1RR
33、xy(R是反对称)IA所以RR-1IA充分性。充分性。任取任取,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/9253定理定理7.9(5)7.9(5)证实证实（5）R在A上传递当且仅当RRR必要性。任取，有RRt(RR)R(因为R在A上是传递)所以RRR。充分性。任取,R，则RRRRR(因为RRR)所以R在A上是传递。54/9254例7.13例例7.13设A是集合，R1和R2是A上关系，证实：若R1，R2是自反和对称，则R1R2也是自反和对称
34、。55/9255例例7.13(1)7.13(1)证实证实若R1，R2是自反和对称，则R1R2也是自反和对称。证实证实因为因为R R1 1和和R R2 2是是A A上自反关系，故有上自反关系，故有I IA A R R1 1 和和 I IA A R R2 2从而得到从而得到 I IA A R R1 1RR2 2。依据定理可知依据定理可知 R R1 1RR2 2在在A A上是自反。上是自反。再由再由R R1 1和和R R2 2对称性有对称性有R R1 1R R1 1-1-1 和和 R R2 2R R2 2-1-1依据定理有依据定理有(R R1 1RR2 2)-1-1R R1 1-1-1RR2 2-1
35、-1R R1 1RR2 2从而证实了从而证实了R R1 1RR2 2也是也是A A上对称关系。上对称关系。56/9256关系性质特点自反性反自反性对称性反对称性传递性o集合表示式IARRIARR-1RR-1IARRR关系矩阵主对角线元素全是1主对角线元素全是0矩阵是对称矩阵若rij1，且ij，则rji0o对M2中1所在位置，M中对应位置都是1关系图每个顶点都有环每个顶点都没有环o假如两个顶点之间有边，一定是一对方向相反边(无单边)o假如两点之间有边，一定是一条有向边(无双向边)o假如顶点xi到xj有边，xj到xk有边，则从xi到xk也有边57/9257例7.14例7.14判断下列图中关系性质，
36、并说明理由。（1 1）对称，不是自反，不是反自反，不是反对称，不是传递。）对称，不是自反，不是反自反，不是反对称，不是传递。（2 2）是反自反，不是自反，是反对称，不是对称，是传递）是反自反，不是自反，是反对称，不是对称，是传递。（3 3）是自反，不是反自反，是反对称，不是对称，不是传递。是自反，不是反自反，是反对称，不是对称，不是传递。58/9258关系性质和运算之间关系自反性反自反性对称性反对称性传递性R1-1R1R2R1R2R1R2R1R259/9259问题o假如存在一条从数据中心a到b电话线，就属于关系R。o怎样确定从一个中心是否有一条电话线(可能不直接)链接到另一个中心？o经过结构包
37、含R最小传递关系来找出每一对有着联络数据中心，这个关系叫做R传递闭包。波士顿波士顿芝加哥芝加哥丹佛丹佛底特律底特律圣地亚哥圣地亚哥纽约纽约60/92607.5 关系闭包o闭包（closure）定义o闭包结构方法o闭包性质o闭包相互关系61/9261闭包定义定义7.14设R是非空集合A上关系，R自反（对称对称或传递传递）闭包是A上关系R，使得R满足以下条件：（1）R是自反（对称对称或传递传递）（2）RR（3）对A上任何包含R自反（对称对称或传递传递）关系R有RR。普通将R自反闭包记作r(R)，对称闭包对称闭包记作s(R)，传递闭包记作t(R)。62/9262闭包结构方法定理定理7.10设R为A上
38、关系，则有（1）r(R)RR0（2）s(R)RR-1（3）t(R)RR2R3 关于这个定理证实，本书不作介绍，仅对它应用做一关于这个定理证实，本书不作介绍，仅对它应用做一点说明。点说明。63/9263经过关系矩阵求闭包方法设关系R，r(R)，s(R)，t(R)关系矩阵分别为M，Mr，Ms和Mt，则MrME对角线上值都改为1MsMM若aij1，则令aji1MtMM2M3沃舍尔算法其中E是和M同阶单位矩阵，M是M转置矩阵。注意在上述等式中矩阵元素相加时使用逻辑加。64/9264经过关系图求闭包方法设关系R，r(R)，s(R)，t(R)关系图分别记为G，Gr，Gs，Gt，则Gr，Gs，Gt顶点集与G
39、顶点集相等。除了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)边，就加上这条边。当检验完全部顶点后就得到图Gt。65/9265例例7.157.15例7.15设A=a,b,c,d，R=,，则R和r(R)，s(R)，t(R)关系图以下列图所表示。其中r(R)，s(R)，t(R)关系图就是使用上述方法直接从R关系图得到。66
40、/9266Warshall 算法输入：M（R关系矩阵）输出：MT（t(R)关系矩阵）1.MTM2.fork1tondo3.fori1tondo4.forj1tondo5.MTi,jMTi,j+MTi,k*MTk,j注意：算法中矩阵加法和乘法中元素相加都使用逻辑加。67/9267Warshall 算法 举例例例设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,
41、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,1*M4,1*MT T1,j1,j 得到得到M M1 1。68/9268Warshall 算法 举例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,
42、21 1，将第将第2 2行分别加到第行分别加到第1,2,41,2,4行上。行上。69/9269Warshall Warshall 算法算法 举例举例k k3 3时，第时，第3 3列中列中M1,3M1,3M2,3M2,3M4,3M4,31 1，将第将第3 3行分别加到行分别加到第第1,2,41,2,4行上。行上。k k4 4时，第时，第4 4列中列中M1,4M1,4 M2,4 M2,4M3,4M3,4M4,4M4,41 1，将第将第4 4行分行分别加到第别加到第1,2,3,41,2,3,4行上。行上。70/92707.6 等价关系与划分定义7.15设R为非空集合上关系。假如R是自反、对称和传递，
43、则称R为A上等价关系(equivalentrelation)。设R是一个等价关系，若R，称x等价于y，记做xy。举例(1)平面上三角形集合中，三角形相同关系。(2)人群中同性关系。71/9271例7.16例7.16设A1,2,8，以下定义A上关系R：R|x，yAxy(mod3)其中xy(mod3)叫做x与与y模模3相等相等，即x除以除以3余数与余数与y除以除以3余数相等余数相等。不难验证R为A上等价关系，因为xA，有xx(mod3)x,yA，若xy(mod3)，则有yx(mod3)x,y,zA，若xy(mod3)，yz(mod3)，则有xz(mod3)72/9272等价类定义定义7.16设R为
44、非空集合A上等价关系，xA，令xR=y|yAxRy称xR为x关于关于R等价类等价类，简称为x等价类，简记为x或x。qx x等价类是等价类是A A中全部与中全部与x x等价元素组成集合。等价元素组成集合。q例例7.167.16中等价类是：中等价类是：1144771,4,71,4,72255882,5,82,5,833663,6 3,6 73/9273商集定义定义7.17设R为非空集合A上等价关系，以R全部等价类作为元素集合称为A关于R商集商集(quotientset)，记做A/R，即A/R=xR|xA例7.16中商集为1,4,7,2,5,8,3,6整数集合Z上模n等价关系商集是nz+i|zZ|i
45、=0,1,n-174/9274划分定义定义7.18设A为非空集合，若A子集族(P(A)，是A子集组成集合)满足下面条件：（1）（2）xy(x,yxyxy)（3）=A则称是A一个划分划分(partitions)，称中元素为A划分块划分块。说明说明q设集合设集合是是A A非空子集集合，若这些非空子集两两不相非空子集集合，若这些非空子集两两不相交，且它们并等于交，且它们并等于A A，则称则称是集合是集合A A划分划分。75/9275例7.17例7.17设Aa,b,c,d，给定1,2,3,4,5,6,以下：1=a,b,c,d2=a,b,c,d3=a,a,b,c,d4=a,b,c5=,a,b,c,d6=
46、a,a,b,c,d判断哪一个是A划分1和2是A划分，其它都不是A划分。因为3中子集a和a,b,c,d有交，4A，5中含有空集，而6根本不是A子集族。76/92767.7 偏序(partialorder)关系定义定义7.19设R为非空集合A上关系。假如R是自反自反、反对称反对称和传递传递，则称R为A上偏序关系偏序关系，记作。设为偏序关系，假如，则记作xy，读作“x小于或等于y”。注意这里“小于或等于”不是指数大小，而是在偏序关系在偏序关系中次序性中次序性。x“小于或等于”y含义是：依照这个序，x排在y前边或者x就是y。依据不一样偏序定义，对序有着不一样解释。偏序关系举例集合A上恒等关系IA小于或
47、等于关系整除关系包含关系77/9277可比定义定义7.20设R为非空集合A上偏序关系，定义(1)x,yA，xyxyxy。(2)x,yA，x与y可比可比xyyx。其中xy读作x“小于小于”y。这里所说“小于小于”是指在偏序中x排在y前边。o在含有偏序关系集合A中任取两个元素x和y，可能有下述几个情况发生：xy(或yx)，xy，x与y不是可比。o比如A1，2，3，是A上整除关系，则有12，13，1=1，2=2，3=3，2和3不可比。78/9278全序关系定义定义7.21设R为非空集合A上偏序关系，假如x,yA，x与与y都是可比都是可比，则称R为A上全序关系全序关系(或线序关系线序关系)。比如数集上
48、小于或等于关系是全序关系，因为任何两个数总是可比大小。整除关系普通来说不是全序关系，如集合1,2,3上整除关系就不是全序关系，因为2和3不可比。79/9279偏序集定义定义7.22集合A和A上偏序关系一起叫做偏序集偏序集，记作。比如比如整数集合Z和数小于或等于关系组成偏序集集合A幂集P(A)和包含关系R组成偏序集。80/9280覆盖(cover)定义定义7.23设为偏序集。x,yA，假如xy 且不存在zA使得xzy，则称y覆盖覆盖x。比如比如1,2,4,6集合上整除关系，有2覆盖1，4和6都覆盖2。但4不覆盖1，因为有124。6也不覆盖4，因为46不成立。81/9281哈斯图(Hasse di
49、agram)o利用偏序关系自反性、反对称性和传递性所得到偏序集合图，称为哈斯图哈斯图。o画偏序集哈斯图方法(1)用小圆圈代表元素。(2)x,yA，若xy，则将x画在y下方。(3)对于A中两个不一样元素x和y，假如y覆盖x，就用一条线段连接x和y。82/9282例7.19例7.19画出偏序集和哈斯图。83/9283例7.20例7.20已知偏序集哈斯图如右图所表示，试求出集合A和关系R表示式。解答解答A=a,b,c,d,e,f,g,hA=a,b,c,d,e,f,g,hR=R=,IIA A 84/9284偏序集中特殊元素定义定义7.24设为偏序集，BA，yB。（1）若x(xByx)成立，则称y为B最
50、小元最小元。（2）若x(xBxy)成立，则称y为B最大元最大元。（3）若x(xBxyxy)成立,则称y为B极小元极小元。（4）若x(xByxxy)成立,则称y为B极大元极大元。363242126B最大元最小元极大元极小元2,3,6,12,24,366,122,3,66无无 无无 24,36 2,312 12 6 6 12 6 6 6 无无 6 2,3 6 6 6 6 6 685/9285特殊元素性质o最小元是B中最小元素，它与B中其它元素都可比。o极小元不一定与B中元素可比，只要没有比它小元素，它就是极小元。o对于有穷集B，极小元一定存在，但最小元不一定存在。最小元假如存在，一定是唯一。o极小
