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

1、一、 证明下列各题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分

2、）给定二部图，如图 试求到的最大匹配一、 证明下列各题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

3、分）给定代数结构和，其中是自然数集合，是数的乘法。设，定义为：试证。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考试方式:闭 卷考试时间:

4、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的下界、上界、下确界

5、、上确界. 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分）用等值演算法判断下列公式的类型

6、(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试卷编

7、号（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=

8、“人类集合”=x | x是人(b) D为全总个体域2（10分）分别画出下列各偏序集的哈斯图，再求出最大元、最小元、极大元和极小元 A a,b,c,d,e ,IA3（10分）设 f：RR, g：RR 求fog, gof. 如果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个按上述比例出现的八进制数字需要多少个二进制数字？若用等长的

9、（长为3）的码字传输需要多少个二进制数字？ 专业:信息与计算科学课程名称:离散数学学分:3试卷编号（G）课程编号:411461考试方式:闭 卷考试时间:100分钟拟卷人(签字): 拟卷日期:审核人(签字)：得分统表:题 号一二三四总 分得 分得 分阅卷人一、将下列命题符号化：（本题共题,每题分,满分分.）小明学习和体育都好.只有努力才能成功.存在函数连续但不可导（论域为全总个体域）凡有理数均可表示成分数（论域为全总个体域）.得 分阅卷人二、计算题：（本题共小题,满分分.）求公式的主析取范式和主合取范式（分）.设.求（分）.设问上共有多少个不同的等价关系（分）.得 分阅卷人三、应用题：（本题共小

10、题,满分分.）.画出集合上整除关系的哈斯图，指出最大元、最小元、极大元和极小元（分）. .设是半群，“”运算定义如下表（分）：abcdaabcdbbcdaccdabddabc .证明是一个循环含幺半群，并给出它的生成元； .把中的每个元素均表示成生成元的幂. .设是一个代数系统，均为有理数，其中为普通加法和普通乘法，问是否为域？为什么？（分）得 分阅卷人四、证明题：（本题共小题,满分分.）.给定代数系统设是从到的同态，是从到的同态.证明:是从到的同态.（分）：.构造下列推理的证明（分）：前提：结论：专业:信息与计算科学课程名称:离散数学学分:3试卷编号（H）课程编号:4114600考试方式:闭

11、 卷考试时间:100分钟拟卷人(签字): 拟卷日期:审核人(签字)：得分统表:题 号一二三四总 分得 分得 分阅卷人一、将下列命题符号化：（本题共题,每题分,满分分.）小明学习好或体育好.除非努力才能成功.存在函数连续且可导（论域为全总个体域）有的有理数能被整除（论域为全总个体域）.得 分阅卷人二、计算题：（本题共小题,满分分.）化一阶逻辑公式为前束范式（分）.设.求（分）.设问上共有多少个不同的等价关系（分）.得 分阅卷人三、应用题：（本题共小题,满分分.）.画出集合上整除关系的哈斯图，指出极大元和极小元（分）. abcaabcbbcaccab.设是半群，“”运算定义如下表（分）： .证明是

12、一个循环含幺半群，并给出它的生成元； .把中的每个元素均表示成生成元的幂. .设是一个代数系统，均为有理数，其中为普通加法和普通乘法，问是否为域？为什么？（分）得 分阅卷人四、证明题：（本题共小题,满分分.）.设、分别是两代数系统上的同态，其中可交换，令是从到的函数，对有：.证明:是从到的同态.（分）：.构造下列推理的证明（分）：前提：结论：专业:信息与计算科学课程名称:离散数学学分:3试卷编号（I）课程编号:4114600考试方式:闭 卷考试时间:100分钟拟卷人(签字): 拟卷日期:审核人(签字)：得分统表:题 号一二三四总 分得 分得 分阅卷人一、将下列命题符号化：（本题共题,每题分,满

13、分分.）只要努力过就不会后悔.我在城在.所有孩子都崇拜某些偶像（论域为全总个体域）一切房子都不一样大（论域为全总个体域）.得 分阅卷人二、计算题：（本题共小题,满分分.）求公式的主析取范式和主合取范式（分）.设.求（分）.设问上共有多少个不同的等价关系（分）.得 分阅卷人三、应用题：（本题共小题,满分分.）.画出集合上整除关系的哈斯图，指出极大元和极小元（分）. .设，“”为上的二元运算，“”运算定义如下表（分）：eabceeabcaaecbbbceaccbae .是否能构成一个群？ .有何性质？ .设是一个代数系统，均为有理数，其中为普通加法和普通乘法，问是否为域？为什么？（分）得 分阅卷人

14、四、证明题：（本题共小题,满分分.）.设有证明:是上的自同构（分）：.构造下列推理的证明（分）：前提：结论：得 分阅卷人一、 证明下列各题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

15、到D的所有简单链；（3） 长度分别是最小和最大的简单圈；（4） 长度分别是最小和最大的基本圈；（5） 从A到D的距离。4、（15分）给定二部图，如图 试求到的最大匹配。业：信息与计算科学课程名称： 离散数学 学分： 3 试卷编号( K)课程编号： 4114600 考试方式： 闭卷 考试时间： 100 分钟拟卷人(签字)： 拟卷日期： 审核人(签字)： 得分统计表： 题号一二总 分得分得 分阅卷人一、 证明下列各题1、 （10分）证明蕴涵式：2、（10分）证明：3、（10分）给定群，则为Abel群4、（10分）给定代数结构，其中S中元为实数有序对，定义为，试证是可交换独异点。得分阅卷人二、 求下

16、列各题的解：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、试求下列公式的主析取范式和主合取

17、范式（15分）：2、（15分）（1）、（2）、，（3）、，（4）、，（5）、v5 v4 v3v1 v23、（15分）给定有向图，如图，试求：（1）、各结点的出度、入度和度；（2）、从v1到v3的所有简单路和基本路；（3）、所有简单回路和基本回路。4、（15分）给定树G，试求对应二叉树答案：一、1、或用推理方法，或用真值表方法（略）。2、5分 5分3、任给有三种情况：（1）存在使成立；1分（2）存在使成立而不存在使成立；或者反之；1分（3）不存在，使成立。1分对于（1），显然有即；3分对于（2）（3），均有。2分因为或和或和。2分综上所述，故。4、首先证明满足结合律，任给，因为而故，因此，满足结

18、合律。5分其次证明有幺元0，任给，有：，故0是的幺元。5分 综上所述，是独异点。二、1、主析取范式为3分2、 3分3分3分3分3分3、（1）、从A到D的所有基本链共有10条，即：ABD，ABED，ABCD，ABCED，ABECD，AFED，AFECD，AFEBD，AFEBCD，AFECBD。3分（2）、从A到D的所有简单链共有14条，即除（1）的10条外，还有ABCEBD，ABECBD，AFEBCED，AFECBED。3分（3）、长度最小的简单圈共4个，即BCDB，BCEB，BDEB，CDEC，长度最大的简单圈共2个，即ABCEBDEFA，AFEBCEDBA。3分（4）、长度最小的基本圈共4个

19、，即同（3）；长度最大的基本圈有2个，为ABDCEFA；ABCDEFA3分； （5）、。3分4、到的最大匹配有多个，如，得分情况根据具体解题过程考虑。一、1、2、3、充分性：因为是群，又对任意，有 可见，是可交换的，故为Abel.必要性：为Abel群，自然是群；又对任意，有4、首先证明是可结合的，任给，有：而故满足结合律，是半群。5分其次证明有幺元，任给，有因此，是幺元。2分最后，证明满足交换律，任给，有，故满足见换律。3分综上可知，是可交换独异点。二、1、2、5分5分5分3、（1）、5分（2）、到的所有简单路共4条，它们是到的所有基本路共2条，它们是：5分（3）、所有基本回路共3条，它们是：

20、。所有简单回路除上3个基本回路外，还有1个，它是5分 4、根据解题过程分步给分。一、1、或用真值表方法（略）。 2、 3、任给有三种情况：（1）存在使成立；1分（2）存在使成立而不存在使成立；或者反之；1分（3）不存在，使成立。1分对于（1），显然有即；3分对于（2）（3），均有。2分因为或和或和。2分综上所述，故。 4、首先证明满足结合律，任给，因为而故，因此，满足结合律。5分，其次证明有幺元0，任给，有：，故0是的幺元。5分综上所述，是独异点。二、1、主合取范式，主析取范式为：。5分2、3分3分 3分3分 3分3、（1）、5分（2）、到的所有简单路共4条，它们是到的所有基本路共2条，它们是

21、：5分（3）、所有基本回路共3条，它们是：。所有简单回路除上3个基本回路外，还有1个，它是5分4、根据解题过程分步给分。专业：信息与计算科学 课程名称： 离散数学 学分： 3 试卷编号（D）一、第一部分1（10分）写出下列公式的真值表A = (pq) rp q rpqr(pq)r0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1001111111010101011101010每错一处扣1分，扣到10分为止2（10分）用等值演算法判断下列公式的类型q(pq) q(pq) （蕴涵等值式） q(pq) （德摩根律） p(qq) （交换律，结合律） p0 （矛盾律） 0

22、（零律） 由最后一步可知，为矛盾式.3（10分）求主析取范式(pq)r (pq)r （析取范式） (pq) (pq)(rr) (pqr)(pqr) m6m7 r (pp)(qq)r (pqr)(pqr)(pqr)(pqr) m1m3m5m7 , 代入并排序，得(pq)r m1m3m5 m6m7 （主析取范式）4（10分）判断下面推理是否正确若今天是1号，则明天是5号. 今天是1号. 所以明天是5号.解 设p：今天是1号，q：明天是5号. (pq)pq（用等值演算法） (pq)pq (pq)p)q pqq 1 推理正确5（10分）用归缪法证明前提：(pq)r, rs, s, p结论：q证明（用归

