离散数学复习题(期末测试卷)_离散数学期末试题

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

复习题

一、填空题（请将每空的正确答案写在答题纸相应位置处，答在试卷上不得分。每小题2分，共16分。）

1．谓词公式xy(P(x,y)Q(y,z))xR(x,y)中x的辖域是。

2．命题公式(pq)的成真赋值为。

3．在1和1000之间（包括1和1000在内）不能被4和5整除的数有个。

4．设R是定义在集合A{1,2,3,4}上的二元关系R{1,1,1,2,2,3,1,4}，则R的对称闭包s(R)。

5．A{1,2,3,4},xymin{x,y},则代数系统A,中的零元是。

6．具有10个结点的无向完全图的边数=。

7．一次同余方程3x1(mod5)的最小正整数解是。

8．84与198的最大公约数是。

二、单项选择题（从下列各题四个备选答案中选出一个正确答案，并将其代号写在答题纸相应位置处。答案错选或未选者，该题不得分。每小题2分，共16分。）

1.设F(x): x是有理数，G(x)：x能表示成分数。在一阶逻辑中，命题“没有不能表示成分数的有理数”可符号化为()。

A.x(F(x)G(x))B.x(F(x)G(x))

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

2.设个体域是整数集，则下列命题的真值为真的是()。

A．yx(xy1)B．xy(xy0)

C．xy(xyy2)D．yx(xyx2)

3.集合A{1,2,,10}上的关系R{x,y|xy10,x,yA}，则R的性质为()。

A、自反的B、传递的、对称的C、对称的D、反自反的、传递的4．对自然数集合N，下列定义的运算中()是不可结合的。

A.abab3B.aba2b

C.abab(mod 3)D.abmin{a,b}

5．下列各图中既是欧拉图，又是汉密尔顿图的是()。

A．B．C．D．

6．对于下列度数序列，可画成简单无向图的是()。

A．(1，1，1，2，3)B．(1，2，2，3，4，5)

C．(1，2，3，4，5，5)D．(2，3，3，4，5，6)

7.含有5个结点、3条边的不同构的简单图有()个。A.2B.3C.4D.5【】

8．5的模6逆等于()。

A．1B．

3C．4D．5

三、计算题（第1、2、3、4小题各7分，第5、6小题各8分共44分。）1．求命题公式(pq)(pr)的主析取范式和主合取范式。

2．设A,R为偏序集，其中A{1,2,3,4,6,9,24,54}，R是A上的整除关系。（1）画出A,R的哈斯图；（2）求A中的极大元；（3）令B{4,6,9}，求B的上确界和下确界。3．求下图1中带权无向图的最小生成树，并求出该最小生成树的权值。4．求解递推方程：an7an112an20,a04,a16。5．有向图D如图2所示，求：（1）D中v1到v3长度为3的通路有几条？（2）D中v1到v1长度为3的回路有几条？（3）D是哪类连通图？

v

4图1图

2v

36．在通讯中要传输字母a,b,c,d,e,f,g，它们出现的频率为：

a:30%,b:20%,c:15%,d:10%,e:10%,f:9%,g:6%，设计传输上述字母的最佳二元前缀码，画出最优树，并求传输100个按上述频率出现的字母所需二进制字个数。

四、证明题（每小题8分，共16分。）1．设R为自然数集N上的关系，定义N上的关系R如下：x,yRxy是偶数。（1）证明R为等价关系；（2）求商集N/R。2．设Z为整数集合，在Z上定义二元运算如下：证明：x,yZ,xyxy2，Z,是群。

五、符号化下列命题，并在自然推理系统P中论证结论的有效性（8分。）

若小张喜欢数学，则小李或小赵也喜欢数学。若小李喜欢数学，则他也喜欢物理。小张确实喜欢数学，可小李不喜欢物理。所以，小赵喜欢数学。

参考答案

一、填空题（请将每空的正确答案写在答题纸相应位置处，答在试卷上不得分。每小题2分，共16分。）

1．P(x,y)Q(y,z)2．10，11，003．600

4．{1,1,1,2,2,3,1,4,2,1,3,2,4,1}5．1 6．457．38．6

二、单项选择题（从下列各题四个备选答案中选出一个正确答案，并将其代号写在答题纸相应位置处。答案错选或未选者，该题不得分。每小题2分，共16分。）

1．C2．C3．C4．B5．C6．A7．C8．D

三、计算题（第1、2、3、4小题各7分，第5、6小题各8分共44分。）

1．解：主合取范式为：（5分）

(pq)(pr)(pq)(pr)

((pq)(rr))((pr)(qq))(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)M4M5M6

主析取范式为：（2分）

(pq)(pr)m0m1m2m3m7

