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

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

第二章 二元关系

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

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

离散数学习题参考答案

第一章 集合

１．分别用穷举法，描述法写出下列集合（１）偶数集合

（２）36的正因子集合（３）自然数中3的倍数（４）大于１的正奇数

(1)E={，-6，-4，-2，0，2，4，6，}

={2 i | i I }

(2)D= { 1, 2, 3, 4, 6, } = {x>o | x|36 }

(3)N3= { 3, 6, 9, ```} = { 3n | nN }

(4)Ad= {3, 5, 7, 9, ```} = { 2n+1 | nN }

２．确定下列结论正确与否（１）φφ

×（２）φ｛φ｝√（３）φφ√（４）φ｛φ｝√（５）φ｛ａ｝×（６）φ｛ａ｝√

（７）｛ａ，ｂ｝｛ａ，ｂ，ｃ，｛ａ，ｂ，ｃ｝｝×（８）｛ａ，ｂ｝｛ａ，ｂ，ｃ，｛ａ，ｂ，ｃ｝｝√（９）｛ａ，ｂ｝｛ａ，ｂ，｛｛ａ，ｂ｝｝｝×（１０）｛ａ，ｂ｝｛ａ，ｂ，｛｛ａ，ｂ｝｝｝√

３．写出下列集合的幂集（１）｛｛ａ｝｝

{φ, {{ a }}}

(2)φ

{φ}（３）｛φ，｛φ｝｝

{φ, {φ}, {{φ}}, {φ,{φ}} }（４）｛φ，ａ，｛ａ，ｂ｝｝

{φ, {a}, {{a,b }}, {φ}, {φ, a }, {φ, {a,b }}，{a, {a b }}, {φ,a,{ a, b }} }（５）Ｐ（Ｐ（φ））

{φ, {φ}, {{φ}}, {φ,{φ}} }

４．对任意集合Ａ，Ｂ，Ｃ，确定下列结论的正确与否（１）若ＡＢ，且ＢＣ，则ＡＣ√（２）若ＡＢ，且ＢＣ，则ＡＣ×（３）若ＡＢ，且ＢＣ，则ＡＣ×（４）若ＡＢ，且ＢＣ，则ＡＣ ×

５．对任意集合Ａ，Ｂ，Ｃ，证明

(1)A(BC)(AB)(AC)左差A(BC)差A(BC)D.MA(BC)

分配(AB)(AC)右(2)A(BC)(AB)(AC)1)左差A(BC)(1)的结论(AB)(AC)差(AB)(AC)右

2)左差A(BC)D.MA(BC)分配(AB)(AC)差(AB)(AC)右(3)A(BC)(AB)(AC)左差A(BC)D.MA(BC)幂等(AA)(BC)

结合,交换(AB)(AC)右(4)(AB)BAB 左差(AB)B对称差((AB)B)((AB)B)

分配,结合((AB)(BB))(A(B)B))

互补((AB)U)(A)

零一

(AB)(AB)右(5)(AB)CA(BC)左差(AB)C结合A(BC)

D.MA(BC)差A(BC)(6)(AB)C(AC)B左差(AB)C结合A(BC)交换A(CB)结合(AC)B

差(AC)B右(7)(AB)C(AC)(BC)右(5)A(C(BC))差A(C(BC))分配A((CB)(CC))互补A((CB)U)

零一A(CB)交换A(BC)(5)(AB)C左

６．问在什么条件下，集合Ａ，Ｂ，Ｃ满足下列等式

(1)A(BC)(AB)C左(AB)(AC)右若要右左,须CA(BC)，CA时等式成立

(2)ABA左右是显然的,AABAB,AB，AB时等式成立

(3)ABBABB,BB,B,代入原式得A，AB时等式成立

(4)ABBAABBA,只能AB,AB, BA,BA,AB时等式成立

(5)ABAB,若B,bB，当bA,bABA矛盾;当bA,bABA矛盾

(6)ABAB右左是显然的,ABAB,AAB,ABBAB,BAABAB时等式成立

(7)(AB)(AC)A左(AB)(AC)A(BC)A(BC)A(BC)A

ABC时等式成立

(8)(AB)(AC)左(AB)(AC)A(BC)A(BC)A(BC)

A(BC),AB,AC时等式成立

(9)(AB)(AC)左(AB)(AC)A(BC)A(BC)A(BC)

