第3章二元关系优秀PPT.ppt

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

1、第3章二元关系现在学习的是第1页，共121页主要内容 3.1 基本概念基本概念3.2 关系的合成关系的合成3.3 关系上的闭包运算关系上的闭包运算3.4 次序关系次序关系3.5 等价关系和划分等价关系和划分现在学习的是第2页，共121页3.1基本概念n3.1.1 关系一个非常普遍的概念n数值的大于关系、整除关系，人类的父子关系、师生关系、同学关系例1nA=a,b,c,d是某乒乓球队的男队员集合，B=e,f,g是女队员集合.A和B之间的混双配对关系：AB=|xAyB=,例2n令=1,2,3,4,A中元素间的关系R：R=,AA现在学习的是第3页，共121页n定义 3.1-1 关系如果A1,A2,A

2、n是集合，R A1A2An，则称R是A1A2An上的n元关系如果 RAn，则称R是A上的n元关系n定义3.1-2 空关系与全域关系设R是A1A2An上的n元关系n若R=，称R为A1A2An上的空关系n若R=A1A2An，称R为A1A2An上的全域关系n恒等关系A上的恒等关系IA定义为：IA AA，且IA=|xA 例A=1,2,3,则IA=,现在学习的是第4页，共121页n思考若R和S都是关系，且R=,，S=,，R=S？n错误n定义3.1-3 关系的相等R1是 A1A2An上 的 n元 关 系,R2是B1B2Bm上的m元关系.那么R1=R2,当且仅当n=m,且对一切i,1in,Ai=Bi,并且R

3、1和R2是相等的有序n元组集合现在学习的是第5页，共121页3.1.2 二元关系n设A、是集合，如果R AB，则称R是一个从A到B的二元关系，若RA2，则称R是A上的二元关系n二元关系简称为关系关系nR xRy 也称之为x与y有R关系nR xRy 也称之为x与y没有R关系后缀表示法后缀表示法中缀表示法中缀表示法现在学习的是第6页，共121页例nR是实数集合，R上的几个关系x2+y2=4=xy现在学习的是第7页，共121页3.1.3 关系矩阵和关系图n关系矩阵有限集合之间的关系可以用矩阵表示便于用计算机来处理设A=a1,a2,am，B=b1,b2,bn是有限集，RAB，A到B的二元关系R可用mn

4、阶矩阵表示：MR=(rij)mn，其中rij=1,如果aiRbj 0,如aiRbj 则称矩阵MR=rij是R的关系矩阵现在学习的是第8页，共121页n例A=a1,a2,B=b1,b2,b3nR是A到B的关系，R=,b1 b2 b3a1 1 0 1a2 1 1 0MR=1 0 11 1 0nS是B上的关系，S=,b1 b2 b3b1 1 0 1b2 1 1 0b3 0 1 0MS=1 0 1 1 1 0 0 1 0现在学习的是第9页，共121页n关系图有向图两种情况nR ABnR AA例：设A=1,2,3,4,B=a,b,cnR AB，R=,nS AA，S=,1。2。3。4。A。B。abcGR:

5、GS:1。4。23现在学习的是第10页，共121页关系的定义域与值域n设R AB定义域定义域(domain)：由所有R的第一个分量组成的集合，称为R的定义域，记作dom R，即 dom R=x|y(R)值域值域(range)：由所有R的第二个分量组成的集合，称为R的值域，记作ran R，即 ran R=y|x(R)例：A=1,2,3,4,R AA，R=,ndom R=1,2nran R=1,2,3现在学习的是第11页，共121页关系的集合运算n关系就是集合n、-、和补运算对关系也适用n特别的R=(AB)-R现在学习的是第12页，共121页思考题n设A和B分别是n元和m元有限集，则共有多少个不同

6、的A到B的关系？n设A(和B)都是非空有限集，则A上的空关系、恒等关系和A上(A到B的)全关系的关系图和关系矩阵有何特点。n怎样通过关系图和关系矩阵求domR和ranR现在学习的是第13页，共121页3.1.4 关系的特性n最重要的一节最重要的一节n这里关系都是集合A上的关系n关系的性质主要有自反性反自反性对称性反对称性传递性现在学习的是第14页，共121页n设R是A上的二元关系，如果对于xA都有R(xRx)，则称R是A上的自反关系.即 R是A上的自反关系x(xAxRx)例：A=1,2,3nR1=,不是自反关系nR2=,自反关系n空关系不是自反关系n全关系、恒等关系自反关系自反关系现在学习的是

