离散数学考试试题

1、(10) x(P(x) A R(x)离散数学考试试题(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)的主析取范式与主合取范式，并写出其相应的成真赋值和成假赋值(15分)。主析取范式与析取范式的区别：主析取范式里每个括号里都必须有全部的变元。主析取范式可由析取范式经等值演算法算得。证明：公式法：因为(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,二进制m0 V mi V m2Vm3Vm7所以，公式(P (QV R»)A( PV (Q R»)为可满足式，其相应的成真赋值为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、式，其相应的成真赋值三、推理证明题（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是三个集合，证明(AU B) C= (A C)U(B C) (10分)证明：因为x 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-。八、证明整数集I上的模m同余关系R=<x,y>|xy(mod m)是等价关系。其中，x y(modm)的含义是 x-y可以被 m整除(15分)。X(modm)=y(modm

6、)证明：1) x I ,因为(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 分)。证明：因为f、g是双射，所以gf ： Z

7、C是双射，所以gf有逆函数(gf) -1： C-A同理 可推f-1g-1: 8A是双射。因为 <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。离散数学考试试题（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)析取三段论PT (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四、只要今天天气不好，就一定有考生不能提前进入考场，当且仅当所有考生提前进入考场，考试才能准时进行。所以，如果考试准时进行，那么天气就好(15分)。解：设P：今天天气好，Q：考试准日进行，A(e) ： e提前进入考场，个体域：考生的集合，则命题可符号化为：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是三个集合，证明 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>,求其关系

12、矩阵及关系图(10分)。有就是1,没就是0七、设 R=<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,求 r(R)、s(R)和 t(R),并作出它们及R的关系图(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>(对称闭包)t(R)=<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<2,2>,<5,1>,<5,4>,<5,5>(传递闭包)九、设 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恒等函数，由hogof =Ia可得f是单射，h是满射；因Ib恒等函数，由fohog=IB可得g是单射，f是满射；因I c恒等函数，由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,问：(1)有多少不同的由X到Y的关系？(2)有多少不同的由X到丫的影射？(3)有多少不同的由X到丫的单射，双射？(12分)G,*是个群，uC G定义G中的运算" "为a b=a*u-1*b ,对任意a,b C G, 求证：G,也是个群。证明：1) a,b C