集 美 大 学 试 卷 纸 2008—2009学年 第 二 学期 试卷 考 生 信 息 栏 学院 专业 班级 姓名 学号 6.经过图中每个结点一次且仅一次的回路称为 哈密尔顿回路 。 7.每个无限循环群有 2 个生成元。 8.四个元素以下的格都是 分配格（或模格） ． A 课程名称 适 用 学院、专业、装 订 线 离散数学 卷别 理学院 信息与计算科学专业 08级 计算机学院 计算机科学技术07级 题号 得分 阅卷人 一 二 三 四 五 9.图2中，点连通度为 1 ，边连通度为 1 ，并写出一个边数最少的边割集 {e7}或{e8} 。 考试 闭卷 √ 方式 开卷 □ 年级 备注 总分 六 图2 图3 10.写出图3中二元树的后根次序遍历法得到的结果 v3v4v1v5v7v6v2v0 。 得 分 一、填空题(共30分，每小题3分)。 得 分 二、应用题(共50分)。 1.设P与Q的真值为F,R与S的真值为T,则命题?(P?(Q?(R??P)))?(R??S)的真值是 T 。 2.公式 ?(P?Q)∧Q的类型为 矛盾式 。 3.设集合A={a, b, c}，则A上的等价关系共有 5 个。 4.若连通平面图有12个结点，7个面，则它有 17 条边。 5.设S={a,b}，其中的三个运算f1，f2，f3如图1所示。则满足交换律的运算有 f1,f2,f3 ；有幺元的运算是 f2 ；有零元的运算是 f1 。 1.（8分）通过逻辑等价公式法求出等价于(P?(Q∨R))∧(?P∨(Q?R))的主析取范式与主合取范式。 解：公式法：因为(P?(Q∨R))∧(?P∨(Q?R)) ?(?P∨Q∨R)∧(?P∨(Q∧R)∨(?Q∧?R)) ?(?P∨Q∨R)∧(((?P∨Q)∧(?P∨R))∨(?Q∧?R)) ?(?P∨Q∨R)∧(?P∨Q∨?Q)∧(?P∨Q∨?R)∧(?P∨R∨?Q)∧(?P∨R∨?R) ?(?P∨Q∨R)∧(?P∨Q∨?R)∧(?P∨?Q∨R) （4?M4∧M5∧M6 分） 图1 P1 P2 ?m0∨m1∨m2∨m3∨m7
? (?P∧?Q∧?R) ∨(?P∧?Q∧R) ∨(?P∧Q∧?R) ∨(?P∧Q∧R) ∨(P∧Q∧R) （8分） 4.（8分）设集合A＝{1,2,3,4,5,6,7,8,9}，D是A上的整除关系，则是偏序集，(1)画出其哈斯图； (2)考虑A的子集：B1＝{1,2,3,6}，求出B1的最大元、极小元、上界、最大下界。 答：(1)哈斯图 2.（7分）设A={1,2,3}，R={<1,2>,<2,2>,<2,3>}，求R的闭包关系r(R)，S(R)，t(R)，并画出R，r(R)，S(R)，t(R)的关系图。 解 r(R)=R∪IA ={<1,2>,<2,2>,<2,3>}∪{<1,1>,<2,2>,<3,3>}= 考 生 信 息 栏 学院 专业 班级 姓名 学号 {<1,1>,<2,2>,<3,3>,<1,2>,<2,3>} S(R)=R∪R-1={<1,2>,<2,2>,<2,3>}∪{<2,1>,<2,2>,<3,2 >}= {<1,2>,<2,1>,<2,2>,<2,3>,<3,2>} t(R)=R∪R2∪R3={<1,2>,<2,2>,<2,3>}∪{<1,2>,<2,2>,<1,3>,<2,3>}∪ 装 订 线 {<1,2>,<1,3>,<2,2>,<2,3>}={<1,2>,<1,3>,<2,2>,<2,3>} （3其关系图如图所示。 1 R 3 1 3 1 3 1 3 2 2 2 2 分） （4分） (2)B1的最大元为6、极小元为1、上界为6、最大下界为1。 r(R) S(R) t(R) （7分） （8分） 3.（5分）一棵树有ni个度数为i的结点，i=2, 3, …, l，则这棵树有多少片树叶？ 解：设这棵树有t片树叶，则这棵树共有(t+n2+n3+…+nl)个结点， (t+n2+n3+…+nl-1)条边． （2分） 由图中结点度数的总和等于边数的二倍，得 (t+n2+n3+…+nl-1)×2=t+2×n2+3×n3+…+l×nl， （4分） 解得：t=1×n3+…+(l-2)×nl+2． （5分） 5.（7分）求叶的权分别为2、4、6、8、10、12、14的最优二叉树及其权。 解：最优二叉树为 （5分） P3 P4
权＝148 （7分） 6.（6分）求群<4, +4>的所有的子群． 考 生 信 息 栏 学院 专业 班级 姓名 学号 得 分 解：群<4, +4>的所有的子群：<{0}, +4> （2分） <{0, 2}, +4> （4分） <{0, 1, 2, 3}, +4> （6分） 装 订 线 三、应用题(共20分)。 1．（9分）符号化下列语句，并用演绎法加以证明。 每个理工类专业的学生都要学习高等数学；有些大学生没有学习高等数学。所以有的大学生不是理工类专业的学生。 解：令P(x):x是理工类专业的学生 Q(x):x要学习高等数学 7.（9分）给出一个如图4所示的有向连通图G。 （1）写出它的邻接矩阵A ； （2）写出它的可达矩阵； （3）图中长度为3的路一共有多少条？ 答：（1） 邻接矩阵为 图4 ?0?0 A???0??0?101??011?； （2分） ?101?100??（3分） （2）可达矩阵为 ?0?0 B???0??0?0?0 （3） A2???0??0?111??111?. （5分） ?111?111?111??02??201??013A?，（6分） ?02111?????02011??12??22?，（ 7分） ?12?01?? （6分） A3中所有元素之和为18，故有18条长3为的路； （8分） P5 P6
考 生 信 息 栏 学院 专业 班级 姓名 学号 （9分） 装 订 线 3、（7分）设