一、 证明下列各题1、 （10分）证明蕴涵式：2、（10分）证明：5、 3、（10分）给定代数结构和，其中是自然数集合，是数的乘法。设，定义为：试证。4、（10分）给定代数结构，其中是实数集合，对中任意元和，定义如下：试证明：是独异点。二、 求下列各题的解：1、试求下列公式的主析取范式和主合取范式（15分）：2、（15分）（1）、（2）、，（3）、，（4）、，（5）、3、（15分给定无向图，如图，试求：F E D CA B （1） 从A到D的所有基本链；（2） 从A到D的所有简单链；（3） 长度分别是最小和最大的简单圈；（4） 长度分别是最小和最大的基本圈；（5） 从A到D的距离。4、（15分）给定二部图，如图 试求到的最大匹配一、 证明下列各题1、 （10分）证明蕴涵式：2、（10分）证明：3、（10分）给定群，则为Abel群4、（10分）给定代数结构，其中S中元为实数有序对，定义为，试证是可交换独异点。二、 求下列各题的解：1、试求下列公式的主析取范式和主合取范式（15分）：2、（15分）设试求和。v5 v4 v3v1 v23、（15分）给定有向图，如图，试求：（1）、各结点的出度、入度和度；（2）、从v1到v3的所有简单路和基本路；（3）、所有简单回路和基本回路。4、（15分）给定树G，试求对应二叉树一、 证明下列各题1、 （10分）证明蕴涵式：2、（10分）证明：3、（10分）给定代数结构和，其中是自然数集合，是数的乘法。设，定义为：试证。4、（10分）给定代数结构，其中S中元为实数有序对，定义为，试证是可交换独异点。二、 求下列各题的解：1、试求下列公式的主析取范式和主合取范式（15分）：2、（15分）（1）、（2）、，（3）、，（4）、，（5）、v5 v4 v3v1 v23、（15分）给定有向图，如图，试求：（1）、各结点的出度、入度和度；（2）、从v1到v3的所有简单路和基本路；（3）、所有简单回路和基本回路。4、（15分）给定树G，试求对应二叉树专业:信息与计算科学课程名称:离散数学学分:3试卷编号（D）课程编号:4114600考试方式:闭 卷考试时间:120分钟拟卷人(签字):拟卷日期:审核人(签字)：得分统计表题 号一二总 分得 分一、第一部分得 分阅卷人1（10分）写出下列公式的真值表A = (pq) r2（10分）用等值演算法判断下列公式的类型q(pq)3（10分）求主析取范式(pq)r4（10分）判断下面推理是否正确若今天是1号，则明天是5号. 今天是1号. 所以明天是5号.5（10分）用归缪法证明前提：(pq)r, rs, s, p 结论：q二、第二部分得 分阅卷人1（10分）在一阶逻辑中将下面命题符号化正数都大于负数2（10分）设偏序集如下图所示，求A的极小元、最小元、极大元、最大元. 设Bb,c,d, 求B的下界、上界、下确界、上确界. 3（10分）G=Z12是12阶循环群,写出 G的所有子群4（10分）考虑110的正因子集合S110关于gcd, lcm运算构成的布尔代数. 写出它所有的子布尔代数5（10分）对权构造一棵最优二元树，并求权和。 求下图的最小生成树，并求最小权和2413332223225522专业:信息与计算科学课程名称:离散数学学分:3试卷编号（E）课程编号:4114600考试方式:闭 卷考试时间:120分钟拟卷人(签字):拟卷日期:审核人(签字)：得分统计表题 号一二总 分得 分一、第一部分得 分阅卷人1（10分）写出下列公式的真值表B = (qp) qp2（10分）用等值演算法判断下列公式的类型(pq)(qp)3（10分）求主合取范式(pq)r4（10分）判断下面推理是否正确若今天是1号，则明天是5号. 明天是5号. 所以今天是1号5（10分）用附加前提证明法构造证明前提：pq, pr, rs结论：sq二、第二部分得 分阅卷人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 = (pq) q2（10分）用等值演算法判断下列公式的类型(pq)(pq)r)3（10分）用主析取范式判两个公式是否等值 p(qr) 与 (pq)r p(qr) 与 (pq)r4（10分）证明为联结词完备集5（10分）直接证明法构造证明前提：(pq)r, rs, s结论：pq二、第二部分得 分阅卷人1（10分）在一阶逻辑中将下面命题符号化（1）人都爱美（2）有人用左手写字个体域分别为(a) D=“人类集合”=x | x是人(b) D为全总个体域2（10分）分别画出下列各偏序集的哈斯图，再求出最大元、最小元、极大元和极小元 A a,b,c,d,e ,IA3（10分）设 f：RR, g：RR 求fog, gof. 如果f和g存在反函数, 求出它们的反函数.