(完整word版)离散数学试卷及答案(17)

1、离散数学试卷（十七）110判断正误20%（每小题2分）1、设 A.B.C是任意三个:集合。(1) 若 A B 且 BC,则ACo()(2) 若 A B 且 BC,则ACo()(3) 若 A B 且 BC,则ACo()(4) A(B C)(AB)(A C)。()(5)(A-B) C=(AC)-(BC)。()2、 可能有某种关系，既不是自反的，也不是反自反的。（）3、 若两图结点数相同，边数相等，度数相同的结点数目相等，则两图是同构的。（）4、 一个图是平面图，当且仅当它包含与 K3,3或 K5在 2 度结点内同构的子图。（）5、 代数系统中一个元素的左逆元并一定等于该元素的右逆元。（）6、 群是

2、每个元素都有逆元的半群。（）二、8%将谓词公式（x）（P（x） Q（x,y）（ y）P（y） （ z）Q（y,z）化为前束析取范式与前束合取范式。8%设集合 A= a,b,c,d上的关系 R= ,写出它的关系矩阵和关系图，并 用矩阵运算方法求出 R 的传递闭包。四、9%1、 画一个有一条欧拉回路和一条汉密尔顿回路的图。2、 画一个有一条欧拉回路，但没有一条汉密尔顿回路的图。离散数学试卷（十七）1113、 画一个有一条欧拉回路，但有一条汉密尔顿回路的图。五、10%证明：若图 G是不连通的，则 G的补图G是连通的。六、10%证明：循环群的任何子群必定也是循环群。七、12%用 CP 规则证明：1.A

3、 B CD,DE F AF。2.( x)(P(x) Q(x)( x)P(x) ( x)Q(x)。八、10%用推理规则证明下式：前提：(x)(F(x)S(x)( y)(M(y) W( y),( y)(M(y) W( y)结论：(x)(F(x)S(x)九、13%若集合 X= (1,2) , (3,4) , (5,6),R 捲1, X2,y2|洛y?x?y1、证明 R 是 X 上的等价关系。2、求出 X 关于 R 的商集。离散数学试卷（十七）112填空20%（每小题2分）题目123456离散数学试卷（十七）113(1)（2）（3）（4）（5）答案NNNYYYNNYN(x)(P(x)Q(x,y)( y

4、)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 分前束析取范式前束合取范式共 8 分、8%01001010MR=1分00010000abed关系图2 分传递闭包 t （R） =4UR=U Rii 1i 14分0 10 00 1 0010 101 01 01 0 100 10 1MR2MRMR=R0 00100010

5、0000 00000000000101001000101010110101010MR3MR2MR=R R R0000000100000000000000008%(x)( u)( z)(P(x)P(u)(P(x)Q(y,z)(Q(x, y)P(u)( Q(x, y) Q(y,z)离散数学试卷(十七)1141111MRMR2MR31111MR=0 0 0 1t(R)=,共 8 分四、9%因为 G=不连通，设其连通分支是G(V1),G(Vm) (m 2),由于任两个连通分支G(Vi)和G(Vj) (i j)之间不连通，故两结点子集V与Vj之间所有连线都在 G 的补图G中。u,v V，则有两种情况:(

6、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%R4MR3MR=0 10 10 10 010 1010 10 0 1 0五、10%离散数学试卷(十七)115P (附加前提)TEESPUSTI(x)Q(x)设G,*是循环群，G=(a)，设S,*是G

7、,*的子群。且S e, S G，则存在最小正整数m,使得：amS，对任意alS，必有丨tm r, 0 r m, t 0,故:aral tmal* atmal* (am)tS即:1rm、ta a * (a ) Srm所以a S，任 m 使aS的最小正整数，且0r m，所以 r=0 即：a1(am)t这说明 S 中任意元素是am的乘幕。所以G,*是以am为生成元的循环群。1、(6 分)AP (附力ABT1AB CDPCDTIDT1DET1DE FPFTIAFCP2、因为xP(x)xQ(x)(七、用 CP 规则证明12%x)P(x) xQ(x)本题亦即：x(P(x) Q(x)(x)P(x) xQ(x

8、)1(x)P(x)2(x) P(x)3P(e)4x(P(x) Q(x)5P(e) Q(e)6Q(e)EG离散数学试卷(十七)ii5(x)P(x)xQ(x)CP、io%y(M(y)W(y)PM (e)W(e)ES(M(e)W(e)TEy (M(y)W(y)EG(y)(M(y)W(y)TE(x)(F(x)S(x)(y)(M(y)W(y)Px(F(x) S(x)TI(x) (F(x)S(x)TE(F(a)S(a)USF (a)S(a)TE(11)F(a)S(a)TE(12)( x)(F(x)S(x)UG1九、13%八(1 )自反性:(x, y) X,由于xx y,故(x, y), (x, y)(2)对称性:(X1, yi), (x2, y2) X ,当(xi,yi), (X2, y2)R时即xiy2X2yi亦X2yixiy有(X2, y2), (xi, yi)离散数学试卷(十七)ii5(Xi,yi), (X2,