离散数学期末试题答案

第一篇：离散数学期末试题答案

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

第二章 二元关系

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，m

R1=R16

这是因为R15是8个顶点以及8个自回路，相 当于左图的点各走了5圈，左图的点各走了3圈， R16就成了原来的R.

3.证明：

(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

4.判断下列等式是否成立(R,R1,R2均是A到B的 二元关系)

(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

23

(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..

24



(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， 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

25

(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}。

26

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是A上的二元关系，判别下列命题正确与否

(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)上的二元 关系，确定它们哪些是自反的，反自反的，对称的， 反对称的，传递的。

27 P(A)={,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}} (1) x是y的一个真子集

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

反自反，不对称，反对称，传递 (2) x与y不相交

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

不自反，也不反自反()，对称，不传递 (3)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

28

=>(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是等价关系，则S也是等价关系。

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)。

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)}

(1) 用矩阵算法和作图法求r(R),s(R),t(R)。 (2)用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. 讨论正实数集上二元关系R的几何意义。 (1)R是自反的 (2)R是对称的 (3)R是传递的

(提示：以第一象限的点讨论)

(1)第一象限角平分线

(2)关于对角平分线对称的点对集合

(3)若有P1(x1,y1)、 P2(x2,y2), 若x2=y1,

必有第三个点P3(x1,y2)

30

第二篇：离散数学期末试题

离散数学考试试题(A卷及答案)

一、(10分)求(PQ)(P∧(Q∨R))的主析取范式 解：(PQ)(P∧(Q∨R))(( P∨Q))∨(P∧Q∧R))

(P∨Q)∨(P∧Q∧R))

(P∨Q∨P)∧(P∨Q∨Q)∧(P∨Q∨R) (P∨Q)∧(P∨Q∨R)

(P∨Q∨(R∧R))∧(P∨Q∨R) (P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R) M0∧M1

m2∨m3∨m4∨m5∨m6∨m7

二、(10分)在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断： 甲说：王教授不是苏州人，是上海人。 乙说：王教授不是上海人，是苏州人。 丙说：王教授既不是上海人，也不是杭州人。

王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人?

解 设设P：王教授是苏州人;Q：王教授是上海人;R：王教授是杭州人。则根据题意应有： 甲：P∧Q 乙：Q∧P 丙：Q∧R

王教授只可能是其中一个城市的人或者3个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有Q∧P，因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为：

((P∧Q)∧((Q∧R)∨(Q∧R)))∨((Q∧P)∧(Q∧R)) (P∧Q∧Q∧R)∨(P∧Q∧Q∧R)∨(Q∧P∧Q∧R) (P∧Q∧R)∨(P∧Q∧R) P∧Q∧R T 因此，王教授是上海人。

三、(10分)证明tsr(R)是包含R的且具有自反性、对称性和传递性的最小关系。

证明 设R是非空集合A上的二元关系，则tsr(R)是包含R的且具有自反性、对称性和传递性的关系。

若R是包含R的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r(R)R。则

1 'sr(R)s(R)=R，进而有tsr(R)t(R)=R。

综上可知，tsr(R)是包含R的且具有自反性、对称性和传递性的最小关系。

四、(15分)集合A={a，b，c，d，e}上的二元关系R为R={，，，，，，，，，，，，，}，

(1)写出R的关系矩阵。

(2)判断R是不是偏序关系，为什么? 解 (1) R的关系矩阵为： ''10M(R)000111111010101

00110001(2)由关系矩阵可知，对角线上所有元素全为1，故R是自反的;rij+rji≤1，故R是反对称的;可计算对应的关系矩阵为：

10M(R2)000由以上矩阵可知R是传递的。

111111010101M(R)

00110001

五、(10分)设A、B、C和D为任意集合，证明(A-B)×C=(A×C)-(B×C)。 证明：因为

∈(A-B)×Cx∈(A-B)∧y∈C

(x∈A∧xB)∧y∈C

(x∈A∧y∈C∧xB)∨(x∈A∧y∈C∧yC) (x∈A∧y∈C)∧(xB∨yC) (x∈A∧y∈C)∧(x∈B∧y∈C) ∈(A×C)∧(B×C) ∈(A×C)-(B×C) 所以，(A-B)×C=(A×C-B×C)。

六、(10分)设f：AB，g：BC，h：CA，证明：如果hgf=IA，fhg=IB，gfh=IC，则f、g、h均为双射，并求出f、g和h。

