2022年2022年离散数学试卷及答案 2.pdf

离散数学试卷（二）第 1 页 共 7 页一、填空20%（每小题 2 分）1、P：你努力，Q：你失败。“除非你努力，否则你将失败”的翻译为；“虽然你努力了，但还是失败了”的翻译为。2、论域 D=1，2，指定谓词P P(1,1)P(1,2)P(2,1)P(2,2)T T F F 则公式),(xyyPx真值为。2、设 S=a1，a2，a8，Bi是 S 的子集，则由B31所表达的子集是。3、设A=2，3，4，5，6 上 的 二 元 关 系|,是质数xyxyxR，则R=（列举法）。R 的关系矩阵MR=。5、设 A=1，2，3，则 A 上既不是对称的又不是反对称的关系R=；A 上既是对称的又是反对称的关系R=。6、设代数系统 ，其中 A=a，b，c,则 幺 元 是；是 否 有 幂 等性；是否有对称性。7、4 阶群必是群或群。8、下面偏序格是分配格的是。*a b c a b c a b c b b c c c b 名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 7 页 -离散数学试卷(二)第 2 页 共 7 页9、n 个结点的无向完全图Kn的边数为，欧拉图的充要条件是。10、公式RQPQPP)()(的根树表示为。二、选择20%（每小题 2 分）1、在下述公式中是重言式为（）A)()(QPQP；B)()()(PQQPQP；CQQP)(；D)(QPP。2、命题公式)()(PQQP中极小项的个数为（），成真赋值的个数为（）。A0；B1；C2；D3。3、设2,1,1,S，则S2有（）个元素。A3；B6；C7；D8。4、设3,2,1S，定义SS上的等价关系,|,cbdaSSdcSSbadcbaR则 由R 产生 的SS上一个划分共有（）个分块。A4；B5；C6；D9。5、设3,2,1S，S上关系 R 的关系图为名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 7 页 -离散数学试卷(二)第 3 页 共 7 页则 R 具有（）性质。A自反性、对称性、传递性；B反自反性、反对称性；C反自反性、反对称性、传递性；D自反性。6、设,为普通加法和乘法，则（）,S是域。A,3|QbabaxxSB,2|ZbanxxSC,12|ZnnxxSD0|xZxxS=N。7、下面偏序集（）能构成格。8、在如下的有向图中，从V1到 V4长度为 3 的道路有（）条。A1；B2；C3；D 4。9、在如下各图中（）欧拉图。10、设R是实数集合，“”为普通乘法，则代数系统 是（）。名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 7 页 -离散数学试卷(二)第 4 页 共 7 页A群；B独异点；C半群。三、证明46%1、设 R 是 A 上一个二元关系，),(),(|,RbcRcaAcAbabaS且有对于某一个试证明若R是 A 上一个等价关系，则S 也是 A 上的一个等价关系。（9 分）2、用逻辑推理证明：所有的舞蹈者都很有风度，王华是个学生且是个舞蹈者。因此有些学生很有风度。（11分）3、若BAf:是从A 到B 的函 数，定 义一 个函 数ABg2:对 任意Bb有)()(|)(bxfAxxbg，证明：若 f 是 A 到 B 的满射，则 g 是从 B 到A2的单射。（10 分）4、若无向图G 中只有两个奇数度结点，则这两个结点一定连通。（8 分）5、设 G 是具有 n 个结点的无向简单图，其边数2)2)(1(21nnm，则 G 是 Hamilton图（8 分）四、计算14%1、设 是一个群，这里+6是模 6 加法，Z6=0 ，1，2，3，4，5，试求出 的所有子群及其相应左陪集。（7 分）2、权数 1，4，9，16，25，36，49，64，81，100 构造一棵最优二叉树。（7 分）名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 7 页 -离散数学试卷(二)第 5 页 共 7 页一、填空 20%（每小题 2 分）1、QP；QP2、T 3、,876540001111131aaaaaBB4、R=,；00000111111100011111111115、R=,；R=,6、a；否；有7、Klein 四元群；循环群8、B 9、)1(21nn；图中无奇度结点且连通10、二、选择20%（每小题2 分）题目1 2 3 4 5 6 7 8 9 10 答案B、D D；D D B D A B B B B、C 三、证明46%1、（9 分）（1）S自反的Aa，由 R 自反，),(),(RaaRaa，Saa,（2）S对称的传递对称定义RSabRRbcRcaSRbcRcaSbaAba,),(),(),(),(,（3）S传递的名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 7 页 -离散数学试卷(二)第 6 页 共 7 页定义传递SScaRRcbRbaRceRebRbdRdaScbSbaAcba,),(),(),(),(),(),(,由（1）、（2）、（3）得；S 是等价关系。2、11 分证明：设P(x)：x 是个舞蹈者；Q(x)：x 很有风度；S(x)：x 是个学生；a：王华上述句子符号化为：前提：)()(xQxPx、)()(aPaS结论：)()(xQxSx 3 分)()(aPaSP)()(xQxPxP)()(aQaPUS)(aPTI).(aQT I)(aSTI)()(aQaST I)()(xQxSxEG 11 分、0 分证明：)(,2121bbBbbAaaf21,满射21212211,),()(,)(,)(aafafafbafbaf是函数由于且使)()()(),()(),()()(|)(),)()(|)(21122122112211bgbgbgabgabgabgabxfAxxbgbxfAxxbg但又为单射任意性知由gbb,21。4、8 分证明：设 G 中两奇数度结点分别为u 和 v，若 u，v 不连通，则 G 至少有两个连通分支G1、G2，使得 u和 v 分别属于 G1和 G2，于是 G1和 G2中各含有 1 个奇数度结点，这与图论基本定理矛盾，因而u，v 一定连通。5、8 分证明：证 G 中任何两结点之和不小于n。名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 7 页 -离散数学试卷(二)第 7 页 共 7 页反证法：若存在两结点u，v 不相邻且1)()(nvdud,令,1vuV，则 G-V1是具有n-2个 结 点 的 简 单 图，它 的 边 数)1(2)2)(1(21nnnm,可 得1)3)(2(21nnm，这与 G1=G-V1为 n-2 个结点为简单图的题设矛盾，因而 G 中任何两个相邻的结点度数和不少于n。所以 G 为 Hamilton 图.四、计算14%1、7 分解：子群有；0 的左陪集：0，1；2，3；4，5 0，3 的左陪集：0，3；1，4；2，5 0，2，4 的左陪集：0，2，4；1，3，5 Z6的左陪集：Z6。2、7 分名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 7 页 -