A(BC)时等式成立

(10)(AB)(AC)((AB)(AC))((AB)(AC))(AB)(AC)(AB)(AC)

由(6)知,(AB)(AC),ABAC,ABAC时等式成立

(11)A(BA)BA(BA)(AB)(AA)(AB)U(AB)B

AB时等式成立

７．设Ａ＝｛ａ，ｂ，｛ａ，ｂ｝，｝，求下列各式（１）φ∩｛φ｝=φ（２）｛φ｝∩｛φ｝={φ} （３）｛φ，｛φ｝｝－φ={φ,{φ}}（４）｛φ，｛φ｝｝－｛φ｝= {{φ}}（５）｛φ，｛φ｝｝－｛｛φ｝｝={φ}（６）Ａ－｛ａ，ｂ｝={{a,b}, φ}（７）Ａ－φ = A（８）Ａ－｛φ｝={a,b,{a,b}}（９）φ－Ａ=φ（１０）｛φ｝－Ａ=φ

８．在下列条件下，一定有Ｂ＝Ｃ吗？（１）ABAC

否，例：A={1，2，3}，B={4}，C={3,4}, ABAC{1,2,3,4},而BC。

（２）ABAC

否，例：A={1，2，3}，B={2，3}，C={2，3，4} ABAC{2,3},而BC。

（３）ABAC

对,若BC,不妨,aB,aC,若aA,aAB,aAB,aAB,aAC,aAC,aAC;若aA,aAB,aAB,aAB,aAC,aAC,aAC矛盾（４）ABAC且ABAC

bB,若bA,bABAC,bC,若bA,bABAC,bC，BC,同理,CB,BC

9.(1)(AB)(BC)AB

证:a左,a(BC),aB,aB;a(AB),而aB,aA,aAB

(2)若A(BC)且B(AC),则B。

若B,aB(AC)(AC),aA(BC),aC,aB即aB,矛盾

10．化简

((ABC)(AB))((A(BC))A)(AB)A(AB)A

(AA)(BA)(BA)BA11.设A={2，3，4}，B={1，2}，C={4，5，6}，求（１）AB{1, 3, 4} （２）ABC{1,3,5,6}（３）(AB)(BC){2,3,5,6}

12.设A={1，2，3，4}，B={1，2，5}，求

(1)P(A)P(B){φ,{1},{2},{1,2}}

(2)P(A)P(B)

{φ,{1},{2},{3},{4},{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}, {1,2,3,},{1,2,4,},{1,3,4,},{2,3,4},{1,2,3,4,},{5},{1,5}, {2,5},{1,2} }

(3)P(A)P(B)

