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

离散数学期末复习试题及答案(二)由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“离散数学试卷及答案二”。

第二章 二元关系

1.设A={1,2,3,4},A上二元关系

R={(a,b)|a=b+2},S={(x,y)|y=x+1 or y=

x2} 求RS,SR,SRS,S2,S

3,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.22

(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I

A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)R

1or(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)R

1and(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否,R

2的定义域不一定与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(R2R3)z,(x,z)R1,(z,y)R2or(z,y)R3z,(x,z)R1,(z,y)R2or(x,z)R

1,(z,y)R3(x,y)R1R2or(x,y)R1R3(x,y)R1R2R1R3

(2)R1(R2R3)R1R2R1R3(x,y)R1(R2R3)z,(x,z)R1,(z,y)R2and(z,y)R3z,(x,z)R

1,(z,y)R2and(x,z)R1,(z,y)R3(x,y)R1R2and(x,y)R1R3(x,y)R1R2R1R3(3)(4)类(1)(2)证明。

7.设R是A上的二元关系，证明对任意自然数m,n，(1)RmRnRmn(2)(Rm)nRmn

由归

(1)1)n1,Rm1RmR2)假定RmRnRmn{(a,b)|cA,(a,c)Rm,(c,b)Rn}n1RmR{(a,b)|cA,(a,c)Rm,(c,b)Rn1}其中,Rn1{(c,b)|dA,(c,d)Rn,(d,b)R}RmRn1{(a,b)|c,dA,(a,c)Rm,(c,d)Rn,(d,b)R}{(a,b)|dA,(a,d)Rmn,(d,b)R}RmnRR(mn)1Rm(n1)

(2)1)n1,RmRm2)假定(Rm)nRmn(Rm)n1(Rm)nRmRmnRm

由(1)RmnmRm(n1)8.设R是A上的二元关系，｜A｜＝n，证明存在 自然数s,t，使RsRt,且0st2n2，其中定义

R0{(a,a)|aA}。

0(ai,aj)R证:R(rij)nn,rij1(ai,aj)R至多有2n2个不同的Rk(kN)出现,

0k2n2,由鸽洞原理,(2n21)个Rk中必存在s,t,0st2n2,RsRt.9.R1，R2是Ａ上的二元关系，判别下列命题正确与否

(1)如果R1，R2自反，则R1R2也自反。

对,aA,(a,a)R1,(a,a)R2,(a,a)R

1R2

(2)如果R1，R2反自反，则R1R2也反自反。

否,若(a,b)R1,(b,a)R2,(a,a)R1R2

(3)如果R1，R2对称，则R1R2也对称。

否,例:A{1,2,3},R1{(1,2),(2,1)},R2{(2,3),(3,2)},(1,2)R

1,(2,3)R2,(1,3)R1R2,而(3,1)R1R2

(4)如果R1，R2反对称，则R1R2也反对称。

