《离散数学作业题(期末测试卷)》由会员分享，可在线阅读，更多相关《离散数学作业题(期末测试卷)（5页珍藏版）》请在金锄头文库上搜索。
1、复习题一、填空题（请将每空的正确答案写在答题纸相应位置处，答在试卷上不得分。每小题2分，共16分。）1谓词公式中的辖域是。2命题公式的成真赋值为。3在1和1000之间（包括1和1000在内）不能被4和5整除的数有个。4设是定义在集合上的二元关系，则的对称闭包。5,则代数系统中的零元是。6具有10个结点的无向完全图的边数=。7一次同余方程的最小正整数解是。884与198的最大公约数是。二、单项选择题（从下列各题四个备选答案中选出一个正确答案，并将其代号写在答题纸相应位置处。答案错选或未选者，该题不得分。每小题2分，共16分。）矚慫润厲钐瘗睞枥庑赖。1. 设: 是有理数，：能表示成分数。在一阶逻辑
2、中，命题“没有不能表示成分数的有理数”可符号化为( )。聞創沟燴鐺險爱氇谴净。A. B. C. D. 2. 设个体域是整数集，则下列命题的真值为真的是( )。A BCD3. 集合上的关系，则的性质为( )。A、自反的 B、传递的、对称的C、对称的 D、反自反的、传递的4对自然数集合，下列定义的运算中( )是不可结合的。 A. B. C. D. 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. 含
3、有5个结点、3条边的不同构的简单图有( )个。【第 1 页 共 2 页】 A. 2 B. 3 C. 4 D. 5 85的模6逆等于( )。A1 B3 C4 D5三、计算题（第1、2、3、4小题各7分，第5、6小题各8分共44分。）1求命题公式的主析取范式和主合取范式。2设为偏序集，其中，是上的整除关系。（1）画出的哈斯图；（2）求中的极大元；（3）令，求的上确界和下确界。酽锕极額閉镇桧猪訣锥。3求下图1中带权无向图的最小生成树，并求出该最小生成树的权值。4求解递推方程：。5有向图D如图2所示，求：（1）D中到长度为3的通路有几条？（2）D中到长度为3的回路有几条？（3）D是哪类连通图？彈贸摄尔
4、霁毙攬砖卤庑。图1 图26在通讯中要传输字母，它们出现的频率为：，设计传输上述字母的最佳二元前缀码，画出最优树，并求传输100个按上述频率出现的字母所需二进制字个数。謀荞抟箧飆鐸怼类蒋薔。四、证明题（每小题8分，共16分。）1设为自然数集上的关系，定义上的关系R如下：是偶数。（1）证明为等价关系；（2）求商集。2设为整数集合，在上定义二元运算如下：，证明：是群。五、符号化下列命题，并在自然推理系统P中论证结论的有效性（8分。）若小张喜欢数学，则小李或小赵也喜欢数学。若小李喜欢数学，则他也喜欢物理。小张确实喜欢数学，可小李不喜欢物理。所以，小赵喜欢数学。厦礴恳蹒骈時盡继價骚。【第 2 页 共 2
5、 页】参考答案一、填空题（请将每空的正确答案写在答题纸相应位置处，答在试卷上不得分。每小题2分，共16分。）1 210，11，00 3600451645 73 86二、单项选择题（从下列各题四个备选答案中选出一个正确答案，并将其代号写在答题纸相应位置处。答案错选或未选者，该题不得分。每小题2分，共16分。）茕桢广鳓鯡选块网羈泪。1C2C3C4B 5C 6A 7C 8D三、计算题（第1、2、3、4小题各7分，第5、6小题各8分共44分。）1解：主合取范式为：（5分）主析取范式为：（2分）2解：（1）的哈斯图如下图所示。 （3分）（2）中的极大元是：24，54； ( 2分)（3）的上确界：无；的下
6、确界：1。 ( 2分)3解：所求该图的最小生成树如下图所示。（5分）【第 1 页 共 3 页】该最小生成树的权值之和W（t）=2+1+1+2+3+4=13（2分）4解：其特征方程为：，其特征根是：（2分）通解为：（2分）代入初值得到：解得：（2分）所以，原方程的解为：。 （1分）5解：先求图D的邻接矩阵及、。，（1分）,（2分）（2分）(1) D中到长度为3的通路有3条。（1分）(2) D中到长度为3的回路有5条。 （1分）(3) D是强连通图。 （1分）6解：按字母顺序，令为传输第个字母的频率，则传输100个字母，各字母出现的频数为，得。将它们按照从小到大顺序排列，得 。（2分）以为权求最优
7、2叉树如下图所示。（4分）传输的前缀码分别为：。传100个所需二进制数字个数为：W(t)=15+30+60+100+40+20=265。 （2分）四、证明题（每小题8分，共16分。）1（1）证明：因为，且是偶数，于是【第 2 页 共 3 页】因此在上是自反的；（1分）若则是偶数，即是偶数，于是因此在上是对称的； （1分）若且则，于是，进而因此在上是传递的； （2分）综上所述，是上的等价关系。 （1分）（2）关于等价关系的所有等价类为和，则。 （3分）2证明：显然，关于是封闭的。 （1分）对于任意，由于， 而，于是，即满足结合律。 （2分），因为，因此2是关于的单位元。（2分），由于且，于是关于存在逆元。 （2分） 所以，是群。（1分）五、符号化下列命题，并在自然推理系统P中论证结论的有效性（8分。）解：设简单命题p：小张喜欢数学。 q：小李喜欢数学。r：小赵喜欢数学。 s：小李喜欢物理。 （2分）前提：结论：（或写为：推理形式为 ） （1分）证明： 前提引入 前提引入 （1）（2）拒取式 （2分） 前提引入 前提引入 （4）（5）假言推理 （2分） （3）（6）析取三段论 （1分）【第 3页 共 3 页】