{ {3},{4},{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{1,2,4},{1,3,4}，{2,3,4},{1,2,3,4} }

(4)P(A)P(B)

{{3},{4},{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{1,2,4},{1,3,4}, {2,3,4},{1,2,3,4},{5},{1,5},{2,5},{1,2,5} }

第三篇：《离散数学》期末复习

《离散数学》期末复习

内容：第一章~第七章 题型：

一、选择题（20%，每题2分）二．填空题（20%，每题2分）

三、计算题（20%，每题5分）

四、证明题（20%，每题5分）

五、判断题（20%，每题2分）

第1章 数学语言与证明方法

1.1 常用的数学符号

1.计算常用的数学符号式子 1.2 集合及其表示法

1.用列举法和描述法表示集合

2.判断元素与集合的关系(属于和不属于)3.判断集合之间的包含与相等关系，空集(E)，全集()4.计算集合的幂集

5.求集合的运算：并、交、相对补、对称差、绝对补

6.用文氏图表示集合的运算 7.证明集合包含或相等

方法一： 根据定义, 通过逻辑等值演算证明

方法二： 利用已知集合等式或包含式, 通过集合演算证明

1.3 证明方法概述

1、用如下各式方法对命题进行证明。 直接证明法：AB为真

 间接证明法：“AB为真”  “ ¬B ¬A为真”  归谬法(反证法)： A¬B0为真

 穷举法： A1B, A2B,…, AkB 均为真

 构造证明法：在A为真的条件下, 构造出具有这种性质的客体B  空证明法：“A恒为假”  “AB为真” 平凡证明法：“B恒为真”  “AB为真”  数学归纳法： 第2章 命题逻辑

2.1 命题逻辑基本概念

1、判断句子是否为命题、将命题符号化、求命题的真值（0或1）。

命题的定义和联结词(¬, , , , )

2、判断命题公式的类型

赋值或解释.成真赋值,成假赋值；重言式(永真式)、矛盾式(永假式)、可满足式:。2.2 命题逻辑等值演算

1、用真值表判断两个命题公式是否等值

2、用等值演算证明两个命题公式是否等值

3、证明联结词集合是否为联结词完备集 2.3 范式

1、求命题公式的析取范式与合取范式

2、求命题公式的主析取范式与主合取范式（两种主范式的转换）

3、应用主析取范式分析和解决实际问题 2.4 命题逻辑推理理论

1、用直接法、附加前提、归谬法、归结证明法等推理规则证明推理有效 第3章 一阶逻辑

3.1 一阶逻辑基本概念

1、用谓词公式符号命题（正确使用量词）

2、求谓词公式的真值、判断谓词公式的类型 3.2 一阶逻辑等值演算

1、证明谓词公式的等值式

2、求谓词公式的前束范式 第4章 关系

4.1 关系的定义及其表示

1、计算有序对、笛卡儿积

2、计算给定关系的集合

3、用关系图和关系矩阵表示关系 4.2 关系的运算

1、计算关系的定义域、关系的值域

2、计算关系的逆关系、复合关系和幂关系

3、证明关系运算满足的式子 4.3 关系的性质

1、判断关系是否为自反、反自反、对称、反对称、传递的2、判断关系运算与性质的关系

3、计算关系自反闭包、对称闭包和传递闭包 4.4 等价关系与偏序关系

1、判断关系是否为等价关系

2、计算等价关系的等价类和商集

3、计算集合的划分

4、判断关系是否为偏序关系

5、画出偏序集的哈期图

6、求偏序集的最大元、最小元、极小元、极大元、上界、下界、上确界、下确界

7、求偏序集的拓扑排序 第5章 函数

1.判断关系是否为函数 2.求函数的像和完全原像

3.判断函数是否为满射、单射、双射 4.构建集合之间的双射函数 5.求复合函数

6.判断函数的满射、单射、双射的性质与函数复合运算之间的关系 7.判断函数的反函数是否存在，若存在求反函数 第6章 图

1.指出无向图的阶数、边数、各顶点的度数、最大度、最小度

2.指出有向图的阶数、边数、各顶点的出度和入度、最大出度、最大入度、最小出度最小入出度

3.根据握手定理顶点数、边数等

4.指出图的平行边、环、弧立点、悬挂顶点和悬挂边 5.判断给定的度数列能否构成无向图

6.判断图是否为简单图、完全图、正则图、圈图、轮图、方体图 7.求给定图的补图、生成子图、导出子图 8.判断两个图是否同构 6.2 图的连通性

1.求图中给定顶点通路、回路的距离

2.计算无向图的连通度、点割集、割点、边割集、割边 3.判断有向图的类型：强连通图、单向连通图、弱连通图 6.3 图的矩阵表示

1.计算无向图的关联矩阵 2.计算有向无环图的关联矩阵 3.计算有向图的邻接矩阵 4.计算有向图的可达矩阵

5.计算图的给定长度的通路数、回路数 6.4 几种特殊的图

1、判断无向图是否为二部图、欧拉图、哈密顿图 第7章 树及其应用 7.1 无向树

1.判断一个无向图是否为树

2.计算无向树的树叶、树枝、顶点数、顶点度数之间的关系 3.给定无向树的度数列，画出非同构的无向树 4.求生成树对应的基本回路系统和基本割集系统 5.求最小生成树 7.2 根树及其应用

1.判断一个有向图是否为根树

2.求根树的树根、树叶、内点、树高 3.求最优树

4.判断一个符号串集合是否为前缀码 5.求最佳前缀码

6.用三种方法遍历根树

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

离散数学考试试题（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。则 ''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。－

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中结点为v1、v2、…、vn。由连通性，必存在与v1相邻的结点，不妨设它为v2（否则可重新编号），连接v1和v2，得边e1，还是由连通性，在v3、v4、…、vn中必存在与v1或v2相邻的结点，不妨设为v3，将其连接得边e2，续行此法，vn必与v1、v2、…、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)＜m，则有2n＝

wVd(w)＜m＋(m－2)(m－3)＋m＝m－

23m＋6，与（1）矛盾。所以，对于G中任意两个不相邻结点u、v都有d(u)＋d(v)≥m。由定理10.26可知，G是哈密尔顿图。离散数考试试题（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}} 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)，>＝