23、缪法） q 结论否定引入 rs 前提引入 s 前提引入 r 拒取式 (pq)r 前提引入 (pq) 析取三段论 pq 置换 p 析取三段论 p 前提引入 10 pp 合取 二、第二部分1（10分）在一阶逻辑中将下面命题符号化正数都大于负数令F(x)：x为正数，G(y)：y为负数 L(x,y)：xy x(F(x)y(G(y)L(x,y) xy(F(x)G(y)L(x,y)2（10分）设偏序集如下图所示，求A的极小元、最小元、极大元、最大元. 设Bb,c,d, 求B的下界、上界、下确界、上确界. 解 极小元：a, b, c, g； 极大元：a, f, h； 没有最小元与最大元. B的下界和最大下界

24、都不存在, 上界有d和f,最小上界为d. 3 （10分）G=Z12是12阶循环群写出 G的所有子群解 1阶子群=0 2阶子群=0,6 3阶子群 =0,4,8 4阶子群 =0,3,6,9 6阶子群=0,2,4,6,8,10 12阶子群=Z12 4（10分）考虑110的正因子集合S110关于gcd, lcm运算构成的布尔代数. 写出它所有的子布尔代数：解 1, 110 1, 2, 55, 110 1, 5, 22, 110 1, 10, 11, 110 1, 2, 5, 10, 11, 22, 55, 110 5（10分）对权构造一棵最优二元树，并求权和解：过程由下图给出， 求下图的最小生成树，并

25、求最小权和232221222每错一处扣0.5分，扣到10分为止一、第一部分1（10分）写出下列公式的真值表B = (qp) qpp q qp(qp) q(qp) qp0 00 11 01 1101100011111每错一处扣1分，扣到10分为止2（10分）用等值演算法判断下列公式的类型(pq)(qp) (pq)(qp) （蕴涵等值式） (pq)(pq) （交换律） 1 由最后一步可知，为重言式3. （10分）求主合取范式(pq)r (pr)(qr) （合取范式） pr p(qq)r (pqr)(pqr) M0M2 qr (pp)qr (pqr)(pqr) M0M4 , 代入并排序，得(pq)r

26、 M0M2M4 （主合取范式） 4（10分）判断下面推理是否正确若今天是1号，则明天是5号. 明天是5号. 所以今天是1号.解 设p：今天是1号，q：明天是5号. (pq)qp（用主析取范式法） (pq)qp (pq)qp (pq)q)p qp (pq)(pq) (pq)(pq) m0m2m3 结果不含m1, 故01时成假赋值，所以推理不正确5（10分）用附加前提证明法构造证明前提：pq, pr, rs 结论：sq证明 s 附加前提引入 pr 前提引入 rs 前提引入 ps 假言三段论 p 拒取式 pq 前提引入 q 析取三段论 二、第二部分1（10分）在一阶逻辑中将下面命题符号化有的无理数大

27、于有的有理数令F(x)：x是无理数，G(y)：y是有理数， L(x,y)：xy $x(F(x)$y(G(y)L(x,y) $x$y(F(x)G(y)L(x,y) 2（10分）已知偏序集的哈斯图如下图所示, 试求出集合A和关系R的表达式。 解 A=a,b,c,d,e,f,g,h R=,IA 3（10分）设G=e, a, b, c是Klein四元群. 给出G的所有自同构. 解 设j是G的自同构, 则j(e)=e, 且j是双射. 因此满足这些条件的映射只有以下六个：j1：ee, aa, bb, cc j2：ee, aa, bc, cb j3：ee, ab, bc, ca j4：ee, ab, ba,

28、 cc j5：ee, ac, bb, ca j6：ee, ac, ba, cb 经验证，x,yG都有 ji(xy) = ji(x) ji(y), i=1,2,6 上述j1, j2, j6是G上的全体自同构 4（10分）写出下图中L1， L2， L3的原子。解 L1的原子是a, L2的原子是a, b, c, L3的原子是a和b. 5（10分）写出下图所示树产生的前缀码解 所示树产生的前缀码为00, 10, 11, 011, 0100, 0101每错一处扣2分，扣到10分为止一、第一部分1（10分）写出下列公式的真值表C = (pq) qp q ppq (pq) (pq) q0 00 11 01

29、11100110100100000每错一处扣1分，扣到10分为止2（10分）用等值演算法判断下列公式的类型(pq)(pq)r)(pq)(pq)r) (p(qq)r （分配律） p1r （排中律） pr （同一律） 由最后一步可知，不是矛盾式，也不是重言式，它是可满足式，其实101, 111是成真赋值，000, 010等是成假赋值. 3（10分）用主析取范式判两个公式是否等值 p(qr) 与 (pq)r p(qr) 与 (pq)r解 p(qr) = m0m1m2m3 m4m5 m7 (pq)r = m0m1m2m3 m4m5 m7 (pq)r = m1m3 m4m5 m7 显见，中的两公式等值，而的不等值. 4（10分）证明为联结词完备集, , 为完