7、第15页，共121页自反关系的特征n定理：设R是集合A上的关系，则R具有自反性 iff IAR证明：必要性xA，由R自反知 R，IAR充分性xA，由IA的定义知 IA，R，即R是自反的n自反关系的关系矩阵主对角线上的所有元素均为1n自反关系的关系图每个结点都有自环线现在学习的是第16页，共121页n令A=1,2,3，下列哪些关系是自反的1。2。1。2。1。2。1。2。33331。2。1。2。1。2。1。2。3333R2R1R3R4R5R6R7R8现在学习的是第17页，共121页反自反关系n设R是集合A上的关系，如果对于xA都有R，则称R为A上的反自反关系。即 R是A上的反自反关系x(xAR)例

8、：A=1,2,3nS1=,不是反自反关系nS2=,反自反关系n空关系反自反关系现在学习的是第18页，共121页反自反关系的特征n定理：设R是集合A上的关系，则R具有反自反性 iff IAR=证明：必要性xA，由R反自反知 R，IAR=充分性假设R不是反自反的，即存在xA，R，则 IAR，与IAR=矛盾 n反自反关系的关系矩阵主对角线上的所有元素均为0n反自反关系的关系图每个结点都没有自环线现在学习的是第19页，共121页n令A=1,2,3，下列哪些关系是反自反的1。2。1。2。1。2。1。2。33331。2。1。2。1。2。1。2。3333R2R1R3R4R5R6R7R8现在学习的是第20页，

9、共121页思考题n设A是n元有限集共有多少个A上的不同的自反关系？共有多少个A上的不同的反自反关系？n是否存在满足下列要求的关系，若有，请给出实例既自反又反自反既不自反又不反自反空集上的空关系空集上的空关系现在学习的是第21页，共121页对称关系n设R是集合A上的关系，若对任何x,yA,只要有xRy,就必有yRx,则称R为A上的对称关系，即 R是A上的对称关系xy(xAyAxRy yRx)n例：邻居关系，朋友关系A=1,2,3nR=,nIAn空关系n全关系现在学习的是第22页，共121页对称关系的特征n对称关系的关系矩阵根据主对角线对称n对称关系的关系图在两个不同的结点之间，若有边的话，则有方

10、向相反的两条边（平行线）现在学习的是第23页，共121页n令A=1,2,3，下列哪些关系是对称的1。2。1。2。1。2。1。2。33331。2。1。2。1。2。1。2。3333R2R1R3R4R5R6R7R8现在学习的是第24页，共121页反对称关系n设R是集合A上的关系,若对x,yA,如果有xRy,和yRx,就有x=y,则称R为A上的反对称关系，即R是A上的反对称关系xy(xAyAxRyyRx)x=y)xy(xAyAxyxRy)y x)Rn例：A=1,2,3R1=,R2=,IA空关系现在学习的是第25页，共121页反对称关系的特征n反对称关系的关系矩阵以主对角线为对称的两个元素中最多有一个1

11、n反对称关系的关系图两个不同的结点之间最多有一条边现在学习的是第26页，共121页n令A=1,2,3，下列哪些关系是反对称的1。2。1。2。1。2。1。2。33331。2。1。2。1。2。1。2。3333R2R1R3R4R5R6R7R8现在学习的是第27页，共121页思考题n是否存在满足下列要求的关系，若有，请给出实例既对称又反对称既不对称又不反对称n设A是n元有限集共有多少个A上的不同的对称关系？共有多少个A上的不同的反对称关系？共有多少个A上不同的既对称又反对称的关系？IA现在学习的是第28页，共121页传递关系nR是A上的关系，对x,y,zA,如果有xRy,和yRz,就有xRz,则称R为

12、A上的传递关系，即R是A上的传递关系xyz(xAyAzAxRyyRz)xRz)n例，=，A=1,2,3,4nR1=,nR2=,nIAn空关系，全关系现在学习的是第29页，共121页传递关系的特征n传递关系的关系矩阵如果aij=1,且ajk=1,则aik=1n传递关系的关系图如果有边,则也有边现在学习的是第30页，共121页n令A=1,2,3，下列哪些关系是传递的1。2。1。2。1。2。1。2。33331。2。1。2。1。2。1。2。3333R2R1R3R4R5R6R7R8现在学习的是第31页，共121页练习n设R是集合A上的一个自反关系,求证：R是对称和传递的，iff 若,R,则 R证明：必要

13、性:已知R是对称和传递的，设R，R，(要证明 R)因为R对称故R,又R 是传递的，且R得R充分性:已知a,b,cA，若，R,则 R先证先证R对称对称：R，(要证明 R)因为R是自反的,所以R，由R且R，根据已知条件得R，即R是对称的再证再证R传递传递：a,b,cA 设 R，R(要证明R)由R对称,得R，由R且R，根据已知条件得R 所以R是传递的现在学习的是第32页，共121页n从下列各题给出的备选答案中选出正确的答案，并将其代号填入题后面的括号内。(1)设A=0,1,2,3，A上的关系R=,，则R是A.自反的 B.对称的 C.反对称的 D.可传递的 ()(2)设R是整数集I上的关系，定义为当且