444

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中结点为v1、v2、…、vn。由连通性，必存在与v1相邻的结点，不妨设它为v2（否则可重新编号），连接v1和v2，得边e1，还是由连通性，在v3、v4、…、vn中必存在与v1或v2相邻的结点，不妨设为v3，将其连接得边e2，续行此法，vn必与v1、v2、…、vn1中的某个结点相邻，得新边en1，由此可见G中至少有n－1条边。

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

12344

333334

34333

4333

133

113

122244 6

第五篇：大学离散数学复习试题

离散数学练习题目

一、选择题

1．设A={{1，2，3}，{4，5}，{6，7，8}}，下列各式中____D______是错的。

A、A； B、{6，7，8}A； C、{{4，5}}A； D、{1，2，3}A。

2.已知集合A={a,b,c},B={b,c,e},则 A⊕B=___C___________ A.{a,b} B={c} C={a,e} D=φ

3.下列语句中，不是命题的是____A_________ A.我说的这句话是真话； B.理发师说“我说的这句话是真话”； C.如果明天下雨，我就不去旅游； D.有些煤是白的，所以这些煤不会燃烧；

4.下面___D______命题公式是重言式。

A.PQR ； B.(PR)(PQ)；C.(PQ)(QR)；

D、(P(QR))((PQ)(PR))。

5.公式(p∧q)∨(p∧～q)的主析取范式是____B_______ A.m1∨m2 B.m2∨m3 C.m0∨m2 D.m1∨m3

6．设L(x)：x是演员，J(x)：x是老师，A(x , y)：x钦佩y，命题“所有演员都钦佩某些老师”符号化为___D______。

A、x(L(x)A(x,y))； B、x(L(x)y(J(y)A(x,y)))； C、xy(L(x)J(y)A(x,y))； D、xy(L(x)J(y)A(x,y))。7.关于谓词公式（x）(y)(P(x,y)∧Q(y,z))∧(x)p(x,y),下面的描述中错误的是__B_____ A．（x）的辖域是（y）（P（x,y）∧Q(y,z)）

B．z是该谓词公式的约束变元

C．（x）的辖域是P（x,y）D．x是该谓词公式的约束变元 8． 设SAB，下列各式中____B___________是正确的。

A、domSB ； B、domSA； C、ranSA； D、domS  ranS = S。9．设集合X，则空关系X不具备的性质是____A________。

A、自反性； B、反自反性； C、对称性； D、传递性。

10.集合A，R是A上的关系，如果R是等价关系，则R必须满足的条件是__D___ A.R是自反的、对称的 B.R是反自反的、对称的、传递的 C.R是自反的、对称的、不传递的 D.R是自反的，对称的、传递的 11.集合A={a,b,c,d},B={1,2,3},则下列关系中__ACD______是函数

A.R={(a,1),(b,2),(c,1),(d,2)} B.R={(a,1),(a,2),(c,1),(d,2)} C.R={(a,3),(b,2),(c,1)} D.R={(a,1),(b,1),(c,1),(d,1)} 已知集合 RA,且R={(1,2),(1,2),(2,1),(2,2),(2,3),(2,4),(3,4),(4,1)},则顶点2的入度和出度分别是___D_______ A.2,3 B.2,4 C.3,3 D.3,4 13.设完全图Kn有n个结点(n≥2)，m条边，当下面条件__C____满足时，Kn中存在欧拉回路．

A．m为奇数 B．n为偶数 C．n为奇数 D．m为偶数 14.下面叙述正确的是____B______ A.二部图K3,3是欧拉图 B.二部图是平面图

K3,3是哈密尔顿图

C.二部图 K3,32

D.二部图K3,3是既不是欧拉图也不哈密尔顿图

15.已知某平面图的顶点数是12，边数是14，则该平面图有__D___个面 A.3 B.2 C.5 D.4 16．设G是n个结点、m条边和r个面的连通平面图，则m等于___A____。

