离散数学复习题及参考解答.doc

《离散数学复习题及参考解答.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、复习题一、填空题（请将每空的正确答案写在答题纸相应位置处，答在试卷上不得分。每小题2分，共16分。）1．谓词公式中的辖域是。2．命题公式的成真赋值为。3．在1和1000之间（包括1和1000在内）不能被4和5整除的数有个。4．设是定义在集合上的二元关系，则的对称闭包。5．,,则代数系统中的零元是。6．具有10个结点的无向完全图的边数=。7．一次同余方程的最小正整数解是。8．84与198的最大公约数是。二、单项选择题（从下列各题四个备选答案中选出一个正确答案，并将其代号写在答题纸相应位置处。答案错选或未选者，该题

2、不得分。每小题2分，共16分。）1.设:是有理数，：能表示成分数。在一阶逻辑中，命题“没有不能表示成分数的有理数”可符号化为()。A.　B.C.D.2.设个体域是整数集，则下列命题的真值为真的是()。A．　　B．C．　D．3.集合上的关系，则的性质为()。A、自反的B、传递的、对称的C、对称的D、反自反的、传递的4．对自然数集合，下列定义的运算中()是不可结合的。A.B.C.D.5．下列各图中既是欧拉图，又是汉密尔顿图的是()。A．B．C．　D．6．对于下列度数序列，可画成简单无向图的是()。A．(1，1，1，

3、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条边的不同构的简单图有()个。【第1页共2页】A.2B.3C.4D.58．5的模6逆等于()。A．1B．3C．4D．5三、计算题（第1、2、3、4小题各7分，第5、6小题各8分共44分。）1．求命题公式的主析取范式和主合取范式。2．设为偏序集，其中，是上的整除关系。（1）画出的哈斯图；（2）求中的极大元；（3）令，求的上确界和下确界。3．求下图1中带权无向图的最小生成树，并求出该最小生成树的权值

4、。4．求解递推方程：。5．有向图D如图2所示，求：（1）D中到长度为3的通路有几条？（2）D中到长度为3的回路有几条？（3）D是哪类连通图？　图1图26．在通讯中要传输字母，它们出现的频率为：，设计传输上述字母的最佳二元前缀码，画出最优树，并求传输100个按上述频率出现的字母所需二进制字个数。四、证明题（每小题8分，共16分。）1．设为自然数集上的关系，定义上的关系R如下：是偶数。（1）证明为等价关系；（2）求商集。2．设为整数集合，在上定义二元运算如下：，证明：是群。五、符号化下列命题，并在自然推理系统P中论

5、证结论的有效性（8分。）若小张喜欢数学，则小李或小赵也喜欢数学。若小李喜欢数学，则他也喜欢物理。小张确实喜欢数学，可小李不喜欢物理。所以，小赵喜欢数学。【第2页共2页】参考答案一、填空题（请将每空的正确答案写在答题纸相应位置处，答在试卷上不得分。每小题2分，共16分。）1．2．10，11，003．6004．5．16．457．38．6二、单项选择题（从下列各题四个备选答案中选出一个正确答案，并将其代号写在答题纸相应位置处。答案错选或未选者，该题不得分。每小题2分，共16分。）1．C2．C3．C4．B5．C6．A7

6、．C8．D三、计算题（第1、2、3、4小题各7分，第5、6小题各8分共44分。）1．解：主合取范式为：（5分）主析取范式为：（2分）2．解：（1）的哈斯图如下图所示。（3分）（2）中的极大元是：24，54；(2分)（3）的上确界：无；的下确界：1。(2分)3．解：所求该图的最小生成树如下图所示。（5分）【第1页共3页】该最小生成树的权值之和W（t）=2+1+1+2+3+4=13（2分）4．解：其特征方程为：，其特征根是：（2分）通解为：（2分）代入初值得到：解得：（2分）所以，原方程的解为：。（1分）5．解：先

7、求图D的邻接矩阵及、。，（1分）,（2分）（2分）(1)D中到长度为3的通路有3条。（1分）(2)D中到长度为3的回路有5条。（1分）(3)D是强连通图。（1分）6．解：按字母顺序，令为传输第个字母的频率，，则传输100个字母，各字母出现的频数为，得。将它们按照从小到大顺序排列，得。（2分）以为权求最优2叉树如下图所示。（4分）传输的前缀码分别为：。传100个所需二进制数字个数为：W(t)=15+30+60+100+40+20=265。（2分）四、证明题（每小题8分，共16分。）1．（1）证明：因为，且是偶数，

8、于是【第2页共3页】因此在上是自反的；（1分）若则是偶数，即是偶数，于是因此在上是对称的；（1分）若且则，于是，进而因此在上是传递的；（2分）综上所述，是上的等价关系。（1分）（2）关于等价关系的所有等价类为和，则。（3分）2．证明：显然，关于是封闭的。（1分）对于任意，由于，而，于是，即满足结合律。（2分），因为，因此2是关于的单位元。（2分），由于且，于是关于存在逆元。（2分）所以