否,例:A{1,2,3},R1{(1,2),(3,2)},R2{(2,3),(2,1)},(1,2)R,3)R,1,(22,(1,3)R1R2(3,2)R1,(2,1)R2,(3,1)R1R2

(5)如果R1，R2传递，则R1R2也传递。

否,例:A{1,2,3,4},R1{(1,1),(2,3)},R2{(1,2),(3,3)},(1,1)R1,(1,2)R2,(1,2)R1R2,(2,3)R1,(3,3)R2,(2,3)R1R2,但(1,3)R1R2

10.设A={a,b,c}，以下分别给出一个P(A)上的二元 关系，确定它们哪些是自反的，反自反的，对称的，反对称的，传递的。 P(A)={,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}（１）ｘ是ｙ的一个真子集

R1{(x,y)|xy,x,yP(A)}

反自反，不对称，反对称，传递（２）ｘ与ｙ不相交

R2{(x,y)|xy,x,yP(A)}

不自反，也不反自反()，对称，不传递（３）xyA

R3{(x,y)|xyA,x,yP(A)}

不自反，也不反自反{a,b,c}{a,b,c}A，对称，不传递。

11.设R是A上二元关系，证明R是传递的当且仅当

R2R。

任(a,b)∈R2,C,(a,c)(c,b)∈R ,由R传递(a,b)∈R , 即R2  R;若(a,b)∈R,(b,c)∈R , 即(a,c)∈R2 R , 所以R传递。

12.R是A上反对称的二元关系，问t(R)总是反对称 的吗？

010111否, 例： R001,t(R)111

100111

13．设R是A上的一个自反关系，证明当且仅当(a,b)和(a,c)属于R推出(b,c)属于R时，R是一个等价 关系。

若(a,b)∈R，又自反(a,a)∈R, 推出(b,a)∈R, 所以对称；

若(a,b)(b,c)∈R , 由对称(b,a)(b,c)∈R , 推出(a,c)∈R ,所以传递。若R等价,(a,b)(a,c)∈R , 由对称性(b,a)(a,c)∈R , 由传递性 ,(b,c)∈R。

14.设R是A上的一个对称和传递的关系，证明如果对A中的每个a，在A中存在b，使得(a,b)∈R，则R是一个等价关系。 aA,bA,(a,b)R,由对称性,(b,a)R,又由传递性,(a,a)R.15.设R是A上的一个传递和自反的关系，设T是 A上的一个二元关系，使得当且仅当(a,b)和(b,a)同时 属于R时，(a,b)∈T，证明T是一个等价关系。 a(a,a)∈R,(a,a)∈R =>(a,a)∈T 若(a,a)∈T,(a,b)(b,a)∈R , 即(b,a)(a,b)∈R

=>(b,a)∈T 若(a,b)(b,c)∈T,(a,b)(b,a)(b,c)(c,b)∈R

=>(a,c)∈R,(c,a)∈R

=>(a,c)∈T

16.设R是A上一个二元关系，设

S={(a,b)｜对某个C，(a,c)∈R且(c,b)∈R｝

证明如果R是等价关系，则Ｓ也是等价关系。

a,(a,a)∈R,(a,a)∈R

=>(a,a)∈S 若(a,b)∈S , 存在c,(a,c)(c,b)∈R 由R对称,(b,c)(c,a)∈R , 所以(b,a)∈S 若(a,b)(b,c)∈S

存在d,e

(a,d)(d,b)(b,e)(e,c)∈R

由R传递(a,b)(b,c)∈R 所以(a,c)∈S

17.设R是A上的二元关系，对所有的xi,xj,xk∈A，如果xiRxj∧xjRxkxkRxi，则称R为循环关系，试证明当且仅当R是等价关系时，R才是自反的和循环的。（其中aRb表示(a,b)∈Ｒ）。

R等价, 当然自反，如果xiRxj且xjRxk则由传递性，xiRxk, 由对称性xkRxi，R是自反, 循环的；

若(a,b)∈R, 由R自反 a,(a,a)∈R, 又(a,b)∈R, 由循环(b,a)∈R，对称，若(a,b)(b,c)∈R，由循环(c,a)∈R, 由对称(a,c)∈R，传递。

18．设R1，R2是A上二元关系，证明(1)r(R1R2)r(R1)r(R2)(2)s(R1R2)s(R1)s(R2)(3)t(R1R2)t(R1)t(R2)(1)r(R1R2)(R1R2)IAR1IAR2R1(IAIA)R2(R1IA)(IAR2)(R1IA)(R2IA)r(R1)r(R2)(2)s(Rc1R2)(R1R2)(R1R2)Rcc1R2R1R2

(Rcc1R1)(R2R2)s(R1)s(R2)(3)(R1R2)2{(a,b)|c,(a,c)R1orR2,(c,b)R1orR2}R221R2R1R2R2R1 29 R2221R2(R1R2)用归纳法可证RnRnn12(R1R2)

n,可得t(R1)t(R2)t(R1R2)

19.设A={a,b,c,d},A上二元关系

R={(a,b),(b,a),(b,c),(c,d)}

（１）用矩阵算法和作图法求r(R),s(R),t(R)。（２）用Warshall算法求t(R)。

110001001111 r(R)=1110101011110011 s(R)= 0101 t(R)=0001000100100000

010010011101010i10110i211100001100010001

0000j20000j1,20000i3111111111111110i311111i41111j20001000100010000j20000j1,2,30000

20.讨论正实数集上二元关系Ｒ的几何意义。（１）Ｒ是自反的（２）Ｒ是对称的（３）Ｒ是传递的

（提示：以第一象限的点讨论）

(1)第一象限角平分线

(2)关于对角平分线对称的点对集合(3)若有P1(x1,y1)、P2(x2,y2), 若x2=y1,必有第三个点P3(x1,y2)