南昌大学 2007～2008学年第一学期期末考试试卷
试卷编号： ( A )卷 课程编号： 课程名称： 离散数学 考试形式： 闭卷 适用班级： 姓名： 学号： 班级： 学院： 专业： 考试日期： 题号 题分 得分 考生注意事项：1、本试卷共 5 页，请查看试卷中是否有缺页或破损。如有立即举手报告以便更换。 2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。 一 20 二 80 三 四 五 六 七 八 九 十 总分 100 累分人 签名 一、 填空题(每题 4 分，共 20 分) 得分 评阅人 1、使得公式p→(q∨r)成真的赋值是_______________________________ 使得公式p→(q∨r)成假的赋值是：_______________________________ 2、设个体域为D=?1,2,3?，试消去公式(?x)P(x)∨(?y)Q(y)中 量词的等价式_______________________________ 3、4个元素的集合共有___ 个不同的划分， 并给出三个划分块的划分_______________________________ 4、设A=?1,2?，求：A×P(A)= _______________________________ 5、无向树T有8片树叶，2个3度分枝点，其余的分枝点都是4度结点，问T有___个4度分枝点? 第 1 页 共 5 页
二、综合题(每小题10分，共 80 分) 得分 评阅人 1、有向图G如图所示。 ⑴ 写出G的邻接矩阵。 （2） 求G中长度为3的路的总数， 其中有多少条回路。 （3） 求G的可达性矩阵。 2、用等价演算证明： p→(q∨r)?(p∧?q)→r 3、求命题公式(?p→q)→(p∨?q)的主析取范式， 并求命题公式的成真赋值 第 2 页 共 5 页
4、将下列命题符号化。并讨论它们的真值 (1) 有些实数是有理数。 （2）每个自然数都有比它大的自然数。 5、证明(?x)(F(x)∨G(x))，(?x)(G(x)→?R (x))，(?x)R(x)?(?x)F(x) 第 3 页 共 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? 第 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 页