解 因IA恒等函数，由hgf=IA可得f是单射，h是满射;因IB恒等函数，由fhg=IB可得g是单射，f是满射;因IC恒等函数，由gfh=IC可得h是单射，g是满射。从而f、g、h均为双射。

由hgf=IA，得f=hg;由fhg=IB，得g=fh;由gfh=IC，得h=gf。

2 -

1-1

-1-1-1

-1

七、(15分)设是一代数系统，运算*满足交换律和结合律，且a*x=a*yx=y，证明：若G有限，则G是一群。

证明 因G有限，不妨设G={a1，a2，…，an}。由a*x=a*yx=y得，若x≠y，则a*x≠a*y。于是可证，对任意的a∈G，有aG=G。又因为运算*满足交换律，所以aG=G=Ga。令e∈G使得a*e=a。对任意的b∈G，令c*a=b，则b*e=(c*a)*e=c*(a*e)=c*a=b，再由运算*满足交换律得e*b=b，所以e是关于运算*的幺元。对任意a∈G，由aG=G可知，存在b∈G使得a*b=e，再由运算*满足交换律得b*a=e，所以b是a的逆元。由a的任意性知，G中每个元素都存在逆元。故G是一群。

八、(20分)(1)证明在n个结点的连通图G中，至少有n-1条边。

证明 不妨设G是无向连通图(若G为有向图，可略去边的方向讨论对应的无向图)。

设G中结点为v

1、v

2、…、vn。由连通性，必存在与v1相邻的结点，不妨设它为v2(否则可重新编号)，连接v1和v2，得边e1，还是由连通性，在v

3、v

4、…、vn中必存在与v1或v2相邻的结点，不妨设为v3，将其连接得边e2，续行此法，vn必与v

1、v

2、…、vn1中的某个结点相邻，得新边en1，由此可见G中至少有n-1条边。

2(2)给定简单无向图G=，且|V|=m，|E|=n。试证：若n≥Cm1+2，则G是哈密尔顿图。

2证明 若n≥Cm。 1+2，则2n≥m-3m+6 (1)

2若存在两个不相邻结点u、v使得d(u)+d(v)

wVd(w)

23m+6，与(1)矛盾。所以，对于G中任意两个不相邻结点u、v都有d(u)+d(v)≥m。由定理10.26可知，G是哈密尔顿图。

3 离散数考试试题(B卷及答案)

一、(10分)使用将命题公式化为主范式的方法，证明(PQ)(P∧Q)(QP)∧(P∨Q)。 证明：因为(PQ)(P∧Q)(P∨Q)∨(P∧Q)

(P∧Q)∨(P∧Q) (QP)∧(P∨Q)(Q∨P)∧(P∨Q) (P∧Q)∨(Q∧Q)∨(P∧P) ∨(P∧Q) (P∧Q)∨P

(P∧Q)∨(P∧(Q∨Q)) (P∧Q)∨(P∧Q)∨(P∧Q) (P∧Q)∨(P∧Q) 所以，(PQ)(P∧Q)(QP)∧(P∨Q)。

二、(10分)证明下述推理： 如果A努力工作，那么B或C感到愉快;如果B愉快，那么A不努力工作;如果D愉快那么C不愉快。所以，如果A努力工作，则D不愉快。

解 设A：A努力工作;B、C、D分别表示B、C、D愉快;则推理化形式为： AB∨C，BA，DCAD

(1)A 附加前提 (2)AB∨C P (3)B∨C T(1)(2)，I (4)BA P (5)AB

T(4)，E (6)B T(1)(5)，I (7)C T(3)(6)，I (8)DC P (9)D T(7)(8)，I (10)AD CP

三、(10分)证明xy(P(x)Q(y))(xP(x)yQ(y))。 xy(P(x)Q(y))xy(P(x)∨Q(y)) x(P(x)∨yQ(y)) xP(x)∨yQ(y) xP(x)∨yQ(y) (xP(x)yQ(y))