A、n+r-2 ； B、n-r+2 ； C、n-r-2 ； D、n+r+2。17.下面几种代数结构中，不是群的是___D____ A. B. C. D.(这里Z，Q，R，N分别表示整数集、有理数集、实数集、自然数集，+普通加法)

二、问答题

1.在程序设计过程中，有如下形式的判断语句： if(a>=0)if(b>1)if(c<0)cout<

请将这段程序化简，并说明化简的理由。解：简化的程序：

if(a>=0 && b>1 && c<0)cout<

设置命题变量： p: a>=0；q:b>1;r:c<0;s:cout<

A=P→(q→(r→s))经过等值演算可得，A与下面的公式是等值的 P∧q∧r→s

2.集合A={ 1, 2, 3, 4, 5, 6, 7, 8, 9 }，R={(x,y)| x|y}, ①证明R是偏序关系。

②写出偏序集（A，R）的极小元、极大元；最小元、最大元 ③写出A的子集B={1,2,3,6}的最小上界、最大下界

解：①根据整除性质可知，R满足自反性，反对称性，传递性。所以R是A上的偏序关系。

②偏序集（A，R）的极小元：1，极大元：5, 6，7，8，9 最小元：1； 最大元：无

③子集B={1,2,3,6}的最小上界：6 子集B={1,2,3,6}的最大下界：1

3.(1)m个男孩子，n个女孩排成一排，任何两个女孩不相邻，有多少种排法？

(n<=m)插空问题

(2)如果排成一个园环，又有多少种排法？

解：(1)考虑5个男孩，5个女孩的情况

男孩的安排方法： _B_B_B_B_B_ 排列总数P(5,5)女孩的安排方法：6个位置安排5个女孩，排列中数 P(6,5)所以：总的排列方法数是 m!*p(m+1,n)

(2)考虑男孩的圆排列情况，结果是(m-1)!*p(m,n)

4.某商家有三种品牌的足球，每种品牌的足球库存数量不少于10只，如果我想买5只足球，有多少种买法？如果每种品牌的足球最少买一只，有多少种买法？

解：①这是一个多重集的组合问题

类别数是k=3，选取的元素个数是 r=5 多重集组合数的计算公式是 N所以：N=C(3+5-1,5)=c(7,5)=21 ②可自由选取的球只有2个 k=3,r=2 N=C(3+2-1,2)=C(4,2)=6

(rk1)!C(kr1,r)

r!(k1)!

5．某软件公司将职工分为三种岗位。该公司65人，有些职工（例如项目管理人员、设计人员）可能从事不止一个岗位的工作。每个职工至少被分在一个岗位。现在软件设计岗位（岗位A）（包括需求分析、概要设计和详细设计等工作）的人数是15人，代码编写岗位（岗位B）的人数是32人，软件测试岗位（岗位C）的人数是28人，同时参加岗位A和岗位B的有12人, 同时参加岗位B和岗位C的有8人, 同时参加岗位A和岗位C组的有3人，问，三个岗位参加的有多少人？

解： 已知 |A|=15，|B|=32，|C|=28，|A∩B|=12，|B∩C|=8，|A∩C|=3 设S表示全班同学总人数，则 |S|=65 求：|A∩B∩C|=？

根据容斥原理：

|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|B∩C|-|A∩C|+|A∩B∩C| 所以|A∩B∩C|=|A∪B∪C|-|A|-|B|-|C|+|A∩B|+|B∩C|+|A∩C| 因为每个同学至少参加一个小组，所以：|A∪B∪C|=|S| 因此：|A∩B∩C|=65-15-32-28+12+8+3=13 答：三个小组都参加的人数是13人

6.证明组合恒等式C(n,r)= C(n-1,r-1)+ C(n-1,r)

说明：也可以直接利用组合演算公式进行演算 7.求1228的个位数是多少? 解：1228的个位数就是1228 mod 10的余数1228mod10(12mod10)28mod1024*7mod10(27mod10)4mod108mod1064

8.已知图G有10条边, 4个3度顶点, 其余顶点的度数均小于2, 问G至少有多少个顶点?

解：由握手定理∑d(v)=2m=20，度数为3的顶点有3个占去12度，还有8度由其余顶点占有，而由题意，其余顶点的度数可为0，1，当均为1时所用顶点数最少，所以应有8个顶点占有此8度，即G中至少有8+4=12个顶点。

9刑侦人员审一件盗窃案时，已经掌握的线索如下：（1）甲或乙盗窃了电脑。

