1、離散數(shù)學(xué)考試試題(A 卷及答案)一、(10分)求(P Q) (PA (QV R)的主析取范式解：(P Q) (PA (Q V R)( ( PVQ)V (PA QA R)(PVQ)V(PA QAR)(PVQVP) A(PVQV Q)A(PVQVR)(PVQ)A(PVQVR)(PVQV(RA R)A (PVQVR)(PVQVR) A(PVQV R)A (PV QV R)Mo A Mim2 V m3 V m4 V m5Vm6 V m7二、 ( 10 分)在某次研討會的休息時間，3 名與會者根據(jù)王教授的口音分別作出下述判斷：甲說：王教授不是蘇州人，是上海人。乙說：王教授不是上海人，是蘇州人。丙說：王教

2、授既不是上海人，也不是杭州人。王教授聽后說：你們3 人中有一個全說對了，有一人全說錯了，還有一個人對錯各一半。試判斷王教授是哪里人？解 設(shè)設(shè)P:王教授是蘇州人；Q:王教授是上海人；R:王教授是杭州人。則根據(jù)題意應(yīng)有：甲：PA Q乙：QA P丙：QA R王教授只可能是其中一個城市的人或者3 個城市都不是。所以，丙至少說對了一半。因此，可得甲或乙必有一人全錯了。又因為，若甲全錯了，則有 QAP,因此，乙全對。同理，乙全錯則甲全對。所 以丙必是一對一錯。故王教授的話符號化為：(PAQ)A(QA R) V ( QAR) V ( QA P) A ( QAR)(PA QA Q A R) V ( PAQA

3、QA R) V ( Q A PA QAR)(PA QA R) V (PA QAR) PAQA RT因此，王教授是上海人。三、(10分)證明tsr(R)是包含R的且具有自反性、對稱性和傳遞性的最小關(guān)系。證明 設(shè) R 是非空集合A 上的二元關(guān)系，則 tsr( R) 是包含 R 的且具有自反性、對稱性和傳遞性的關(guān)系。 一 一 一 一 _若R是包含 R的且具有自反性、對稱性和傳遞性的任意關(guān)系，則由閉包的定義知r(R) R。則sr( R) s( R ) = R ,進而有 tsr( R) t( R ) = R。綜上可知，tsr(R)是包含R的且具有自反性、對稱性和傳遞性的最小關(guān)系。四、(15分)集合 A=

4、a, b, c, d, e上的二元關(guān)系 R為R=, , , , ， ， ， ， ， ， ， ， ， ，(1) 寫出R 的關(guān)系矩陣。(2) 判斷R 是不是偏序關(guān)系，為什么？解 (1) R 的關(guān)系矩陣為：111110M (R)0001101010100110001(2)由關(guān)系矩陣可知，對角線上所有元素全為1,故R是自反的；rij + rji wi,故R是反對稱的；可計算對應(yīng)的關(guān)系矩陣為：11111 01 101M (R)2M (R2)0 0 1 0 100011 00001R 是傳遞的。五、 ( 10 分)設(shè)A、 B、 C 和 D 為任意集合，證明(AB)XC=(AX C) (BX C)。證明：因

5、為C(AB)XC xC(AB)AyCC(XCAAX B)AyCC(xCAAyCCAx B)V(xAA yCA y C)(x e aa y e C) a( x bv y C)(x e aa y e C) a ( x e ba y e C)C(AXC)A (BXC)C (AXC)-(BXC)所以，(AB) XC=(AXCBXC)。六、(10 分)設(shè) f: A B, g: B C, h: C A,證明：如果 h g f= Ia, f h g=lB, g f h=lC,則 f、g、 h 均為雙射，并求出f 1、 g 1和 h 1。解 因Ia恒等函數(shù)，由h g f=lA可得f是單射，h是滿射；因Ib恒等

6、函數(shù)，由f h g= Ib可彳導(dǎo)g是 單射，f是滿射；因Ic恒等函數(shù)，由g f h=lC可得h是單射，g是滿射。從而f、g、h均為雙射。由 h g f= IA,得 f =h g;由 f h g = IB,得 g =f h;由 g f h=Ic,得 h =g f。七、(15分)設(shè)是一代數(shù)系統(tǒng)，運算*滿足交換律和結(jié)合律，且 a*x=a*y x=y,證明：若G有限，則G 是一群。證明 因G有限，不妨設(shè) G = a1,a2，an。由a*x= a*y x=y得，若xwy,則a*xw a*y。于是可證，對任意的 aCG,有aG=Go又因為運算*滿足交換律，所以 aG=G=Ga。令eCG使得a*e =a。對

7、任意的 bC G,令c*a=b,則b*e= (c*a)*e= c*(a*e)= c*a=b,再由運算*滿足交換律得 e*b=b, 所以e是關(guān)于運算*的幺元。對任意 aCG,由aG=G可知，存在bCG使得a*b = e,再由運算*滿足交 換律得b*a=e,所以b是a的逆元。由a的任意性知，G中每個元素都存在逆元。故 G是一群。八、 ( 20 分) ( 1)證明在n 個結(jié)點的連通圖G 中，至少有n 1 條邊。證明 不妨設(shè) G 是無向連通圖(若G 為有向圖，可略去邊的方向討論對應(yīng)的無向圖)。設(shè)G中結(jié)點為Vi、V2、Vn。由連通性，必存在與Vl相鄰的結(jié)點，不妨設(shè)它為V2(否則可重新編號)，連接V和V2

8、 ,得邊備，還是由連通性，在V3、V4、Vn中必存在與Vi或V2相鄰的結(jié)點，不妨設(shè)為V3 ,將其連接得邊 e ,續(xù)行此法，Vn必與Vi、V2、Vn 1中的某個結(jié)點相鄰，得新邊 01 ,由此可 見 G 中至少有n i 條邊。(2)給定簡單無向圖 G=,且| V| =m, | E| =n。試證：若nR cm i + 2,則G是哈密爾頓圖。證明 若 nA cm, 1 + 2,則 2nA m2 3m+ 6(1)。若存在兩個不相鄰結(jié)點 u、v使彳導(dǎo)d(u)+d(V)vm,則有2n= d(w)vm+ ( m2)( m3) + m = m? wV3m+6,與(1)矛盾。所以，對于 G中任意兩個不相鄰結(jié)點 u

9、、v都有d( u) +d( v) mo由定理10.26可知， G 是哈密爾頓圖。離散數(shù)考試試題(B 卷及答案)（10分）使用將命題公式化為主范式的方法，證明（P Q） （PAQ） （Q P）A（PVQ）。證明：因為(P Q) (PA Q) ( PVQ) V(PAQ)(PA Q) V(PAQ)(Q P)A(PVQ) ( Q VP) A (PVQ)(PA Q) V ( QAQ) V(PAP) V (PAQ)(PA Q) V P(PA Q) V (PA (QV Q)(PA Q) V (PA Q) V (PA Q)(PA Q)V(PAQ)所以，(P Q) (PAQ) (Q P) A (PVQ)o （1

10、0分）證明下述推理： 如果A努力工作，那么 B或C感到愉快；如果 B愉快，那么A不努力工作；如果 D愉快那么C不愉快。所以，如果 A努力工作，則 D不愉快。解 設(shè)A: A努力工作；B、C、D分別表示B、C、D愉快；則推理化形式為:A BVC, B A, D CA DA(2) A BV CP(3) BV CT(1)(2)(4) BAP(5) AB(6) BT(1)(5)(7) CT(3)(6)(8) D CP(9) DT(7)(8)(10) A DCP三、(10分)證明 x y(P(x)x y(P(x) Q(y) x y(附加前提,IT(4) , E,I,I,IQ(y)( xP(x) yQ(y)

11、。P(x) VQ(y)x( P(x) V yQ(y)x P(x) V yQ( y)xP(x) V yQ(y)(xP( x) yQ( y)四、（10分）設(shè)A= ，1 , 1 ， 1 , , 1, 1,1, 1 , B=0, 0,求 P(A)、P(B)0、P(B) Bo解 P(A)= , , 1 , 1 , , 1, P(B)-0 = , 0 , 0 ，0, 0 0 = ，0 , 0 ，0, 0P(B) B = ,0 , 0 ，0, 00, 0 = ,0, 0 ，0, 0五、(15 分)設(shè)X = 1 , 2, 3, 4, R是 X 上的二元關(guān)系， R= , , , , , , (1)畫出R的關(guān)系圖

12、。(2)寫出R的關(guān)系矩陣。(3)說明R是否是自反、反自反、對稱、傳遞的。解(1) R的關(guān)系圖如圖所示：(2) R的關(guān)系矩陣為：M (R)(3)對于R的關(guān)系矩陣，由于對角線上不全為11100 0 0 0111011101, R不是自反的；由于角線上存在非0元，R不是反自反的；由于矩陣不對稱,R不是對稱的;經(jīng)過計算可得M (R2)11100 0 0 011101110M (R),所以R是傳遞的。六、(15分)設(shè)函數(shù) f: RX R RX R, f 定義為：f() = 。證明f是單射。(2)證明f是滿射。(3)求逆函數(shù)f1。(4)求復(fù)合函數(shù)f 1 f和f f。證明(1)對任意的x,y,X1,y1 C

13、R,若 f()=f(),則 =,x+ y=x1 + y1, x y=x1 y1, 從而 x= x1, y= y1, 故 f是單射。(2)對任意的 e RX R,令 x= u一w2y= u- ,貝U f() = = ,所以f是滿射。2 fT(u,。，八,11，、,1,、 x y x y x y (x y)(4) f f() =f (f() =f () = = 22f f()=f(f()=f() = = 。七、(15 分)給定群 ,若對 G 中任意元 a 和 b,有 a3*b3= (a*b) 3, a4*b4= ( a*b) 4, a5*b5= (a*b)5,試證是Abel群。證明對G中任意元a和

14、b。因為 a3*b3= (a*b)3,所以 a1*a3*b3*b 1 = a 1*(a*b)3*b 1 ,即得 a2*b2= (b*a)2。同理，由 a4*b4= (a*b)4可得，a3*b3= (b*a)3。由 a5*b5= (a*b) 5可得，a4*b4= ( b*a)4。于是(a3*b3)*( b*a) = ( b*a)4= a4*b4,即 b4*a=a*b4。同理可得，(a2*b2)*( b*a) = ( b*a)3= a3*b3,即 b3*a= a* b3。由于(a*b)* b3= a*b4= b4*a= b*(b3*a)= b*(a*b3)=(b*a)*b3,故 a*b= b*a。八、(15分)(1)證明在n個結(jié)點的連通圖 G中，至少有n- 1條邊。證明 不妨設(shè)G是無向連通圖(若 G為有向圖，可略去邊的方向討論對應(yīng)的無向圖)。設(shè)G中