離散數(shù)學(xué)考試試題

1、(10) x(P(x) A R(x)離散數(shù)學(xué)考試試題(A卷及答案)一、證明題(10分)1) (PA 8 AC)A (APV QV C(AA(P Q)C。P<->Q=(p->Q)合取(Q->p)證明：(PAQA C) A(A PV QV C)(PV QV AV C) A( AV PV QV C)(PV QV A) A ( AV PV Q) V C反用分配律(PAQAA) V(AA PAQ) V C(A A ( PA Q V ( PA Q) V C再反用分配律(AA (P Q) VC(AA(P Q)C2) (P Q) P Q證明： (P Q) ( (PAQ)( PV Q)

2、P Q二、分別用真值表法和公式法求(P (QV討)A( PV (QF)的主析取范式與主合取范式，并寫出其相應(yīng)的成真賦值和成假賦值(15分)。主析取范式與析取范式的區(qū)別：主析取范式里每個(gè)括號(hào)里都必須有全部的變?cè)?。主析取范式可由析取范式?jīng)等值演算法算得。證明：公式法：因?yàn)?P (QV R) A ( PV (Q R)(PVQVF)A(PV(QAF)V( QR»)(PVQVR A (PVQ A ( PVR)V(QAR)分配律(PVQVR)A ( PVQVQ A (PVQVR)A( PVRVQ A ( P(PV QV R A ( PV QR) A ( PVQV R)M 4AM5AM 6使(非P

3、析取Q析取R)為0所賦真值，即100,二進(jìn)制m0 V mi V m2Vm3Vm7所以，公式(P (QV R»)A( PV (Q R»)為可滿足式，其相應(yīng)的成真賦值為000、001、真值表法:P Q RQ RP (QV R)PV (Q R(P (QV R) A( PV (Q R)0 0 011110 0 101110 1 001110 1 111111 0 010101 0 101001 1 001001 1 11111由真值表可知，公式（P （QV R） A （為 000、 001、 010、 011、111:成假賦值為:100、 101、 110。PV （Q R）為可滿足

4、式，其相應(yīng)的成真賦值三、推理證明題（10分）1） PV QQV R R S P So證明：P(2) PVQP(3) QT(1)(2)(4) QRP(5) RT(3)(4)(6) RSP(7) ST(5)(6)(8) PSCP附加前提,I （析取三段論）,I （析取三段論）,I （假言推理）xP(x)Q(y) A x(P(x) A R(x)2） x(P(x) Q(y) A R(x), 證明(1) xP(x)(2)P(a)(3) x(P(x) Q(y) A R(x)(4)P(a) Q(y) A R(a)(5)Q(y) A R(a)(6)Q(y)R(a)(8)P(a)(9)P(a) A R(a)(1

5、1)Q(y) A x(P(x) AR(x)五、已知 A B、C是三個(gè)集合，證明(AU B) C= (A C)U(B C) (10分)證明：因?yàn)閤 C (AU B) C x C (AU B)-Cx (AU E) A x C(xCAV x B) A x C(xCAA x QV(xCBA x Cx C (A- C V x (B- Cx £ (A-C U(B-C)所以，(AU 6C= (A- C) u (B-。八、證明整數(shù)集I上的模m同余關(guān)系R=<x,y>|xy(mod m)是等價(jià)關(guān)系。其中，x y(modm)的含義是 x-y可以被 m整除(15分)。X(modm)=y(modm

6、)證明：1) x I ,因?yàn)?x-x ) /m=0,所以 x x(mod m),即 xRx。2) x,y C I ,若 xRy,則 x y(mod m),即(x-y ) /m=kC I ,所以(y - x ) /m=-k CI,所以 y x(mod m),即 yRx。3) x,y,z C I ,若 xRy, yRz,則(x-y ) /m=u C I , (y-z ) /m=v I ,于是(x-z ) /m= (x-y+y-z ) /m=u+v C I ,因止匕 xRz。九、若 f:AfB和 g:B-C是雙射，則(gf) -1=f-1g-1 (10 分)。證明：因?yàn)閒、g是雙射，所以gf ： Z

7、C是雙射，所以gf有逆函數(shù)(gf) -1： C-A同理 可推f-1g-1: 8A是雙射。因?yàn)?<x,y> Cf-1g-1 存在 z (<x,z> C g-1 <z,y> Cf-1) 存在 z (<y,z> f <z,x>C g)<y,x> e gf <x,y> £ ( gf ) -1,所以(gf ) -1 =f-1 g-1。離散數(shù)學(xué)考試試題（B卷及答案）、證明題（10分）1)(P VQ)A(PA (QVR) V(PAQ)V (PAR) T(P VQ)A(P V R)(摩根律)證明：左端 (P VQ)A

8、(PV(QAR) V(P VQ)A (PVQ)A(PVR) V (P V Q)A (P V R)(分配律)(P VQ)A (PV R) V (P V Q)A (P V R)(等P律)T(代入)2) x y(P(x)Qy)(xP(x)yQy)證明：x y(P(x) Qy)x y( Rx)vQy)x(P(x) VyQy)xP(x) VyQy)xP(x) V yQy)(xP(x)yCKy)二、求命題公式(P Q)(P VQ）的主析取范式和主合取范式（10分）解：(P Q) (P V Q)(P Q) V (P V Q)(PVQ)V(PV Q)(PAQ) V (P V Q)(PV PV Q) A ( Q

9、V PV Q)(P V Q)M1析取要使之為假，即賦真值001,即M1mOV m2V m3使之為真三、推理證明題（10分）1)(P (Q S) A ( RV P) AQ R S證明：(1)R(2)RV P(3)P(4)P (Q S)(5)Q S(6)QS(8)R S2)x(A(x)yB(y) ,x(B(x)證明：(1)x(A(x)yRy)(2) A(a)yB(y)pT (1) (2)析取三段論P(yáng)T (3) (4) I假言推理PT (5) (6) I假言推理CPyC(y)卜 xA(x)yQy)。PT(1)ES(3)x(B(x)yC(y)P(4)x(B(x)Qc)T(3)ES Rb) qc)(6)

10、 A(a)B(b)代a)C(c)(8) xA(x) Qc)(9) xA( x)yC( y)T(4) UST(2)UST(5)(6)I假言三段論T(8)EGTUG四、只要今天天氣不好，就一定有考生不能提前進(jìn)入考場(chǎng)，當(dāng)且僅當(dāng)所有考生提前進(jìn)入考場(chǎng)，考試才能準(zhǔn)時(shí)進(jìn)行。所以，如果考試準(zhǔn)時(shí)進(jìn)行，那么天氣就好(15分)。解：設(shè)P：今天天氣好，Q：考試準(zhǔn)日進(jìn)行，A(e) ： e提前進(jìn)入考場(chǎng)，個(gè)體域：考生的集合，則命題可符號(hào)化為：P x A(x), xA(x) QkQ P。(1) P x A(x)P(2) PxA(x)T(1) E(3) xA(x)PT(2)E(4) xA(x)QP(5)(xA(x)QA(QxA

11、(x)T(4) E(6) QxA(x)T(5) I(7) Q PT(6)(3) I五、已知 A B、C是三個(gè)集合，證明 An (B U C)=(A n B) U (A n C) (10分)證明： x An ( BU C)xAA x(BU C)x AA (x BV x C)( x AAx B) V (x A Ax C)x (AAB) V xAAC x(AA B) U ( AA C)，a n( bu C)= (An B)u(An C)六、A= x 1,x 2,x 3 , B= y 1,y 2,R=<xi, yi>,<x2, y2>,<x 3, y 2>,求其關(guān)系

12、矩陣及關(guān)系圖(10分)。有就是1,沒就是0七、設(shè) R=<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,求 r(R)、s(R)和 t(R),并作出它們及R的關(guān)系圖(15分)。r(R)=<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,1>,<2,2>,<3,3><5,5>(自反閉包)s(R)=<2,1>,<2,5>,<2,4&

13、gt;,<3,4>,<4,4>,<5,2>,<1,2>,<4,2>,<4,3>(對(duì)稱閉包)t(R)=<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<2,2>,<5,1>,<5,4>,<5,5>(傳遞閉包)九、設(shè) f ： AB,g： BC,h： CA,證明：如果hogof = I a,f ohog= I b,gofoh=Ic,則f、g、h均為雙射，并求出 f1、g-1和h7(10分

14、)。解 因Ia恒等函數(shù)，由hogof =Ia可得f是單射，h是滿射；因Ib恒等函數(shù)，由fohog=IB可得g是單射，f是滿射；因I c恒等函數(shù)，由gof oh= I c可得h是單射，g是滿射。 從而f、g、h均為雙射。由 hogof = I a,得 f 1= hog；由 f ohog= I b,得 g 1 = f oh；由 gof oh= I c,得 h 1= gof。五.(12 分)令 X=x1,x2，,xm,Y=y1,y2,yn,問(wèn)：(1)有多少不同的由X到Y(jié)的關(guān)系？(2)有多少不同的由X到丫的影射？(3)有多少不同的由X到丫的單射，雙射？(12分)G,*是個(gè)群，uC G定義G中的運(yùn)算" "為a b=a*u-1*b ,對(duì)任意a,b C G, 求證：G,也是個(gè)群。證明：1) a,b C