【计算机】南理工《离散数学》A卷(附答案)(3)

1、南京理工大学课程考试试卷 (学生考试用)课程名称：离散数学A学分：4.5 大纲编号试卷编号： 考试方式：闭密 满分分值：100考试时间：120分钟组卷日期：20XX年1月3日 组卷教师(签字)朱保平 审定人(签字) 金忠学生班级：计算机学院10级1 . (6分)试把下列语句翻译为谓词演算公式(1)所有蜜蜂均喜欢所有的花粉；(2)有些人对某些药物过敏；2 (6分)已知公理：(A) (PaQ)t P(B) (PaQ)t Q(C) (Pt (Qt (P 八 Q)及分离规则和代入规则。试用假设推理证明下面公式为定理(P > R) > (Q ) S) (P Q) > (S R)3. (

2、6分)试把函数八函区区区)=f (a, gi(X5,4), x2,g2 (x，X4)(其中a为自然数) 化为(m, n)标准迭置。4. (6分)已知知识的表示如下：(D -x(P(x) > (A(x) B(x)(2) -x(A(x) > Q(x)(3) -x(P(x) ，Q(x)结论：x(P(x) B(x)试用归结原理推理证明之。5. (8 分)已知：A=a, b, B =6, 1,2。试求(D 2A(2) Ax2B6. (8分)已知R为A上的自反2的，对称的二元关系，试证明：(1)对于斡WN , R'具有对称性；(2) t(R)为A上的等价关系。7. （6 分）G=（V,

3、E）是一个简单无向图，n=|V|,m=|E|。证明 m>1/2（n-1）（n-2）,则 G 是连通图。8. （6分）已知A,B,C,D为四个集合，f为A到C的满射，g为B到D的满射，且 Ac B =C cD =G ,构造映射 h: A= Bt Cu D ,且对于 Vx w Au B , 厂”乂）当乂亡人 .h （x） = J r，试证明h为A=B到C= D的潴射。lg（x）当 xwB9. （6分）A为任意一个集合，试证明|A| W2IAI。10. （8分）根据要求作图：（1）画出一个非哈密尔顿图但有哈密尔顿通路的欧拉图，它有奇数个顶点，偶数条边；（2）画出一个不是欧拉图的哈密尔顿图，它有

4、偶数个顶点，奇数条边。11. （8分）G= （V,E）是一个简单平面图，|E|<30,试证明至少有一个顶点的度数小 于或等于4。12. （6分）试证明简单连通图G的任何一条边都可以是某一生成树的枝。13. （8分）已知Z为整数集，为Z上的二元运算，且对于Vm,n w z , m4n=m+n-30, 试证明（Z,4）为群。14. （6分）设（H,）是9,）的子群，aH和bH是H在G上的两个左陪集，证明要么aH cbH =，要么aH=bH015. （6分）设f和g都是群（A,。）到群（B, *）的同态映射，（1）证明f （eA） =eB,其中eA与eB分别为群（A,。）与群（B, *）的幺元

5、；（2）证明（C,。）是（A,。）的一个子群，其中 C=x|xw A且f（x） = g（x）。南京理工大学课程考试试卷答案及评分标准课程名称:离散数学W4.5教学大纲编号:06022104试卷编号：考试方式：闭卷满分分值：100 考试时间:120 分钟1 .解(1)记B (e)表示e为蜜蜂;P (e)表示e为花粉；原句可以翻译为：Vx(B(X)t (Vy(P(y)T L(x, y)-3分(2)记P (e)表示e为人；M (e)表示e为药物；W (e1, e2)表示e1对e2过敏。原句可以翻译为：三x(P(x) a(三y(M (y)八W(x, y)3分2 .证明：(1) Pt Q前提假设(2)

6、(Qt S) a(PaQ)前提假设(3) (Qt S)八(Pa.Q)t (Qt S)公理(A)代入(4) (Qt S)八(P 八 Q)t (P aQ)公理(B)代入(5) Qt S(2) (3)分离(6) P aQ(2) (4)分离(7) (PaQ)t P公理(A)(8) (PaQ)t Q公理(B)(9) P(6)分离(10) Q(6) (8)分离2分(11) S(5) (10)分离(12) St(Rt(SaR)公理(C)代入(13) Rt (SaR)(11) (12)分离(14) R(1) (9)分离2分(15) SaR(13) (14)分离2分3 .解：h(Xi,X2,X4,X5)= f(

7、SaOI- gl(l44,S4Ol4l),l42,g2(l4l/43)(Xl,X2,X4,X5)6分4 .证明：(1) -P(x1) A(x1) B(x1)(2) -A(x2) Q(x2)(3) P(a)(4) 一Q(a)(5) -P(x3) -B(x3)(6)P(a) B(a)a/x1(1)(3)归结-Aa反2(2)(4)归结(8)B(a)(6)归结(9)一 P(a)a反3(5)(8)归结(10)(9)归结6分5.解：(1) 2B =曲 B,1,2, *-4 分(5)A 2B =(a, ),(a, B),(a,1,2), (a, ),(b, ),(b,B),(b,1,2), (b, )4分6

8、.证明：(1)对于i用数学归纳法。显然，当i=1时，R1=R具有对称性。归纳假设当i=k时，Rk具有对称性。考察当i=k+1时，Rk+1是否具有对称性。K 1对于任意的(x,y)WR ,因为RK+ = Rk VR ,所以存在z A ,使得：(x,z) w RK , (z, y) w R由RK及R的对称性，得到：(z,x) w RK , (y,z) w R由复合关系的定义，有(y,x) W R©Rk w rk41因此，RK41具有对称性。4分(2)因为R为A上的自反的，故 Aa £ R2 t(R)即t(R)具有自反性。对于任意的(x, yz t(R)既R ,则存在k,使得(x

9、, y) RK 0由于RK具有对称性，所以(y,x)wRK ,从而(y,x)t(R)即t(R)具有对称性。由传递闭包的定义，知道t(R)具有传递性。综上所述，t(R)具有等价性。4分7证明：采用反证法。如果G不连通，则G可以分为两个不连通的子图，G1 =(V1, E1),G2 =(V2, E2)于是有：m =| E1| | E2|-1/2 |V1|(|V1| -1) 1/2|V2|(|V2| -1)_1/2(|V1 | -1)(|V2 | -2) =1/2(n -1)(n -2)6分8.证明：对于任意 yWCuD,因为CuD=4,则有y w C或y w D。如果y w C ,则由f的满射性，存

10、在y w A ,使得f (x) = y , 即存在x w A= B ,使得h(x) = y。如果y w D ,则由g的满射性，存在x w B，使得g(x) = y , 即存在x w A = B ,使得h(x) = y。综上所述，h为满射。6分9证明：对于一个任意元素 x W A，定义f(x) =x 2Af是一一个A到2A的映射。显然，当x1 #x2时，3 #x2,即fx1 = fx2A 一所以f是单射。从而由势的定义知道 |A|E|2 |。6分10.解:(1)11证明:用反证法。设平面图简单图有n个顶点,(2)假设所有顶点次数5,则有5nW2m。又因为对简单平面图都成立mw 3n-6,故m+6

11、 & 3n,从而，有 5(m+6)w15nW3(2m),即 30 这与题意中m<30矛盾。12证明:简单连通图 G有n个顶点，m条边，并设e为简单连通图G的任一条边。构造图G的只有边e的生成子图To逐个考察图G的其他任意一条边，如果将该边加入T中不形成回路,则将该边加入T中，直到T中有n-1条边为止。此时，T就是包含了枝e的一个生成树。13证明:(1)显然，运算在 Z上是封闭的。(2)显然，运算“”满足结合律。(3) e=30是幺元。 对vm Z Z，有:m e = e m = m 30 -30 = m(4)对于 Vm z ,m有逆元，m1=60-m。综上所述，(Z, )是一个群。14证明：设aH cbH于,Vh w aH c bH ,根据陪集的定义知三hih w H , 使 h = ah = bh21故 a = bh2 hi3分 Vx w aH, ：3h3 w H ,使得x = ah3 = bh2% %1丁 H 为群，/. h4 =h2% h3 w H ,即x =bh4 w bH ,从而 bH 工 aHVx w bH时同理可证bH3aH所以，bH =aH ,即命题得证。3分15.证明：(1)因为 eA eB =eA ,故 f (eA a) = f (eA)。又因为f(eA陶)=3 *3)所以彳4到 f (eA) = f (eA) f (eA)因