四、(10分)设A={，1，{1}}，B={0，{0}}，求P(A)、P(B)-{0}、P(B)B。 解 P(A)={，{}，{1}，{{1}}，{，1}，{，{1}}，{1，{1}}，{，1，{1}}} P(B)-{0}={，{0}，{{0}}，{0，{0}}-{0}={，{0}，{{0}}，{0，{0}}

4 P(B)B={，{0}，{{0}}，{0，{0}}{0，{0}}={，0，{{0}}，{0，{0}}

五、(15分)设X={1，2，3，4}，R是X上的二元关系，R={<1，1>，<3，1>，<1，3>，<3，3>，<3，2>，<4，3>，<4，1>，<4，2>，<1，2>} (1)画出R的关系图。 (2)写出R的关系矩阵。

(3)说明R是否是自反、反自反、对称、传递的。 解 (1)R的关系图如图所示： (2) R的关系矩阵为：

10M(R)11反自反的;由于矩阵不对称，R不是对称的;

经过计算可得

1011101100 00(3)对于R的关系矩阵，由于对角线上不全为1，R不是自反的;由于对角线上存在非0元，R不是10M(R2)111011101100M(R)，所以R是传递的。 00

六、(15分)设函数f：R×RR×R，f定义为：f()=。 (1)证明f是单射。 (2)证明f是满射。 (3)求逆函数f。

(4)求复合函数ff和ff。

证明 (1)对任意的x，y，x1，y1∈R，若f()=f()，则=，x+y=x1+y1，x-y=x1-y1，从而x=x1，y=y1，故f是单射。

(2)对任意的∈R×R，令x=-1-

1uwuwuwuwuw

，y=，则f()=<+，-22222uw>=，所以f是满射。 2(3)f()=<-1-1uwuw，>。 22-1

-1(4)ff()=f(f())=f()=<

xyxyxy(xy)，>=

22

33

444

5

55ff()=f(f())=f()==<2x，2y>。

七、(15分)给定群，若对G中任意元a和b，有a*b=(a*b)，a*b=(a*b)，a*b=(a*b)，

3试证是Abel群。

证明 对G中任意元a和b。

因为a*b=(a*b)，所以a*a*b*b=a*(a*b)*b，即得a*b=(b*a)。同理，由a*b=(a*b)可得，a*b=(b*a)。由a*b=(a*b)可得，a*b=(b*a)。

于是(a*b)*(b*a)=(b*a)=a*b，即b*a=a*b。同理可得，(a*b)*(b*a)=(b*a)=a*b，即b*a=a*b。

由于(a*b)*b=a*b=b*a=b*(b*a)=b*(a*b)=(b*a)*b，故a*b=b*a。

八、(15分)(1)证明在n个结点的连通图G中，至少有n-1条边。

证明 不妨设G是无向连通图(若G为有向图，可略去边的方向讨论对应的无向图)。

设G中结点为v

1、v

2、…、vn。由连通性，必存在与v1相邻的结点，不妨设它为v2(否则可重新编号)，连接v1和v2，得边e1，还是由连通性，在v

3、v

4、…、vn中必存在与v1或v2相邻的结点，不妨设为v3，将其连接得边e2，续行此法，vn必与v

1、v

2、…、vn1中的某个结点相邻，得新边en1，由此可见G中至少有n-1条边。

(2)试给出|V|=n，|E|=(n-1)(n-2)的简单无向图G=是不连通的例子。 解 下图满足条件但不连通。

12344

3

3

333334

4

4

4

4

2

2

3

3

34333

5

5

5

4

4

4333

133

113

122244 6

第三篇：2005-2006(1A)离散数学期末试卷答案

安徽大学2005-2006学年第一学期 《离散数学》期末考试试卷(A卷答案)

一、选择题(210=20分)

C,B,C,B,D,D,D,B,A,A

二、填空题(每空2分，总215=30分) 1.PQ，PQ，PQ

2.x(R(x)Q(x))，x(Q(x)R(x)Z(x))

3.{,{,{}},{{}},{}} 4.{1}和{2}，{1,2}，，无

5.2，5 6.{1,1,2,2,1,2,2,1,3,3,4,4,3,4,4,3} 7.f(f19(B))B，Bf1(f(B))

三、计算题(每小题8分，总28=16分)

1. 用等值演算法求命题公式((PQ)R)(PQ)的主析取范式和主合取范式。 解：

((PQ)R)(PQ)((PQ)R)(PQ)((PQ)R)(PQ)(PQ)(PQ)R(P(QQ))RPR4分

(PQR)(PQR)(主合取范式)(0，2)(1,3,4,5,6,7)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(主析取范式)2.设A3，解：因为

8分

(B)16，(AB)64，试求B，AB，AB和AB。

。于(B)16，所以B4;因为(AB)64，所以AB6(2分)是集合A,B的文氏图如下：

所以，AB1(4分)，AB2(6分)，AB5(8分)。

四、证明题(

1、2小题每小题9分，

3、4小题每小题8分，总分34) 1. 用CP规则证明P(QR)，Q(RS)，PQS。 证： ①Q P(附加前提) 1分 ②Q(RS) P 2分 ③RS T①②I 3分 ④P(QR) P 4分 ⑤P P 5分 ⑥QR T④⑤I 6分 ⑦R T①⑥I 7分 ⑧S T③⑦I 8分 ⑨QS CP 9分 2. 设R1和R2是A上的关系，证明下列各式： (a)r(R1R2)r(R1)r(R2) (b)s(R1R2)s(R1)s(R2)

(c)t(R1R2)t(R1)t(R2) 证：

(a)r(R1R2)R1R2I(R1I)(R2I)r(R1)r(R2)

(这里I是A上的相等关系) 3分

(b)s(R1R2)(R1R2)(R1R2)(R1R2)(R1R2)

~~~~~(R1R)(R2R2)s(R1)s(R2) 6分

(c)因为t(R1R2)R1，t(R1R2)R2且关系t(R1R2)具有传递特性，根据传递闭包定义 t(R1R2)t(R1)，t(R1R2)t(R2)，所以t(R1R2)t(R1)t(R2)。 9分

3. 设函数f:RRRR，f定义为：f(x,y)xy,xy。 (1)证明f是单射; (2)证明f是满射。 证明：(1)x1,y1，x2,y2RR，若f(x1,y1)f(x2,y2)，即

x1y1x2y2则，易得x1x2，y1y2，x1y1,x1y1x2y2,x2y2，

x1y1x2y2从而是单射。 4分

(2)p,qRR，由f(x,y)p,q，通过计算可得而p,q的原象存在，f是满射的。 8分 4. 设AN，B(0,1)。证明ABc。 证明：

定义一个从AB到实数R的函数f：

x(pq)/2，从

y(pq)/2f:ABR，f(n,x)nx，其中nN，x(0,1)

因为f是单射且Rc，所以ABc。 4分

此外，作映射g:(0,1)AB，g(x)0,x，其中x(0,1)。因为g是单射，故cAB。

所以ABc。 8分

第四篇：离散数学试题答案[范文]

《计算机数学基础》离散数学试题

一、单项选择题(每小题2分，共10分) 1. 命题公式(PQ)Q为 ()

(A) 矛盾式 (B) 可满足式(C) 重言式 (D) 合取范式

2. 设C(x): x是国家级运动员，G(x): x是健壮的，则命题“没有一个国家级运动员不是健壮的”可符号化为 ()

(A)x(C(x)G(x))(B)x(C(x)G(x))

(C)x(C(x)G(x))(D)x(C(x)G(x))

3.设集合A={{1,2,3}, {4,5}, {6,7,8}}，则下式为真的是()

(A) 1A(B) {1,2, 3}A

(C) {{4,5}}A(D) A

4. 设A={1,2},B={a,b,c},C={c,d}, 则A×(BC)= ()

(A) {<1,c>,<2,c>}(B) {,<2,c>}(C) {,}(D) {<1,c>,}

5. 如第5题图所示各图，其中存在哈密顿回路的图是 ()

二、填空题(每小题3分，共15分)

6. 设集合A={,{a}}，则A的幂集P(A7. 设集合A={1,2,3,4 }, B={6,8,12}, A到B的关系R={x,yy2x,xA,yB},那么R1=

8.图G如第8题图所示，

那么图G的割点是-abfced第8题图

9. 连通有向图D含有欧拉回路

的充分必要条件是.10.设X={a,b,c}，R是X上的二元关系，其关系矩阵为

101，那么R的关系图为MR=100100

三、化简解答题(每小题8分，共24分) 11. 简化表达式(((A(BC))A)(B(BA)))(CA).

12. 设代数系统(R*, )，其中R*是非0实数集，二元运算为：a,bR, ab=ab. 试问是否满足交换律、结合律，并求单位元以及可逆元素的逆元.13. 化简布尔表达式aab(cab).

四.计算题(每小题8分，共32分)

14. 求命题公式(PQ)(PQ)的真值表.

15.试求谓词公式x(P(x)xQ(x,y)yR(x,y))A(x,y)中，x,x,y的辖域，试

问R(x,y)和A(x,y)中x,y是自由变元，还是约束变元?16.设R1是A1={1,2}到A2=(a,b,c)的二元关系，R2是A2到A3={,}的二元关系，R1= {<1,a>,<1,b>,<2,c>}, R2={,}试用关系矩阵求R1R2的集合表达式.

v

217图G如第17题图

求图G的最小生成树.

v4v

3第17题图

五、证明题(第18题10分，第19题9分)18. 证明(PQ)((QR)R)(PS))S19. 设G为9个结点的无向图，每个结点的度数不是5就是6，试证明G中至少有5个度数为6的结点，或者至少有6个度数为5的结点.

《计算机数学基础》离散数学试题

之五解答

一、单项选择题(每小题2分，共15分) 1.B2.D3. C4.A5.C

二、填空题(每小题3分，共15分) 6. {,{},{{a}},{,{a}}}

7.{<6,3>,<8,4> }8.a, f9. D中每个结点的入度=出度.10. 见第10题答案图.三、化简解答题(每小题8分，共24分)

11 (((A(BC))A)(B(BA)))(CA)

c第10题答案图

(A(B(~BA)))(CA)(2分)

(A(AB))(CA)AC~A)

(4分)

(6分)(8分)

12. a,b,cR*, ab=ab=ba=ba，可交换;(2分)(ab)c=abc=abc=a(bc)=a(bc)=a(bc)，可结合.(4分)易见，单位元为1.(6分)

对aR*, aa1=aa1=1=a1a=a1a，故a的逆元：a1

-

-

-

-

(8分) a

13.aab(cab)

=aabcaab(2分)

=aab(5分)=(aa)(ab)ab(8分)

四、计算题(每小题8分，共32分)

表中最后一列的数中，每对1个数得2分.15. x的辖域：(P(x)xQ(x,y)yR(x,y))(2分) x的辖域：Q(x,y)(4分) y的辖域：R(x,y)(6分) R(x,y)中的x,y是约束变量，A(x,y)中的x,y是自由变量.(8分)

110

16.MR1,(2分)

001

01

(4分)MR20100

01

11001(6分)MR1R201

0010000



R1R2{1,}(8分)

v217图G的最小生成树，如第17题答案图.

首先选对边( v 1, v 2)得2分，

再每选对一条边得

1 分.

v4v

3第17题答案图

五、证明题(第18题10分，第19题9分，共19分)18.

①QRP(2分)②RP(4分)

③Q①，②析取三段论

④PQP(7分)

⑤P③，④拒取式⑥PSP

⑦S⑤，⑥析取三段论(10分)

19. 由第5章定理1(握手定理)的推论，G中度数为5的结点个数只能是0,2,4,6,8五种情况;(3分) 此时，相应的结点度数为6的结点个数分别为9，7，5，3，1个，(6分)

以上五种对应情况(0,9),(2,7),(4,5),(6,3),(8,1)，每对情况，两数之和为9，且满足第2个数大于或等于5，或者第1个数大于或等于6，意即满足至少有度数为6的结点5个，或者至少有度数为5的结点6个,(9分)

第五篇：离散数学考试试题（A卷及答案）

一、(10分)判断下列公式的类型(永真式、永假式、可满足式)? 1)((PQ)∧Q)((Q∨R)∧Q) 2)((QP)∨P)∧(P∨R) 3)((P∨Q)R)((P∧Q)∨R) 解：1)永真式;2)永假式;3)可满足式。

