离散数学样卷十二套(含答案).doc

证明下列各题1、 （10 分）证明蕴涵式： ()PQ2、 （10 分）证明： ,11fgfgI为 函 数 为 函 数 5、3、 （10 分）给定代数结构 ,N和 0,1，其中 N是自然数集合， 是数的乘法设 :01f，定义为： 2,()knfn否 则试证 N， ， ， 4、 （10 分）给定代数结构 ,R，其中 是实数集合，对 R中任意元 a和 b， 定义如下： abab试证明： ,R是独异点 求下列各题的解：1、试求下列公式的主析取范式和主合取范式（15 分）：()()PQ€2、 （15 分） 0123123R设 ， ， ， ， ， ， ， ， ， ， ， ， 试 求（1） 、 ， （2） 、 ， （3） 、 R， （4） 、 1R， （5） 、 1R3、 （15 分给定无向图 ,GVE，如图，试求：F E DCA B （1） 从 A 到 D 的所有基本链；（2） 从 A 到 D 的所有简单链；（3） 长度分别是最小和最大的简单圈；（4） 长度分别是最小和最大的基本圈；（5） 从 A 到 D 的距离。

4、 （15 分）给定二部图 12,GVE，如图9v8 7v 6 1V1v 2 3v 4 5v 2试求 V到 2的最大匹配、、 证明下列各题1、 （10 分）证明蕴涵式： ()PQP2、 （10 分）证明： ()()()ABCAC3、 （10 分）给定群 ,G，则 ,为 Abel 群 22()(,())abab4、 （10 分）给定代数结构 ,S，其中 S 中元为实数有序对， 定义为,,,2abcdabd，试证 ,是可交换独异点 求下列各题的解：1、试求下列公式的主析取范式和主合取范式（15 分）：(()PQR2、 （15 分）设 ,,,Rabca试求 (),rRs和 ()t3、 （15 分）给定有向图 ,GVE，如图，试求：（1） 、各结点的出度、入度和度；（2） 、从 v1到 v3的所有简单路和基本路；（3） 、所有简单回路和基本回路4、 （15 分）给定树 G，试求对应二叉树、、 证明下列各题1、 （10 分）证明蕴涵式： ()PQPv5 v4 v3v1 v22、 （10 分）证明： ,11fgfgI为 函 数 为 函 数 。

3、 （10 分）给定代数结构 ,N和 0,1，其中 N是自然数集合， 是数的乘法设 :0,1f，定义为： 2,()knfn否 则试证 N， ， ， 4、 （10 分）给定代数结构 ,S，其中 S 中元为实数有序对， 定义为,,,2abcdabd，试证 ,是可交换独异点 求下列各题的解：1、试求下列公式的主析取范式和主合取范式（15 分）：(()PQR2、 （15 分） 0123123R设 ， ， ， ， ， ， ， ， ， ， ， ， 试 求（1） 、 ， （2） 、 ， （3） 、 R， （4） 、 1R， （5） 、 1R3、 （15 分）给定有向图 ,GVE，如图，试求：（1） 、各结点的出度、入度和度；（2） 、从 v1到 v3的所有简单路和基本路；（3） 、所有简单回路和基本回路4、 （15 分）给定树 G，试求对应二叉树专业:信息与计算科学 课程名称: 离散数学 学分: 3试卷编号（D）v5 v4 v3v1 v2课程编号: 4114600 考试方式: 闭 卷 考试时间: 120 分钟拟卷人(签字 ): 拟卷日期:审核人(签字)：得分统计表题 号 一 二 总 分得 分一、第一部分1（10 分）写出下列公式的真值表A = (pq) r2（10 分）用等值演算法判断下列公式的类型q(pq)3（10 分）求主析取范式(pq)r得 分阅卷人4（10 分）判断下面推理是否正确若今天是 1 号，则明天是 5 号. 今天是 1 号. 所以明天是 5 号.5（10 分）用归缪法证明前提：( pq)r, rs, s, p 结论：q二、第二部分1（10 分）在一阶逻辑中将下面命题符号化正数都大于负数得 分阅卷人2（10 分）设偏序集如下图所示，求 A 的极小元、最小元、极大元、最大元. 设 B＝{ b,c,d}, 求 B 的下界、上界、下确界、上确界. 3（10 分） G=Z12是 12 阶循环群,写出 G 的所有子群4（10 分）考虑 110 的正因子集合 S110关于 gcd, lcm 运算构成的布尔代数.写出它所有的子布尔代数5（10 分）⑴对权 10,864,93,251,94构造一棵最优二元树，并求权和。

⑵求下图的最小生成树，并求最小权和2413332223225522专业:信息与计算科学 课程名称: 离散数学 学分: 3试卷编号（E）课程编号: 4114600 考试方式: 闭 卷 考试时间: 120 分钟拟卷人(签字): 拟卷日期:审核人(签字)：得分统计表题 号 一 二 总 分得 分一、第一部分1（10 分）写出下列公式的真值表B = (qp) qp2（10 分）用等值演算法判断下列公式的类型(pq)(qp)得 分阅卷人3（10 分）求主合取范式(pq)r4（10 分）判断下面推理是否正确若今天是 1 号，则明天是 5 号. 明天是 5 号. 所以今天是 1 号5（10 分）用附加前提证明法构造证明前提：pq, pr, rs 结论： sq二、第二部分1（10 分）在一阶逻辑中将下面命题符号化有的无理数大于有的有理数2（10 分）已知偏序集的哈斯图如下图所示, 试求出集合 A 和关系 R 的表达式. 3（10 分）设 G={e, a, b, c}是 Klein 四元群. 给出 G 的所有自同构.得 分阅卷人4（10 分）写出下图中 L1， L2， L3的原子。

5（10 分）写出下图所示树产生的前缀码专业:信息与计算科学 课程名称: 离散数学 学分: 3试卷编号（F）课程编号: 4114600 考试方式: 闭 卷 考试时间: 120 分钟拟卷人(签字 ): 拟卷日期:审核人(签字)：得分统计表题 号 一 二 总 分得 分一、第一部分1（10 分）写出下列公式的真值表C = (pq) q2（10 分）用等值演算法判断下列公式的类型((pq)(pq))r)得 分阅卷人3（10 分）用主析取范式判两个公式是否等值⑴ p(qr) 与 (pq)r⑵ p(qr) 与 (pq)r4（10 分）证明{}为联结词完备集5（10 分）直接证明法构造证明前提：(p q)r, rs, s 结论：pq二、第二部分1（10 分）在一阶逻辑中将下面命题符号化（1）人都爱美（2）有人用左手写字个体域分别为(a) D=“人类集合”={ x | x 是人}(b) D 为全总个体域2（10 分）分别画出下列各偏序集的哈斯图，再求出最大元、最小元、极大元和极小元 A ＝〔a,b,c,d,e 〕 ≤＝〔,,,,,, ∪I A3（10 分）设  f：R→R, g：R→R 23()()2xf gx求 fg, gf. 如果 f 和 g 存在反函数 , 求出它们的反函数.4（10 分）下图中的 L1, L2, L3和 L4是否是有补格。

得 分阅卷人5（10 分）用 Huffman 算法产生最佳前缀码在通信中，八进制数字出现的频率如下：0：25% 1：20%2：15% 3：10%4：10% 5：10%6：5% 7：5%求传输它们的最佳前缀码，并求传输 10000 个按上述比例出现的八进制数字需要多少个二进制数字？若用等长的（长为 3）的码字传输需要多少个二进制数字？ 专业: 信息与计算科学 课程名称: 离散数学 学分: 3试卷编号（G）课程编号: 411461 考试方式: 闭 卷 考试时间: 100 分钟拟卷人(签字): 拟卷日期:审核人(签字)：得分统表:题 号 一 二 三 四 总 分得 分1． 小明学习和体育都好.2．只有努力才能成功.3．存在函数连续但不可导（论域为全总个体域） ．4．凡有理数均可表示成分数（论域为全总个体域）.得 分 阅卷人 一、将下列命题符号化：（本题共 4题,每题 5分, 满分 20分.）1．求公式 ()()PQ的主析取范式和主合取范式（ 12分）.2．设 1,3(1,2),(3)AR上 的 二 元 关 系 .求 r(R)、 s及 t()（分）.3．设 1,23A问 上共有多少个不同的等价关系（ 10分）.1.画出集合 1234612A， ， ， ， ， 上整除关系的哈斯图，指出最大元、最小元、极大元和极小元（ 分）. 得 分 阅卷人 二、计算题：（本题共 3小题,满分 4分.）得 分 阅卷人 三、应用题：（本题共 3小题,满分 0分.）2.设 U＝ （ s,） 是半群， s=a,bcd， “”运算定义如下表（ 10分）：(1).证明 U是一个循环含幺半群，并给出它的生成元；2.把 中的每个元素均表示成生成元的幂 . 3.设 (,)A是一个代数系统， 3Axab， 、 均为有理数，其中“”、为普通加法和普通乘法，问 (,)是否为域？为什么？（ 8分）四、证明题：（本题共 2小题,满分 16分.）1.给定代数系统 (,)(,)(,).UXVYWZ设 f是从 U到 V的同态， h是从V到 W的同态.证明: hfo是从 到 的同态.（ 8分）：a b c da a b c db b c d ac c d a bd d a b c得 分 阅卷人2.构造下列推理的证明（ 8分）：前提： ()(),(),()xABxCx.结论： .专业:信息与计算科学 课程名称 : 离散数学 学分: 3试卷编号（H）课程编号: 4114600 考试方式: 闭 卷 考试时间: 100 分钟拟卷人(签字 ): 拟卷日期:审核人(签字)：得分统表:题 号 一 二 三 四 总 分得 分1． 小明学习好或体育好.2．除非努力才能成功.3．存在函数连续且可导（论域为全总个体域） ．4．有的有理数能被 2整除（论域为全总个体域） .得 分 阅卷人 一、将下列命题符号化：（本题共 4题,每题 5分, 满分 20分.）1．化一阶逻辑公式 ()()()xPyQxR为前束范式（ 12分）.2．设 , (,),()AabcRabc上 的 二 元 关 系 .求 r(R)、 s及 t()（1分） .3．设 1,234,A问 A上共有多少个不同的等价关系（ 10分）.1.画出集合 23491A， ， ， ， 上整除关系的哈斯图，指出极大元和极小元（ 2分） . 。