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

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

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 中，表达式 (ab)(abc)(b c)的等价式是 ( ) A.b(ac) B.(ab)(a b) C.(ab)(abc)(bc) D.(bc)(ac) 4.设

2、 i 是虚数，是复数乘法运算，则G=是群，下列是G 的子群是 ( ) A. B.-1, C.i, D.-i, 5.设 Z 为整数集， A 为集合， A 的幂集为P(A),+ 、-、/为数的加、减、除运算，为集合的交运算，下列系统中是代数系统的有( ) A.Z，+，/B.Z，/C.Z，-， /D.P(A) ，6.下列各代数系统中不含有零元素的是( ) A.Q，* Q 是全体有理数集，* 是数的乘法运算B.Mn(R),* ,Mn(R) 是全体 n 阶实矩阵集合，*是矩阵乘法运算C.Z，Z 是整数集，定义为 x xy=xy,x,yZ D.Z，+ ， Z 是整数集， +是数的加法运算7.设 A=1,2

3、,3 ，A 上二元关系R 的关系图如下：R 具有的性质是A.自反性B.对称性C.传递性D.反自反性8.设 A=a,b,c ， A 上二元关系R=a,a ，b,b , a,c ， 则关系 R 的对称闭包S(R)是( ) A.RIAB.R C.Rc,a D.RIA9.设 X=a,b,c,Ix是 X 上恒等关系，要使Ixa,b ， b,c ， c,a ， b,aR 为 X 上的等价关系， R 应取 ( ) A. c,a ， a,c B. c,b ， b,a C. c,a ， b,a D. a,c ， c,b 10.下列式子正确的是( ) A. B.C.D.11.设解释R 如下：论域D 为实数集， a

