《离散数学试卷及答案》由会员分享,可在线阅读,更多相关《离散数学试卷及答案(12页珍藏版)》请在金锄头文库上搜索。
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)(abc)(bc)的等价式是( )A.b(ac)B.(ab)(ab)C.(ab)(abc)(bc)D.(bc)(ac)4.设i是虚数,是复数乘法运算,则G=是群,下列是G的子群
2、是( )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,yZD.Z,+,Z是整数集,+是数的加法运算7.设A=1,2,3,A上二元关系R的关系图如下:R具有的性质是A.自反性B.对称性C.传递性D.反自反性8.设A=a,b,c,A
3、上二元关系R=a,a,b,b,a,c,则关系R的对称闭包S(R)是( )A.RIA B.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,aC.c,a,b,a D.a,c,c,b10.下列式子正确的是( )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(
4、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)BC.A(x)B D.(x)A(x)(x)B13.谓词公式(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.PQ15.以下命题公式中,为永假式的是( )A.p(pqr) B.(pp
5、)pC.(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为
6、非空集合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)如下图
7、所示,试用邻接矩阵方法求长度为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;(1)作出偏序关系R的哈斯图(2)令B=1,2,3,5,求B的最大,最小元,极大、极小元,上界,下确界,下界,下确界。29.(6分)求(PQ)(PQ)的主合取范式并给出所有使命题为真的赋值。30.(5分)设带权无向图G如下,求G的最小生成树T及T的权总和,要求写出解的过程。31.(4分)求公式(x)F(x,
8、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(x)(x)B(x)五、应用题(共15分)35.(9分)如果他是计算机系本科生或者是计算机系研究生,那么他一定学过DELPHI语言而且学过C+语言。只要他学过DELPHI语言或者C+语言,那么他就会编程序。因此如果他是计
9、算机系本科生,那么他就会编程序。请用命题逻辑推理方法,证明该推理的有效结论。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 117.1 018.单位元 119.xy xy20.入射 满射21.xR=yR 22.A
10、(x) B(y)23.(M(x)D(x) M(x)D(x)24.可满足式 永假式(或矛盾式)25.陈述句 真值三、计算题26. M= M2= G中长度为2的路总数为18,长度为2的回路总数为6。27.当n是偶数时,xP(A),xn= 当n是奇数时,xP(A),xn=x 于是:当n是偶数,(a-1ba)na-nbnan =(a-1)nbnan= 当n是奇数时, (a-1ba)na-nbnan =a-1ba(a-1)nbnan =a-1baa-1ba=28.(1)偏序关系R的哈斯图为 (2)B的最大元:无,最小元:无; 极大元:2,5,极小元:1,3 下界:4, 下确界4; 上界:无,上确界:无2
11、9.原式(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=130.令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=1531.原式(x1F(x1,y)y1G(x,y1)x2H(x2)