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,