(完整word版)離散數(shù)學(xué)期末考試試題及答案

1、離散數(shù)學(xué)試題 (B 卷答案 1)一、證明題( 10 分)1) ( PA( QAR)V(QAR)V(PAR) R證明：左端(PAQAR)V(QVP)AR)( PAQ)AR)V(QVP)AR)( (PVQ)AR)V(QVP)AR)( (PVQ)V(QVP)AR( (PVQ)V(PVQ)ARTAR 置換)R2)x (A(x) B(x) xA(x) xB(x)證明 ： x(A(x) B(x) x( A(x)VB(x)x A(x)VxB(x)xA(x)VxB(x)xA(x) xB(x)二、求命題公式(PV(QAR)(PA QAR)的主析取范式和主合取范式(10 分)。證明：(PV(QAR) (PAQAR

2、) (PV(QAR)V(PAQA R)(PA( QVR)V(PAQAR)(PAQ)V( PAR)V(PAQAR)(PAQAR)V(PAQAR)V( PAQAR)V( PAQ(PAQAR)m0Vm1Vm2Vm7M3VM4VM5VM6三、推理證明題（10 分）1）CVD，(CVD)E，E (AAB)，(AAB) (RVS) RVS證明：(1) (CVD)EP(2)E (AAB)P(3) (CVD)(AAB)T(1)(2)，I(4) (AAB)(RVS)P(5) (CVD)(RVS)T(3)(4)，I(6) CVDP(7) RVST(5)，I2)x(P(x)Q(y)AR(x)，xP(x) Q(y)A

3、x(P(x)AR(x)證明 (1) xP(x)PP(a)T,ESR)Vx(P(x) Q(y)AR(x) PP(a)Q(y)AR(a) T(3),US(5)Q(y)AR(a)T(2)(4),1Q(y)T(5),I(7) R(a)T(5),I(8) P(a)AR(a)T(2)(7),I(9)x(P(x)AR(x)T(8),EG(10) Q(y)Ax(P(x)AR(x)T(6)(9),I四、 某班有 25 名學(xué)生，其中 14 人會打籃球，12 人會打排球，6 人會打籃球和排球，5人會打籃球和網(wǎng)球，還有2 人會打這三種球。而6 個會打網(wǎng)球的人都會打另外一種球，求不會打這三種球的人數(shù)(10 分)。解：A

4、，B, C 分別表示會打排球、 網(wǎng)球和籃球的學(xué)生集合。則|A|=12，|B|=6，|C|=14 ,|AnC|=6,|BnC|=5,|AnBnc|=2。先求|AnB|。6=|(AUC)nB|=|(AnB)U(BnC)|=|(AnB)|+|(BnC)|-|AnBnc|=|(AnB) |+5-2 , | (AnB) |=3。于是|AUBUC|=12+6+14-6-5-3+2=20。不會打這三種球的人數(shù)25-20=5。五、 已知 A B、C 是三個集合，證明 A-(BUC)=(A-B)n(A-C)(10 分)。證明： x A-(BUC)x AAx(BUC)x AA(x BAx C)(x AAx B)A

5、(x AAx C)x(A-B)Ax(A-C)x(A-B)n(A-C)A-(BUC)=(A-B)n(A-C)六、 已知 R、S 是 N 上的關(guān)系，其定義如下：R=| x, y NA y=x , S=| x, yNAy=x+1。求 R1、R*S、S*R、R 1 , 2、S1 , 2 (10 分)。-12解：R =| x , y NAy=x 2R*S=| x , y NA y=x +1S*R=| x,yNAy=(x+1)2,R 1,2= ,S1,2=1,4。七、 設(shè) R=, , ，求 r(R)、s(R)和 t(R) (15 分)。解: r(R)=, , , s(R)=, , , , R2= R5=，

6、 ，R3=， ， R4=， ， t(R)=， ，八、證明整數(shù)集 I 上的模 m 同余關(guān)系 R=|x y(mod m)是等價關(guān)系。其中，x y(mod m)的含義是 x-y 可以被 m 整除(15 分)。證明：1) x I，因為(x-x ) /m=0，所以 x x(mod m)，即 xRx。2)x, y I，若 xRy，貝 U x y(mod m)，即(x-y ) /m=k I，所以(y - x ) /m=-k I，所以 y x(mod m)，即 yRx。3)x, y, z I， 若 xRy, yRz， 則(x-y ) /m=u I , (y-z ) /m=v I， 于是(x-z ) /m=(

7、x-y+y-z )/m=u+v I ，因此 xRz。九、若 f:ATB 和 g:BTC 是雙射，則(gf)-1=f-1g-1(10 分)。證明：因為 f、g 是雙射，所以 gf :ATC 是雙射，所以 gf 有逆函數(shù)(gf )-1:CTA。同理可推f-1g-1:CTA 是雙射。因為 f g 存在 z( g f ) 存在 z( f g) gf ( gf)-1，所以( gf)-1=f-1g-1。離散數(shù)學(xué)試題 (B 卷答案 2)一、證明題( 10 分)1)(PVQ)A( PA( QVR)V( PAQ)V( PAR) T證明：左端 (PVQ)A(PV(QAR)V(PVQ)A(PVR)(摩根律)(PVQ

8、)A(PVQ)A(PVR)V(PVQ)A(PVR)( 分配律)(PVQ)A(PVR)V(PVQ)A(PVR) ( 等冪律)T（ 代入 ）2) x y(P(x) Q(y)( xP(x)yQ(y)證明： x y(P(x)Q(y)x y(P(x)VQ(y)x( P(x)VyQ(y)x P(x)VyQ(y)xP(x)VyQ(y)( xP(x) yQ(y)、求命題公式 ( P Q) (PVQ) 的主析取范式和主合取范式( 10 分)解： ( P Q) (PVQ) ( P Q)V(PVQ)的集合，則命題可符號化為:P x A(x)， xA(x) Q Q P。(PVQ)V(PVQ)(PAQ)V(PVQ) (

9、PVPVQ)A( QV PVQ) (PVQ)M1 m0V m2Vm3三、推理證明題(10 分)1)(P (Q S)A( RVP)AQ R證明：(1)RRVP(3)P(5)Q(6)Q(7)S考場，考試才能準(zhǔn)時進行。所以，如果考試準(zhǔn)時進行，那么天氣就好(解 設(shè) P:今天天氣好，Q:考試準(zhǔn)時進行，A(e) : e 提前進入考場，個體域：考生x(A(x)yB(y)， x(B(x)yC(y)丨丨 xA(x) yC(y)。證明：(1) x(A(x)yB( y)P(2) A( a)yB( y)T(1)，ES(3) x( B( x)yC( y)P(4) x( B( x) C(c)T(3)，ES(5)B(b)

10、C(c)T(4)，US(6) A(a) B( b)T(2)，US(7) A(a) C(c)T(5)(6)，I(8) xA(x) C(c)丁，UG(9) xA(x) yC(y)T(8)，EGS(8)R四、只要今天天氣不好，就一定有考生不能提前進入考場，當(dāng)且僅當(dāng)所有考生提前進入2)I(4)P(QS)15 分)。(i) P x A(x)P(2) PxA(x)T(i)，E(3) xA(x) PT(2)，E(4) xA(x) QP(5)( xA(x) Q)A(QxA(x)T(4)，E(6) QxA(x)T(5)，I(7) Q PT(6)(3)五、已知AB、C 是三個集合，證明 An(BUC)=(AnB)

11、U(AnC) (10 分)證明： x An(BUC)x AAx(BUC)xAA(xBVxC)(x AAx B)V(x AAx C)x(AnB)Vx AnC x(AnB)U(AnC). An(BUC)=(AnB)U(AnC)六、A= x1,x2,x3 ， B= y1,y2， R=, ，求其關(guān)系矩陣及關(guān)系 圖(10 分)。七、設(shè) R=,，求 r(R)、s(R)和 t(R)，并作出它們及 R 的關(guān)系圖(15 分)。解： r(R)=,s(R)=,R2=R5=,3R3=,4R4=,t(R)=,八、 設(shè) Ri是 A 上的等價關(guān)系，R2是 B 上的等價關(guān)系，A豐且 B豐。關(guān)系 R 滿足：, R Ri且 R2

12、,證明 R 是 AXB 上的等價關(guān)系(10 分)。證明 對任意的 AXB,由 Ri是 A 上的等價關(guān)系可得 Ri，由 R?是 B 上的等價關(guān)系可得 R2。再由 R 的定義，有, R,所以 R 是自反 的。對任意的 、AXB,若R,則 Ri且 R2。由 Ri對稱得 Ri，由 R2對稱得 R2。再由 R 的定義，有, R,即R,所以 R 是對稱的。對任意的 、 AXB，若 R且R,則 Ri且 R2, Ri且 R2。由 Ri、 Ri及 Ri的傳遞性得 Ri,由 R2、 R2及 R2的傳遞性得 Ri。再由 R 的定義， 有, R,即 R,所以 R 是傳遞的。綜上可得，R 是 AXB 上的等價關(guān)系。九、

13、設(shè) f: A B, g: B C, h: C A，證明：如果 h g f=IA,f h g =IB,g f h= lc,則iiif、 g、 h 均為雙射,并求出 f 、 g 和 h (i0 分)。解 因 lA恒等函數(shù)，由 h g f= lA可得 f 是單射，h 是滿射；因 IB恒等函數(shù)，由 f h g=IB可得 g 是單射, f 是滿射；因 IC恒等函數(shù),由 g f h= IC可得 h 是單射, g 是滿射。從 而 f、 g、 h 均為雙射。由 h g f=IA，得廠=h g；由 f h g =IB,得i= f h;由 g f h = lc,得 = g f。離散數(shù)學(xué)試題 (B 卷答案 3)一、

14、 (I0 分)判斷下列公式的類型(永真式、永假式、可滿足式)？(寫過程)I)P (PVQV R) 2)(Q P)VP)A(PVR) 3)( PVQ) R) (PAQ)VR)解: i) 重言式； 2) 矛盾式； 3) 可滿足式二、 (10 分)求命題公式(PV(QAR) (PVQVR)的主析取范式，并求成真賦值。解：(PV(QAR) (PVQVR)(PV(QAR)VPVQVRPA( QVR)VPVQVR( PAQ)V( PAR)V(PVQ)VR( (PVQ)V(PVQ)V( PAR)VRiV( PAR)VR) im0VmiVm2Vm3Vm4Vm5Vm6Vm7該式為重言式,全部賦值都是成真賦值。三

15、、 ( i0 分)證明 (PAQAA) C)A(A (PVQVC) (AA(P Q) C證明: (PAQAA) C)A(A (PVQVC)( (PAQAA)VC)A( AV(PVQVC)( PVQVA)VC)A( AVPVQ)VC)( PVQVA)A( AVPVQ)VC(PVQVA)A( AVPVQ) C(PVQVA)V( AVPVQ) C(PAQAA)V(AAPAQ) C(AA(PAQ)V( PAQ)C(AA(PVQ)A( PVQ)C(AA(Q P)A(P Q) C(AA(P Q) C四、 (10 分)個體域為1 , 2，求 x y (x+y=4 )的真值。解： x y(x+y=4)x(x+

16、1=4)V(x+2=4)(1+1=4)V(1+2=4)A(2+1=4)V(2+2=4)(0V0)A(0V1)0A10五、 (10 分)對于任意集合 A, B,試證明：P(A)nP(B)=P(AnB)解： x P(A)nP(B) , x P(A)且 x P(B)，有 x A 且 x B,從而 x AnB, x P(AnB) ，由于上述過程可逆，故 P(A)nP(B)=P(AnB)六、(10分）已知 A=1，2，3，4，5 和R=， ，求 r(R) 、s(R) 和 t(R)。解：r(R)=， 2，1， ， ， s(R) =， ，t(R)=， ， ， ，, 七、 (10 分)設(shè)函數(shù) f: RXR R

17、XR, R 為實數(shù)集，f 定義為：f()=。1)證明 f 是雙射。解: 1) , RXR,若 f()=f()，即 =,則 x1+y1=x2+y2且 x1-y1=x2-y2得 x1=x2, y1=y2從而 f 是單射。2) RXR,由 f()=,通過計算可得 x=(p+q)/2 ; y=(p-q)/2 ; 從而的原象存在，f 是滿射。八、 (10 分)是個群，u G,定義 G 中的運算“”為 a b=a*u-1*b，對任意 a, b G 求證：也是個群。證明：1) a, b G, a b=a*u-1*b G,運算是圭寸閉的。2)a, b, c G (a b)c= (a*u-1*b) *u-1*c

18、=a*u-1* (b*u-1*c ) =a (b c),運算是可結(jié)合的。3)a G 設(shè) E 為 的單位元，貝 U a E=a*u-1*E=a,得 E=u,存在單位元 u。4)a Q a x=a*u-1*x=E , x=u*a-1*u，貝 U x a=u*a-1*u*u-1*a=u=E，每個元素都有逆丿元。所以也是個群。解：最優(yōu)二叉樹為權(quán)=(2+4)X4+6X3+12X2+(8+10)X3+14X2= 148離散數(shù)學(xué)試題(B 卷答案 4)、證明題(10 分)1)(PVQ)A(PA( QVR)V( PAQ)V( PAR) T九、（10 分）已知:D=, V=1 , 2 , 3 , 4 , 5, E

19、= , , , , ,求 D 的鄰接距陣A 和可達距陣 P。P 如下：0101000100A=0001100000100001111111111P=111110000011111解：1） D 的鄰接距陣 A 和可達距陣十、（10 分）求葉的權(quán)分別為 2、4、6、8 10、12、14 的最優(yōu)二叉樹及其權(quán)。 G 求證：也是個群。證明：左端(PVQ)A(PV(QAR)V(PVQ)A(PVR)(摩根律)(PVQ)A(PVQ)A(PVR)V(PVQ)A(PVR)(分配律)(PVQ)A(PVR)V(PVQ)A(PVR)(等幕律)T (代入)2) x(P(x)Q(x)AxP(x) x(P(x)AQ(x)證明

20、：x(P(x)Q(x)AxP(x) x(P(x)Q(x)AP(x)x( P(x)VQ(x)AP(x) x(P(x)AQ(x) xP(x)AxQ(x) x(P(x)AQ(x)(4) P(c)VQ(c) T(3),US(5) Q(c)T(2)(4),I(6)x Q(x) T(5),EG四、例 5 在邊長為 1 的正方形內(nèi)任意放置九個點，證明其中必存在三個點，使得由它們 組成的三角形(可能是退化的)面積不超過 1/8 (10 分)。證明：把邊長為 1 的正方形分成四個全等的小正方形，則至少有一個小正方形內(nèi)有 三個點，它們組成的三角形(可能是退化的)面積不超過小正方形的一半，即 1/8 。五、已知AB

21、、C 是三個集合，證明 An(BUC)=(AnB)U(AnC) (10 分)解：(PQ) (PVQ)(PQ)V(PVQ)(PVPVQ)A(QVPVQ) (PV推理證明題 (10 分)(QS)A( RVP)AQRS證明：(1)R附加前提(2)RVPP(3)PT(1)(2),I(4)P(QS)P(5)QST(3)(4),I(6)QP(7)ST(5)(6),I(8)RSCPx(P(x)VQ(x)，x P(x)x Q (x)證明： (1)x P(x)P(2)P(c)T(1),US( PAQ)V二、求命題公式 ( P Q) (PVQ) 的主析取范式和主合取范式( 10 分)Q) M1 m0Vm2Vm3(

22、PV1)(PQ) (PVQ)V(PVQ)證明：TxAA(BUC)x AAx(BUC)x AA(xBVx C)(x AAxB)V(xAAx C)x(AAB)Vx AACx(AAB)U(AAC). AA( BUC)=(AAB)U(AAC)六、=A1,A，An是集合 A 的一個劃分，定義 R=|a、bA,I=1,2 J ?n，貝 U R 是 A 上的等價關(guān)系（15 分）。證明：a A 必有 i 使得 aA，由定義知 aRa,故 R 自反。a,b A 若 aRb，貝 U a,b A，即 b,a A，所以 bRa,故 R 對稱。a,b,c A,若 aRb 且 bRc,貝 U a,b A及 b,c A。因

23、為 i豐j 時 A A A=，故 i=j , 即a,b,c A,所以 aRc,故 R 傳遞。總之 R 是 A 上的等價關(guān)系。七、 若 f:ATB 是雙射，則 f1:BTA 是雙射（15 分）。證明：對任意的 x A,因為 f 是從 A 到 B 的函數(shù)，故存在 y B,使 f , f-1。所以,f-1是滿射。對任意的 x A,若存在 y1,y2 B,使得 f-1且 f-1,則有 f 且 f。因為 f 是函數(shù)，則 y1=y2。所以，f-1是單射。因此 f-1是雙射。八、 設(shè)是群，和是的子群，證明：若 AUB= G,貝UA= G 或 B= G （10分）。證明 假設(shè)AMG 且 B豐G,則存在 a A

24、, a B,且存在 b B, b A （否則對任意的 a A, a B，從而 A B，即 AUB = B,得 B= G,矛盾。）對于元素 a*b G,若 a*b A，因 A 是子群，a-A,從而 a *（ a*b） = b A，所以 矛盾，故 a*b A。同理可證 a*b B，綜合有 a*b AUB = G。綜上所述，假設(shè)不成立，得證A= G 或 B= G。九、 若無向圖 G 是不連通的，證明 G 的補圖G是連通的（10 分）。證明 設(shè)無向圖 G 是不連通的，其 k 個連通分支為 G、G2、Gk。任取結(jié)點u、v G,若u和v不在圖 G 的同一個連通分支中，則u,v不是圖 G 的邊，因而u,v

25、是圖G的邊；若u和v在圖G的同一個連通分支中，不妨設(shè)其在連通分支Gi（K ik）中，在不同于Gi的另一連通分支上取一結(jié)點w,則u,w和w,v都不是圖 G 的邊，因而u,w和w,v都是G的邊。綜上可知，不管那種情況，u和v都是可達的。由u和v的任意性可知，G是連通的。離散數(shù)學(xué)試題（B卷答案5）、(10 分)求命題公式(PAQ) ( P R)的主合取范式。解：(PAQ) (PR)(PAQ) ( P R)A(PR) (PAQ)(PAQ)V( PAR)A(PVR)V( PVQ)(PAQ)V( PAR)(PVR)A(QVP)A(QVR)(PVQVR)A(PVQVR)A(PVQVR)A(PVQVR)M1A

26、M3AM4AM5、( 8 分)敘述并證明蘇格拉底三段論 解：所有人都是要死的，蘇格拉底是人，所以蘇格拉底是要死的。符號化：F(x): x 是一個人。G (x) : x 要死的。A:蘇格拉底。 命題符號化為 x(F( x) G( x)，F(xiàn)( a)G( a)證明：( 1 ) x(F(x) G(x) P( 2)F(a)G(a)T(1),US( 3 )F(a)P( 4 )G(a)T(2)(3),I、( 8 分) 已知 A、B、C 是三個集合，證明An(BuC)=(AnB)u(AnC)證明：/ x An(BuC)x AAx(BuC)x AA(x BVx C)(x AAx B)V(x AAx C)x(An

27、B)Vx AnCx(AnB)U(AnC) An(BUC)=(AnB)U(AnC)四、(10 分)已知 R 和 S 是非空集合 A 上的等價關(guān)系，試證：1) RnS 是 A 上的等價關(guān)系；2)對 a A aRHs=aRnas解：x A,因為 R 和 S 是自反關(guān)系，所以 R、 S,因而 RnS, 故 RnS 是自反的。x、y A,若 RnS,則 R、 S,因為 R 和 S 是對稱關(guān)系，所以因 R S,因而 RAS,故 RAS 是對稱的。x、y、z A,若 RAS 且 RAS,則 R S 且 R、 S,因為 R 和 S 是傳遞的，所以因 R、 S,因而 RAS,故 RAS 是傳遞的?？傊?RAS

28、是等價關(guān)系。2)因為 x aRAS RASRAS xaRAxaSxaRAaS所以 aRAS=aRAaS。五、(10 分)設(shè)A= a, b, c, d, R 是 A上的二元關(guān)系，且 R= , , ，求 r(R)、s(R)和 t( R)。解 r(R) =RU|A=, , , , ,-1s( R)=RUR=,2R = , R3= , 4R = , = R2it( R) =R=i1 六、(15 分) 設(shè) A、 B、 C、D是集合，f 是 A 到 B 的雙射,g 是 C 到 D 的雙射 令 h：AxC BxD 且 AxC, h() = 。證明 h 是雙射。證明：1)先證 h 是滿射。 BXD,貝 UbB

29、,d D,因為 f 是 A 到 B 的雙射，g 是 C 到 D 的雙射，所以存在 a A, c C,使得 f(a)=b , f(c)=d ,亦即存在 AxC,使得 h()= = ,所以 h 是滿射。2)再證 h 是單射。、 Ax C ,若 h() = h(),貝 U =,所以 f(a1) = f(a2) , g(c1) = g(c2),因為 f 是 A 到 B 的雙射，g 是 C到 D 的雙射，所以 a1 = a2 , c1 = c2 ,所以 = ,所以 h 是單射。綜合 1 )和 2)h 是雙射。七、(12 分)設(shè)是群， H 是 G 的非空子集， 證明是的子群的充要條件 是若 a, b H,

30、則有 a*b-1H。證明：a,b H 有 b-1 H,所以 a*b-1 H。-1嚴(yán)a H,貝 U e=a*a Ha-1=e*a-1 H/ a,b H 及 b-1 H,. a*b=a* (b-1)-1 H H G 且 HM , *在 H 上滿足結(jié)合律 是 的子群。八、(10 分)設(shè) G=是簡單的無向平面圖，證明 G 至少有一個結(jié)點的度數(shù)小于等于5。解：設(shè) G 的每個結(jié)點的度數(shù)都大于等于6,則 2|E|= d(v) 6|V|，即|E| 3|V|，與簡單無向平面圖的|E| 3|V|-6 矛盾，所以 G 至少有一個結(jié)點的度數(shù)小于等于5。九、 G=,A=a,b,c,*的運算表為：(寫過程，7 分)*a

31、涵殛瓦(1)G 是否為阿貝爾群？(2)找出 G 的單位元；(3)找出 G 的幕等元(4)求 b 的逆元和 c 的逆元解：(1) (a*c)*(a*c)=c*c=b=a*b=(a*a)*(c*c)(a*b)*(a*b)=b*b=c=a*c=(a*a)*(b*b)(b*c)*(b*c)=a*a=a=c*b=(b*b)*(c*c)所以 G 是阿貝爾群(2)因為 a*a=a a*b=b*a=b a*c=c*a=c 所以 G 的單位元是 a(3)因為 a*a=a 所以 G 的幕等元是 a(4)因為 b*c=c*b=a，所以 b 的逆元是 c 且 c 的逆元是 b十、(10 分)求葉的權(quán)分別為 2、4、6

32、、& 10、12、14 的最優(yōu)二叉樹及其權(quán)。解：最優(yōu)二叉樹為（20 分）用公式法判斷下列公式的類型:(1) ( PVQ) (P Q)(2) (P Q) (PA(QVR)解：(1)因為(PVQ) (P Q) ( PVQ)V(PAQ)V( PAQ) (PAQ)V(PAQ)V( PAQ)Vm2Vm3Mo所以，公式(PVQ) (P Q)為可滿足式。(2)因為(P Q) (PA(QVR)( ( PVQ)V(PAQAR)(PVQ)V(PAQAR)(PVQVP)A(PVQVQ)A(PVQVR)(PVQ)A(PVQVR)(PVQV(RAR)A(PVQVR)(PVQVR)A(PVQVR)A(PVQVR)

33、MoAM1m2Vm3Vm4Vm5Vm6Vm7所以，公式(P Q) (PA(QVR)為可滿足式。563212161410權(quán)=148離散數(shù)學(xué)試題（B卷答案6）二、(15 分)在謂詞邏輯中構(gòu)造下面推理的證明：每個科學(xué)家都是勤奮的，每個勤奮又身體健康的人在事業(yè)中都會獲得成功。存在著身體健康的科學(xué)家。所以，存在著事業(yè)獲得成功的人或事業(yè)半途而廢的人。解：論域：所有人的集合。Q(x) :x是勤奮的；H(x):x是身體健康的；S(x):x是科學(xué)家；C(x):x是事業(yè)獲得成功的人；F(X):x是事業(yè)半途而廢的人；則推理化形式為：x(S(x)Q(x),x(Q(x)AH(x) C (x),X(S(X)AH(X)Ix

34、(C (x)VF(x)下面給出證明：(1)X(S(X)AH(x)PS(a)AH(a)T(1),ESX(S(X)Q(X)PS(a)Q(a)T(1),USS(a)T(2),IQ(a)T(4)(5),IH(a)T(2),I(8)Q(a)AH(a)T 7),1(9)X(Q(X)AH(X) C(X)P(10)Q(a)AH(a) C(a)T(9),Us(11)C(a)T(8)(10),(12)XC (X)T(11),EG(13)x(C(x)VF(x)T(12),I三、 (10 分)設(shè) A = , 1 , 1 ,B= 0, 0,求P(A)、P(B)0、P(B)B。解 P(A)= , ,1 , 1 , , 1

35、, , 1 , 1 , 1, , 1 , 1P(B) 0 = , 0 , 0, 0 ,0 0 = ,0 ,0 ,0, 0P(B) B= ,0 , 0, 0, 0 0, 0= , 0 ,0 ,0, 0四、 (15 分)設(shè) R 和 S 是集合 A 上的任意關(guān)系，判斷下列命題是否成立？(1)若 R 和 S 是自反的，則 R*S 也是自反的。若 R 和 S 是反自反的，則 R*S 也是反自反的。(3) 若 R 和 S 是對稱的，則 R*S 也是對稱的。(4) 若 R 和 S 是傳遞的，則 R*S 也是傳遞的。(5) 若 R 和 S 是自反的，貝yRnS 是自反的。(6) 若 R 和 S 是傳遞的，則

36、RUS 是傳遞的。解(1)成立。對任意的aA，因為 R 和 S 是自反的，貝U R, s,于是 R*s,故 R*S 也是自反的。不成立。例如，令 A = 1 , 2 , R= , S= ，則 R 和 S 是反自反 的，但 R*S= 不是反自反的。(3)不成立。例如，令A(yù)= 1 , 2, 3, R= , , , S= ,貝 U R 和 S 是對稱的，但 R*S= , 不是對稱的。不成立。例如，令 A = 1 , 2 , 3, R= , , , S= , , ,貝 U R 和 S 是傳遞的，但 R*S= , , 不是傳遞 的。(5)成立。對任意的aA,因為 R 和 S 是自反的，貝yR, S ,

37、于是 Rns,所以 RnS是自反的。五、(15 分)令 X = X1, x2,xm , Y= y1, y2,yn。問(1) 有多少個不同的由 X 到 Y 的函數(shù)？(2) 當(dāng) n、m 滿足什么條件時，存在單射，且有多少個不同的單射？(3) 當(dāng) n、 m 滿足什么條件時 存在雙射 且有多少個不同的雙射？解(1)由于對 X 中每個元素可以取 Y 中任一元素與其對應(yīng)，每個元素有n 種取法，所以不同的函數(shù)共 nm個。(2)顯然當(dāng)|m|w|n|時,存在單射。由于在 Y 中任選 m 個元素的任一全排列都形成X 到Y(jié) 的不同的單射，故不同的單射有Cnm! = n(n 1)(n m 1)個。顯然當(dāng)|m|= |n

38、|時,才存在雙射。此時Y 中元素的任一不同的全排列都形成X 到 Y的不同的雙射，故不同的雙射有m!個。六、 (5 分)集合 X 上有 m 個元素， 集合 Y 上有 n 個元素， 問 X 到 Y 的二元關(guān)系總共 有多少個？解 X 到 Y 的不同的二元關(guān)系對應(yīng) XXY 的不同的子集，而 XXY 的不同的子集共有 個2mn,所以 X 到 Y 的二元關(guān)系總共有2mn個。七、(10 分)若是群，則對于任意的 a、b G,必有惟一的 x G 使得 a*x= b。證明 設(shè) e 是群 的幺元。令 x= a-1*b，則 a*x= a*( a1*b) = (a*aj*b= e*b= b。所以，x= 1*b 是 a

39、*x = b 的解。若 x G 也是 a*x= b 的解，貝 U x = e*x = (a-1*a)*x = a-1*(a*x ) = a-1*b = x。所以，x =a1*b是 a*x= b 的惟一解。八、(10 分)給定連通簡單平面圖G= ，且|V|= 6, |E|= 12。證明：對任意 f F，d(f) = 3。證明 由偶拉公式得 |V|E|+ |F|= 2，所以 |F|= 2 |V|+ |E|= 8,于是 d(f) = 2|E|=fF24。若存在 f F，使得 d(f) 3,貝 U 3|F|V2|E|= 24,于是|F|V8,與|F|= 8 矛盾。故對任 意 f F, d(f)=3。離

40、散數(shù)學(xué)試題( B 卷答案 7)一、(15 分)設(shè)計一盞電燈的開關(guān)電路，要求受 3 個開關(guān) A、B、C 的控制：當(dāng)且僅當(dāng) A 和 C 同時關(guān)閉或 B 和 C 同時關(guān)閉時燈亮。設(shè)F 表示燈亮。(1) 寫出 F 在全功能聯(lián)結(jié)詞組 中的命題公式。(2)寫出F的主析取范式與主合取范式。解(1)設(shè) A:開關(guān) A 關(guān)閉；B:開關(guān) B 關(guān)閉；C :開關(guān) C 關(guān)閉；F = (AAC)V(BAC)。在全功能聯(lián)結(jié)詞組 中：A(AAA) A AAAC( AAC)( A C) (A C) (AC)AVB( AAB)( A A)A(B B)( A A) (B B)所以F (A C) (A C)V(B C) (B C)(A

41、 C) (A C) (A C) (A C) (B C) (B C) (B C) (B C)(2)F(AAC)V(BAC)(AA(BVB)AC)V(AVA)ABAC)(AABAC)V(AABAC)V(AABAC)V( AABAC)m3Vm5Vm7主析取范式M0AM1AM2AM4AM6主合取范式二、( 10 分)判斷下列公式是否是永真式？(1)( xA(x) xB(x) x(A(x) B(x)。(2)( xA(x)xB( x)x(A(x) B(x)。解 (1)( xA(x) xB(x) x(A(x) B(x)(xA(x)VxB(x) x(A(x) B(x)(xA(x)VxB(x)Vx( A(x)V

42、B(x)(xA(x)AxB(x)Vx A(x)VxB(x)(xA(x)Vx A(x)VxB(x)A( xB(x)Vx A(x)VxB(x)x(A(x)VA(x)VxB(x)T所以，(xA(x) xB(x) x(A(x) B(x)為永真式。(2)設(shè)論域為1 , 2，令 A(1) = T ; A(2) = F; B(1) = F; B(2) = T。貝 U xA(x)為假，xB(x)也為假，從而 xA(x) xB(x)為真；而由于 A(1) B(1)為假, 所以 x(A(x) B(x)也為假，因此公式(xA(x) xB(x) x(A(x) B(x)為假。該公式不 是永真式。(15 分)設(shè) X 為集

43、合，A= P(X) - X且 A 工，若|X|= n,問(1)偏序集 A， 是否有最大元？(2)偏序集 A,是否有最小元？(3)偏序集A,中極大元和極小元的一般形式是什么？并說明理由。解 偏序集A, 不存在最大元和最小元，因為n 2?？疾?P(X)的哈斯圖，最底層的頂點是空集，記作第0 層，由底向上，第一層是單元集，第二層是二元集，由|X|= n,則第 n 1 層是 X 的 n 1 元子集，第 n 層是 X。偏序集A, 與偏序集P(X), 相比，恰好缺少第 0 層和第 n 層。因此A, 的極小元就是 X 的所有單元集，即x, x X;而極大元恰好是比 X 少一個元素，即 X x , xX。四、

44、(10 分)設(shè) A = 1 , 2, 3, 4, 5, R 是 A 上的二元關(guān)系，且 R= , , , , , ，求r(R)、s(R)和 t(R)。解r(R)= RUIA= , , , , , , ,s(R)=RUR1 =,R2= , , , , , , R3=, , , , , , R4=, , , , , , = R2t(R) = Ri= , , , , , , , , , 。五、 (10 分)設(shè)函數(shù) g :ATB , f: BTC ,(1)若 fg 是滿射，則 f 是滿射。若 f g 是單射，則 g 是單射。證明 因為 g :ATB, f: BTC,由定理 5.5 知，f g 為 A 到

45、 C 的函數(shù)。(1) 對任意的 z C ,因 fg 是滿射，則存在 x A 使 f g(x)=乙即 f(g(x) = z。由 g：ATB可知g(x) B,于是有 y= g(x) B,使得 f(y)= z。因此，f 是滿射。(2) 對任意的X1、 X2 A,若X1豐x2,則由f g是單射得f g(x1)工f g(x2),于是f(g(x1)豐f(g(X2),必有 g(x1)豐g(x2)。所以，g 是單射。六、 (10 分)有幺元且滿足消去律的有限半群一定是群。證明 設(shè)是一個有幺元且滿足消去律的有限半群，要證 是群，只需證 明 G 的任一元素 a 可逆。考慮 a , a2,ak,。因為 G 只有有限

46、個元素，所以存在 kl,使得 ak= al。令 m= k l,有al*e= al*am,其中 e 是幺兀。由消去率得am= e。于是，當(dāng) m= 1 時，a= e,而 e 是可逆的；當(dāng) m 1 時，a*am-1= am-1*a = e。從而 a 是可逆的，其逆元是 am-1?？傊琣 是可逆的。七、 (20 分)有向圖 G 如圖所示，試求：(1) 求 G 的鄰接矩陣 A。(2) 求出 A2、A3和 A4, V1到 V4長度為 1、2、3 和 4 的路有多少？求出ATA和AAT,說明ATA和AAT中的第(2 , 2)元素和第(2 , 3)元素的意義。(4) 求出可達矩陣 P。(5) 求出強分圖。解

47、(1)求 G 的鄰接矩陣為A0 10 0(2)由于0111021 2032 320 2013012 24041 3A2A3A40111021 2032 30011020 1012 2所以 V1到V長度為 1、 2、3 和4的1勺路的個彳數(shù)分別為1、1、2、3由于000 021 2 1T031 2T12 1 0A AAA001 121 2 1021 310 2 1再由定理 10.19 可知，所以AA的第(2, 2)元素為 3,表明那些邊以V2為終結(jié)點且具有不同始結(jié)點的數(shù)目為3,其第(2，3)元素為 0，表明那些邊既以V2為終結(jié)點又以V3為終結(jié)點，并且具有相同始結(jié)點的數(shù)目為0。AAT中的第(2，2

48、)元素為 2,表明那些邊以v2為始結(jié)點且具有不同終結(jié)點的數(shù)目為2，其第(2, 3)元素為 1,表明那些邊既以v2為始結(jié)點又以V3為始結(jié)點，并且具有相同終結(jié)點的數(shù)目為1。構(gòu)成 G 的強分圖。離散數(shù)學(xué)試題(B 卷答案 8)一、(10 分)證明(PVQ)A(P R)A(Q S)l SVR證明 因為 SVR R S,所以，即要證(PVQ)A(P R)A(Q S)1R S。0 101012340 0110 2B4A A A3A4+0 101010 1000 00 111所以求可達矩陣為P0 111。0 1110 111因為11021 20323074101012 2041 3074 7+11021 20

49、32 3074 711020 1012 2043 4因為P PT0 1110 1110 1110 1110 0 0 0111111111111000011011011 , V2,V3,V4R附加前提(2)P RPPT(1)(2) , I(4)PVQP(5)QT(3)(4), IQ SP(7)ST(5)(6) , I(8) R SCP(9)SVRT(8), E二、(15 分)根據(jù)推理理論證明：每個考生或者勤奮或者聰明，所有勤奮的人都將有所作為，但并非所有考生都將有所作為, 所以，一定有些考生是聰明的。設(shè) P(e)： e 是考生，Q(e)： e 將有所作為，A(e): e 是勤奮的，B(e)： e

50、 是聰明的，個體域：人的集合，則命題可符號化為：x(P(x) (A(x)VB(x),x(A(x) Q(x),x(P(x) Q(x)l x(P(x)AB(x)。(1) x(P(x) Q(x)P(2) x( P(x)VQ(x)T(1), E(3) x(P(x)AQ(x)T(2), E(4)P(a)AQ(a)T(3) , ES(5)P(a)T(4), I(6) Q(a)T(4), I(7) x(P(x) (A(x)VB(x)P(8)P(a)(A(a)VB(a)T(7), US(9)A(a)VB(a)T(8)(5) , I(10) x(A(x) Q(x)P(11)A(a) Q(a)T(10), US(

51、12) A(a)T(11) (6) , I(13)B(a)T(12)(9), I(14)P(a)AB(a)T(5)(13) , I(15) x(P(x)AB(x)T(14), EG三、(10 分)某班有 25 名學(xué)生，其中 14 人會打籃球，12 人會打排球，6 人會打籃球和排球，5 人會打籃球和網(wǎng)球， 還有 2 人會打這三種球。 而 6 個會打網(wǎng)球的人都會打另外 一種球，求不會打這三種球的人數(shù)。解設(shè) A、B、C 分別表示會打排球、網(wǎng)球和籃球的學(xué)生集合。則：|A|=12,|B|=6,|C|=14,|AAC|=6,|BAC|=5,|AnBAC|=2,|（AUC）QB|=6。因為|（AUC）nB|

52、= （AnB）U（Bnc）|=|（AnB）|+|（Bnc）| AnBnC|=|（AnB）|+5 2 =6,所以 |（AnB）|= 3。于是 |AUBUC|= 12+ 6+ 14 6 5 3 + 2 = 20,| A BC|= 25 20= 5。故，不會打這三種球的共 5 人。3四、 （10 分）設(shè) A1、A2和 A3是全集 U 的子集，則形如Ai（Ai為 Ai或A,）的集合稱i 1為由 A1、A2和 A3產(chǎn)生的小項。試證由 A1、A2和 A3所產(chǎn)生的所有非空小項的集合構(gòu)成全 集 U 的一個劃分。證明 小項共 8 個，設(shè)有 r 個非空小項 S1、S2、sr（r 8）。對任意的 a U,則 a A

53、i或 aA，兩者必有一個成立，取Ai為包含元素 a 的 Ai_3rrrr或Ai ,貝 U a Ai,即有 a s,于是 Us。又顯然有s U，所以 U = s。1i 1i 1i 1i 1任取兩個非空小項sp和 sq,若 SpMSq,則必存在某個 Ai和A分別出現(xiàn)在 sp和 Sq中， 于是 Spnsq=。綜上可知， S1, S2,，Sr是 U 的一個劃分。五、 （15 分）設(shè) R 是 A 上的二元關(guān)系，則：R 是傳遞的 R*R R。證明（5）若 R 是傳遞的，則 R* R z（xRzAzSy）xRcAeSy,由 R 是傳遞的 得 xRy，即有 R,所以 R*R R。反之，若 R*R R,則對任意

54、的 x、y、z A，如果 xRz 且 zRy，則 R*R,于是 有 R,即有 xRy,所以 R 是傳遞的。六、 （15 分）若 G 為連通平面圖，則 n m+ r = 2,其中，n、m、r 分別為 G 的結(jié)點 數(shù)、邊數(shù)和面數(shù)。證明對 G 的邊數(shù) m 作歸納法。當(dāng) m= 0 時，由于 G 是連通圖，所以 G 為平凡圖，此時 n= 1, r = 1,結(jié)論自然成立。假設(shè)對邊數(shù)小于 m 的連通平面圖結(jié)論成立。下面考慮連通平面圖 G 的邊數(shù)為 m 的情況。設(shè) e 是 G 的一條邊，從 G 中刪去 e 后得到的圖記為 G,并設(shè)其結(jié)點數(shù)、邊數(shù)和面數(shù) 分別為 n、m 和 r。對 e 分為下列情況來討論：若 e

55、 為割邊，則 G 有兩個連通分支 Gi和 G2。Gi的結(jié)點數(shù)、邊數(shù)和面數(shù)分別為ni、mi和 ri。顯然 ni+ n2= n = n, mi+ m2= m = m 1, ri+2= r + 1 = r + 1。由歸納假設(shè)有 ni mi+ri= 2, n2 m2+ r2= 2，從而(ni+ n2) (mi+ m2) + (ri+ r2)= 4, n (m 1)+ (r + 1)=4，即 nmr=2。若 e 不為割邊，則 n = n, m = m 1, r = r 1,由歸納假設(shè)有 n m + r = 2,從而 n (mi)r i= 2，即 n mr= 2。由數(shù)學(xué)歸納法知,結(jié)論成立。七、 (10 分

56、)設(shè)函數(shù) g:ATB, f: BTC,則：(i)f g 是 A 到 C 的函數(shù)；對任意的 x A，有 f g(x) = f(g(x)。證明(1)對任意的 x A，因為 g: ATB 是函數(shù)，則存在 y B 使 g。對于 y B，因 f：BTC 是函數(shù)，則存在 z C 使 f。根據(jù)復(fù)合關(guān)系的定義，由 g 和 f 得 g*f,即 f g。所以 Df g= A。對任意的 x A,若存在 yi、y2 C,使得、 f g= g*f，則存在 ti使 得 g 且 f,存在 t2使得 g 且 f。因為 g： ATB是函 數(shù)，貝 V ti= t2。又因 f:BTC 是函數(shù)，則 yi= y2。所以 A 中的每個元

57、素對應(yīng) C 中惟一的元 素。綜上可知, f g 是 A 到 C 的函數(shù)。對任意的 x A，由 g： ATB是函數(shù)，有 g 且 g(x) B,又由 f：BTC 是函數(shù)，得 f，于是 g*f= f g。又因 f g 是 A 到 C 的函數(shù)， 則可寫為 f g(x)= f(g(x)。八、 (15 分)設(shè) 是 的子群，定義 R= |a、b G 且 ab H, 則R 是 G 中的一個等價關(guān)系，且 aR= aH。證明 對于任意 a G,必有 a1 G 使得 a1*a = e H，所以 R。若 R,則 a1*b H。因為 H 是 G 的子群，故(a1*b)1= b1*a H。所以 R。若 R, R,則 a1

58、*b H , b1*c H。因為 H 是 G 的子群，所以(a1*b)*( b1*c) = a1*c H，故 R。綜上可得，R 是 G 中的一個等價關(guān)系。對于任意的 b aR,有 R, a1*b H ,則存在 h H 使得 a1*b= h, b= a*h,b R,故 aH aR。所以，aR= aH。證明：(PAQAA C)A(A PVQVC) ( PVQVAVC)A( AVPVQVC)(PVQVAVC)A( AVPVQVC) (PVQVA)A( AVPVQ)VC(PAQAA)V(AAPAQ)VC (AA(PAQ)V( PAQ)VC (AA(P Q)VC(AA(P Q) Co(F T)V(F T

59、)A(F T)V(F T)(P(1) R(1)A(P(1) R(2)V(P(2)(T F)A(T F)V(T F)A(T F)是 b aH，RaH。對任意的 b aH ,存在 h H 使得 b = a*h, a1*b= h H, a,離（B卷答案9）、(10 分)證明(PAQAA C)A(APVQVC) (AA(P Q) Co、（10 分）舉例說明下面推理不正確：x y(P(x) Q(y),y z( R( y) Q(z) Ix z(P(x) R(z)o解: 設(shè)論域為1 , 2，令 P(1) = P(2) = T ; Q(1) = Q(2) = T;R(1) = R(2) = F。則:y(P(x

60、)Q(y)x(P(x)Q(1)V(P(x)Q(2)(P(1) Q(1)V(P(1) Q(2)A(P(2)Q(1)V(P(2)z(R(y)Q(z)(T T)V(T T)A(TT)V(T T)y(R(y) Q(1)V(R(y)Q(2)(R(1) Q(1)V(R(1)Q(2)A(R(2)Q(1)V(R(2)z(P(x)R(z)x(P(x)R(1)A(P(x)R(2)R(1)A(P(2) R(2)所以，X y(P(x) Q(y), y z(R(y) Q(z)l xz(P(x) R(z)不正確。三、(15 分)在謂詞邏輯中構(gòu)造下面推理的證明：所有牛都有角，有些動物是牛，所以，有些動物有角。解：令P(X):X是牛