4、=0,f(x,y)=x-y,A(x,y):xy.下列公式在R 下为真的是( ) A.( x)( y)( z)(A(x,y) A(f(x,z),f(y,z) B.( x)A(f(a,x),a) C.(x)(y)（A(f(x,y),x) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 6 页D.(x)(y)(A(x,y) A(f(x,a),a) 12.设 B 是不含变元x 的公式，谓词公式(x)(A(x) B)等价于 ( ) A.(x)A(x) B B.(x)A(x) B C.A(x) B D.(x)A(x) (x)B 13.谓词公式 (x

5、)(P(x,y) (z)Q(x,z)(y)R(x,y) 中变元 x( ) A.是自由变元但不是约束变元B.既不是自由变元又不是约束变元C.既是自由变元又是约束变元D.是约束变元但不是自由变元14.若 P：他聪明； Q：他用功；则“他虽聪明，但不用功”，可符号化为( ) A.PQ B.P Q C.P Q D.P Q 15.以下命题公式中，为永假式的是( ) A.p(pqr) B.(p p) p C.(qq)p D.(q p)(p p) 二、填空题 (每空 1 分，共 20 分) 16.在一棵根树中，仅有一个结点的入度为_，称为树根，其余结点的入度均为_。17.A=1,2,3,4 上二元关系R=

6、2， 4 ， 3， 3 ， 4， 2 ， R 的关系矩阵MR中m24=_,m34=_。18.设 s,* 是群，则那么 s 中除 _外， 不可能有别的幂等元；若 s,* 有零元，则|s|=_。19.设 A 为集合，P(A) 为 A 的幂集，则 P(A)， 是格， 若 x,yP(A), 则 x,y 最大下界是 _，最小上界是 _。20.设函数 f:X Y,如果对 X 中的任意两个不同的x1和 x2，它们的象y1和 y2也不同， 我们说 f是_函数，如果ranf=Y ，则称 f 是_函数。21.设 R 为非空集合A 上的等价关系，其等价类记为xR。x,y A，若 x,y R，则xR与 yR的关系是

7、_，而若 x,yR，则 xR yR=_ 。22.使公式 (x)( y)(A(x) B(y)(x)A(x) (y)B(y) 成立的条件是_不含有y，_不含有 x。23.设 M(x):x 是人， D(s):x 是要死的， 则命题 “所有的人都是要死的”可符号化为 (x)_,其中量词 (x)的辖域是 _。24.若 H1H2 Hn是_， 则称 H1,H2, Hn 是相容的， 若 H1H2 Hn是_，则称 H1,H2,Hn是不相容的。25. 判断一个语句是否为命题，首先要看它是否为，然后再看它是否具有唯一的。三、计算题(共 30 分) 26.(4 分)设有向图 G=(V,E)如下图所示， 试用邻接矩阵方

8、法求长度为2 的路的总数和回路总数。27.(5)设 A=a,b,P(A) 是 A 的幂集，是对称差运算，可以验证是群。设n 是正整数，求(a-1ba)na-nbnan28.(6 分)设 A=1,2,3,4,5,A上偏序关系R= 1，2 ， 3，2 ， 4，1 ， 4，2 ， 4， 3 ， 3，5 ， 4，5IA; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 6 页(1)作出偏序关系R 的哈斯图(2)令 B=1,2,3,5 ，求 B 的最大，最小元，极大、极小元，上界，下确界，下界，下确界。29.(6 分)求 (PQ)(P Q)的主合

9、取范式并给出所有使命题为真的赋值。30.(5 分)设带权无向图G 如下，求 G 的最小生成树T 及 T 的权总和，要求写出解的过程。31.(4 分)求公式 (x)F(x,y) (y)G(x,y) (x)H(x) 的前束范式。四、证明题(共 20 分) 32.(6 分)设 T 是非平凡的无向树，T 中度数最大的顶点有2 个，它们的度数为k(k2),证明 T中至少有 2k-2 片树叶。33.(8 分)设 A 是非空集合， F 是所有从 A 到 A 的双射函数的集合，是函数复合运算。证明： F, 是群。34.(6 分)在个体域D=a1,a2,， an中证明等价式：(x)(A(x) B(x)(x)A(

10、x) (x)B(x) 五、应用题 (共 15 分) 35.(9 分)如果他是计算机系本科生或者是计算机系研究生，那么他一定学过DELPHI 语言而且学过 C+语言。 只要他学过DELPHI 语言或者C+语言， 那么他就会编程序。因此如果他是计算机系本科生，那么他就会编程序。请用命题逻辑推理方法，证明该推理的有效结论。36.(6 分)一次学术会议的理事会共有20 个人参加，他们之间有的相互认识但有的相互不认识。但对任意两个人，他们各自认识的人的数目之和不小于20。问能否把这20个人排在圆桌旁，使得任意一个人认识其旁边的两个人?根据是什么 ? 参考答案一、单项选择题(本大题共15 小题，每小题1

11、分，共 15 分) 1.B 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 17.1 0 18.单位元1 19.xy xy 20.入射21. xR= yR22.A(x) B(y) 23.(M(x) D(x) M(x) D(x) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 6 页24.可满足式永假式 (或矛盾式 ) 25.陈述句真值三、计算题26. M=1100101010110011M2=2110211121211011Mijji21

12、41418,Miji2146G 中长度为2 的路总数为18，长度为2 的回路总数为6。27.当 n 是偶数时，xP(A),xn=当 n 是奇数时，xP(A),xn=x 于是：当n是偶数， (a-1b a)na-n bnan=( a-1)nbnan=当 n 是奇数时，(a-1b a)na-nbnan=a-1b a(a-1)nbnan=a-1b aa-1b a=28.(1)偏序关系R 的哈斯图为(2)B 的最大元：无，最小元：无；极大元： 2，5，极小元： 1，3 下界： 4， 下确界 4；上界：无，上确界：无29.原式(PQ)(P Q)(P Q) (PQ) (PQ)(P Q)(P Q) (PQ)

13、 (PQ P Q)(PQ)(P Q) (P Q)(P Q) (PQ)(P Q) P(Q Q) P(Q Q) (PQ)(P Q) 命题为真的赋值是P=1,Q=0 和 P=1,Q=1 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 6 页30.令 e1=(v1,v3), e2=(v4,v6) e3=(v2,v5), e4=(v3,v6) e5=(v2,v3), e6=(v1,v2) e7=(v1,v4), e8=(v4,v3) e9=(v3,v5), e10=(v5,v6) 令 ai为 ei上的权，则a1a2a3a4a5=a6=a7=a8a

14、9=a10取 a1的 e1T,a2的 e2T,a3的 e3T,a4的 e4T,a5的 e5 T,即，T 的总权和 =1+2+3+4+5=15 31.原式(x1F(x1,y)y1G(x,y1)x2H(x2) (换名 ) x1y1(F(x1,y)G(x,y1)x2H(x2) x1y1(F(x1,y1)G(x,y1)x2H(x2) x1y1x2(F(x1,y1)G(x,y1)H(x2) 四、证明题32.设 T 中有 x 片树叶， y 个分支点。于是T 中有 x+y 个顶点，有x+y-1 条边，由握手定理知T 中所有顶点的度数之的d viix y()1=2(x+y-1) 。又树叶的度为1，任一分支点的

15、度大于等于2 且度最大的顶点必是分支点，于是d viixy()1 x1+2(y-2)+k+k=x+2y+2K-4 从而 2(x+y-1) x+2y+2k-4 x2k-2 33.从定义出发证明：由于集合A 是非空的，故显然从A 到 A 的双射函数总是存在的，如A上恒等函数，因此F 非空(1)f,g F,因为 f 和 g 都是 A 到 A 的双射函数，故fg 也是 A 到 A 的双射函数，从而集合 F 关于运算是封闭的。(2)f,g,h F,由函数复合运算的结合律有f(g h)=(fg) h 故运算是可结合的。(3)A 上的恒等函数IA也是 A 到 A 的双射函数即IAF,且fF有 IAf=fIA

16、=f,故 IA是 F，中的幺元(4)fF,因为 f 是双射函数， 故其逆函数是存在的， 也是 A 到 A 的双射函数， 且有 f f-1=f-1f=IA,因此 f-1是 f 的逆元由此上知 F，是群34.证明 (x)(A(x) B(x) x(A(x) B(x) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 6 页(A(a1)B(a1)(A(a2)B(a2) (A(an)B(an) (A(a1)A(a2) A(an)(B(a1)B(a2) (B(an) (A(a1)A(a2) A(an)(B(a1)B(a2) (B(an) (x)A(x

17、) (x)B(x) (x)A(x) (x)B(x) 五、应用题35.令 p：他是计算机系本科生q：他是计算机系研究生r：他学过DELPHI 语言s:他学过 C+语言t:他会编程序前提： (pq)(rs),(rs)t 结论： pt 证 p P(附加前提 ) pq TI (pq)(rs) P(前提引入 ) rs T I r T I rs TI (rs)t P(前提引入 ) t T I 36.可以把这20 个人排在圆桌旁，使得任一人认识其旁边的两个人。根据：构造无向简单图G=,其中 V=v1,v2,，V20是以 20 个人为顶点的集合，E 中的边是若任两个人vi和 vj相互认识则在vi与 vj之间连一条边。ViV,d(vi)是与 vi相互认识的人的数目，由题意知vi,vjV 有 d(vi)+d(vj)20,于是 G中存在汉密尔顿回路。设 C=Vi1Vi2Vi20Vi1是 G 中一条汉密尔顿回路，按这条回路的顺序按其排座位即符合要求。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 6 页