14、仅当|i1-i2|10时，i1Ri2，则R是A.自反的 B.对称的 C.反对称的 D.可传递的 ()B A B 现在学习的是第33页，共121页n下图给出了1,2,3上三个关系的关系图，试对每一个图所表示的关系的性质作出判别，并将选中的性质的代号填入相应的括号内A.自反的 B.对称的 C.反对称的 D.传递的 E.反自反则1是（）则2是（）则3是（）ABAB A A E E现在学习的是第34页，共121页思考题n关系的性质对于集合运算是否保持封闭？即自反（反自反、对称、反对称、传递）关系的交、并、差、对称差及补关系是否仍是自反（反自反、对称、反对称、传递）的？反对称传递对称反自反自反 R1R1

15、R2R1-R2R1R2R1R2R1,R2不反对称不反对称反对称不反对称反对称不传递不传递不传递不传递传递对称对称对称对称对称不反自反反自反反自反反自反反自反不自反不自反不自反自反自反现在学习的是第35页，共121页3.2 关系的合成（复合）n3.2.1 关系的合成定义定义:设是R1从A到B的关系，R2是从B到C的关系，则R1和R2的复合关系是从A到C的关系，记作R1R2(R1R2)，定义为：R1R2=|xAzCy(yBR1R2)例nR兄妹关系，S母子母子关系，RS舅舅和外甥舅舅和外甥关系nA=1,2,3,4,B=2,3,4,C=1,2,3,R是A到B的关系;S是B到C的关系R=x+y=6=,S

16、=y-z=1=,R S=,现在学习的是第36页，共121页练习nA=1,2,3 B=1,2,3.4 C=1,2,3,4,5R AB S BCR=,S=,求 R S=,。C123。41。2。3。A1。2。3。A。B123。4RS5。C123。45现在学习的是第37页，共121页n设A=1,2,3,4,5,R和S都是A上二元关系.如果R=,S=,求RS，SR，(RS)R，R(SR)，RR，SSRS=,SR=,(RS)R=R(SR)=RR=,SS=,不满足交换律满足结合律？现在学习的是第38页，共121页关系复合运算的性质n设R是A到B的二元关系,IA,IB分别是A和B上的相等关系,则IAR=RIB