二、(8分)个体域为{1，2}，求xy(x+y=4)的真值。

解：xy(x+y=4)x((x+1=4)∨(x+2=4))

((1+1=4)∨(1+2=4))∧((2+1=4)∨(2+1=4)) (0∨0)∧(0∨1) 1∧10

三、(8分)已知集合A和B且|A|=n，|B|=m，求A到B的二元关系数是多少?A到B的函数数是多少?

解：因为|P(A×B)|=2|A×B|=2|A||B|=2mn，所以A到B的二元关系有2mn个。因为|BA|=|B||A|=mn，所以A到B的函数mn个。

四、(10分)已知A={1,2,3,4,5}和R={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>}，求r(R)、s(R)和t(R)。

解：r(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<1,1>,<2,2>,<3,3>,<4,4>,<5,5>} s(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<3,2>,<4,3>,<4,5>} t(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<1,1>,<1,3>,<2,2>,<2,4>,<1,4>}

五、(10分) 75个儿童到公园游乐场，他们在那里可以骑旋转木马，坐滑行铁道，乘宇宙飞船，已知其中20人这三种东西都乘过，其中55人至少乘坐过其中的两种。若每样乘坐一次的费用是0.5元，公园游乐场总共收入70元，求有多少儿童没有乘坐过其中任何一种。

