资源描述
2020/4/26,1,第四章二元关系,主要内容：关系的概念及表示方法关系的性质关系的运算:关系的复合，求逆关系，关系的闭包。三种关系:等价关系，相容关系，次序关系。,2020/4/26,2,一、序偶与有序n元组1.定义:由两个对象x、y组成的序列称为有序二元组，也称之为序偶，记作；称x、y分别为序偶的第一，第二元素。注意，序偶与集合x,y不同：序偶：元素x和y有次序；集合x,y：元素x和y的次序无关紧要。,4-1序偶与集合的笛卡尔积,2020/4/26,3,2.定义：设，是两个序偶，如果x=u和y=v则称和相等，记作=。3.定义：有序3元组是一个序偶,其第一个元素也是个序偶。有序3元组,c可以简记成，但不是有序3元组。,2020/4/26,4,4.定义：有序n元组是一个序偶,其第一个元素本身是个有序n-1元组,记作,xn。且可以简记成。5.定义=(x1=y1)(x2=y2)(xn=yn),2020/4/26,5,例如“斗兽棋”的16颗棋子，,设：A=红,蓝B=象,狮,虎,豹,狼,狗,猫,鼠每个棋子可以看成一个序偶，斗兽棋可记成集合AB：,2020/4/26,6,1.定义:设A、B是集合，由A的元素为第一元素，B的元素为第二元素组成序偶的集合，称为A和B的笛卡尔积，记作AB，即AB=|xAyB例1设A=0,1，B=a,b，求AB，BA，AA。解：AB=,BA=,AA=,可见ABBA所以，集合的笛卡尔积运算不满足交换律。,2020/4/26,7,另外(AB)C=,c|ABcCA(BC)=|aABC,因不是有序三元组,所以(AB)CA(BC)。故也不满足结合律。,2.性质1)如果A、B都是有限集，且|A|=m,|B|=n，则|AB|=mn。证明：由笛卡尔积的定义及排列组合中的乘法原理，直接推得此定理。2)A=B=,2020/4/26,8,3)对和满足分配律。设A,B,C是任意集合，则A(BC)=(AB)(AC)；A(BC)=(AB)(AC)；(AB)C=(AC)(BC)；(AB)C=(AC)(BC)；证明：任取A(BC)xAyBCxA(yByC)(xAyB)(xAyC)ABAC(AB)(AC)所以式成立。（其余可以类似证明）,2020/4/26,9,4)若C,则AB(ACBC)(CACB)证明：充分性：设AB，求证ACBC任取ACxAyCxByC(因AB)BC所以,ACBC。必要性：若C,由ACBC求证AB取C中元素y,任取xAxAyCACBC(由ACBC)xByCxB所以,AB。所以AB(ACBC)类似可以证明AB(CACB)。,2020/4/26,10,5)设A、B、C、D为非空集合，则ABCDACBD证明：首先,由ABCD证明ACBD任取xA，任取yB，所以xAyBABCD(由ABCD)xCyD所以,ACBD。其次,由AC，BD证明ABCD任取ABxAyBxCyD(由AC，BD)CD所以,ABCD证毕。,2020/4/26,11,6)约定(A1A2)An-1)An)=A1A2An特别AAA=An设R是实数集合，则R2表示笛卡尔坐标平面，R3表示三维空间，Rn表示n维空间。3.应用1)令A1=x|x是学号A2=x|x是姓名A3=男,女A4=x|x是出生日期A5=x|x是班级A6=x|x是籍贯则A1A2A3A4A5A6中一个元素：这就是学生档案数据库的一条信息，所以学生的档案就是A1A2A3A4A5A6的一个子集。,2020/4/26,12,2)令A=a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z是英文字母表一个英文单词可以看成有序n元组：如at=,boy=,data=,computer=于是可以说：atA2,boyA3,dataA4,computerA8,所以英文词典中的单词集合可以看成是AA2An的一个子集。作业P105,2020/4/26,13,4-2关系及其表示法,相关按照某种规则，确认了二个对象或多个对象之间有关系，称这二个对象或多个对象是相关的。,例1：大写英文字母与五单位代码的对应关系R1:令=A,B,C,D,Z=30,23,16,22,21是五单位代码集合=11000,10011,01110,10010,10001R1=,.,2020/4/26,14,例2：令=1,2,3,4,A中元素间的关系R2：R2=,AA,关系的定义定义1:设A、是集合，如果AB，则称R是一个从A到B的二元关系。如果RAA，则称R是A上的二元关系。二元关系简称为关系。定义2:任何序偶的集合，都称之为一个二元关系。如:R=,基本概念,2020/4/26,15,RxRy也称之为x与y有关系。,RxRy也称之为x与y没有关系。,例3.R是实数集合，R上的几个熟知的关系,从例3中可以看出关系是序偶(点)的集合(构成线、面)。,2020/4/26,16,关系的定义域与值域定义域(domain)：设RAB，由所有R的第一个元素组成的集合，称为R的定义域。记作domR，即domR=x|y(R)值域(range)：设RAB，由所有R的第二个元素组成的集合，称为R的值域。记作ranR，即ranR=y|x(R)令：R1=,domR1=1,2,3,4ranR1=1,2,3,4,2020/4/26,17,枚举法：即将关系中所有序偶一一列举出，写在大括号内。如R=,。谓词公式法：即用谓词公式表示序偶的第一元素与第二元素间的关系。例如R=|xR时，从x到y引一条有向弧(边)。这样得到的图形称为R的关系图。,关系的表示方法,2020/4/26,18,例设A=1,2,3,4,B=a,b,c,R1AB,R2AA，R1=,R2=,R1、R2的关系图如下：,2020/4/26,19,矩阵表示法：设A=a1,a2,am，B=b1,b2,bn是个有限集，RAB，定义R的mn阶矩阵MR=(rij)mn，其中,例：R1=,R2=,2020/4/26,20,空关系：因为AB，(或AA)，所以也是一个从A到B(或A上)的关系，称之为空关系。即无任何元素的关系，它的关系图中只有结点,无任何边；它的矩阵中全是0。完全关系(全域关系)：AB(或AA)本身也是一个从A到B(或A上)的关系，称之为完全关系。即含有全部序偶的关系。它的矩阵中全是1。,三个特殊关系,2020/4/26,21,A上的恒等关系IA：IAAA,且IA=|xA为A上的恒等关系。例如A=1,2,3,则IA=,A上的、完全关系及IA的关系图及矩阵如下：,2020/4/26,22,由于关系就是集合，所以集合的、-、和运算对关系也适用。例如A是学生集合，R是A上的同乡关系，S是A上的同姓关系，则RS：或同乡或同姓关系RS：既同乡又同姓关系R-S：同乡而不同姓关系RS：同乡而不同姓,或同姓而不同乡关系R：不是同乡关系,这里R=(AA)-R作业P109、c)d),关系的集合运算,2020/4/26,23,本节中所讨论的关系都是集合A中的关系。关系的性质主要有：自反性、反自反性、对称性、反对称性和传递性。一.自反性定义:设R是集合A中的关系，如果对于任意xA都有R(xRx)，则称R是A中自反关系。即R是A中自反的关系x(xAxRx)例如：在实数集合中,“”是自反关系，因为，对任意实数x，有xx.,4-3关系的性质,2020/4/26,24,从关系有向图看自反性:每个结点都有环。从关系矩阵看自反性：主对角线都为1。,令A=1,2,3，确定以下八个关系中哪些是自反的？,2020/4/26,25,二.反自反性定义：设R是集合A中的关系，如果对于任意的xA都有R，则称R为A中的反自反关系。即R是A中反自反的x(xAR)从关系有向图看反自反性:每个结点都无环。从关系矩阵看反自反性：主对角线都为0。如实数的大于关系，父子关系是反自反的。注意：一个不是自反的关系，不一定就是反自反的，如前边R6、R7非自反,也非反自反。,2020/4/26,26,R2、R5、R8、均是反自反关系。,观察下图：,2020/4/26,27,三.对称性定义:R是集合A中关系,若对任何x,yA,如果有xRy,必有yRx,则称R为A中的对称关系。R是A上对称的xy(xAyAxRy)yRx)从关系有向图看对称性:在两个不同的结点之间，若有边的话，则有方向相反的两条边。从关系矩阵看对称性：以主对角线为对称的矩阵。例邻居关系和朋友关系是对称关系。,2020/4/26,28,R3、R4、R6、R8均是对称关系。,2020/4/26,29,四.反对称性定义:设R为集合A中关系,若对任何x,yA,如果有xRy,和yRx,就有x=y,则称R为A中反对称关系。,由R的关系图看反对称性：两个不同的结点之间最多有一条边。从关系矩阵看反对称性：以主对角线为对称的两个元素中最多有一个1。另外对称与反对称不是完全对立的，有些关系它既是对称也是反对称的，如空关系和恒等关系。,2020/4/26,30,上面R1、R2、R4、R5、R8均是反对称关系。R4、R8既是对称也是反对称的。,2020/4/26,31,五.传递性定义:R是A中关系，对任何x,y,zA,如果有xRy,和yRz,就有xRz,则称R为A中传递关系。即R在A上传递xyz(xAyAzAxRyyRz)xRz)例实数集中的、，集合、是传递的。从关系关系图和关系矩阵中不易看清是否有传递性。必须直接根据传递的定义来检查。检查时要特别注意使得传递定义表达式的前件为F的时候此表达式为T，即是传递的。即若R与R有一个是F时(即定义的前件为假)，R是传递的。,例如A=1,2,下面A中关系R是传递的。通过带量词的公式在论域展开式说明R在A上传递,xyz(xAyAzAxRyyRz)xRz)xyz(xRyyRz)xRz)(为了简单做些删改)yz(1RyyRz)1Rz)yz(2RyyRz)2Rz)(z(1R11Rz)1Rz)z(1R22Rz)1Rz)(z(2R11Rz)2Rz)(z(2R22Rz)2Rz)(1R11R1)1R1)(1R11R2)1R2)(1R22R1)1R1)(1R22R2)1R2)(2R11R1)2R1)(2R11R2)2R2)(2R22R1)2R1)(2R22R2)2R2)(FF)F)(FT)T)(TF)F)(TF)T)(FF)F)(FT)F)(FF)F)(FF)F)T,2020/4/26,33,以上R1、R3、R4、R5、R8均是传递的关系。,本节要求：1.准确掌握这五个性质的定义。2.熟练掌握五个性质的判断和证明。R是A中自反的x(xAxRx)R是A中反自反的x(xAR)R是A上对称的xy(xAyAxRy)yRx)R是A上反对称的xy(xAyAxRyyRx)x=y)xy(xAyAxyxRy)yx)R在A上传递xyz(xAyAzAxRyyRz)xRz)注意性质表达式的前件为F时此表达式为T，即R是满足此性质的。(自反和反自反性除外),2020/4/26,35,2020/4/26,36,下面归纳这八个关系的性质：Y-有N-无,2020/4/26,37,2020/4/26,38,练习1:令I是整数集合，I上关系R定义为：R=|x-y可被3整除，求证R是自反、对称和传递的。证明：自反性：任取xI,因x-x=0,0可被3整除,所以有R,故R自反。对称性：任取x,yI,设R,由R定义得x-y可被3整除,即x-y=3n(nI)，y-x=-(x-y)=-3n=3(-n),-nNR,R是对称的。传递性:任取x,y,zI,设xRy,yRz,由R定义得x-y=3m,y-z=3n(m.nI)x-z=(x-y)+(y-z)=3m+3n=3(m+n),m+nN所以xRz,所以R传递。证毕,2020/4/26,39,练习2：设R是集合A上的一个自反关系,求证：R是对称和传递的，当且仅当和在R中,则有也在R中。证明：必要性已知R是对称和传递的。设R又R，(要证出R)因R对称的故R,又已知R由传递性得R。所以有如果和在R中,则有也在R中。充分性已知任意a,b,cA，如和在R中,则有也在R中。,2020/4/26,40,先证R对称任取a,bA设R，(要证出R)因R是自反的,所以R，由R且R，根据已知条件得R，所以R是对称的。再证R传递任取a,b,cA设R，R。(要证出R)由R是对称的,得R，由R且R，根据已知条件得R，所以R是传递的。作业第113页、,2020/4/26,41,4-4关系的复合,下面介绍由两个关系生成一种新的关系，即关系的复合运算。例如，有3个人a,b,c，A=a,b,c，R是A上兄妹关系，S是A上母子关系，RS即a是b的哥哥,b是a的妹妹;b是c的母亲，c是b的儿子。则a和c间就是舅舅和外甥的关系,记作RS,称它是R和S的复合关系。,2020/4/26,42,1.定义:设R是从X到Y的关系，S是从Y到Z的关系，则R和S的复合关系记作RS。定义为：RS=|xXzZy(yYRS)显然，RS是从X到Z的关系。2.复合关系的计算方法(俗称过河拆桥法)A=1,2,3B=1,2,3.4C=1,2,3,4,5RABSBC枚举法R=,S=,则RS=,2020/4/26,43,有向图法,关系矩阵法令A=a1,a2,amB=b1,b2,bnC=c1,c2,ctRABSBC,2020/4/26,44,2020/4/26,45,谓词公式法设I是实数集合，R和S都是I上的关系，定义如下：R=|y=x2+3xS=|y=2x+3,所以RS=|y=2x2+6x+3,三.性质关系复合运算不满足交换律，但是1.满足结合律:RABSBCTCD则,2020/4/26,46,b(bBR(ST)b(bBRc(cCST)bc(bBR(cCST)cb(cC(bBRST)c(cCb(bBRS)T)c(cC(RS)T),所以,可以用下图形象表示:,证明：任取,2020/4/26,47,2.RABSBCTBC,证明任取R(ST)b(bBRST)b(bBR(ST)b(bBRS)(bBRT)b(bBRS)b(bBRT)RSRT(RS)(RT)所以R(ST)=(RS)(RT),2020/4/26,48,证明任取R(ST)b(bBRST)b(bBR(ST)b(bBRS)(bBRT)b(bBRS)b(bBRT)RSRT(RS)(RT)所以R(ST)(RS)(RT)x(A(x)B(x)xA(x)xB(x),2020/4/26,49,3.R是从A到B的关系，则,验证:,令A=1,2,3,B=a,b,c,d,从这两个图看出它们的复合都等于R。,2020/4/26,50,4.关系的乘幂令R是A上关系，由于复合运算可结合，所以关系的复合可以写成乘幂形式。即,例如R是A上关系，如上图所示,可见R2,表明在R图上有从a到c有两条边的路径:abc;R3,表明在R图上有从a到d有三条边的路径:abcd。.如果Rk,表明在R图上有从x到y有k条边(长为k)的路径(x,yA)。,有,(m,n为非负整数),2020/4/26,51,4-5逆关系,一.定义R是从A到B的关系，如果将R中的所有序偶的两个元素的位置互换，得到一个从B到A的关系，称之为R的逆关系，记作RC，或R-1。RC=|RRCR二.计算方法1.R=,RC=,2020/4/26,52,2.RC的有向图：是将R的有向图的所有边的方向颠倒一下即可。3.RC的矩阵M=(MR)T即为R矩阵的转置。如,三.性质令R、S都是从X到Y的关系，则1.(RC)C=R2.(RS)C=RCSC。3.(RS)C=RCSC。4.(RS)C=RCSC。,2020/4/26,53,证明1：任取(RS)C，则(RS)CRSRSRCSCRCSC所以(RS)C=RCSC，其它类似可证。5.RSRCSC。证明：充分性，已知RCSC，则任取RRCSCSRS必要性，已知RS，则任取RCRSSCRCSC,2020/4/26,54,6.(R)C=RC证明:任取(R)CRRRCRC(R)C=RC,7.令R是从X到Y的关系，S是Y到Z的关系，则(RS)C=SCRC。(注意RCSC)证明：任取(RS)CRSy(yYRS)y(yYSCRC)SCRC所以(RS)C=SCRC,2020/4/26,55,8.R是A上关系，则R是对称的，当且仅当RC=RR是反对称的，当且仅当RRCIA。证明：充分性，已知RC=R(证出R对称)任取x,yA设R,则RC,而RC=R所以有R，所以R对称。必要性，已知R对称，(证出RC=R)先证RCR，任取RC,则R,因R对称所以有R，所以RCR。再证RRC，任取R,因R对称，所以有R，则RC,所以RRC。最后得RC=R。,2020/4/26,56,证明充分性，已知RRCIA，(证出R反对称)任取x,yA设R且R，RRRRC，RRCIA(因RRCIA)x=y所以R反对称。必要性，已知R反对称，(证出RRCIA)任取RRCRRCRRCRRx=y(因R反对称)IA所以RRCIA。,作业：第118页a)b)、,2020/4/26,57,4-6关系的闭包运算,关系的闭包是通过关系的复合和求逆构成的一个新的关系。这里要介绍关系的自反闭包、对称闭包和传递闭包。,一.例子给定A中关系R，如图所示，求A上另一个关系R，使得它是包含R的“最小的”(序偶尽量少)具有自反(对称、传递)性的关系。这个R就是R的自反(对称、传递)闭包。,2020/4/26,58,这三个关系图分别是R的自反、对称、传递闭包。,二.定义：给定A中关系R,若A上另一个关系R，满足：RR；R是自反的(对称的、传递的)；R是“最小的”，即对于任何A上自反(对称、传递)的关系R,如果RR,就有RR。则称R是R的自反(对称、传递)闭包。记作r(R)、s(R)、t(R)(reflexive、symmetric、transitive),2020/4/26,59,三.计算方法定理1.给定A中关系R,则r(R)=RIA。证明：令R=RIA,显然R是自反的和RR，下面证明R是“最小的”：如果有A上自反关系R且RR,又IAR,所以RIAR,即RR。所以R就是R的自反闭包。即r(R)=RIA。定理2.给定A中关系R,则s(R)=RRC。证明方法与1.类似。定理3.给定A中关系R,则t(R)=RR2R3.。证明：令R=RR2R3.,显然有RR；,2020/4/26,60,证R是传递的：任取x,y,zA,设有RR,由R定义得必存在整数i,j使得Ri,Rj,根据关系的复合得Ri+j,又因Ri+jR,所以R,R传递。证R是“最小的”：如果有A上传递关系R且RR,（证出RR）任取R,则由R定义得必存在整数i,使得Ri,根据关系的复合得A中必存在i-1个元素e1,e2,.,ei-1，使得(见49页)RR.R。因RR,有RR.R。由于R传递，所以有R。RR。综上所述，R就是R的传递闭包，即t(R)=RR2R3=Ri,2020/4/26,61,用上述公式计算t(R)，要计算R的无穷大次幂,好象无法实现似的。其实则不然，请看下例:A=1,2,3A中关系R1,R2,R3,如下：R1=,R2=,R3=,R12=,R13=R14=所以t(R1)=R1R12R13=R1R22=,R23=,R23=IA,R24=R2.t(R2)=R2R22R23R32=,R33=R32t(R3)=R3R32,2020/4/26,62,定理4.给定A中关系R,如果A是有限集合，|A|=n则t(R)=RR2.Rn。证明：令R=RR2R3.,R=RR2.Rn显然有RR,下面证明RR：任取R,由R定义得必存在最小的正整数i使得Ri,(下面证明in)如果in,根据关系的复合得A中必存在i-1个元素e1,e2,.,ei-1，使得RR.R。上述元素序列:x=e0,e1,e2,.,ei-1,y=ei中共有i+1个元素，i+1n,而A中只有n个元素，所以上述元素中至少有两个相同，设ej=ek(j,1,1,1,2,2,2,2,2020/4/26,121,P109X=a,b,cY=sX到Y的所有关系：XY=,XY的任何一个子集都是一个从X到Y的关系。如果|X|=m|Y|=n则有2mn个从X到Y的关系,故,有23=8个关系:R0=R1=R2=R3=R4=,R5=,R6=,R7=,设|A|=n，有多少个A上的关系？因为RAA,所以AA有多少个子集就有多少个A上关系,由集合的幂集就是该集合的子集构成的,所以A上关系个数就是AA的幂集P(AA)的元素个数|P(AA)|,而2|AA|=2nn=2n2。所以有2n2个不同的A上关系。P113A=1,2,3，A上五个关系如下：(T略有改动),上述五个关系中，哪些是等价关系？如果是等价关系，求其商集。哪些是相容关系？如果是相容关系，求其完全覆盖。哪些是偏序关系？如是偏序关系,画Hasse图,并求的极小(大)元、最小(大)元、上界与下界、上确界和下确界。等价关系：S和AA，对应的商集分别是：A/S=1,2,3A/AA=1,2,3相容关系:S和AA，对应的完全覆盖分别是：CS(A)=1,2,3CAA(A)=1,2,3偏序关系:T的极小元、最小元、下界、下确界都是：1的极大元、最大元、上界、上确界都是：3,c)R和S都对称，RS不一定对称。,举反例：,第118页R和S都是A上关系，a)R和S都自反,RS一定自反。b)R和S都反自反,RS不一定反自反。,举反例：,d)R和S都传递，RS不一定传递。,举反例：,S是上关系。a)证明传递，当且仅当S2S(可用此定理判定传递)证明：充分性，已知S2S任取x,y,zX,且有S,S,根据关系的复合得S2,由已知得S,所以传递。必要性，已知传递,任取S2,根据关系的复合得z(zXSS),由传递得S所以S2S,2020/4/26,126,b)证明自反，当且仅当IXS。(可用此定理判定自反)证明：充分性，已知IXS，任取xX,有IX,由已知得S,所以自反。必要性，已知自反，任取IX,得x=y,而S自反，所以SIXS,S是上关系，证明是自反和传递，则S2=S。其逆为真吗？证明由a)得传递，则S2S，只证明SS2任取S,又已知自反，所以S,于是有SS，由关系的复合得S2所以有SS2,最后得S2。其逆不一定为真。例如S如图所示：它满足S2，但不自反。,2020/4/26,128,R是A上关系，a)R自反，Rc也自反。因为任取xA,因R自反，所以R,Rcb)R对称，Rc也对称。因为R对称，所以Rc=RRc也对称。,c)R传递，Rc也传递。方法1.任取x,y,zA,且有Rc,Rc,于是R,R，因R传递，于是有Rc，Rc传递。方法2.t(Rc)=Rc(Rc)2(Rc)3=Rc(R2)c(R3)c=(RR2R3)c=(t(R)c=Rc(因为R传递，所以t(R)=R)所以Rc传递。(R2)c(RR)c=(RcRc)=(Rc)2,P113(4)R和S都A上是自反、对称、传递的，求证RS也是自反、对称和传递的。证明：一.证明RS的自反性方法1用自反定义证：任取xA,(证出RS)因R和S都自反，所以有R，S，于是有RS，所以RS也自反。方法2用恒等关系IA证：(证出IARS)方法3用自反闭包证：(证出r(RS)=RS,即(RS)IA=RS)因R和S都自反，所以r(R)=R,r(S)=S,r(RS)=(RS)IA=(RIA)(SIA)=r(R)r(S)=RS所以RS也自反。,二.证明RS的对称性：方法1用对称定义证：任取x,yA,设RS,(证出RS.)方法2用求逆关系证：(证出(RS)c=RS.)因为R和S对称，所以有Rc=R，Sc=S，而(RS)c=RcSc=RS，RS对称。方法3用对称闭包证：(证出s(RS)=RS,即(RS)(RS)c=RS.)因为R和S对称，所以s(R)=R,s(S)=Ss(RS)=(RS)(RS)c=(RS)(RcSc)=(RRc)(RSc)(SSc)(SRc)=(s(R)(RSc)(s(S)(SRc)=(R(RSc)(S(SRc)=RSRS对称。,三.证明R的传递性：方法1用传递定义证：任取x,y,zA,设RS,RS,(证出RS)RSRSRSRS(RR)(SS)RS（因为R、S传递）RS所以RS传递。方法2用传递闭包证：证出t(RS)=RS,即(RS)(RS)2(RS)3.=RS.方法3用定理证：证出(RS)(RS)(RS)用方法2、方法3证明此题的传递性有很大难度。R(ST)(RS)(RT),P127(1)R的有向图如图所示，求r(R)、s(R)、t(R)。(5)R1和R2是A上关系，且R2R1，求证a)r(R2)r(R1),b)s(R2)s(R1),c)t(R2)t(R1)。证明：a)r(R2)=R2IAR1IA=r(R1),b)s(R2)=R2(R2)cR1(R1)c=s(R1),(因为R2R1，所以(R2)c(R1)c)c)先用归纳法证明(R2)i(R1)i,i=1时，R2R1显然结论成立假设ik时，结论成立，即(R2)i(R1)i；i=k+1时,(R2)k+1=(R2)kR2(R1)kR1=(R1)k+1,t(R2)=R2(R2)2.(R2)k.R1(R1)2.(R1)k=t(R1)。c)的另一证法：,c)因为R2R1，又R1t(R1)，所以R2t(R1)。于是有t(R2)和t(R1)都是包含R2的传递关系，而t(R2)是包含R2的最小的传递关系，所以t(R2)t(R1)。(7).R1和R2是A上关系，求证a)r(R1R2)=r(R1)r(R2),b)s(R1R2)=s(R1)s(R2),c)t(R1)t(R2)t(R1R2),证明：a)r(R1R2)=(R1R2)IA=(R1IA)(R2IA)=r(R1)r(R2),b)s(R1R2)=(R1R2)(R1R2)c=(R1R2)(R1)c(R2)c=(R1(R1)c)(R2(R2)c)=s(R1)s(R2),c)因R1(R1R2)且R2(R1R2)，由题(5)得t(R1)t(R1R2),t(R2)t(R1R2)，所以有t(R1)t(R2)t(R1R2)。,(8).R是A上关系，R*=tr(R),求证:a)(R+)+=R+b)RR*=R+=R*Rc)(R*)*=R*R+=t(R)=RR2R3=R*=rt(R)=IARR2R3.=证明：a)(R+)+=t(t(R),因为t(R)是传递的，所以t(t(R)=t(R),即(R+)+=R+。b)RR*=R(IARR2R3.)复合对并可分配，=RR2R3=R+。类似可证R*R=R+c)(R*)*=tr(tr(R)=trtr(R)=trrt(R)(tr(R)=rt(R)=trt(R)(rt(R)是自反的，rrt(R)=rt(R)=ttr(R)=tr(R)(tr(R)是传递的，ttr(R)=tr(R)=R*,第130页(1).X是集合，且|X|=4，X有多少个不同的划分？解.第134页(2).X是集合，且|X|=4，X上有多少个不同的等价关系？解.此题的答案与上题一样。因为每个划分对应一个等价关系。,(4).R是A上关系，设S=|cARR求证若R是等价关系，则S也是等价关系。证明：a)证S自反：任取aA，R是自反的，有R,由S定义得S,(S定义中c就是a)S自反.b)证S对称:任取a,bA，且有S,由S定义得cARR,由R对称得cARR,由S定义得S,S对称.c)证S传递:任取a,b,cA,有S,S,由S定义得(dARR)(eARR),由于R传递,所以有R,R,由S定义得S,所以S传递.所以S是A上等价关系.(6).R是A上对称和传递的关系，证明如果aA,bA,使得R,则R是一个等价关系.证明:任取aA,有已知得bA,使得R,由R对称得R,又由R传递得,R,R自反,R是等价关系.,(1)(7).R和S都是A上等价关系,下面哪个是A上等价关系?证明或举反例说明.a)RSb)RSc)R(即AA-R)d)R-Se)R2f)r(R-S)解.a)c)d)f)不是.请看反例:,b).RS是等价关系,前面已经证明过.(第113页题(4)e).证R2自反,任取aA,因为R自反,所以R,根据关系的复合得,RR,即R2,所以R2自反。证R2对称,(R2)c=(Rc)2=R2(由R对称得Rc=R)R2对称证R2传递，任取a,b,cA,设有R2,R2,根据关系的复合得,(dARR)(eARR),由于R传递,所以有R,R,R2所以R2传递。最后得R2是等价关系。第139页(2).X=x1,x2,x3,x4,x5,x6,R是X上相容关系，其简化关系矩阵如下：求X的完全覆盖。解.R的简化图为：CR(X)=x1,x2,x3,x1,x3,x6,x3,x4,x5,x3,x5,x6,o,第145页(1).给定集合3,5,15，1,2,3,6,12，3,9,27,54，为整除关系，分别画出上述集合上的的关系图，Hasse图，并指出哪些是全序关系。,(6)P=x1,x2,x3,x4,x5,P上偏序关系的Hasse图如图所示，求子集x1,x2,x3，x2,x3,x4，x3,x4,x5和P的极小(大)元、最小(大)元、上界、下界、最小上界和最大下界(上确界和下确界)。,
展开阅读全文