(pqr)(pqr)(pqr)(pqr)(pqr)2．解：（1）A,R的哈斯图如下图所示。（3分）

429（2）A中的极大元是：24，54；(2分)

（3）B的上确界：无；B的下确界：1。(2分)3．解：所求该图的最小生成树如下图所示。（5分）

该最小生成树的权值之和

W（t）=2+1+1+2+3+4=13（2分）

4．解：其特征方程为：x27x120，其特征根是：x13,x24（2分）

通解为：anc13nc24n（2分）

代入初值得到：c1c24,3c14c26

解得：c110,c26（2分）

所以，原方程的解为：

an103n64n。（1分）

5．解：先求图D的邻接矩阵A及A2、A3。

11A

0

1110

220112，（1分）A1001



0001

122

541113,（2分）A1000

1102

233

232（2分）110



122

(1)D中v1到v3长度为3的通路有3条。（1分）(2)D中v1到v1长度为3的回路有5条。（1分）(3)D是强连通图。（1分）

6．解：按字母顺序，令pi为传输第i个字母的频率，i1,2,,7，则传输100个字母，各字母出现的频数为wi100pi，得

w130,w220,w315,w410,w510,w69,w76。将它们按照从小到大顺序排列，得691010152030。（2分）以wi为权求最优2叉树如下图所示。

6（4分）

传输的前缀码分别为：a01,b11,c001,d100,e101,f0001,g0000。传100个所需二进制数字个数为：

W(t)=15+30+60+100+40+20=265。（2分）

四、证明题（每小题8分，共16分。）1．（1）证明：

xN,因为xx2x，2xN且是偶数，于是x,xR,因此R在N上是自反的；（1分）

x,yN,若x,yR,则xy是偶数，即yx是偶数，于是y,xR, 因此R在N上是对称的；（1分）

x,y,zN,若x,yR且y,zR,则xy2k1yz2k2,k1,k2Z，于是xz(xy)(yz)2y2(k1k2y)，进而x,zR,因此R在N上是传递的；（2分）

综上所述，R是N上的等价关系。（1分）

（2）N关于等价关系R的所有等价类为[0]R{0,2,4,6,}和[1]R{1,3,5,7,}，则N/R{[0]R,[1]R}。（3分）

2．证明：显然，Z关于是封闭的。（1分）

对于任意x,y,zZ，由于

(xy)z(xy2)z(xy2)z2xyz4，而 x(yz)x(yz2)x(yz2)2xyz4，于是

(xy)zx(yz)，即满足结合律。（2分）

（2分）xZ，因为x2x22x2x，因此2是Z关于的单位元。

xZ，由于4xZ且x(4x)x(4x)22(4x)x，于是

x关于存在逆元4x。（2分）所以，Z,是群。（1分）

五、符号化下列命题，并在自然推理系统P中论证结论的有效性（8分。）解：设简单命题

p：小张喜欢数学。q：小李喜欢数学。

r：小赵喜欢数学。s：小李喜欢物理。（2分）前提：p(qr),qs,p,s 结论：r

（或写为：推理形式为p(qr),qs,p,sr）（1分）证明：

(1)qs前提引入(2)s前提引入

（2）拒取式（2分）(3)q（1）

(4)p(qr)前提引入(5)p前提引入

（5）假言推理（2分）(6)qr（4）

（6）析取三段论（1分）(7)r（3）

离散数学复习题

离散数学复习题一、填空1、命题中的否定联接词；蕴含联接词2、一个命题公式，若在所有赋值下取值为真，则称此公式为式；若……假，则……..为 永假 式；若至少存在一组赋值，其命题为真，则......

离散数学复习题

离散数学复习题• 设命题p，r的真值为1，命题q，s的真值为0，则（p→q）(﹁r→s)的真值为。• 只要4不是素数，3就是素数，用谓语表达式符号化为。• D=｛｝，则幂集ρ(D)=• A={a,{b}}，B=｛｝，则A×B=•......

本科离散数学复习题

离散数学复习题一、填空题1.集合A={,1}，B={1,2}，则2A2B=_________，2A2B=_________. A与B的笛卡尔积AB=_________.2.1000以内的所有正整数中，能被4和5同时整除的共有_____个，不能......

离散数学复习题1

逻辑1、给出的真值表2、证明为永真式 谓词量词和推理1、使用量词和谓词表达不存在这一事实2、证明前提“在这个班上的某个学生没有读过书”和班上的每个学生都通过了第一门......

离散数学函数复习题答案

第6章 函数一、选择题（每题3分）1、设A{a,b,c},B{1,2,3}，则下列关系中能构成A到B函数的是（ C ）A、f1{a,1,a,2,a,3}B、f2{a,1,b,1,b,2}C、f4{a,1,b,1,c,1}D、f1{a,1,a,2,b,2,c,3}2......