离散数学试卷与答案.pdf

.-可修编.一、单项选择题(本大题共 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 是虚数，是复数乘法运算，则 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 具有的性质是 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)(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)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：他用功；则“他虽聪明，但不用功”，可符号化为()A.PQ B.PQ C.PQ D.PQ 15.以下命题公式中，为永假式的是()A.p(pqr)B.(pp)p C.(qq)p D.(qp)(pp)二、填空题(每空 1 分，共 20 分)16.在一棵根树中，仅有一个结点的入度为_，称为树根，其余结点的入度均为_。17.A=1,2,3,4上二元关系 R=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: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)的辖域是_。24.若 H1H2Hn是_，则称 H1,H2,Hn 是相容的，若 H1H2Hn是_，则称 H1,H2,Hn是不相容的。25.判断一个语句是否为命题，首先要看它是否为，然后再看它是否具有唯一的。三、计算题(共 30 分)26.(4 分)设有向图 G=(V,E)如下图所示，试用邻接矩阵方法求长度为 2 的路的总数和回路总数。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)作出偏序关系 R 的哈斯图(2)令 B=1,2,3,5，求 B 的最大，最小元，极大、极小元，上界，下确界，下界，下确界。29.(6 分)求(PQ)(PQ)的主合取 X 式并给出所有使命题为真的赋值。30.(5 分)设带权无向图 G 如下，求 G 的最小生成树 T 及 T 的权总和，要求写出解的过程。31.(4 分)求公式(x)F(x,y)(y)G(x,y)(x)H(x)的前束 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(x)(x)B(x)五、应用题(共 15 分)35.(9 分)如果他是计算机系本科生或者是计算机系研究生，那么他一定学过 DELPHI 语言而且学过 C+语言。只要他学过 DELPHI 语言或者 C+语言，那么他就会编程序。因此如果他是计算机系本科生，那么他就会编程序。请用命题逻辑推理方法，证明该推理的有效结论。36.(6 分)一次学术会议的理事会共有 20 个人参加，他们之间有的相互认识但有的相互不认识。但对任意两个人，他们各自认识的人的数目之和不小于 20。问能否把这 20个人排在圆桌旁，使得任意一个人认识其旁边的两个人?根据是什么?参考答案 一、单项选择题(本大题共 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=2110211121211011 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 的哈斯图为 (2)B 的最大元：无，最小元：无；极大元：2，5，极小元：1，3 下界：4，下确界 4；上界：无，上确界：无 29.原式(PQ)(PQ)(PQ)(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+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 且度最大的顶点必是分支点，于是 d viix y()1x1+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,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-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 中一条汉密尔顿回路，按这条回路的顺序按其排座位即符合要求。.-可修编.一、单项选择题（本大题共 15 小题，每小题 1 分，共 15 分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1下列是两个命题变元 p，q 的小项是（）Appq Bpq Cpq Dppq 2 令 p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（）Apq Bpq Cpq Dpq 3下列语句中是命题的只有（）A1+1=10 Bx+y=10 Csinx+siny0 Dx mod 3=2 4下列等值式不正确的是（）A(x)A(x)A B(x)(BA(x)B(x)A(x)C(x)(A(x)B(x)(x)A(x)(x)B(x)D(x)(y)(A(x)B(y)(x)A(x)(y)B(y)5谓词公式(x)P(x,y)(x)(Q(x,z)(x)(y)R(x,y,z)中量词x 的辖域是（）A(x)Q(x,z)(x)(y)R(x,y,z)BQ(x,z)(y)R(x,y,z)CQ(x,z)(x)(y)R(x,y,z)DQ(x,z)6设 R 为实数集，函数 f：RR，f(x)=2x，则 f 是（）A满射函数 B入射函数 C双射函数 D非入射非满射 7设 A=a,b,c,d，A 上的等价关系 R=,IA，则对应于 R 的 A的划分是（）Aa,b,c,d Ba,b,c,d Ca,b,c,d Da,b,c,d 8设 A=，B=P(P(A)，以下正确的式子是（）A,B B,B C,B D,B 9设 X，Y，Z 是集合，一是集合相对补运算，下列等式不正确的是（）A(X-Y)-Z=X-(YZ)B(X-Y)-Z=(X-Z)-Y C(X-Y)-Z=(X-Z)-(Y-Z)D(X-Y)-Z=X-(YZ)10设*是集合 A 上的二元运算，称 Z 是 A 上关于运算*的零元，若（）A,Ax 有 x*Z=Z*x=Z BZA，且Ax有 x*Z=Z*x=Z CZA，且Ax有 x*Z=Z*x=x DZA，且Ax有 x*Z=Z*x=Z .-可修编.11在自然数集 N 上，下列定义的运算中不可结合的只有（）Aa*b=min(a,b)Ba*b=a+b Ca*b=GCD(a,b)(a,b 的最大公约数)Da*b=a(mod b)12设 R 为实数集，R+=x|xRx0，*是数的乘法运算，是一个群，则下列集合关于数的乘法运算构成该群的子群的是（）AR+中的有理数 BR+中的无理数 CR+中的自然数 D1，2，3 13设是环，则下列正确的是（）A是交换群 B是加法群 C对*是可分配的 D*对是可分配的 14下列各图不是欧拉图的是（）15设 G 是连通平面图，G 中有 6 个顶点 8 条边，则 G 的面的数目是（）A2 个面 B3 个面 C4 个面 D5 个面 第二部分 非选择题（共 85 分）二、填空题（本大题共 10 小题，每空 1 分，共 20 分）请在每小题的空格中填上正确答案。错填、不填均无分。16 一公式为之充分必要条件是其析取 X 式之每一析取项中均必同时包含一命题变元及其否定；一公式为之充分必要条件是其合取 X 式之每一合取项中均必同时包含 一命题变元及其否定。17前束 X 式具有形式(Q1V1)(Q2V2)(QnVn)A，其中 Qi(1in)为，A 为的谓词公式。18设论域是a,b,c，则(x)S(x)等价于命题公式；(x)S(x)等价于命题公式。19设 R 为 A 上的关系，则 R 的自反闭包 r(R)=，对称闭包 s(R)=。20某集合 A 上的二元关系 R 具有对称性，反对称性，自反性和传递性，此关系 R 是，其关系矩阵是。21设是一个偏序集，如果 S 中的任意两个元素都有和，则称 S 关于构成一个格。22设 Z 是整数集，在 Z 上定义二元运算*为 a*b=a+b+ab，其中+和是数的加法和乘法，则代数系统的幺元是，零元是。23如下平面图有 2 个面 R1和 R2，其中 deg(R1)=，deg(R2)=。.-可修编.24无向图 G 具有一条欧拉回路，当且仅当 G 是，并且所有结点的度数都是。25在下图中，结点v2的度数是，结点v5的度数是。三、计算题（本大题共 6 小题，第 2627 小题每小题 4 分，第 28、30 小题每小题 5 分，第 29、31 小题每小题 6 分，共 30 分）26（4 分）求出从 A=1,2到 B=x,y的所有函数，并指出哪些是双射函数，哪些是满射函数。27（4 分）如果论域是集合a,b,c，试消去给定公式中的量词：)0yx)(x)(y(。28（5 分）设 A=a,b,c，P（A）是 A 的幂集，是集合对称差运算。已知是群。在群中，找出其幺元。找出任一元素的逆元。求元素 x 使满足ax=b。29（6 分）用等值演算法求公式(pq)(pq)的主合取 X 式 30（5 分）画出 5 个具有 5 个结点 5 条边的非同构的无向连通简单图。31（6 分）在偏序集中，其中 Z=1,2,3,4,6,8,12,14，是 Z 中的整除关系，求集合D=2,3,4,6的极大元，极小元，最大元，最小元，最小上界和最大下界。四、证明题（本大题共 3 小题，第 3233 小题每小题 6 分，第 34 小题 8 分，共 20 分）32（6 分）用等值演算法证明(qs)r)(s(pr)(s(pq)r 33（6 分）设 n 阶无向树 G=中有 m 条边，证明 m=n-1。34（8 分）设 P=,1,1,2,1,2,3，是集合 P 上的包含关系。（1）证明：是偏序集。（2）在（1）的基础上证明是全序集 五、应用题(15 分）35（9 分）在谓词逻辑中构造下面推理的证明：每个在学校读书的人都获得知识。所以如果没有人获得知识就没有人在学校读书。（个体域：所有人的集合）.-可修编.-可修编.-可修编.