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

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

1、1/7 一、单项选择题(本大题共 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)(bc)的等价式是()A.b(ac)B.(ab)(ab)C.(ab)(abc)(bc)D.(bc)(ac)4.设 i 是

2、虚数，是复数乘法运算，则 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 是整数集，定义为 xxy=xy,x,yZ D.Z，+，Z 是整数集，+是数的加法运算 7.设 A=1,2,3，A 上二元关系 R 的关系图如下：R

3、具有的性质是 A.自反性 B.对称性 C.传递性 D.反自反性 8.设 A=a,b,c，A 上二元关系 R=a,a，b,b,a,c，则关系 R 的对称闭包 S(R)是()A.RIA B.R C.Rc,a D.RIA 9.设 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=0,f(x,y)=x-y,A(x,y):xy.下列公式在 R 下为真的是()A.(x)

4、(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)2/7 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)(P(x,y)(z)Q(x,z)(y)R(x,y)中变元 x()A.是自由变元但不是约束变元 B.既不是自由变元又不是约束变元 C.既是自由变元又是约束变元 D.是约束变元但不是自由变元 14.若 P：他聪明；Q：他用功；则“他

5、虽聪明，但不用功”，可符号化为()A.PQ B.PQ C.PQ D.PQ 15.以下命题公式中，为永假式的是()A.p(pqr)B.(pp)p C.(qq)p D.(qp)(pp)二、填空题(每空 1 分，共 20 分)16.在一棵根树中，仅有一个结点的入度为_0_，称为树根，其余结点的入度均为_1_。17.A=1,2,3,4上二元关系 R=2，4，3，3，4，2，R 的关系矩阵 MR中m24=_1_,m34=_0_。18.设s,*是群，则那么 s 中除_幺元_外，不可能有别的幂等元；若s,*有零元，则|s|=_1_。19.设 A 为集合，P(A)为 A 的幂集，则 P(A)，是格，若 x,y

6、P(A),则 x,y 最大下界是_，最小上界是_。20.设函数 f:XY,如果对 X 中的任意两个不同的 x1和 x2，它们的象 y1和 y2也不同，我们说 f是_入射_函数，如果 ranf=Y，则称 f 是_满射_函数。21.设 R 为非空集合 A 上的等价关系，其等价类记为xR。x,yA，若x,yR，则 xR与yR的关系是_，而若x,yR，则xRyR=_。22.使公式(x)(y)(A(x)B(y)(x)A(x)(y)B(y)成立的条件是_不含有 y，_ 不含有 x。23.设 M(x):x 是人，D(s):x 是要死的，则命题“所有的人都是要死的”可符号化为(x)_,其中量词(x)的辖域是_

7、。24.若 H1H2Hn是_，则称 H1,H2,Hn 是相容的，若 H1H2Hn是_，则称 H1,H2,Hn是不相容的。25.判断一个语句是否为命题，首先要看它是否为 ，然后再看它是否具有唯一的 。三、计算题(共 30 分)26.(4分)设有向图G=(V,E)如下图所示，试用邻接矩阵方法求长度为2的路的总数和回路总数。3/7 27.(5)设 A=a,b,P(A)是 A 的幂集，是对称差运算，可以验证是群。设 n 是正整数，求(a-1ba)na-nbnan 28.(6 分)设 A=1,2,3,4,5,A 上偏序关系 R=1，2，3，2，4，1，4，2，4，3，3，5，4，5IA;(1)作出偏序关

8、系 R 的哈斯图(2)令 B=1,2,3,5，求 B 的最大，最小元，极大、极小元，上界，下确界，下界，下确界。29.(6 分)求(PQ)(PQ)的主合取范式并给出所有使命题为真的赋值。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 的双

9、射函数的集合，是函数复合运算。证明：F,是群。34.(6 分)在个体域 D=a1,a2,，an中证明等价式：(x)(A(x)B(x)(x)A(x)(x)B(x)五、应用题(共 15 分)35.(9 分)如果他是计算机系本科生或者是计算机系研究生，那么他一定学过 DELPHI 语言而且学过 C+语言。只要他学过 DELPHI 语言或者 C+语言，那么他就会编程序。因此如果他是计算机系本科生，那么他就会编程序。请用命题逻辑推理方法，证明该推理的有效结论。36.(6分)一次学术会议的理事会共有20个人参加，他们之间有的相互认识但有的相互不认识。但对任意两个人，他们各自认识的人的数目之和不小于 20。

10、问能否把这 20 个人排在圆桌旁，使得任意一个人认识其旁边的两个人?根据是什么?4/7 参考答案 一、单项选择题(本大题共 15 小题，每小题 1 分，共 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=yR 22.A(x)B(y)23.(M(x)D(x)M(x)D(x)24.可满足式 永假式(或矛盾式)25.陈述句 真值 三、计算题 26.M=1100101010110011 M2=211021

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

12、)(PQ)(PQ)(PQ)(PQ)(PQ)(PQPQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)P(QQ)P(QQ)(PQ)(PQ)命题为真的赋值是 P=1,Q=0 和 P=1,Q=1 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=a8a9=a10 取 a1的 e1T,a2的 e2T,a3的 e3T,a4的 e4T,a5的 e5T,即，T 的总权和=1+

13、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，任一分支点的度大于等于 2 且度最大的顶点必是分支点，于是 6/7 d viix y()1x1+2(y-2)+k+k=x+2y+2K-4

14、从而 2(x+y-1)x+2y+2k-4 x2k-2 33.从定义出发证明：由于集合 A 是非空的，故显然从 A 到 A 的双射函数总是存在的，如 A上恒等函数，因此 F 非空 (1)f,gF,因为 f 和 g 都是 A 到 A 的双射函数，故 fg 也是 A 到 A 的双射函数，从而集合 F 关于运算是封闭的。(2)f,g,hF,由函数复合运算的结合律有 f(gh)=(fg)h 故运算是可结合的。(3)A上的恒等函数IA也是A到A的双射函数即IAF,且fF有IAf=fIA=f,故IA是 F，中的幺元 (4)fF,因为 f是双射函数，故其逆函数是存在的，也是A到A的双射函数，且有ff-1=f-

15、1f=IA,因此 f-1是 f 的逆元 由此上知F，是群 34.证明(x)(A(x)B(x)x(A(x)B(x)(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)(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 TI r TI rs TI (rs)t P(前提引入)t TI 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 中一条汉密尔顿回路，按这条回路的顺序按其排座位即符合要求。7/7