《离散数学》课程教学资源（试卷习题）试卷（答案）22

离散数学试题(22)参考答案 一、单项选择题： 题号123456789 答案CD D 题号10112131415 二、填空题： 1.{6,12:{2,4,8,101.2.2;n。3.以主对角线为对称的元素不能同时为1： 两个不同结点间的定向弧线，不可能成对出现。4.满射：入射。 5.1: *e a b ee a b b a 6.3:1:1。 7.()A(PR):. 三、判断改正题 1.×若AUB=AUC,则不一定B=C。2.√。 3.XB的极大元b∈B但可以不唯一。4.√。 5.X运算*不一定可结合。 6.×有限整环一定是域，但反之不成立。 7.×有制点的连通图不可能是汉密尔顿图。8.√。 9.×无多重边和自环的图是简单图。 10.√。 四、简答题： 1.解：若R,R是自反的，则R。R也是自反的。因为 a∈A,R,R自反，.<a,a>eR,<a,a>eR2,从而<a,a>eRoR, 即R。R也是自反的。 若R,R是对称的，但R。R不一定是对称的。 如：A={a,b,c,R={ka,b>,<b,a>},R={kb,c>,<c,b>},则R,R是对

离散数学试题（22）参考答案 146 一、单项选择题： 题号 1 2 3 4 5 6 7 8 9 答案 C D D B A D B D D 题号 10 11 12 13 14 15 答案 A D C A D B 二、填空题： 1．{6，12}；{2，4，8，10}。 2． 2 2 n ； n n 。 3．以主对角线为对称的元素不能同时为 1； 两个不同结点间的定向弧线，不可能成对出现。4．满射；入射。 5．1； 6．3；1；1。 7． (P  Q  R)  (P  Q  R) ； M000  M001 。 三、判断改正题： 1．× 若 AB = AC ，则不一定 B = C 。 2．√ 。 3．× B 的极大元 bB 但可以不唯一。 4．√ 。 5．× 运算*不一定可结合 。 6．× 有限整环一定是域，但反之不成立。 7．× 有割点的连通图不可能是汉密尔顿图。 8．√ 。 9．× 无多重边和自环的图是简单图。 10．√ 。 四、简答题： 1．解：若 1 2 R , R 是自反的，则 R1 R2  也是自反的。因为 1 2 a A ,R , R 自反， 1 2   a,a R ,  a,a R ，从而 1 2  a,a R  R ， 即 R1 R2  也是自反的。 若 1 2 R , R 是对称的，但 R1 R2  不一定是对称的。 如：A = {a , b , c}， { , , , } R1 =  a b   b a  ， { , , , } R2 =  b c   c b  ，则 1 2 R , R 是对 * e a b e e a b a a b e b b e a

离散数学试题(22)参考答案 称的，但R。R=《Ka,c>}不是对称的。 2.要设计一个方案使各城市间能够通讯且总造价最小，即要求该图连通、无回路、边权之 和最小的子图即最小生成树，由避圈法或破圈法可得： 其最小生成树为： 5 of 其树权即最小造价为：1+2+3+5+7=18。 3.解：(1)1)a,b∈S易证a*b=a+b+ab∈S,即运算*是封闭的。 2)Va,b,ceS .(a*b)*c=(a+b+ab)*c=a+b+ab+c+(a+b+ab)c a+b+c+ab+ac+bc+abc. 而 a*(b*c)=a*(b+c+bc)=a+(b+c+bc)+a(b+c+bc) =a+b+c+bc+ab+ac+abc, ∴.(a*b)*c=a*(b*c),即*可结合。 3)设S关于*有么元e,则Va∈S,e*a=a*e=a。 而a*e=e*a=a+e+ea=a,∴.e=0。 4)a∈S设有逆元a1。则a幸a1=a1*a=e, 即a+a+a=0,小。石即S中任意元部有逆元，综上得 出，<S.*>构成群。 (2)由2*x*3=2+x+3+2x+3x+6+6x=12x+11=7, 4.解：原式一(PvQ)AR)V(PAR)-(-PAQ)VRv(PAR) 台(-(PAQ)ARA(PAR) 五、证明题： 147

离散数学试题（22）参考答案 147 称的，但 { , } R1  R2 =  a c  不是对称的。 2．要设计一个方案使各城市间能够通讯且总造价最小，即要求该图连通、无回路、边权之 和最小的子图即最小生成树，由避圈法或破圈法可得： 其最小生成树为： 其树权即最小造价为：1+2+3+5+7=18。 3．解：（1）1） a,bS 易证 a b = a +b + abS ，即运算*是封闭的。 2） a,b,c  S , ( ) ( ) ( ) a b c ab ac bc abc a b c a b ab c a b ab c a b ab c = + + + + + +    = + +  = + + + + + + 而 , ( ) ( ) ( ) ( ) a b c bc ab ac abc a b c a b c bc a b c bc a b c bc = + + + + + +   =  + + = + + + + + +  (a b)  c = a  (b  c) ，即*可结合。 3）设 S 关于*有幺元 e，则 a  S , e  a = a  e = a 。 而 a  e = e  a = a + e + ea = a ,  e = 0 。 4） aS 设有逆元 −1 a 。则 a  a = a  a = e −1 −1 ， 即 0 1 1 + + = − − a a aa ， a a a + − =  − 1 1 ，即 S 中任意元都有逆元，综上得 出，  S,   构成群。 （2）由 2 x3 = 2+ x +3+ 2x +3x + 6+ 6x =12x +11= 7， 3 1  x = − 。 4．解：原式  ((P  Q)  R)  (P  R)  (P  Q)  R  (P  R)  ((P  Q)  R  (P  R)) 。 五、证明题：

离散数学试题(22)参考答案 1.证明：1)<a,b>∈A×A,a+b=b+a,<a,b>,<a,b>eR,即R自反。 2)<a,b>,<c,d>eR,则la+d=b+c,∴.d+a=c+b, 即c+b=d+a,从而<c,d>,<a,b>∈R,即R对称。 3) V<<a,b>,<c,d>>ER,<<c,d>.<e,f>>ER 则a+d=b+c,c+f=d+e∴.f=d+e-c 从而a+f=a+d+e-c=b+c+e-c=b+e, .<a,b>,<e,f>eR,即R传递 综上得出，R是等价关系， [K2,5>]R={ka,b><a,b>eA×A,a+5=b+2 =(<a,b><a,b>EAxA,a=b-3) ={kl,4>,<2,5>,<3,6>,<4,7>,<5,8>,<6,9>} 2.证明：(1)B P(附加前提)》 (2)B→(AAS) p (3)A-S T1)(2l (④)A T()I (⑤)A→BAC P (6)BAC T4)(5L ()C T61 (8)(E→F)→C (9)(E→F) T781 (10)EAF T(9)E ()E T(IO)I (12)B→E CP 3.解：设Qx):x是有理数，Rx):x是实数，Zx):x是整数。 命题形式化：x(Q(x)→R(x),3r(Q(x)AZ(x)卜3x(Rx)AZ(x》。 证明：(1)3x(Q(x)AZ(x》 148

离散数学试题（22）参考答案 148 1．证明：1）   a,b  A A ,a + b = b + a , a,b , a,b  R , 即 R 自反。 2）   a,b , c,d R , 则a + d = b + c ,d + a = c +b , 即 c + b = d + a , 从而 c,d , a,b R ，即 R 对称。 3） a d b c c f d e f d e c a b c d R c d e f R + = + + = + = + −          ,  , , , , , , , , 则 从而 a + f = a + d + e − c = b + c + e − c = b + e ，   a,b , e, f  R, 即 R 传递。 综上得出，R 是等价关系。 且 { 1,4 , 2,5 , 3,6 , 4,7 , 5,8 , 6,9 } { , , , 3} [ 2,5 ] { , , , 5 2} =             =      = −   =      + = + a b a b A A a b R a b a b A A a b 2．证明：（1） B P(附加前提) （2） B → (A  S) P (3) AS T(1)(2)I (4) A T(3)I (5) A→ BC P (6) B C T(4)(5)I (7) C T(6)I (8) (E → F) → C P (9) (E → F) T(7)(8)I (10) E  F T(9)E (11) E T(10)I (12) B → E CP 3．解：设 Q(x)：x 是有理数，R(x)：x 是实数，Z(x)：x 是整数。 命题形式化： x(Q(x) → R(x)), x(Q(x)  Z(x)) ├ x(R(x)  Z(x)) 。 证明：（1） x(Q(x)  Z(x)) P

离散数学试题(22)参考答案 (2)2(a)Z(a) ES(1) (3)(a) T21 (4)x(Q(x)→R(x) (5)Q(a)→R(a) US(④) (6)R(a) T351 (7)Z(a) TO) (8)R(a)Z(a) T(6(7) (9)3x(R(x)AZ(x) EG(8) .结论有效。 4.证明：设完全二叉树T有i个分枝点，t片树叶。则n=t,对于完全二叉树有 ,a=d空 149

离散数学试题（22）参考答案 149 (2) Q(a)  Z(a) ES(1) (3) Q(a) T(2)I (4) x(Q(x) → R(x)) P (5) Q(a) → R(a) US(4) (6) R(a) T(3)(5)I (7) Z(a) T(2)I (8) R(a)  Z(a) T(6)(7)I (9) x(R(x)  Z(x)) EG(8)  结论有效。 4．证明：设完全二叉树 T 有 i 个分枝点，t 片树叶。则 n = i+t ，对于完全二叉树有 i = t –1 ,  n = t-1+t ,  2 +1 = n t