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

一、证明下列各题1、（10分）证明蕴涵式：()PPQQ2、（10分）证明：,1111fgfg为函数为函数。5、3、（10分）给定代数结构,N和0,1,，其中N是自然数集合，是数的乘法。设:0,1fN，定义为：12,,()0knnkNfn否则试证01N，，，。。4、（10分）给定代数结构,R，其中R是实数集合，对R中任意元a和b，定义如下：ababab试证明：,R是独异点。二、求下列各题的解：1、试求下列公式的主析取范式和主合取范式（15分）：()()PQPQ2、（15分）010203121323R设，，，，，，，，，，，，试求（1）、RR，（2）、1R，（3）、11R，（4）、1R，（5）、11R3、（15分给定无向图,GVE，如图，试求：FEDCAB（1）从A到D的所有基本链；（2）从A到D的所有简单链；（3）长度分别是最小和最大的简单圈；（4）长度分别是最小和最大的基本圈；（5）从A到D的距离。4、（15分）给定二部图12,,GVEV，如图9v8v7v6v1V1v2v3v4v5v2V试求1V到2V的最大匹配一、证明下列各题1、（10分）证明蕴涵式：()PQPPQ2、（10分）证明：()()()ABCABAC3、（10分）给定群,G，则,G为Abel群222()()(,())ababGabab4、（10分）给定代数结构,S，其中S中元为实数有序对，定义为,,,2abcdacbdbd，试证,S是可交换独异点。二、求下列各题的解：1、试求下列公式的主析取范式和主合取范式（15分）：((()))PPQQR2、（15分）设,,,,,,Rabbcca试求(),()rRsR和()tR。3、（15分）给定有向图,GVE，如图，试求：（1）、各结点的出度、入度和度；（2）、从v1到v3的所有简单路和基本路；（3）、所有简单回路和基本回路。4、（15分）给定树G，试求对应二叉树v5v4v3v1v2一、证明下列各题1、（10分）证明蕴涵式：()PQQPQ2、（10分）证明：,1111fgfg为函数为函数。3、（10分）给定代数结构,N和0,1,，其中N是自然数集合，是数的乘法。设:0,1fN，定义为：12,,()0knnkNfn否则试证01N，，，。4、（10分）给定代数结构,S，其中S中元为实数有序对，定义为,,,2abcdacbdbd，试证,S是可交换独异点。二、求下列各题的解：1、试求下列公式的主析取范式和主合取范式（15分）：((()))PPQQR2、（15分）010203121323R设，，，，，，，，，，，，试求（1）、RR，（2）、1R，（3）、11R，（4）、1R，（5）、11R3、（15分）给定有向图,GVE，如图，试求：（1）、各结点的出度、入度和度；（2）、从v1到v3的所有简单路和基本路；（3）、所有简单回路和基本回路。4、（15分）给定树G，试求对应二叉树v5v4v3v1v2专业:信息与计算科学课程名称:离散数学学分:3试卷编号（D）课程编号: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,≼如下图所示，求A的极小元、最小元、极大元、最大元.设B＝{b,c,d},求B的下界、上界、下确界、上确界.3（10分）G=Z12是12阶循环群,写出G的所有子群4（10分）考虑110的正因子集合S110关于gcd,lcm运算构成的布尔代数.写出它所有的子布尔代数5（10分）⑴对权100,81,64,49,36,25,16,9,4,1构造一棵最优二元树，并求权和。⑵求下图的最小生成树，并求最小权和2413332223225522专业:信息与计算科学课程名称:离散数学学分:3试卷编号（E）课程编号:4114600考试方式:闭卷考试时间:120分钟拟卷人(签字):拟卷日期:审核人(签字)：得分统计表题号一二总分得分一、第一部分1（10分）写出下列公式的真值表B=(qp)qp2（10分）用等值演算法判断下列公式的类型(pq)(qp)3（10分）求主合取范式(pq)r得分阅卷人4（10分）判断下面推理是否正确若今天是1号，则明天是5号.明天是5号.所以今天是1号5（10分）用附加前提证明法构造证明前提：pq,pr,rs结论：sq二、第二部分1（10分）在一阶逻辑中将下面命题符号化有的无理数大于有的有理数得分阅卷人2（10分）已知偏序集A,R的哈斯图如下图所示,试求出集合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)r得分阅卷人4（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〕≤＝〔a,b,a,c,a,d,a,e,b,e,c,e,d,e∪IA3（10分）设f：R→R,g：R→R23()()223xxfxgxxx求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．凡有理数均可表示成分数（论域为全总个体域）.1．求公式()()PQPQ的主析取范式和主合取范式（12分）.得分阅卷人一、将下列命题符号化：（本题共4题,每题5分,满分20分.）得分阅卷人二、计算题：（本题共3小题,满分34分.）2．设1,2,3,(1,2),(2,2),(2,3)AAR上的二元关系.求r(R)、s(R)及t(R)（12分）.3．设1,2,3,A问A上共有多少个不同的等价关系（10分）.1.画出集合1234612A，，，，，上整除关系的哈斯图，指出最大元、最小元、极大元和极小元（12分）.2.设U＝（s,）是半群，s=a,b,c,d，“”运算定义如下表（10分）：(1).证明U是一个循环含幺半群，并给出它的生成元；(2).把U中的每个元素均表示成生成元的幂.3.设(,,)A是一个代数系统，3Axxab，ab、均为有理数，其中得分阅卷人三、应用题：（本题共3小题,满分30分.）abcdaabcdbbcdaccdabddabc“”、“”为普通加法和普通乘法，问(,,)A是否为域？为什么？（8分）四、证明题：（本题共2小题,满分16分.）1.给定代数系统(,),(,),(,).UXVYWZ设f是从U到V的同态，h是从V到W的同态.证明:hf是从U到W的同态.（8分）：2.构造下列推理的证明（8分）：前提：(()()),(()()),()xAxBxxBxCxxCx.结论：().xAx得分阅卷人专业:信息与计算科学课程名称:离散数学学分:3试卷编号（H）课程编号:4114600考试方式:闭卷考试时间:100分钟拟卷人(签字):拟卷日期:审核人(签字)：得分统表:题号一二三四总分得分1．小明学习好或体育好.2．除非努力才能成功.3．存在函数连续且可导（论域为全总个体域）．4．有的有理数能被2整除（论域为全总个体域）.1．化一阶逻辑公式(()())()xPxyQyxRx为前束范式（12分）.得分阅卷人一、将下列命题符号化：（本题共4题,每题5分,满分20分.）得分阅卷人二、计算题：（本题共3小题,满分34分.）2．设,,,(,),(,),(,)AabcARabbbbc上的二元关系.求r(R)、s(R)及t(R)（12分）.3．设1,2,3,4,A问A上共有多少个不同的等价关系（10分）.1.画出集合234912A，，，，上整除关系的哈斯图，指出极大元和极小元（12分）.2.设U＝（s,）是半群，s=a,b,c，“”运算定义如下表（10分）：(1).证明U是一个循环含幺半群，并给出它的生成元；(2).把U中的每个元素均表示成生成元的幂.3.设(,,)A是一个代数系统，2Axxab，ab、均为有理数，其中得分阅卷人三、应用题：（本题共3小题,满分30分.）abcaabcbbcaccab“”、“”为普通加法和普通乘法，问(,,)A是否为域？为什么？（8分）四、证明题：（本题共2小题,满分16分.）1.设f、g分别是两代数系统(,),(,)XY上的同态，其中(,)Y可交换，令h是从X到Y的函数，对xX有：()()()hxfxgx.证明:h是从X到Y的同态.（8分）：2.构造下列推理的证明（8分）：前提：(()),,.PSRQPR.结论：.Q得分阅卷人专业:信息与计算科学课程名称:离散数学学分:3试卷编号（I）课程编号:4114600考试方式:闭卷考试时间:100分钟拟卷人(签字):拟卷日期:审核人(签字)：得分统表:题号一二三四总分得分1．只要努力过就不会后悔.2．我在城在.3．所有孩子都崇拜某些偶像（论域为全总个体域）．4．一切房子都不一样大（论域为全总个体域）.1．求公式()PQR的主析取范式和主合取范式（12分）.得分阅卷人一、将下列命题符号化：（本题共4题,每题5分,满分20分.）得分阅卷人二、计算题：（本题共3小题,满分34分.）2．设1,2,(1,2)AAR上的二元关系.求r(R)、s(R)及t(R)（12分）.3．设1,2,A问A上共有多少个不同的等价关系（10分）.1.画出集合234789A，，，，，上整除关系的哈斯图，指出极大元和极