解 设A、B、C分别表示骑旋转木马、坐滑行铁道、乘宇宙飞船的儿童组成的集合，|A∩B∩C|=20，|A∩B|+|A∩C|+|B∩C|-2|A∩B∩C|=55，|A|+|B|+|C|=70/0.5=140。

由容斥原理，得

|A∪B∪C|=|A|+|B|+|C|―|A∩B|―|A∩C|―|B∩C|+|A∩B∩C| 所以

|A∩B∩C|=75-|A∪B∪C|=75-(|A|+|B|+|C|)+(|A∩B|+|A∩C|+|B∩C|-2|A∩B∩C|)+|A∩B∩C|=75-140+55+20=10 没有乘坐过其中任何一种的儿童共10人。

六、(12分)已知R和S是非空集合A上的等价关系，试证：1)R∩S是A上的等价关系;2)对a∈A，[a]R∩S=[a]R∩[a]S。

解：x∈A，因为R和S是自反关系，所以∈R、∈S，因而∈R∩S，故R∩S是自反的。

x、y∈A，若∈R∩S，则∈R、∈S，因为R和S是对称关系，所以因∈R、∈S，因而∈R∩S，故R∩S是对称的。

1 x、y、z∈A，若∈R∩S且∈R∩S，则∈R、∈S且∈R、∈S，因为R和S是传递的，所以因∈R、∈S，因而∈R∩S，故R∩S是传递的。

