《2022年离散数学试卷及答案一.docx》由会员分享，可在线阅读，更多相关《2022年离散数学试卷及答案一.docx（11页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选学习资料 - - - - - - - - - 一、单项挑选题 本大题共 15 小题, 每道题 1 分,共 15 分在每道题列出的四个选 项中只有一个选项是符合题目要求的,请将正确选项前的字母填在题后的括号内；1.一个连通的无向图G,假如它的全部结点的度数都是偶数,那么它具有一条 A.汉密尔顿回路B.欧拉回路C.汉密尔顿通路D.初级回路2.设 G 是连通简洁平面图,G 中有 11 个顶点 5 个面,就 G 中的边是 A.10 B.12 C.16 D.14 3.在布尔代数L 中,表达式 ababcb c的等价式是 A.b ac B.aba b C.ababcbc D.bcac 4.设 i 是虚
2、数, 是复数乘法运算,就G=是群,以下是G 的子群是 A. B.-1, C.i, D.-i, 5.设 Z 为整数集, A 为集合, A 的幂集为 PA,+ 、-、/为数的加、减、除运算,为集合的交 运算,以下系统中是代数系统的有 A.Z,+,/B.Z,/C.Z,-, /D.PA ,6.以下各代数系统中不含有零元素的是 A.Q,* Q 是全体有理数集,* 是数的乘法运算 B.MnR,* ,MnR 是全体 n 阶实矩阵集合,*是矩阵乘法运算 C.Z,Z 是整数集,定义为 x xy=xy, x,yZ D.Z,+, Z 是整数集, +是数的加法运算 7.设 A=1,2,3 ,A 上二元关系 R 的关系
3、图如下：R 具有的性质是 A.自反性 B.对称性 C.传递性 D.反自反性名师归纳总结 8.设 A=a,b,c ,A 上二元关系R=a,a,b,b,a,c ,就关系 R 的对称闭包SR是 第 1 页,共 6 页A.R IAB.R C.Rc,a D.RIA9.设 X=a,b,c,Ix是 X 上恒等关系,要使Ix a,b,b,c,c,a, b,a R 为 X 上的等价关系, R 应取 A.c,a,a,cB. c,b,b,a C. c,a,b,a D. a,c,c,b 10.以下式子正确选项 A. B.C.D. 11.设说明R 如下：论域D 为实数集, a=0,fx,y=x-y,Ax,y:xy.以下
4、公式在R 下为真的是 A. x y zAx,y Afx,z,fy,z B. xAfa,x,a C.xy（Afx,y,x - - - - - - -精选学习资料 - - - - - - - - - D.xyAx,y Afx,a,a 12.设 B 是不含变元x 的公式,谓词公式xAx B等价于 A.xAx B B.xAx B C.Ax B D.xAx xB 13.谓词公式 xPx,y zQx,z yRx,y 中变元 x A.是自由变元但不是约束变元B.既不是自由变元又不是约束变元C.既是自由变元又是约束变元D.是约束变元但不是自由变元14.如 P：他聪慧； Q：他用功；就“ 他虽聪慧,但不用功”,
5、可符号化为 A.PQ B.P Q C.P Q D.P Q 15.以下命题公式中,为永假式的是 A.p pqr B.p p p C. qqp D. q pp p 二、填空题 每空 1 分,共 20 分 16.在一棵根树中,仅有一个结点的入度为 _,称为树根,其余结点的入度均为 _；17.A=1,2,3,4 上二元关系 R= 2, 4, 3, 3, 4 , 2 , R 的关系矩阵 M R中m24=_,m 34=_；18.设s,* 是群,就那么 s 中除 _外,不行能有别的幂等元； 如s,*有零元,就|s|=_；19.设 A 为集合,PA 为 A 的幂集,就PA,最小上界是 _；是格,如 x,yPA
6、, 就 x,y 最大下界是 _,20.设函数 f:X Y,假如对 X 中的任意两个不同的 x 1和 x2,它们的象 y1 和 y2 也不同, 我们说 f是_函数,假如 ranf=Y ,就称 f 是_函数；21.设 R 为非空集合 A 上的等价关系,其等价类记为xR；x,y A,如 x,y R,就xR 与 y R 的关系是 _,而如 x,yR,就 xR yR=_ ；22.使公式 x yAx ByxAx yBy 成立的条件是_不含有y,_不含有 x；23.设 Mx:x 是人, Ds:x 是要死的, 就命题 “ 全部的人都是要死的”可符号化为 x_,其中量词 x的辖域是 _；24.如 H 1H2 H
7、n是_,就称 H1,H2, Hn 是相容的, 如 H1H2 Hn是_,就称 H1,H 2, Hn 是不相容的；25. 判定一个语句是否为命题,第一要看它是否为 的；三、运算题 共 30 分 26.4 分设有向图 G=V,E如下图所示, 试用邻接矩阵方法求长度为,然后再看它是否具有唯独2 的路的总数和回路总数；27.5设 A=a,b,PA 是 A 的幂集,是对称差-1bana-nbnan运算,可以验证是群；设 n 是正整数,求 a28.6 分设 A=1,2,3,4,5,A上偏序关系R= 1,2,3,2, 4,1,4,2,4, 3,3,5,4,5 IA ; 名师归纳总结 - - - - - - -
8、第 2 页,共 6 页精选学习资料 - - - - - - - - - 1作出偏序关系 R 的哈斯图2令 B=1,2,3,5 ,求 B 的最大,最小元,极大、微小元,上界,下确界,下界,下确界；29.6 分求 PQ P Q的主合取范式并给出全部使命题为真的赋值；30.5 分设带权无向图 G 如下,求 G 的最小生成树 T 及 T 的权总和,要求写出解的过程；31.4 分求公式 xFx,y yGx,y xHx 的前束范式；四、证明题共 20 分 T 中度数最大的顶点有2 个,它们的度数为kk2,证明 T32.6 分设 T 是非平凡的无向树,中至少有 2k-2 片树叶；33.8 分设 A 是非空集
9、合, F 是全部从 A 到 A 的双射函数的集合,是函数复合运算；证明：F, 是群；34.6 分在个体域 D=a 1,a2, , an中证明等价式： xAx Bx xAx xBx 五、应用题 共 15 分 35.9 分假如他是运算机系本科生或者是运算机系讨论生,那么他肯定学过 DELPHI 语言而且学过 C+ 语言； 只要他学过 DELPHI 语言或者 C+语言, 那么他就会编程序；因此假如他是运算机系本科生,那么他就会编程序；请用命题规律推理方法,证明该推理的有效结论；36.6 分一次学术会议的理事会共有20 个人参与,他们之间有的相互熟悉但有的相互不熟悉；但对任意两个人,他们各自熟悉的人的
10、数目之和不小于20；问能否把这20个人排在圆桌旁,使得任意一个人熟悉其旁边的两个人.依据是什么 . 参考答案1.B 一、单项挑选题本大题共15 小题,每道题1 分,共 15 分 2.D 3.A 4.A 5.D 6.D 7.D 8.C 9.D 10.B 11.A 12.A 13.C 14.B 15.C 二、填空题16.0 1 1 xy 17.1 0 18.单位元19.xy 20.入射21. x R= y R名师归纳总结 22.Ax By Mx Dx 第 3 页,共 6 页23.Mx Dx - - - - - - -精选学习资料 - - - - - - - - - 24.可满意式 永假式 或冲突式
11、 25.陈述句 真值 三、运算题1100n26. M=1010101100112110M2=21112121101144M ij 218,4M ij 26i1j1i1G 中长度为 2 的路总数为18,长度为 2 的回路总数为6；27.当 n 是偶数时,xPA,xn=当 n 是奇数时,xPA,xn=x 于是：当 n 是偶数, a-1ba na-n bna= a-1 nbnan=当 n 是奇数时,a-1bana-nb nann=a-1baa-1 nbna=a-1baa-1ba=28.1偏序关系 R 的哈斯图为2B 的最大元：无,最小元：无；极大元： 2,5,微小元： 1,3 下界： 4, 下确界
12、4；上界：无,上确界：无29.原式 PQP QP Q PQ PQP Q P Q PQ PQ P Q P QP Q P QP Q PQP Q PQ Q PQ Q PQP Q 名师归纳总结 命题为真的赋值是P=1,Q=0 和 P=1,Q=1 第 4 页,共 6 页- - - - - - -精选学习资料 - - - - - - - - - 30.令 e1=v 1,v3, e2=v 4,v6 e3=v 2,v5, e4=v 3,v6 e5=v 2,v3, e6=v 1,v2 e7=v 1,v4, e8=v 4,v3 e9=v 3,v5, e10=v 5,v6 令 ai为 ei上的权,就a1a2a3a4
13、a5=a6=a7=a8a9=a10取 a1的 e1T,a2的 e2T,a3的 e3T,a4的 e4T,a5的 e5 T,即,T 的总权和 =1+2+3+4+5=15 31.原式 x1Fx1,yy 1Gx,y 1x 2Hx 2 换名 x1y1Fx 1,yGx,y 1x 2Hx 2 x1y 1 Fx1,y1Gx,y 1x 2Hx 2 x1y 1x2 Fx 1,y1Gx,y 1Hx 2 四、证明题32.设 T 中有 x 片树叶, y 个分支点；于是 T 中全部顶点的度数之的x yi1d v i=2x+y-1 ；T 中有 x+y 个顶点,有 x+y-1 条边,由握手定理知又树叶的度为1,任一分支点的度
14、大于等于2 且度最大的顶点必是分支点,于是xyd vi x1+2y-2+k+k=x+2y+2K-4 i1从而 2x+y-1 x+2y+2k-4 x2k-2 33.从定义动身证明：由于集合 A 是非空的,故明显从 A 到 A 的双射函数总是存在的,如 A上恒等函数,因此 F 非空1 f,g F,由于 f 和 g 都是 A 到 A 的双射函数,故 f g 也是 A 到 A 的双射函数,从而集合 F 关于运算 是封闭的；2 f,g,h F,由函数复合运算的结合律有 f g h=f g h 故运算 是可结合的；3A 上的恒等函数 I A也是 A 到 A 的双射函数即 I AF,且 fF 有 I A f
15、=f I A=f, 故 IA是 F,中的幺元名师归纳总结 4fF,由于 f 是双射函数, 故其逆函数是存在的, 也是 A 到 A 的双射函数, 且有 f f f=I A,因此 f-1 是 f 的逆元-1=f-1第 5 页,共 6 页由此上知 F,是群34.证明 xAx Bx x Ax Bx - - - - - - -精选学习资料 - - - - - - - - - Aa 1Ba 1 Aa 2Ba2 Aa nBa n Aa 1Aa 2 AanBa 1Ba2 Ba n Aa 1Aa 2 Aa n Ba 1Ba 2 Ba n xAx xBx xAx xBx 五、应用题35.令 p：他是运算机系本科生
16、 q：他是运算机系讨论生 r：他学过 DELPHI 语言 s:他学过 C+语言 t:他会编程序 前提： pqrs,rst 结论： pt 证 p P附加前提 pq TI pqrs P前提引入 rs T I r T I rs TI rst P前提引入 t T I 36.可以把这 20 个人排在圆桌旁,使得任一人熟悉其旁边的两个人；依据：构造无向简洁图 G=,其中 V=v 1,v2, ,V 20 是以 20 个人为顶点的集合,E 中 的边是如任两个人 v i 和 v j 相互熟悉就在 vi 与 v j 之间连一条边；v i,vjV 有 dv i+dv j 20,于是 G V iV,dvi是与 v i相互熟悉的人的数目,由题意知 中存在汉密尔顿回路；设 C=V i1V i2 Vi20V i1是 G 中一条汉密尔顿回路, 按这条回路的次序按其排座 位即符合要求；名师归纳总结 - - - - - - -第 6 页,共 6 页