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

离散数学试卷（十七）参考答案 一、 填空20%（每小题2分） 1 题目 2 3 4 1)(2)(3)(4)(5) 答案NN 二、8% (x(P(x)→Q(x,y》→(3yPy)A(Ez)Qy,z》 台(xP(x)vQ(x,y》v(y)Py)A(EzQ,》 台(3xP(x)AQ(xy)v(3y)Py)A(3)Qy,:》2分 一(3xP(x)A一Qxy》v(日u)P(w)A(E)Qy,=》4分 台(3x3u)(3(P(x)AQ(x,y》V(P()AQy,》6分 前束析取范式 台（日x)3u3z(P(x)vP(u)A(P(x)vQy,z)》 (Q(x.y)vP(u))(Q(x.y)vQ(y.=))) 前束合取范式 共8分 三、8% 「01001 1010 0001 1分 L0000 关索图日 b c d 2分 传递闭包t(®=UR=UR 4分 「01001「0100]「1010] 10101010 0101 Me =MgoMg 0001°0001 0000 00000000 0000 12

离散数学试卷(十七)参考答案 112 一、 填空 20%（每小题 2 分） 题目 1 2 3 4 5 6 （1） （2） （3） （4） （5） 答案 N N N Y Y Y N N Y N 二、8% (x)(P(x) → Q(x, y)) → ((y)P( y)  (z)Q( y,z))   (x)(P(x)  Q(x, y))  ((y)P( y)  (z)Q( y,z))  (x)(P(x)  Q(x, y))  ((y)P( y)  (z)Q( y,z)) 2 分  (x)(P(x)  Q(x, y))  ((u)P(u)  (z)Q( y,z)) 4 分  (x)(u)(z)((P(x)  Q(x, y))  (P(u)  Q( y,z))) 6 分 前束析取范式 ( ( , ) ( )) ( ( , ) ( , ))) ( )( )( )(( ( ) ( )) ( ( ) ( , )) Q x y P u Q x y Q y z x u z P x P u P x Q y z              前束合取范式 共 8 分 三、8% MR =             0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 0 1 分 关系图 2 分 传递闭包 t(R) =  i=1 U R i == i i U R 4 =1 4 分  M R M R M R 2 =  =             0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 0              0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 0 =             0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 0

离散数学试卷（十七）参考答案 [1010]「01001「0101 0101 M= = 000000000000 「0101]「0100]「1010 1010 M=M oMg 00010000 00000000 0000 [11111 1111 Mg+Me Me+Mg 0001 6分 0000 t (R)=K,,,,,,,,) 四、9% 五、10% 因为G=不连通，设其连通分支是G),.,G(W)(m之2)， 由于任两个连通分支G(,)和G(V)(≠)之间不连通，故两结点子集%，与V,之间所 有连线都在G的补图G中。 4,v∈V,则有两种情况 (1)u,V,分别属于两个不同结点子集V和V,由于G(),GV)是两连通分支，故(u,) 在不G中，故边(u,v)在G中连通。 (2)u,y,属于同一个结点子集V,可在另一结点子集V中任取一点w,故边(u,w)和 边(w,v)均在G中，故邻接边(u,w)(w,v)组成的路连接结点u和v,即u,v在G 113

离散数学试卷(十七)参考答案 113 M R M R M R 3 = 2  =             0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 0              0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 0 =             0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 M R M R M R 4 = 3  =             0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1              0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 0 =             0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 0 2 3 4 M R M R M R M R + + + =             0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 6 分 t(R)={,,,,,,,,} 共 8 分 四、9% 五、10% 因为 G=不连通，设其连通分支是 ( ), , ( ) ( 2) G V1  G Vm m  ， 由于任两个连通分支 ( ) G Vi 和 G(V ) (i j) j  之间不连通，故两结点子集 Vi 与Vj 之间所 有连线都在 G 的补图 G 中。 u,v V ，则有两种情况： （1）u , v，分别属于两个不同结点子集 Vi 和 Vj，由于 G(Vi) , G(Vj)是两连通分支，故(u , v) 在不 G 中，故边（u , v） 在 G 中连通。 （2）u ,v ，属于同一个结点子集 Vi，可在另一结点子集 Vj 中任取一点 w，故边(u , w)和 边 (w , v )均在 G 中，故邻接边( u ,w ) ( w , v ) 组成的路连接结点 u 和 v，即 u , v 在 G

离散数学试卷（十七）参考答案 中也是连通 大、10% 设是循环群，G-(a,设是的子群。且S≠{e,S≠G,则存在最小正整数 m,使得：a"∈S,对任意aeS,必有I=m+r,0≤r0 故：a=d-m=d*am=d*(a)∈S即：ad=a*(ayeS 所以a'eS,任m使a"∈S的最小正整数，且0≤r是以a"为生成元的循环群。 七、用CP规则证明12% 1、(6分) ①A P(附加前提) ②AVB T①I ③AVB→CAD ④CAD T②③1 GD T④I ⑥DVE T51 ⑦DVE→F P ⑧F T⑥⑦1 ⑨A→F CP 2、因为xPx)v3xOx)=-(x)P(x)→3xOx) 本题亦即：x(P(x)VQ(x》→-(x)P(x)→3xQ(x) ①-x)P(x) P(附加前提〉 ②(3x)-P(x) T①E ③-Pe) ES② ④Va(Px)vQ(x) ⑤P(e)vQ(e) US④ 114

离散数学试卷(十七)参考答案 114 中也是连通。 六、10% 设是循环群,G=(a)，设是的子群。且 S  {e},S  G ，则存在最小正整数 m，使得： a S m  ，对任意 a S l  ，必有 l = tm + r, 0  r  m, t  0 ， 故： a a a a a a S r l tm l tm l m t = = =  − − − * *( ) 即： a a a S l r m t = *( )  所以 a S r  ，任 m 使 a S m  的最小正整数，且 0  r  m ，所以 r=0 即： l m t a = (a ) 这说明 S 中任意元素是 m a 的乘幂。 所以是以 m a 为生成元的循环群。 七、用 CP 规则证明 12% 1、(6 分) ① A P（附加前提） ② A  B T①I ③ A B →C  D P ④ C  D T②③I ⑤ D T④I ⑥ D  E T⑤I ⑦ D E → F P ⑧ F T⑥⑦I ⑨ A → F CP 2、因为 x P(x)  x Q(x)  (x)P(x) → x Q(x) 本题亦即： x(P(x)  Q(x))  (x)P(x) → x Q(x) ① (x)P(x) P（附加前提） ② (x)P(x) T①E ③ P(e) ES② ④ x(P(x)  Q(x)) P ⑤ P(e)  Q(e) US④

离散数学试卷（十七）参考答案 ⑥0e) T361 ⑦(3x)2(x) EGO ⑧-(x)P(x)→3xQx) 八、10% (3(M(y)W(y)) P (2)M(e)A-W(e) ES(I) 3)-(Me)→W(e) 2呢 (4)3y-(My)→Wy) EG(3) ⑤)-(yMy)→Wy) T4E (6)(xF(x)AS(x)→(yMy)→W(y》P ()3x(F(x)AS(x》 T561 (8(Vx)(F(x)S(x)) TOE (9)-(F(a)AS(a) US(8) -F(a)v-S(a) T9)E aDF(a)→S(a TOOE D(xXF(x)→S(x) UGAD 九、13% (1)自反性：(x,y)∈X,由于x+y=x+y,故∈R (2)对称性：(x,),(x2,乃2)∈X,当∈R时 即x+2=2+亦x2+片=+2有∈R (3)传递性：(x(2,2（）∈X, 当∈ReR时 115

离散数学试卷(十七)参考答案 115 ⑥ Q(e) T③⑤I ⑦ (x)Q(x) EG⑥ ⑧ (x)P(x) → xQ(x) CP 八、10% ⑴ y(M ( y)  W ( y)) P ⑵ M (e)  W (e) ES⑴ ⑶ (M (e) →W (e)) T⑵E ⑷ y(M ( y) →W ( y)) EG⑶ ⑸ (y)(M ( y) →W ( y)) T⑷E ⑹ (x)(F(x)  S(x)) → (y)(M ( y) →W ( y)) P ⑺ x(F(x)  S(x)) T⑸⑹I ⑻ (x)(F(x)  S(x)) T⑺E ⑼ (F(a)  S(a)) US⑻ ⑽ F(a)  S(a) T⑼E ⑾ F(a) → S(a) T⑽E ⑿ (x)(F(x) → S(x)) UG⑾ 九、13% （1）自反性： (x, y) X,由于x + y = x + y,故 (x, y),(x, y) R (2) 对称性： (x1 , y1 ),(x2 , y2 ) X,当 (x1 , y1 ),(x2 , y2 ) R时 即x1 + y2 = x2 + y1 亦 x2 + y1 = x1 + y2有 (x2 , y2 ),(x1 , y1 ) R （3）传递性： ( , ), ( , ), ( , ) ,  x1 y1 x2 y2 x3 y3  X 当 (x1 , y1 ),(x2 , y2 )  R,  (x2 , y2 ),(x3 , y3 )  R时

离散数学试卷（十七）参考答案 即+为=+4相加化简得x+y,=x+y故∈R x2+3=x3+y2 由等价关系的定义知R是X上的等价关系。 2、XWR={[]R} 116

离散数学试卷(十七)参考答案 116 x y x y x y x y R x y x y x y x y + = +      + = + + = + ( , ),( , ) 1 3 3 1 1 1 3 3 2 3 3 2 即 1 2 2 1相加化简得 故 由等价关系的定义知 R 是 X 上的等价关系。 2、X/R={[]R}