2022年2022年离散数学试题与答案 .pdf

《2022年2022年离散数学试题与答案 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年离散数学试题与答案 .pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散数学试题一与参考答案一、填空20% （每小题2 分）1设7|),5()( |xExxBxNxxA且且（N：自然数集，E+正偶数）则BA0，1，2，3，4，6 。2 A ， B ， C 表 示 三 个 集 合 ， 文 图 中 阴 影 部 分 的 集 合 表 达 式 为ACB)(。3设 P，Q 的真值为 0，R，S的真值为 1，则)()(SRPRQP的真值 = 1 。4公式PRSRP)()(的主合取范式为)()(RSPRSP。5若解释 I 的论域 D 仅包含一个元素，则)()(xxPxxP在 I下真值为1 。6设 A=1 ，2，3，4 ，A 上关系图为则 R2 = , , , 。7设 A=a

2、，b，c，d，其上偏序关系 R 的哈斯图为则 R=, IA。8图的补图为A B C 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 7 页 - - - - - - - - - 。9设 A=a ，b，c，d ，A 上二元运算如下：* a b c d a b c d a b c d b c d a c d a b d a b c 那么代数系统 的幺元是a ，有逆元的元素为a , b , c ,d ，它们的逆元分别为a , d , c , d 。10下图所示的偏序集中，是格的为

3、c 。二、选择20% （每小题2 分）1、下列是真命题的有（ C D）Aaa；B ,；C,；D。2、下列集合中相等的有（B、C）A4，3；B，3，4；C4，3，3 ；D 3，4。3、设 A=1 ，2，3，则 A 上的二元关系有（C ）个。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 7 页 - - - - - - - - - A 23 ；B 32 ；C332；D223。4、设 R，S 是集合 A 上的关系，则下列说法正确的是（A）A若 R，S 是自反的，则SR是自反的；

4、B若 R，S 是反自反的，则SR是反自反的；C若 R，S 是对称的，则SR是对称的；D若 R，S 是传递的，则SR是传递的。5、设 A=1 ，2，3，4，P（A） （A 的幂集）上规定二元系如下|(|)(,|,tsAptstsR则 P（A）/ R=（ D）AA ；BP(A) ；C1，1 ，2 ，1 ，2，3 ，1 ，2，3，4 ；D，2 ，2，3，2 ，3，4 ，A 6、设 A=，1 ，1 ，3，1 ，2，3 则 A 上包含关系“”的哈斯图为（ C ）7、下列函数是双射的为（A ）Af : IE , f (x) = 2x ；Bf : NNN, f (n) = ；Cf : RI , f (x)

5、= x ；Df :IN, f (x) = | x | 。（注： I整数集， E偶数集，N自然数集， R实数集）8、图 中 从 v1到 v3长度为 3 的通路有（D ）条。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 7 页 - - - - - - - - - A 0；B1；C2；D3。9、下图中既不是 Eular 图，也不是 Hamilton 图的图是（ B）10、 在一棵树中有 7 片树叶，3 个 3 度结点， 其余都是 4 度结点则该树有（ A ）个 4 度结点。A

6、1；B2； C3； D4 。三、证明26% 1. R 是集合 X 上的一个自反关系， 求证：R 是对称和传递的， 当且仅当 和在 R 中有在 R 中。 （8分）证 ： “”Xcba,若Rc,ab,a由 R 对 称 性知Ra,ca,bc,bb,ac,ac,ba,ab,aa,bb,acb,ab,c,a即 R 是传递的。2. f 和 g 都是群 到的同态映射， 证明是的一个子群。其中 C=)()(|1xgxfGxx且(8 分) 证：Cba,，有)()(),()(bgbfagaf，又)()(,)()(1111bgbgbfbf)()()()(1111bgbgbfbfaf (agbgagbfafb()(*

7、)()(*)()111)1baCb1 是 的子群。3. G= (|V| = v ，|E|=e ) 是每一个面至少由k（k3）条边围成的连通平面图，则2)2(kvke， 由此证明彼得森图（Peterson ）图是非平面图。 （11名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 7 页 - - - - - - - - - 分）四、用构造证明法证明下题（每小题8 分）1、FAFEDDCBA,2、)()()()(xxQxxPxQxPx五、计算18% 1、设集合 A=a ，b，c，

8、d上的关系 R= , , , 用矩阵运算求出 R 的传递闭包 t (R)。（9 分）2、 如下图所示的赋权图表示某七个城市721,vvv及预先算出它们之间的一些直接通信线路造价， 试给出一个设计方案， 使得各城市之间能够通信而且总造价最小。（分）三、证明26% 1、证：“”Xcba,若Rc,ab,a由R对 称 性 知Ra,ca,bc,bb,ac,ac,ba,ab,aa,bb,acb,ab,c,a即 R 是传递的。2、证Cba,，有)()(),()(bgbfagaf，又名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理

9、- - - - - - - 第 5 页，共 7 页 - - - - - - - - - )()(,)()(1111bgbgbfbf)()()()(1111bgbgbfbfaf (agbgagbfafb()(*)()(*)()111)1baCb1 是 的子群。3、证：设 G有 r 个面，则rkFderii1)(2，即ker2。而2rev故keevrev22即得2)2(kvke。 （8 分）彼得森图为10,15,5vek，这样2)2(kvke不成立，所以彼得森图非平面图。 （3 分）四、逻辑推演16% a)证明：A附加前提BA附加DCBA前提引入DC假言推理 ID化简ED附加FED前提引入F假言推

10、理2、证明)(xxP附加前提)(cPUS名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 7 页 - - - - - - - - - )()(xQxPx前提引入)()(cQcPUS)(cQ假言推理)(xxQUG五、计算18% 1.解：0000100001010010RM，00000000101001012RRRMMM000000000101101023RRRMMM，000000001010010134RRRMMM0000100011111111432)(RRRRRtMMMMMt (R)= , , , , , , , , 2.解： 用库斯克（ Kruskal）算法求产生的最优树。算法略。结果如图：树权 C(T)=23+1+4+9+3+17=57 即为总造价。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 7 页 - - - - - - - - -