总之R∩S是等价关系。

2)因为x∈[a]R∩S∈R∩S∈R∧∈S x∈[a]R∧x∈[a]S x∈[a]R∩[a]S 所以[a]R∩S=[a]R∩[a]S。

七(10分)设A、B、C、D是集合，f是A到B的双射，g是C到D的双射，令h：A×CB×D且∈A×C，h()=。证明h是双射。

证明：1)先证h是满射。

∈B×D，则b∈B，d∈D，因为f是A到B的双射，g是C到D的双射，所以存在a∈A，c∈C，使得f(a)=b，f(c)=d，亦即存在∈A×C，使得h()==，所以h是满射。

2)再证h是单射。

、∈A×C，若h()=h()，则=，所以f(a1)=f(a2)，g(c1)=g(c2)，因为f是A到B的双射，g是C到D的双射，所以a1=a2，c1=c2，所以=，所以h是单射。 综合1)和2)，h是双射。

八、(12分)是个群，u∈G，定义G中的运算“”为ab=a*u-1*b，对任意a,b∈G，求证：也是个群。

证明：1)a,b∈G，ab=a*u-1*b∈G，运算是封闭的。

2)a,b,c∈G，(ab)c=(a*u-1*b)*u-1*c=a*u-1*(b*u-1*c)=a(bc)，运算是可结合的。 3)a∈G，设E为的单位元，则aE=a*u-1*E=a，得E=u，存在单位元。

4)a∈G，ax=a*u-1*x=E，x=u*a-1*u，则xa=u*a-1*u*u-1*a=u=E，每个元素都有逆元。 所以也是个群。

九、(10分)已知：D=，V={1,2,3,4,5}，E={<1,2>,<1,4>,<2,3>,<3,4>,<3,5>,<5,1>}，求D的邻接距阵A和可达距阵P。

解：D的邻接距阵A和可达距阵P如下：

A= 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0

1 0 1 0 0

0 0 1 0 0

P=

1 1 1 0 1

1 1 1 0 1

1 1 1 0 1

1 1 1 0 1

1 1 1 0 1

十、(10分)求叶的权分别为

2、

4、

6、

8、

10、

12、14的最优二叉树及其权。

解：最优二叉树为

权=148

离散数学考试试题(B卷及答案)

一、(10分)求命题公式(P∧Q)(PR)的主合取范式。

解：(P∧Q)(PR)((P∧Q)(PR))∧((PR)(P∧Q))((P∧Q)∨(P∧R))∧((P∨R)∨(P∨Q)) (P∧Q)∨(P∧R) (P∨R)∧(Q∨P)∧(Q∨R)

(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R) M1∧M3∧M4∧M5

二、(8分)叙述并证明苏格拉底三段论