（2）若甲盗窃了电脑，则作案时间不能发生在午夜前。（3）若乙证词正确，则在午夜时屋里灯光未灭。（4）若乙证词不正确，则作案时间发生在午夜前。（5）午夜时屋里灯光灭了。

请通过命题逻辑推理，推论出谁是真正的盗窃犯？（写出详细的推理步骤）解 设p： 甲盗窃了电脑，q： 乙盗窃了电脑，r： 作案时间发生在午夜前，s： 乙证词正确，t：午夜时屋里灯光灭了。

前提： p∨q，p→~r，s→~t，~s→r，t(7)非p。。

10.插入排序算法的时间T与数据规模n的递推关系如下，求出T与n的显示关系表达式

T(n)T(n1)n1 T(1)0

解：

T(n)T(n1)n1 T(n2)n2n1T(n3)n3n2n1 T(nk)nkn2n1T(nk)kn-(12k)k(k1)T(nk)kn2令n-k=1，那么 k=n-1，所以：

n(n1)n(n1)n(n1) T(n)T(1)0222答：T与n的显示关系是：T(n)

11.解下列一阶同余方程组

n(n1)2x1(mod 3)x2(mod 4)x3(mod 5)解：已知a11,a22,a33;m13,m24,m35 方程组的齐次通解是：xkLcm(1,2,3)6k 60k 根据中国剩余定理，特解是：

x0a1M1(M1mod m1)a2M2(M2mod m2)a3M3(M3mod m3)M1m2m320,M2m1m315,M3m1m212 111M1mod m1是下列同余方程的解

3)，解得：x=2，即M12 M1x1(mod m1)即20x1(mod11同理可解得：M23，M33 11 7

x0a1M1(M1mod m1)a2M2(M2mod m2)a3M3(M3mod m3)mod m（120221533123）mod 60111所以：(4090108)mod 60238mod 6058

同余方程组的解是 xxx06k58 60k

12.假设需要加密的明文数据是a=8,选取两个素数p=7,q=19,使用RSA算法： ① 计算出密钥参数

② 利用加密算法计算出密文c ③ 利用解密算法根据密文c反求出明文a 解：① 取 p=7,q=19;计算 n=p*q=7*19=133 计算φ(n)=(p-1)*(q-1)=(7-1)*(19-1)=108 选取较小的数w,使w与108互质, 5是最小的,于是w=5 计算d,使d*w≡1(mod φ(n)),即d*5 mod 108=1,取d=65，d*5除以108余数为1, 于是算出d=65 至此加密、解密参数计算完成：

公钥w=5,n=133.私钥d=65,n=133.② 加密

cmwmodn85mod133((82mod133)*(83mod133))mod133

(64*113)mod13350③ 解密

acdmodn5065mod133

aA0A6 其中，A050, Ai(Ai1)2

根据上述递推公式可以计算出：A1502mod133106,A21062mod13364

A3642mod133106，„„, A61062mod13364 aA0A6(50*64)mod1338

解密后的明文与原来的明文是相等的，所以算法正确。

13.设A={1，2，3，4，6，9，12，24},R定义为R{(a,b)|ab(mod 3)}，（1）证明R是一个等价关系；（2）写出A的商集；

14.基于字典序的组合生成算法

问题说明：假设我们需要从5个元素中选取3个的所有组合，已知组合个数为 C（５，３）＝１０，按字典序，其具体组合为： 123,124,125,134,135,145,234,235,245,345 所谓按字典序生成组合，就是已知当前的组合（例如135），求下一个组合（例如，145）。下面给出算法的函数头：

//数组s[]:函数运行前，保存当前的组合，函数结束后，是新生成的下一个组合 //n,r:表示从n个元素中选取r个元素的组合 void next_comb(int s[],int n,int r)解：

void next_comb(into s[],int n,int r){

int j,m,max_val;

max_val=n;

m=r;

while(s[m]==max_val)

{

m=m-1;

max_val=max_val-1;

}

s[m]=s[m]+1;

for(j=m+1;j

s[j]=s[j-1]+1;}

15.某单位要从A,B,C三人选派若干人出国考察, 需满足下述条件:(1)若A去, 则C必须去;(2)若B去, 则C不能去;(3)A和B必须去一人且只能去一人.问有几种可能的选派方案? 9