离散数学期末复习试题及答案(二).docx

离散数学期末复习试题及答案(二)

第一篇：离散数学期末复习试题及答案(二)第二章二元关系1.设A={1,2,3,4},A上二元关系R={(a,b)|a=b+2}，S={(x,y)|y=x+1ory=x2}求RS,SR,SRS,S2,S3,SRc。RS={(3,2),(4,3),(4,1)}SR={(2,1),(3,2)}SRS={(2,2),(3,3),(3,1)}S2={(1,1),(1,3),(2,2),(2,4),(3,2),(4,1),(4,3)}S3={(1,2),(1,4),(2,1),(2,2),(2,3),(3,1),(3,3),(4,2),(4,4)}SRc={(1,4),(2,3),(4,4)}2．A={a,b,c,d,e,f,g,h}，给定A上关系R的关系图如下：图3－14求最小正整数ｍ，ｎ，ｍ＜ｎ，使Ｒm＝Ｒn。Ｒ1＝Ｒ16这是因为R15是8个顶点以及8个自回路，相当于左图的点各走了5圈，左图的点各走了3圈，R16就成了原来的R．３．证明：(1)(InA)IA(a,a)I2nA,aA,(a,a)IA,...,(a,a)IA,(b,b)InA,bA,(b,b)IA.(2)IARRIAR(a,b)R,a,bA,(a,a)IA,(b,b)IA,(a,b)IAR,(a,b)RIA,即RIAR,RRIA;(a,b)IAR,若(a,b)R,则(a,b)IAR,矛盾,得IARR;同理,RIAR.事实上，当|A|有限时，R与IA复合，相当于矩阵与单位矩阵相乘，不会变化。(3)(RIn2nA)IARR...Rn1(RIA)IAR;设(RIk2A)IARR...Rk(RIk1(I2A)...RkARR)(RIA)(RR2...Rk1)(I2ARR...Rk)IR2...RkRk1AR４．判断下列等式是否成立（Ｒ,Ｒ1,Ｒ2均是Ａ到Ｂ的二元关系）(1)(Rccc1R2)R1R2对,(a,b)(Rc1R2)(b,a)R1R2(b,a)R1or(b,a)R2(a,b)Rc1or(a,b)Rc2(a,b)Rcc1R2(2)(Rcc1R2)R1Rc2对(a,b)(Rc1R2)(b,a)R1R2(b,a)R1and(b,a)R2(a,b)Rcc1and(a,b)R2(a,b)Rcc1R2(3)(R1R2)R1R2对cccc(a,b)(R1R2)(R1R2)c(b,a)R1R2(b,a)R1,(b,a)R2(a,b)Rc1,(a,b)Rc2(a,b)Rcccc1R2R1R2(4)(AB)cAB否,例:A{1,2},B{3,4},AB{(1,3),(2,3),(1,4),(2,4)}(AB)c{(3,1),(3,2),(4,1),(4,2)}(5)c否,c与的定义域,值域对换了一下.(6)(R)c(Rc)对,(a,b)(R)c(b,a)R(b,a)R(a,b)Rc(a,b)Rc(7)(Rcc1R2)R2Rc1否,R2的定义域不一定与R1的值域相同(8)如果Rcc1R2,则R1R2对,(a,b)Rc1,(b,a)R1R2,(a,b)Rc2.(9)如果R1Rcc2,则R1R2对,(a,b)Rc1,(b,a)R1R2,(a,b)Rc2，R1R2,(c,d)R2,(c,d)R1,(d,c)Rc2,而(d,c)Rc1..(10)R1R2R2R1否,R2的定义域不一定与R1的值域相同.5.设R1,R2是集合A上的二元关系，如果R2R1，其中r,s,t分别是自反闭包，对称闭包，传递闭包的记号。试证明:(1)r(R2)r(R1)R2R1,IAIA,R2IAR1IA(2)s(R2)s(R1)R2Rcc1,R2R1Rcc2R2R1R1(3)t(R2)t(R1)R222R1(R2)1(R1)1(即R2R2R1R1)(a,b)R(a,b)(R2R1(R1)1b)R22)1(a,2,cA,(a,c),(c,b)R2R1,(a,b)R21,(a,b)(R1)1(a,b)t(R2),k,使(a,b)(R2)k(R1)kt(R1).6.设R1,R2,R3,R4分别是A到B，B到C，B到C，Ｃ到D的二元关系，证明(1)R1(R2R3)R1R2R1R3(x,y)R1(