解：所有人都是要死的，苏格拉底是人，所以苏格拉底是要死的。 符号化：F(x)：x是一个人。G(x)：x要死的。A：苏格拉底。 命题符号化为x(F(x)G(x))，F(a)G(a) 证明：

(1)x(F(x)G(x)) P (2)F(a)G(a) T(1),US (3)F(a) P (4)G(a) T(2)(3),I

三、(8分)已知A、B、C是三个集合，证明A∩(B∪C)=(A∩B)∪(A∩C) 证明：∵x A∩(B∪C) x A∧x(B∪C)

 x A∧(xB∨xC)

( x A∧xB)∨(x A∧xC)  x(A∩B)∨x A∩C  x(A∩B)∪(A∩C)

∴A∩(B∪C)=(A∩B)∪(A∩C)

四、(10分)已知R和S是非空集合A上的等价关系，试证：1)R∩S是A上的等价关系;2)对a∈A，[a]R∩S=[a]R∩[a]S。

解：x∈A，因为R和S是自反关系，所以∈R、∈S，因而∈R∩S，故R∩S是自反的。

x、y∈A，若∈R∩S，则∈R、∈S，因为R和S是对称关系，所以因∈R、∈S，因而∈R∩S，故R∩S是对称的。

x、y、z∈A，若∈R∩S且∈R∩S，则∈R、∈S且∈R、∈S，因为R和S是传递的，所以因∈R、∈S，因而∈R∩S，故R∩S是传递的。

总之R∩S是等价关系。

2)因为x∈[a]R∩S∈R∩S

∈R∧∈S x∈[a]R∧x∈[a]S x∈[a]R∩[a]S 所以[a]R∩S=[a]R∩[a]S。

五、(10分) 设A={a，b，c，d}，R是A上的二元关系，且R={，，，}，求r(R)、s(R)和t(R)。

解 r(R)=R∪IA={，，，，，，，} s(R)=R∪R={，，，，，} R={，，，} R={，，，} R={，，，}=R

t(R)=R={，，，，，，，，} i1i

4232-

1六、(15分) 设A、B、C、D是集合，f是A到B的双射，g是C到D的双射，令h：A×CB×D且∈A×C，h()=。证明h是双射。

证明：1)先证h是满射。

∈B×D，则b∈B，d∈D，因为f是A到B的双射，g是C到D的双射，所以存在a∈A，c∈C，使得f(a)=b，f(c)=d，亦即存在∈A×C，使得h()==，所以h是满射。

2)再证h是单射。

、∈A×C，若h()=h()，则= ，所以f(a1)=f(a2)，g(c1)=g(c2)，因为f是A到B的双射，g是C到D的双射，所以a1=a2，c1=c2，所以=，所以h是单射。

综合1)和2)，h是双射。

七、(12分)设是群，H是G的非空子集，证明是的子群的充要条件是若a，bH，则有a*bH。

证明： a,b∈H有b∈H，所以a*b∈H。 a∈H，则e=a*a∈H

4 -1-

1-1-1a=e*a∈H ∵a,b∈H及b∈H，∴a*b=a*(b)∈H ∵HG且H≠,∴*在H上满足结合律 ∴是的子群。

八、(10分)设G=是简单的无向平面图，证明G至少有一个结点的度数小于等于5。

解：设G的每个结点的度数都大于等于6，则2|E|=d(v)≥6|V|，即|E|≥3|V|，与简单无向平面图-

1-1

-1-1-1的|E|≤3|V|-6矛盾，所以G至少有一个结点的度数小于等于5。 九.G=,A={a,b,c},*的运算表为：(写过程，7分)

(1)G是否为阿贝尔群?

(2)找出G的单位元;(3)找出G的幂等元(4)求b的逆元和c的逆元 解：(1)(a*c)*(a*c)=c*c=b=a*b=(a*a)*(c*c) (a*b)*(a*b)=b*b=c=a*c=(a*a)*(b*b) (b*c)*(b*c)=a*a=a=c*b=(b*b)*(c*c) 所以G是阿贝尔群

(2)因为a*a=a a*b=b*a=b a*c=c*a=c 所以G的单位元是a (3)因为a*a=a 所以G的幂等元是a (4)因为b*c=c*b=a，所以b的逆元是c且c的逆元是b

十、(10分)求叶的权分别为

2、

4、

6、

8、

10、

12、14的最优二叉树及其权。

解：最优二叉树为

权=148 5