17、=Rn例：令A=1,2,3,B=a,b,c,d1。2。3。AIA。Babc。dR1。2。3。ARIB。abc。d。Babc。d1。2。3。AB现在学习的是第39页，共121页n定理3.21设R1是从A到B的关系,R2和R3是从B到C的关系,R4是从C到D的关系,则(a)R1(R2R3)=R1R2R1R3(b)R1(R2R3)R1R2R1R3(c)(R2R3)R4=R2R4R3R4(d)(R2R3)R4R2R4R3R4现在学习的是第40页，共121页证明(a)任取R1(R2R3)b(bBR1R2R3)b(bBR1(R2R3)b(bBR1R2)(bBR1R3)b(bBR1R2)b(bBR1R3)R

18、1R2R1R3(R1R2)(R1R3)所以R1(R2R3)=(R1R2)(R1R3)现在学习的是第41页，共121页证明(b)任取R1(R2R3)b(bBR1R2 R3)b(bBR1(R2 R3)b(bBR1R2)(bBR1 R3)b(bBR1R2)b(bBR1 R3)R1R2 R1 R3(R1R2)(R1R3)所以 R1(R2 R3)(R1R2)(R1R3)现在学习的是第42页，共121页n定理3.22 设R1,R2和R3分别是从A到B,B到C和C到D的关系,那么(R1R2)R3=R1(R2R3)(复合运算满足结合律)证明：R1 (R2 R3)b(bB R1 R2 R3)b(bB R1 c(

19、cC R2 R3)bc(bB R1(cC R2 R3)cb(cC(bB R1 R2 R3)c(cCb(bB R1 R2)R3)c(cC R1 R2)R3)(R1 R2)R3现在学习的是第43页，共121页3.2.2 关系R的幂n当R是A上的一个关系时,R可与自身合成任意次而形成A上的一个新关系，即 RR=R2，R2R=RR2=R3，n定义3.22 设R是集合A上的二元关系,nN,那么R的n次幂记为Rn,定义如下:(1)R0=IA(2)Rn+1=RnRn定理3.23设R是A上的二元关系,并设m和n是N的元素,那么(1)RmRn=Rm+n (2)(Rm)n=Rmn现在学习的是第44页，共121页n

20、定理3.24设A=n,R是集合A上的一个关系,那么i,jZ，使Ri=Rj而 0ij证明：为方便起见，记因为总共只有m个定义在n元有限集A上的不同的关系，所以以下m+1个R的方幂 R0,R1,R2,Rm之中，必有相同者。所以存在i和j，0ijm 使 Ri=Rj鸽巢原理（抽屉原则）现在学习的是第45页，共121页n定理3.25设R是集合A上的一个二元关系.若i,jZ,ij,使Ri=Rj.记d=j-i,那么(a)对所有k Z,k0,Ri+k=Rj+k(b)对所有k,m Z,k,m0,Ri+md+k=Ri+k(c)记S=R0,R1,R2,Rj-1,那么对nN,RnS证明(a)：i.k=0时，Ri=Rj

21、ii.设k=t时，Ri+t=Rj+t则k=t+1时，Ri+t+1=Ri+tR=Rj+tR=Rj+t+1得证现在学习的是第46页，共121页证明(b)：i.k=0时，证明Ri+md=Ri m=0时，Ri=Ri设m=t时，Ri+td=Ri则m=t+1时，Ri+(t+1)d=Ri+tdRd=RiRd=Ri+d=Ri+j-i=Rj=Riii.设k=n时，Ri+md+n=Ri+n则k=n+1时，Ri+md+n+1=Ri+md+nR=Ri+nR=Ri+n+1得证现在学习的是第47页，共121页证明(c)：只需证n j时,RnS由n j i,必存在s,tZ使得n=i+sd+t(0td-1)因为 i.n=j时

22、，j=i+1*d+0=i+j-i ii.设n=k时，存在s,t使得k=i+sd+t(0td-1)则n=k+1时,k+1=i+sd+t+1,分两种情况讨论情况1:td-1,则s和t+1就是要求的两个数情况2:t=d-1,则t+1=d，k+1=i+(s+1)d+0,即s+1和0是要求的两个数总之，存在s,tZ使得n=i+sd+t(0td-1)由(b)知Rn=Ri+sd+t=Ri+t 且td-1，则 i+t i+d-1=i+j-i-1=j-1即 Rn=Ri+t S现在学习的是第48页，共121页例n设A=a,b,c,d,R=,求R0,R2,R3,R4R0=,R2=,R3=,R4=,nR4=R2,根据

23、定理3.25(c)对nN,RnR0,R1,R2,R3易证R5=R3,R6=R4=R2用归纳法可得R2n+1=R3和R2n=R2(n1)现在学习的是第49页，共121页现在学习的是第50页，共121页3.2.3 合成关系的矩阵表达n定理3.26 设X=x1,x2,xm,Y=y1,y2,yn,Z=z1,z2,zp,R是X到Y的关系,MR=aij是mn矩阵,S是Y到Z的关系,MS=bij是np矩阵.则MRS=cij=MRMS,这里是逻辑乘,是逻辑加现在学习的是第51页，共121页n例3设 X=1,2,Y=a,b,c,Z=,R是X到Y的关系，S是Y到Z的关系，R=,S=,则现在学习的是第52页，共12

24、1页现在学习的是第53页，共121页n定理3.27 关系矩阵的乘法是可结合的nMRS=MRMS cij=aijbijnMRS=MRMS cij=aijbijnMR cij=aijnMR-S=MR MS cij=aij(bij)n定理：设R是集合A上的一个二元关系，R是传递的 iff R2R证明：必要性 R2t,使得xRt 且 tRy又R是传递的，所以xRy，即R2R 充分性 x,y,z A,若xRy 且 yRz，则 R2 R2R，R，即R是传递的现在学习的是第54页，共121页补充定理n定理1：设R1是由A到B的关系，R2和R3是由B到C的关系，R4是由C到D的关系，则如果 R2 R3,则R1

25、R2 R1R3,R2R4 R3R4n定理2：设R1和R2是由A到B的关系，S1和S2是由B到C的关系，若 R1 R2,S1 S2,则 R1S1 R2S2证明：1.R1R2则b，b B使得 aR1b 且 bR2c R2 R3 bR3c即 R1R3 R1R2 R1R3 类似可证R2R4 R3R4现在学习的是第55页，共121页3.3.1 逆关系n定义3.31设R是从A到B的二元关系,关系R的逆(或叫R的逆关系)记为R-1(Rc),是一从B到A的二元关系,定义如下:R-1=|Rn例I上的关系“”集合族上的关系的逆是关系 空关系的逆是空关系(AB)-1=BAR=,nR-1=,现在学习的是第56页，共1

26、21页逆关系的关系图和关系矩阵nR-1的关系图将R关系图的所有边的方向颠倒n R-1的矩阵 R矩阵的转置：M=(MR)T现在学习的是第57页，共121页n定理3.32 设R,S,R1和R2都是从A到B的二元关系,那么下列各式成立:(a)(R-1)-1=R(b)(RS)-1=R-1 S-1(c)(RS)-1=R-1 S-1(d)(R)-1=(R-1)(e)(RS)-1=R-1 S-1(f)R1 R2 R1-1 R2-1(g)(R1R2)-1=R2-1 R1-1 现在学习的是第58页，共121页n定理：R是A上关系，则 R是对称的，当且仅当 R-1=R R是反对称的，当且仅当 RR-1 IA证明：

27、充分性，已知 R-1=R (证明R对称)任取x,yA 设R,则R-1,而R-1=R 即有R，所以R对称必要性，已知R对称，(证明R-1=R)先证R-1R，任取R-1,则R,又R对称所以有R，所以R-1R。再证R R-1，任取R,因R对称，所以有R，则RC,所以RR-1。综上R-1=R现在学习的是第59页，共121页证明 充分性，已知RR-1IA，(证明R反对称)任取x,yA 设R 且R，则R 且 R-1，所以RR-1，因为RR-1IA所以 IA ，即x=y 所以R反对称必要性，已知R反对称，(证明RR-1 IA)任取RR-1 则R 且 R-1 即R 且 R因为R反对称，所以x=y 即IA 所以

28、RR-1 IA现在学习的是第60页，共121页思考题n关系的性质对于复合运算和逆是否保持封闭？即自反（反自反、对称、反对称、传递）关系的复合关系和逆关系是否仍是自反（反自反、对称、反对称、传递）的？反对称传递对称反自反自反R1-1R1R2R1,R2反对称不反对称传递不传递对称不对称反自反不反自反自反自反现在学习的是第61页，共121页3.3 关系上的闭包运算n例1。2。31。2。31。2。31。2。3现在学习的是第62页，共121页n定义3.32 设R是A上的二元关系,若有A上的关系R,满足：(i)RR(ii)R是自反的(对称的、传递的)(iii)对于任何A上自反(对称、传递)的关系R”,如果

29、RR”,就有RR”则称R是R的自反(对称、传递)闭包。记作r(R)、(s(R)、t(R)(reflexive、symmetric、transitive)nR的自反(对称,传递)闭包是包含R并且具有自反(对称,传递)性质的最小关系现在学习的是第63页，共121页闭包的性质n定理3.34设R是集合A上的二元关系(a)R是自反的当且仅当r(R)=R(b)R是对称的当且仅当s(R)=R(c)R是传递的当且仅当t(R)=R证明(a)：充分性显然必要性：由闭包的定义Rr(R)又RR，且R是自反的根据闭包的极小性，有r(R)R则r(R)=R现在学习的是第64页，共121页闭包的计算n定理3.3-53.3-7

30、 设R是非空集A的关系,则(1)r(R)=RIA(2)s(R)=RR-1(3)证明(1):设R=R IA.显然,R是自反的，且R R.假设R是A上的自反关系且R R.因R是自反的,所以R IA,又R R,所以R R IA=R所以,R=r(R).证毕现在学习的是第65页，共121页证明(2):设R=R R-1(i)显然R R(ii)又(R R-1)-1=R-1 R=R R-1 R是对称的(iii)假设R是A上的对称关系且R R 则 R-1 R-1 R=R R-1 R 综上，s(R)=R=RR-1现在学习的是第66页，共121页证明(3):令R=RR2R3.,（只需证明t(R)R 且 R t(R)

31、）(i)先证t(R)R(利用闭包的极小性)显然 R R(再证明R是传递的)x,y,zA,设有R,R,由R定义得必存在整数i,j使得Ri,Rj,则Ri+jR,所以R,R传递由闭包的极小性可得t(R)R(ii)再证 Rt(R)Rt(R)R2t2(R)t(R)则R3=R2R t2(R)t(R)t2(R)t(R)这个过程可以一直进行下去，即得Rit(R)Rt(R)综合(i)(ii)R=t(R)现在学习的是第67页，共121页例(a)整数集合I上的关系的自反闭包是,对称闭包是关系,传递闭包是关系自身(b)整数集合I上的关系的自反闭包是自身,对称闭包是全域关系,传递闭包是自身(c)的自反闭包是全域关系,对

32、称闭包是,的传递闭包是全域关系(d)空关系的自反闭包是恒等关系,对称闭包和传递闭包是自身(e)设R是I上的关系,xRy当且仅当y=x+1,那么t(R)是关系现在学习的是第68页，共121页n定理3.38 设R是n元有限集A上的关系,则存在自然数kn，使得证明：显然只需证a,bA,若t(R),则存在自然数p使得Rp,即存在序列x1,x2,xp-1满足aRx1,x1Rx2,xp-1Rb若满足上述条件的最小p值大于n，则由于A是有限集，必存在s,t使得 xs=xt，其中0s tp，因此可得到 aRx1,x1Rx2,xsRxt+1,xp-1Rb即Rp-(t-s),与p是最小的假设矛盾现在学习的是第69

33、页，共121页例nA=1,2,3，A上关系R1,R2,R3,如下：(1)R1=,(2)R2=,(3)R3=,求它们的传递闭包解：(1)R12=R13=t(R)=R1 R12 R13=R1 (2)R22=,R23=,=IA R24=R23 t(R)=R2 R22 R23现在学习的是第70页，共121页闭包的性质n定理设R和S都是集合A上的关系且RS，则(a)r(R)r(S)(b)s(R)s(S)(c)t(R)t(S)证明(a)：显然r(S)是自反的，且RS r(S)，由闭包的极小性可知r(R)r(S)现在学习的是第71页，共121页闭包的应用n例：传递闭包在语法分析中的应用设有一字母表V=A,B

34、,C,D,e,d,f.假设文法G 为(1)A A f;(2)B D d e;(3)C e;(4)A B;(5)B D e;(6)D B fR 为定义在V 上的二元关系,(x i,x j)R 表示从x i 出发用一条规则推出一串字符,使其第一个字母恰好为x jt(R):每个字母连续使用文法可能推出的头字符.现在学习的是第72页，共121页n定理3.39(a)如果R是自反的,那么s(R)和t(R)都是自反的(b)如果R是对称的,那么r(R)和t(R)都是对称的(c)如果R是传递的,那么r(R)是传递的证明(c)：证明R是传递的,那么r(R)是传递的 r2(R)=(RIA)2=(RIA)(RIA)=

35、R2R R IA =R IA(R是传递的，R2 R)=r(R)r(R)是传递的现在学习的是第73页，共121页n定理3.310 设R是集合A上的二元关系,那么(a)rs(R)=sr(R)(b)rt(R)=tr(R)(c)st(R)ts(R)证明(a)：Rs(R)r(R)rs(R)，sr(R)srs(R)rs(R)是对称的（定理3.39）srs(R)=rs(R)即得sr(R)rs(R)同理可证rs(R)sr(R)sr(R)=rs(R)n通常将t(R)记成R+，tr(R)记成R*，即t(R)=R+=RR2.Rn=tr(R)=rt(R)=R*=R0RR2.Rn=Rii=1Rii=0现在学习的是第74

36、页，共121页3.4 次序关系n常遇到的重要关系n例数值的、关系集合的、关系图书馆的图书按书名的字母次序排序词典中的字(词)的排序计算机中文件按文件名排序程序按语句次序执行.现在学习的是第75页，共121页3.4.1 偏序关系n定义3.41 如果集合A上的二元关系R是自反的,反对称的和传递的,那么称R为A上的偏偏序关系序关系,或称半序关系称序偶为偏序偏序集集n通常，把偏序关系R记作,如果,则记作ab,读作“a小于等于b”n注意注意：定义中的“”不是指普通中的实数中的大小关系的,而是一般的偏序关系现在学习的是第76页，共121页例n设集合Aa,b,c,A上的关系R,判断R是否是偏序关系。n设A是

37、非零自然数集,DA是A上的整除关系,判断DA是否是偏序关系n设A是一个集合，则集合的“包含”关系是否是其幂集上的偏序关系（是）（是）（是）现在学习的是第77页，共121页例nA=1,2,4,62。1。64现在学习的是第78页，共121页哈斯图(Hasse)n描述偏序集的关系图,可以简化简化为哈斯图哈斯图n简化规则用小圆圈代表元素如果xy,并且xy,则将代表y的小圆圈画在代表x的小圆圈的上方若xy，且在A中不存在任何其它元素z，使得xz,zy(x是y的直接前辈，或y是x的直接后裔)，则有一条由x到y的连线现在学习的是第79页，共121页例2。1。642。1。84。6。4。现在学习的是第80页，共

38、121页练习1.设A=a,b,c，则“”关系是(A)上的偏序关系，则(A),R)是偏序集,画出其哈斯图2.设A=2,3,6,12,24,36,画出的哈斯图现在学习的是第81页，共121页nA=1,2,12,的哈斯图现在学习的是第82页，共121页偏序集中的重要元素n极小元与极大元，最小元与最大元设是一偏序集合,B是A的子集若存在元素bB,使得B中没有没有元素x满足xb且xb,则称b为B的一个极小元极小元若存在元素bB,使得B中没有没有元素x满足xb且bx,则称b为B的一个极大元极大元如存在元素bB,使得xB,均有bx,则称b为B的最小元最小元如存在元素bB,使得xB,均有xb,则称b为B的最大

39、元最大元现在学习的是第83页，共121页例n设的哈斯图如下所示：讨论当B取相应集合时，其最大元,最小元,极大元,极小元abcdefghia,ba,b无无无无a,bc无无cB极小元极小元极大元极大元最小元最小元最大元最大元a,ba,b,c现在学习的是第84页，共121页abcdefghiB极小元极小元极大元极大元最小元最小元最大元最大元a,b,c,db,c,d,fa,c,f,ia,bc,d无无无无bfbfaiai现在学习的是第85页，共121页几点说明n极大(小)元总是存在的n最大(小)元可能不存在n极大(小)元未必是最大(小)元n极大(小)元未必是唯一的n如果B存在最大(小)元x,则x就是B的

40、极大(小)元n孤立点则又是极大元,也是极小元现在学习的是第86页，共121页n定理3.41 设是一偏序集，且BA,如果B有最大(最小)元，那么它是唯一的证明：假设a和b都是B的最大元,那么ab和ba.则a=b(是反对称性的)类似可证最小元的唯一性现在学习的是第87页，共121页n上界与下界，上确界与下确界设是一偏序集合,B是A的子集如存在aA,使得xB,均有xa,则称B有上界，并称a为B的一个上界上界(Upper Bound)如存在aA,使得xB,均有ax,则称B有下界，并称a为B的一个下界下界(Lower Bound)若a是B的上界，并且对B的每一个上界a皆有a a，则称 a是B的最小上界最

41、小上界(上确界，Least Upper Bound)，记作lub若a是B的下界，并且对B的每一个下界a皆有 a a，则称 a是B的最大下界最大下界(下确界，Greatest Lower Bound)，记作glb现在学习的是第88页，共121页abcdefghiB上界上界下界下界上确界上确界下确界下确界a,ba,b,cc,d,e,f,g,h,i无无无无无无c,e,f,h,i无无c无无现在学习的是第89页，共121页abcdefghiB上界上界下界下界上确界上确界下确界下确界a,b,c,db,c,d,fa,c,f,if,h,i无无f无无f,h,ibfbiaia现在学习的是第90页，共121页n定理

42、3.42 如果是非空有限偏序集,则A的极小(大)元素常存在,最大下界和最小上界也可能存在或不存在,但如果它们存在,则是唯一的.n定理3.43设是偏序集合且BA,如果B的最小上界(最大下界)存在,那么是唯一的n定理3.44设是偏序集合,B是A的子集(a)如果b是B的最大(小)元,那么b是B的极大(小)元(b)如果b是B的最大(小)元,那么b是B的lub(glb)(c)如果b是B的一个上(下)界且bB,那么b是B的最大(小)元现在学习的是第91页，共121页练习n给定一偏序关系的Hasse图。12。24。36。最大元上界上确界下界A6,12,241,2,32,3下确界最小元极大元极小元B无24无无

43、无246,12,24,366,12,24,36无246611,2,3,6111124,36166246112,311无2,32,3现在学习的是第92页，共121页3.4.2 拟序关系n如果集合A上的二元关系R是反自反的和传递的,那么称R为A上的拟序关系拟序关系,称序偶为拟序集拟序集n通常，把拟序关系R记作,如果,则记作ab,读作“a小于b”n例实数集合中的是拟序关系集合的是拟序关系现在学习的是第93页，共121页n定理定理 拟序关系是反对称的证明：设R是A上的拟序关系假设R不是反对称的，则x,yA,xy,xRy且yRx，由R的传递性得xRx，与R反自反矛盾 R反对称n定理定理3.45 在集合A

44、上,(a)如果R是一拟序关系,那么r(R)=RIA是偏序关系(b)如果R是一偏序关系,那么R-IA是拟序关系现在学习的是第94页，共121页n可比较如果是一偏序,或ab或ba,我们说a和b是可比较的n线序集全序集定义3.46 在偏序集中.如果a,bA,a，b均可比较.那么叫做A上的线序关系(或全序关系),这时的序偶叫做线序集或全序集、链.3.4.3 线序集和良序集2。1。84。现在学习的是第95页，共121页n良序集定义3.47如果A上的二元关系R是一偏序偏序关系,且A的每一非空子集都有最小元,那么R叫做A上的良序关系,序偶叫做良序集良序集必是线序集定理3.46是良序集n*3.4.4 词典序和

45、标准序n*3.4.5 数学归纳法的推广现在学习的是第96页，共121页思考题n证明或用反例否定下列命题(1)每一个偏序关系的逆都是偏序关系(2)每一个拟序关系的逆都是拟序关系(3)每一个全序关系的逆都是全序关系(4)每一个良序关系的逆都是良序关系现在学习的是第97页，共121页3.5 等价关系和划分n3.5.1 等价关系定义3.51如果集合A上的二元关系R是自反的,对称的和传递的,那么称R是等价关系设R是A上的等价关系,a,bA.若aRb,记作ab,读做“a等价于b”.例n空关系n全关系n恒等关系n同学集合A=a,b,c,d,e,f,g,A中的关系R是“住在同一房间”现在学习的是第98页，共1

46、21页n例集合A=1,2,3,4,5,6,7,R=|x-y可被3整除(或x/3与y/3的余数相同)n定义3.52设k是一正整数而a,bI.如果对某整数m,a-b=mk,那么a和b是模k等价,写成ab(mod k)n定理3.51模k等价是任何集合A上的等价关系现在学习的是第99页，共121页等价关系的关系矩阵与关系图n关系矩阵可简化为三角矩阵n关系图每一结点都有一自环线（可省略）如果有从a到b的弧,那么也有从b到a的弧（可画成无向图）如果从a到c有一条路径,则从a到c有一条弧现在学习的是第100页，共121页nA=1,2,3,4,5,6,7,R是模3等价关系，画出其简化关系图2。5。1。4。7。

47、3。6。等价关系等价关系R R的有向图可能由若干个独立子图构成的，的有向图可能由若干个独立子图构成的，每个独立子图都是完全关系图每个独立子图都是完全关系图(团团)现在学习的是第101页，共121页判断下图中哪些是等价关系A=1,2,31。2。1。2。331。2。1。2。1。2。1。2。3333R2R1R5R61。2。1。2。33R3R4R7R8现在学习的是第102页，共121页等价类n定义3.53 R是A上的等价关系，aA,由a确定的集合aR:aR=x|xAR称集合aR为a关于R的等价类,简记为an称a为等价类a的表示元素.n如果等价类个数有限,则R的不同等价类的个数叫做R的秩;n等价类aR,

48、aaR现在学习的是第103页，共121页例nR是I上模4等价关系04=-8,-4,0,4,8,14=-7,-3,1,5,9,24=-6,-2,2,6,10,34=-5,-1,3,7,11,nA=a,b,c,d,e,f,R=,a=b=c=a,b,cd=e=d,ef=f秩是3现在学习的是第104页，共121页等价关系图求等价类R图中每个独立子图上的结点，构成一个等价类图中每个独立子图上的结点，构成一个等价类现在学习的是第105页，共121页n下述三个等价关系各有几个等价类？说出对应的各个等价类。练习1。2。3R21。2。3R1。R3。123现在学习的是第106页，共121页等价类的性质n定理3.5

49、2 设R是非空集合A上的等价关系,aRb iffa=b证明：充分性 aa=b,即ab,aRb必要性x a,则aRx,R对称,xRa又 aRb，且R传递，xRb，即x b ab，类似可证ba a=b现在学习的是第107页，共121页n定理3.53 设R是集合A上的等价关系,则对所有a,bA,或者a=b,或者ab=证明：如果A=,断言无义地真设A.若aRb，根据定理3.52得a=b若R,假设ab,则存在cab，cacb,R,R,由R对称得 R又由R传递得R,矛盾定理得证现在学习的是第108页，共121页思考n设R是集合A上的等价关系，a,bA,若ab=,则R证明：假设R,由等价类定义得ba,又bb

50、，所以bab，矛盾现在学习的是第109页，共121页n定 理 3.56 设 R是 A上 的 二 元 关 系,设R=tsr(R)是R的自反对称传递闭包,那么(a)R是A上的等价关系,叫做R诱导的等价关系(b)若R是等价关系且RR,那么RR.R是包含R的最小等价关系.n例A=a,b,cRtsr(R)现在学习的是第110页，共121页等价类与划分n3.5.2 划分定义3.55给定非空集合A和非空集合族=A1,A2,Am,如果(i)A=A1A2Am(ii)AiAj=或Ai=Aj(i,j=1,2,m)称集合族为集合A的一个划分划分划分的元素Ai称为划分的块块如果划分是有限集合,则不同块的个数叫划分的秩秩