离散数学期末试卷A.doc

《离散数学期末试卷A.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、南昌大学2007～2008学年第一学期期末考试试卷试卷编号：(A)卷课程编号：课程名称：离散数学考试形式：闭卷适用班级：姓名：学号：班级：学院：专业：考试日期：题号一二三四五六七八九十总分累分人签名题分2080100得分考生注意事项：1、本试卷共5页，请查看试卷中是否有缺页或破损。如有立即举手报告以便更换。2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。一、填空题(每题4分，共20分)得分评阅人1、使得公式p→(q∨r)成真的赋值是使得公式p→(q∨r)成假的赋值是：2、设个体域为D=í1,2,3ý，试消去公式("x

2、)P(x)∨($y)Q(y)中量词的等价式3、4个元素的集合共有个不同的划分，并给出三个划分块的划分4、设A=í1,2ý，求：A×P(A)=5、无向树T有8片树叶，2个3度分枝点，其余的分枝点都是4度结点，问T有个4度分枝点?第5页共5页二、综合题(每小题10分，共80分)得分评阅人1、有向图G如图所示。⑴写出G的邻接矩阵。（2）求G中长度为3的路的总数，其中有多少条回路。（3）求G的可达性矩阵。2、用等价演算证明：p→(q∨r)Û(p∧Øq)→r3、求命题公式(Øp→q)→(p∨Øq)的主析取范式，并求命题公式的成真赋值第

3、5页共5页4、将下列命题符号化。并讨论它们的真值(1)有些实数是有理数。（2）每个自然数都有比它大的自然数。5、证明("x)(F(x)∨G(x))，("x)(G(x)→ØR(x))，("x)R(x)Þ("x)F(x)第5页共5页6、设A=í1,2,3,4ý，A上二元关系R定义为：R=í<1,2>,<2,1>,<2,3>,<3,4>ý求R的自反闭包、对称闭包和传递闭包。7、下面的0、1串集合，哪些是前缀码？做出前缀码对应的二叉树。（1）í01,10,11,000,111ý（2）í01,11,000,0010,0011ý第5页共

4、5页8、某单位按编制有7个工作空缺：p1，p2，…，p7，有10个申请者：a1，a2，…，a10。它们能胜任的工作集合依次是íp1,p5,p6ý，íp2,p6,p7ý，íp3,p4ý，íp1,p5ý，íp6,p7ý，íp3ý，íp2,p3ý，íp1,p3ý，íp1ý，íp5ý。如果规定每个申请者最多只能安排一个工作。试给出一种方案使分配到工作的申请者最多。第5页共5页