【計算機】南理工《離散數(shù)學》A卷(附答案)(3)

1、南京理工大學課程考試試卷 (學生考試用)課程名稱：離散數(shù)學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)及分離規(guī)則和代入規(guī)則。試用假設(shè)推理證明下面公式為定理(P > R) > (Q ) S) (P Q) > (S R)3. (

2、6分)試把函數(shù)八函區(qū)區(qū)區(qū))=f (a, gi(X5,4), x2,g2 (x，X4)(其中a為自然數(shù)) 化為(m, n)標準迭置。4. (6分)已知知識的表示如下：(D -x(P(x) > (A(x) B(x)(2) -x(A(x) > Q(x)(3) -x(P(x) ，Q(x)結(jié)論：x(P(x) B(x)試用歸結(jié)原理推理證明之。5. (8 分)已知：A=a, b, B =6, 1,2。試求(D 2A(2) Ax2B6. (8分)已知R為A上的自反2的，對稱的二元關(guān)系，試證明：(1)對于斡WN , R'具有對稱性；(2) t(R)為A上的等價關(guān)系。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 ,構(gòu)造映射 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分）根據(jù)要求作圖：（1）畫出一個非哈密爾頓圖但有哈密爾頓通路的歐拉圖，它有奇數(shù)個頂點，偶數(shù)條邊；（2）畫出一個不是歐拉圖的哈密爾頓圖，它有

4、偶數(shù)個頂點，奇數(shù)條邊。11. （8分）G= （V,E）是一個簡單平面圖，|E|<30,試證明至少有一個頂點的度數(shù)小 于或等于4。12. （6分）試證明簡單連通圖G的任何一條邊都可以是某一生成樹的枝。13. （8分）已知Z為整數(shù)集，為Z上的二元運算，且對于Vm,n w z , m4n=m+n-30, 試證明（Z,4）為群。14. （6分）設(shè)（H,）是9,）的子群，aH和bH是H在G上的兩個左陪集，證明要么aH cbH =，要么aH=bH015. （6分）設(shè)f和g都是群（A,。）到群（B, *）的同態(tài)映射，（1）證明f （eA） =eB,其中eA與eB分別為群（A,。）與群（B, *）的幺元

5、；（2）證明（C,。）是（A,。）的一個子群，其中 C=x|xw A且f（x） = g（x）。南京理工大學課程考試試卷答案及評分標準課程名稱:離散數(shù)學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前提假設(shè)(2)

6、(Qt S) a(PaQ)前提假設(shè)(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)歸結(jié)-Aa反2(2)(4)歸結(jié)(8)B(a)(6)歸結(jié)(9)一 P(a)a反3(5)(8)歸結(jié)(10)(9)歸結(jié)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用數(shù)學歸納法。顯然，當i=1時，R1=R具有對稱性。歸納假設(shè)當i=k時，Rk具有對稱性?？疾飚攊=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由復(fù)合關(guān)系的定義，有(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證明:用反證法。設(shè)平面圖簡單圖有n個頂點,(2)假設(shè)所有頂點次數(shù)5,則有5nW2m。又因為對簡單平面圖都成立mw 3n-6,故m+6

11、 & 3n,從而，有 5(m+6)w15nW3(2m),即 30 這與題意中m<30矛盾。12證明:簡單連通圖 G有n個頂點，m條邊，并設(shè)e為簡單連通圖G的任一條邊。構(gòu)造圖G的只有邊e的生成子圖To逐個考察圖G的其他任意一條邊，如果將該邊加入T中不形成回路,則將該邊加入T中，直到T中有n-1條邊為止。此時，T就是包含了枝e的一個生成樹。13證明:(1)顯然，運算在 Z上是封閉的。(2)顯然，運算“”滿足結(jié)合律。(3) e=30是幺元。 對vm Z Z，有:m e = e m = m 30 -30 = m(4)對于 Vm z ,m有逆元，m1=60-m。綜上所述，(Z, )是一個群。14證明：設(shè)aH cbH于,Vh w aH c bH ,根據(jù)陪集的定義知三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)因