离散数学试卷及答案.doc

1、1一、单项选择题(本大题共 15 小题，每小题 1 分，共 15 分) 在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。1.一个连通的无向图 G，如果它的所有结点的度数都是偶数，那么它具有一条( )A.汉密尔顿回路 B.欧拉回路C.汉密尔顿通路 D.初级回路2.设 G 是连通简单平面图，G 中有 11 个顶点 5 个面，则 G 中的边是( )A.10 B.12 C.16 D.143.在布尔代数 L 中，表达式(ab)(a bc)(bc)的等价式是( )A.b(a c)B.(ab) (a b)C.(ab) (a bc)(bc)D.(bc)(a c)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,yZD.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.RI A B.R C.R c,a D.RI A9.设 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,aC.c,a ， b,a D.a,c ， c,b10.下列式子正确的是( )A. B. C. D. 11.设解释 R 如下：论域 D 为实数集，a=0,f(x

4、,y)=x-y,A(x,y):x是群。设 n 是正3整数，求(a -1ba)n a-nbnan28.(6 分) 设 A=1,2,3,4,5,A 上偏序关系R=1，2 ， 3，2 ， 4，1 ， 4，2 ， 4，3 ， 3，5 ， 4，5I A;(1)作出偏序关系 R 的哈斯图(2)令 B=1,2,3,5，求 B 的最大，最小元，极大、极小元，上界，下确界，下界，下确界。29.(6 分) 求(PQ) (PQ)的主合取范式并给出所有使命题为真的赋值。30.(5 分) 设带权无向图 G 如下，求 G 的最小生成树 T 及 T 的权总和，要求写出解的过程。31.(4 分) 求公式( x)F(x,y)(

5、 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,，a n中证明等价式：( x)(A(x)B(x) ( x)A(x)( x)B(x)五、应用题(共 15 分)35.(9 分) 如果他是计算机系本科生或者是计算机系研究生，那么他一定学过 DELPHI 语言而且学过 C+语言。

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

7、6.0 117.1 018.单位元 119.xy xy20.入射 满射421.x R=y R 22.A(x) B(y)23.(M(x)D(x) M(x)D(x)24.可满足式 永假式(或矛盾式)25.陈述句 真值三、计算题26. M= 10M2=10ijji2148,Mij2146G 中长度为 2 的路总数为 18，长度为 2 的回路总数为 6。27.当 n 是偶数时， xP(A),x n=当 n 是奇数时， xP(A),x n=x于是：当 n 是偶数，(a -1b a ) n a -nb na n= (a -1)nb na n= 当 n 是奇数时，(a -1b a ) n a -nb na

8、n=a -1b a (a -1)nb na n=a -1b a a -1b a= 28.(1)偏序关系 R 的哈斯图为(2)B 的最大元：无，最小元：无；极大元：2，5，极小元：1，3下界：4， 下确界 4；上界：无，上确界：无29.原式 (PQ)(PQ)(P Q)(PQ) (PQ)(PQ)(PQ)(P Q) (P QP Q)(P Q)(PQ) (PQ)(PQ) (PQ)(PQ) P(QQ)5 P(QQ) (PQ)(PQ)命题为真的赋值是 P=1,Q=0 和 P=1,Q=130.令 e1=(v1,v3), e2=(v4,v6)e3=(v2,v5), e4=(v3,v6)e5=(v2,v3),

9、e6=(v1,v2)e7=(v1,v4), e8=(v4,v3)e9=(v3,v5), e10=(v5,v6)令 ai 为 ei 上的权，则a1,其中 V=v1,v2,，V 20是以 20 个人为顶点的集合，E中的边是若任两个人 vi 和 vj 相互认识则在 vi 与 vj 之间连一条边。ViV,d(v i)是与 vi 相互认识的人的数目，由题意知 vi,vjV 有 d(vi)+d(vj) 20,于是 G 中存在汉密尔顿回路。设 C=Vi1Vi2Vi20Vi1 是 G 中一条汉密尔顿回路，按这条回路的顺序按其排座位即符合要求。7一、单项选择题（本大题共 15 小题，每小题 1 分，共 15 分

10、）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1下列是两个命题变元 p，q 的小项是（ ）Appq BpqCpq Dppq2令 p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（ ）Apq BpqCpq Dpq3下列语句中是命题的只有（ ）A1+1=10 Bx+y=10Csinx+siny,I A，则对应于 R 的 A 的划分是（ ）Aa,b,c,d Ba,b,c,dCa,b,c,d Da,b,c,d8设 A=，B=P(P(A)，以下正确的式子是（ ）A, B B,BC,B D,B9设 X，Y，Z 是集合，一

11、是集合相对补运算，下列等式不正确的是（ ）A(X - Y)- Z=X- (YZ)B(X - Y)- Z=(X- Z)- YC(X - Y)- Z=(X- Z)- (Y- Z)D(X - Y)- Z=X- (YZ)10设*是集合 A 上的二元运算，称 Z 是 A 上关于运算* 的零元，若（ ）A 有 x*Z=Z*x=Z,x8BZ A，且 有 x*Z=Z*x=ZxCZ A，且 有 x*Z=Z*x=xDZ A，且 有 x*Z=Z*x=Z11在自然数集 N 上，下列定义的运算中不可结合的只有（ ）Aa*b=min(a,b)Ba*b=a+bCa*b=GCD(a,b)(a,b 的最大公约数)Da*b=a(

12、mod b)12设 R 为实数集，R +=x|xRx0，*是数的乘法运算， 是一个群，则下列集合关于数的乘法运算构成该群的子群的是（ ）AR +中的有理数 BR +中的无理数 CR +中的自然数 D1 ，2，313设是环，则下列正确的是（ ）A是交换群 B是加法群C 对*是可分配的 D*对 是可分配的14下列各图不是欧拉图的是（ ）15设 G 是连通平面图，G 中有 6 个顶点 8 条边，则 G 的面的数目是（ ）A2 个面 B3 个面C4 个面 D5 个面第二部分 非选择题（共 85 分）二、填空题（本大题共 10 小题，每空 1 分，共 20 分）请在每小题的空格中填上正确答案。错填、不填

13、均无分。16一公式为 之充分必要条件是其析取范式之每一析取项中均必同时包含一命题变元及其否定；一公式为 之充分必要条件是其合取范式之每一合取项中均必同时包含一命题变元及其否定。17前束范式具有形式(Q 1V1)(Q2V2)(QnVn)A，其中 Qi(1in) 为 ，A 为 的谓词公式。18设论域是a,b,c，则( x)S(x)等价于命题公式 ；( )S(x)等价于命题公式 x。19设 R 为 A 上的关系，则 R 的自反闭包 r(R)= ，对称闭包 s(R)= 。20某集合 A 上的二元关系 R 具有对称性，反对称性，自反性和传递性，此关系 R 是 ，其关系矩阵是 。21设是一个偏序集，如果

14、S 中的任意两个元素都有 和 ，则称 S 关于构成一个格。22设 Z 是整数集，在 Z 上定义二元运算*为 a*b=a+b+ab，其中+和是数的加法和乘法，9则代数系统的幺元是 ，零元是 。23如下平面图有 2 个面 R1 和 R2，其中 deg(R1)= ，deg(R 2)= 。24无向图 G 具有一条欧拉回路，当且仅当 G 是 ，并且所有结点的度数都是 。25在下图中，结点 v2 的度数是 ，结点 v5 的度数是 。三、计算题（本大题共 6 小题，第 2627 小题每小题 4 分，第 28、30 小题每小题 5 分，第 29、31 小题每小题 6 分，共 30 分）26 （4 分）求出从

15、A=1,2到 B=x,y的所有函数，并指出哪些是双射函数，哪些是满射函数。27 （4 分）如果论域是集合a,b,c，试消去给定公式中的量词： 。)0yx)(28 （5 分）设 A=a,b,c ，P（A）是 A 的幂集， 是集合对称差运算。已知是群。在群中，找出其幺元。 找出任一元素的逆元。 求元素 x 使满足ax=b。29 （6 分）用等值演算法求公式(pq) (pq) 的主合取范式30 （5 分）画出 5 个具有 5 个结点 5 条边的非同构的无向连通简单图。31 （6 分）在偏序集中，其中 Z=1,2,3,4,6,8,12,14，是 Z 中的整除关系，求集合D=2,3,4,6的极大元，极小

16、元，最大元，最小元，最小上界和最大下界。四、证明题（本大题共 3 小题，第 3233 小题每小题 6 分，第 34 小题 8 分，共 20 分）32 （6 分）用等值演算法证明(qs) r)(s (p r) (s(pq)r33 （6 分）设 n 阶无向树 G=中有 m 条边，证明 m=n- 1。34 （8 分）设 P=,1,1,2,1,2,3， 是集合 P 上的包含关系。（1）证明：是偏序集。（2）在（1）的基础上证明是全序集五、应用题(15 分）35 （9 分）在谓词逻辑中构造下面推理的证明：每个在学校读书的人都获得知识。所以如果没有人获得知识就没有人在学校读书。 （个体域：所有人的集合）11