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

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

ID:51776214

大小:687.00 KB

页数:5页

时间:2020-03-15

离散复习题及参考解答.doc_第1页
离散复习题及参考解答.doc_第2页
离散复习题及参考解答.doc_第3页
离散复习题及参考解答.doc_第4页
离散复习题及参考解答.doc_第5页
资源描述:

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

1、复习题一、填空题(请将每空的正确答案写在答题纸相应位置处,答在试卷上不得分。每小题2分,共18分。)1.设为真命题,为假命题,则复合命题的真值为。2.令是人,喜欢吃米饭。在一阶逻辑中,命题“不是所有的人都喜欢吃米饭.”的符号化形式为。3.已知命题公式A中含三个命题变项,则极大项M4的公式是。4.在1到500之间的整数(包含1与500)中,既不被5整除、也不被6整除的数有个。5.设,,则的传递闭包=。6.设是一个连通的平面图,共有个结点,条边和个面,则结点、边和面的关系为(欧拉定理)。7.在整数加群中

2、,。8.设为整数集,的逆元。9.300与168的最大公约数是。二、单项选择题(从下列各题四个备选答案中选出一个正确答案,并将其代号写在答题纸相应位置处。答案错选或未选者,该题不得分。每小题2分,共20分。)【第3页共3页】1.下列命题公式中,是永真公式的是()。A.B.C.D.2.关于谓词公式,下面的描述中错误的是()。A.的辖域是B.的辖域是C.是该谓词公式的约束变元D.是该谓词公式的约束变元3.5阶无向完全图的边数为()。A.5B.10C.15D.204.有向图G如右图所示,在G中,从V1到V3

3、长度为3的通路有()条。A.0B.1C.2D.35.下列图中,()是强连通图。A.B.C.D.6.在一棵树中有7片树叶,3个3度结点,其余都是4度结点,则该树有()个4度结点。A.1B.2C.3D.47.对于集合,不封闭的二元运算是()。A.B.C.D.8.下列各图中()是欧拉图。A.B.C.D.9.设是12阶循环群,则的生成元有()个。A.2B.3C.4D.510.3的模5逆等于()。A.1B.2C.3D.4三、计算题(每小题各8分,共40分。)1.求命题公式的主析取范式。2.设集合上二元关系定义

4、为,验证是偏序集,并画出哈斯图。3.求下列带权图的最小生成树,画出最小生成树,并求其权值。4.求树叶的权分别为2,3,9,18,23和29的最优2叉树T,并求树权W(T)。5.求解递推方程:。四、证明题(12分。)设,在上定义二元关系,,,(1)证明是上的等价关系;(2)求商集。五、应用题(10分)符号化下列命题,并在自然推理系统P中用逻辑推理确定谁是作案者。①营业员A或B盗窃了金项链。②若A作案,则作案时间不在营业时间。③若B提供的证据正确,则货柜未上锁。④若B提供的证据不正确,则作案时间发生在营

5、业时间。⑤货柜上了锁。参考答案一、填空题1.0(或F)2.(或)3.4.3335.6.7.-68.9.12二、单项选择题1.C2.D3.B4.D5.A6.A7.D8.B9.C10.B三、计算题(每小题各8分,共40分。)1.解:主析取范式为:2.解:R所对应的关系矩阵为由关系矩阵可知,对角线上所有元素全为1,故自反;,故反对称;由此可计算出对应的矩阵。由以上矩阵可知传递。所以,是偏序关系。对应的哈斯图如下图所示。3.解:所求该图的最小生成树如下图所示。该最小生成树的权值之和W(t)=2+1+1+2+

6、3+4=134.解:所求的最优2叉树如下图所示。该最优2叉树的权为W(t)=2×4+3×4+9×3+18×2+23×2+29×2=1875.解:其特征方程为:,其特征根是:通解为:代入初值得到:解得:所以,原递推方程的解为:。四、证明题(12分。)证明:(1)由于①自反性:,有,即是上的自反关系;②对称性:,有,即是上的对称关系;③传递性:,有故是上的传递关系。由(1)、(2)、(3)可知是上的等价关系。(2)上的等价类为:所以,五、应用题(10分)解:设简单命题p:A作案盗窃金项链。q:B作案盗窃

7、金项链。r:作案发生在营业时间。s:B提供的证据正确。t:货柜上了锁前提:结论:(或写为:推理形式为)证明:前提引入前提引入(1)(2)拒取式前提引入(3)(4)假言推理前提引入(5)(6)拒取式前提引入(7)(8)析取三段论

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。