苏XI友离散数学模拟试题1(附参考答案).docVIP

离散数学模拟试题1一、 单项选择题（本大题共8小题，每小题2分，共16分）1.p:a是2的倍数，q:a是4的倍数。命题“除非a是2的倍数，否则a不是4的倍数。”符号化为（ ）；Apq BqpCpq Dpq2.设解释如下:个体域Da,b，F(a,a)= F(b,b)=0,F(a,b)=F(b,a)=1,在解释下,下列公式中真值为1的是（ ）；A. x$yF(x,y) B. $xyF(x,y) C. xyF(x,y) D. $x$yF(x,y)3.设G为n阶m条边的无向简单连通图，下列命题为假的是A.G一定有生成树 B.m一定大于等于nC.G不含平行边和环 D.G的最大度（G）n-14.设G为完全图K5，下面命题中为假的是（ ）A. G为欧拉图 B.G为哈密尔顿图C. G为平面图 D.G为正则图5.对于任意集合X,Y,Z,则A. XY=XZY=Z B. XY=XZY=Z C. XY=XZY=Z D. XY=XZY=Z6.下面等式中唯一的恒等式是A.ABC(AB)=C B. AA=AC. A(BC)=(AB)( AC ) D.A(BC)=(AB)(AC)7.设R为实数集,定义*运算如下:a*b=a+b-ab, 则*运算满足A.结合律 B.交换律C.有幺元 D.冥等律8.在有补格L中, 求补A. 是L中的一元运算 B.一定有唯一的补元C.不一定是L中的一元运算 D.可能没有补元.二、填空题（本大题共8小题，每空3分，共24分）请在每小题的空格中填上正确答案。错填、不填均无分。1.含n个命题变项的重言式的主合取范式为 .2.设个体域为整数集合Z，命题x$y(xy=1)的真值为 .3.任何一棵非平凡树至少有 片树叶.4.已知n阶无向简单图G有m条边, 则G的补图有 条边.5.设R=1,1,1,1, 2,3, 3,2,则domRranR= .6.设A=1,2, B=1,2,3,则从A到B的不同函数有 个.7.如果无向连通图G有n个顶点m条边，并且mn，则G中必含有 .8.设R为实数集合，h是R上的函数，h(x)=2x,则h是从代数系统R，+，0到自身的 .三、简答题（本大题共8小题，每小题5分，共40分）1.设p：224，q：337，r：448，求下列各复合命题的真值：(1) (pq)r(2) (pr)(qr)(3) (pq) (qr)(4) q(pr)(5) (pq)(pqr)2.求公式x ($yF(x,y) $zG(x,z)的前束范式.3.已知无向图G有12条边，1度顶点有2个，2度、3度、5度顶点各1个，其余顶点的度数均为4，求4度顶点的个数.4.已知连通的平面图G的阶数n=6,边数m=8,面数r=4.求G的对偶图G*的阶数n*,边数m*,面数r*.5.设A=a,b,c,c ,a,b,B=a,b,b,计算(1)AB(2)AB(3)P(B)6.设函数f:NN,f(n)=2n+1，这里N是自然数的集合，回答f 是否为单射的、满射的或双射的？并说明理由。7.设代数系统V=Z6, Z6=0,1,5,为模6乘法.(1) 给出运算的运算表.(2) 求出所有可逆元素关于运算的逆元.(3) 说明V构成什么代数系统.8.设Zn为模n加群,f：Z12Z3，f(x)=(x)mod3,则f为同态映射.(1) 说明f是否为单同态和满同态.(2) 令H=x|f(x) =0,计算H.四、证明题（本大题共4小题，每小题5分，共20分）1.在命题逻辑中构造下面推理的证明:前题：ps，qr， s，pq结论：r2证明在具有n个顶点的简单无向图G中，至少有两个顶点的度数相同.3.设A,B,C为集合,证明A(B-C)=(A-C) (B-C).4. 设G为群，令C=a|aGxG(ax=xa).证明：C是G的子群。.离散数学模拟试题参考答案一、单项选择题1.B 2.A 3.B 4.C 5.D 6.D 7.B 8.C二、填空题1.1. 2.0. 3.2. 4.(1/2)n(n-1)-m. 5.2,2. 6.9. 7.回路. 8.自同构.三、简答题1.由题设，p=1，q=0，r=1.(1) (pq)r(10)1010.(2) (pr)(qr)(11)(01)100.(3) (pq)(qr)(10)(01)(11)(01)111.(4) q(pr)0(11)111.(5) (pq)(pqr)(10)(101)1(011)100.2. x($yF(x,y)$zG(x,z)x(yF(x,y)$zG(x,z) x$y$z(F(x,y) G(x,z)x$y$z(F(x,y)G(x,z).3.设4度顶点为x个，则根据握手定理，有212=12+2+3+5+4x，解得，x=3，即无向图G有3个4度顶点.4. n*=r=4，m*=m=8，r*=n=6.5. (1)AB=a,b,c,c,a,ba,b,b=a,b.(2)AB=AB-AB=a,b,c,c,a,b,b-a,b=a,b,c,c,b.(3)P(B)=,a,b,b,a,b,b.6.对n1,n2N，当n1n2时，f(n1)=2n1+1f(n2)=2n2+1，所以f是单射的.ranf=2n+1|nNN，所以f不是满射的，从而不是双射的. 7.(1) 运算的运算表为:012345000000010123452024024303030340420425054321(2)由表可知，e=1为运算的幺元，故e-1=e，即1-1=1. 又55=1，所以，5-1=5，Z6中其余元素皆无逆元.(3)由运算表知，对x,yZ6，有xyZ6，所以，V是代数系统；对x,y,zZ6，有(xy)z=(xy)mod6z=(xy)mod6)z)mod6=(xyz)mod6 =(x(yz)mod6)mod6=x(yz)mod6=x(yz)，所以，运算满足结合律，V是半群；由(1)知，e=1为运算的幺元，所以，V是独异点(幺半群)；又由(1)知，Z6中的元素0,2,3,4无逆元，所以，V不是群.综上，V=是独异点，而且是可交换独异点.8.(1)对3,6Z12，有f(3)=(3)mod3=f(6)=(6)mod3=0，所以f不是单同态的；ranf=0,1,2=Z3，所以，f是满同态的.(2)对0,3,6,9Z12，有f(0)=(0)mod3=0，f(3)=(3)mod3=0，f(6)=(6)mod3=0，f(9)=(9)mod3=0，而对xZ12，当x0,3,6,9时，f(x)=(x)mod30，故H=0,3,6,9.四、证明题1. s 前提引入ps 前提引入p 拒取式 pq 前提引入q 析取三段论qr 前提引入r 假言推理2.反证法. 设G中不存在度数相同的顶点，则由图G为简单图可知，G的顶点的度数列必为：0,1,2,n-1. 删去0度顶点后得到的图G仍然是简单图，且其顶点度数列为：1,2,n-1，与G是简单图矛盾. 故图G中至少有两个顶点的度数相同.3. A(B-C)=A(BC)=ABCC=(AC)(BC)=(