南昌大学2007～2008学年第一学期期末考试试卷
试卷编号：课程编号：适用班级：学院：
题号题分得分一20二80三
B卷
课程名称：离散数学姓名：专业：
四五六七
考试形式：学号：
闭卷班级：
考试日期：
八九十总分100累分人签名
考生注意事项：1、本试卷共4页，请查看试卷中是否有缺页或破损。如有立即举手报告以便更换。2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。
一、填空题每题4分，共20分
得分评阅人
1、使得公式q∧p→q→p成真的赋值是：________使得公式q∧p→q→p成假的赋值是：________2、设Aab，B123，求：A×B____________________B×A____________________3、一棵无向树T有2个4度结点，3个3度结点，其余的结点都是树叶，问T有________片树叶4、指出公式zPx∧xRxz→yQxy∨Rxy中的约束变元________和________自由变元。5、A1234，A上二元关系R和S分别为：R122433S132442S____________________R
第1页共6页
f二、综合题每小题10分，共80分
得分评阅人
1、用等价演算证明：p→q→rp∧q→r
2、求命题公式p→q∧r的主合取范式并求命题公式的成假赋值
3、将下列命题符号化。并讨论它们的真值（1）凡是人都要休息。
（2）每个自然数都有比它大的自然数。
第2页共6页
f4、用CP规则证明。xFx→RxxFx→xRx
5、设A12345，A上的等价关系R定义为：R12213443∪IA画出关系图，找出所有等价类，总结等价类和关系图的关系。

6、无向图G如图所示。⑴写出G的邻接矩阵。⑶求G中长度为3的路的总数，其中有多少条回路。⑷求G的连通矩阵。
第3页共6页
f7、求带权3456789的最优二叉树T。
8、某单位按编制有7个工作空缺：p1，p2，，p7，有10个申请者：a1，a2，，a10。它们能胜任的工作集合依次是p1p5p6，p2p6p7，p3p4，p1p5，p6p7，p3，p2p3，p1p3，p1，p5。如果规定每个申请者最多只能安排一个工作。试给出一种方案使分配到工作的申请者最多。
离散数学B卷答案
一填空题1成真的赋值是：00，10，11成假的赋值是：012、A×Ba1a2a3b1b2b3B×A1a1b2a2b3a3b3、T有9片叶子4、约束变元：x，y，z，自由变元：x，y5、12133342
二、综合题1、p→q→rr