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

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

1、2066628238.doc 1 一、填空20%（每小题 2 分）1设7|),5()(|xExxBxNxxA且且（N：自然数集，E+正偶数）则BA。2A，B，C 表示三个集合，文图中阴影部分的集合表达式为。3设 P，Q 的真值为 0，R，S 的真值为 1，则)()(SRPRQP的真值=。4公式PRSRP)()(的主合取范式为。5若解释I 的论域 D 仅包含一个元素，则)()(xxPxxP在 I 下真值为。6设 A=1，2，3，4，A 上关系图为则 R2=。7设 A=a，b，c，d，其上偏序关系R 的哈斯图为则 R=。A B C 名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 8

2、页 -2066628238.doc 2 8图的补图为。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 那么代数系统 的幺元是，有逆元的元素为，它们的逆元分别为。10下图所示的偏序集中，是格的为。二、选择20%（每小题2 分）1、下列是真命题的有（）Aaa；B,；C,；D。2、下列集合中相等的有（）A4，3；B，3，4；C4，3，3；D 3，4。3、设 A=1，2，3，则 A 上的二元关系有（）个。名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 8 页 -2066628238.doc 3

3、 A 23；B 32；C332；D223。4、设 R，S 是集合 A 上的关系，则下列说法正确的是（）A若 R，S 是自反的，则SR是自反的；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=（）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 上包含关系“”的哈斯图为（）7、下列函数是双射的为（）Af:IE,f(x)

4、=2x；B f:NNN,f(n)=；C f:RI,f(x)=x；Df:IN,f(x)=|x|。（注：I整数集，E偶数集，N自然数集，R实数集）8、图中 从 v1到 v3长度为 3 的通路有（）条。A 0；B1；C2；D3。9、下图中既不是Eular 图，也不是Hamilton 图的图是（）名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 8 页 -2066628238.doc 4 10、在一棵树中有7 片树叶，3 个 3 度结点，其余都是4 度结点则该树有（）个 4 度结点。A1；B2；C3；D4。三、证明26%、R 是集合 X 上的一个自反关系，求证：R 是对称和传递的，当且仅当

5、 和在 R 中有 在 R 中。（8 分）、f 和 g 都是群 到 的同态映射，证明是的一个子群。其中 C=)()(|1xgxfGxx且(8 分)、G=(|V|=v，|E|=e)是每一个面至少由k（k3）条边围成的连通平面图，则2)2(kvke，由此证明彼得森图（Peterson）图是非平面图。（11 分）四、逻辑推演16%用 CP 规则证明下题（每小题8 分）1、FAFEDDCBA,2、)()()()(xxQxxPxQxPx五、计算18%1、设集合 A=a，b，c，d上的关系 R=,用矩阵运算求出R的传递闭包t(R)。（9 分）名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 8

6、页 -2066628238.doc 5 2、如下图所示的赋权图表示某七个城市721,vvv及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。（分）一、填空 20%（每空 2 分）1、2(x+1)；2、a,c,a,b,c,c,c,a,b,a,a,a；3、3,6,2,6,2,4,5,1,3,1,2,1；4、反对称性、反自反性；4、2,2,2,2,；5、1；6、)()()(RQPRQPRQP；7、任意 x，如果 x 是素数则存在一个 y，y 是奇数且 y 整除 x；8、),(),(),(uyxQzyPzxPuzyx。二、选择 20%（每小题2 分）题

7、目1 2 3 4 5 6 7 8 9 10 答案C C C C A B D A D C 三、证明 16%(每小题 8 分)1、AP（附加前提）BATIDCBAP名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 8 页 -2066628238.doc 6 DCT I DTI EDTI FEDPFT I FACP 2、)()()()()()()()()(xxQxxPxQxPxxxQxPxxxQxxP本题可证)(xxPP（附加前提）)(xPxTE)(aPES)()(xQxPxP)()(aQaPUS)(aQT I)(xxQEG)()(xxQxxPCP四、14%1、证明：（1）自反性：yxy

8、xXyx由于,自反RRyxyx,（2）对称性：XyxXyx2211,时当Ryxyx2211,21121221yxyxyxyx也即即有对称性故RRyxyx1122,名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 8 页 -2066628238.doc 7（3）传递性：XyxXyxXyx332211,时且当RyxyxRyxyx33222211,)2()1(23321221yxyxyxyx即23123221)2()1(yxyxyxyx即1331yxyx有传递性故RRyxyx3311,由（1）（2）（3）知：R 是 X 上的先等价关系。2、X/R=2,1R五、10%1、000010000

9、1010010RM；关系图2、00000000101001012RRRMMM000000000101101023RRRMMM2340000000010100101RRRRMMMM,4635RRRRMMMM0000100011111111432)(RRRRRtMMMMMt(R)=,。名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 8 页 -2066628238.doc 8 六、20%1、（1）)()(|,)()(|,xgxfydomgdomfxyxxgyxfydomgxdomfxyxgf)()(,|xgxfdomgdomfxxdomhgdomfgfh令（2）)()()(|,xgxfxhydomgdomfxyxh使得若有对21,yydomhx)()()(,)()()(21xgxfxhyxgxfxhy21,)(yygf有是函数或由于)(xhyydomhx使得有唯一即也是函数gf。2、证明：ttfgTtgf)(,则对有一左逆若是入射所以是入射故ffg,。的左逆元是故则且若或只有一个值则对令若此时令使入射由定义如下是入射fgtsgtfgstfctsgSsTcsgTfstsgstfTtfTfsSTff,)()()()(,)()(,)()(,|,),(:,左逆函数为使必能构造函数入射即若fggf,。名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 8 页 -