离散数学考试试题(A、B卷及答案)

1、离散数学考试试题(A卷及答案）一、证明题（10分）1) (PQA®C)(A®PQC)Û (A(P«Q)®C。P<->Q=(p->Q)合取（Q->p）证明: (PQA®C)(A®PQC)Û(ØPØQØAC)(ØAPQC)Û(ØPØQØA)(ØAPQ)C反用分配律ÛØ(PQA)(AØPØQ)CÛØ( A(PQ)(ØPØQ)C再反

2、用分配律ÛØ( A(P«Q)CÛ(A(P«Q)®C2) Ø(P­Q)Û ØP¯ØQ。证明：Ø(P­Q)ÛØ(Ø(PQ)ÛØ(ØPØQ)ÛØP¯ØQ。2、 分别用真值表法和公式法求(P®(QR)(ØP(Q«R)的主析取范式与主合取范式，并写出其相应的成真赋值和成假赋值（15分）。主析取范式与析取范式的区别：主析取范式里每

3、个括号里都必须有全部的变元。主析取范式可由 析取范式经等值演算法算得。证明：公式法：因为(P®(QR)(ØP(Q«R)Û(ØPQR)(ØP(QR)(ØQØR)Û(ØPQR)(ØPQ)(ØPR)(ØQØR)分配律Û(ØPQR)(ØPQØQ)(ØPQØR)(ØPRØQ)(ØPRØR)Û(ØPQR)(ØPQØR)(Ø

4、;PØQR)Û使（非P析取Q析取R）为0所赋真值，即100，二进制为4Û所以，公式(P®(QR)(ØP(Q«R)为可满足式，其相应的成真赋值为000、001、010、011、111：成假赋值为：100、101、110。真值表法：P Q RQ«RP®(QR)ØP(Q«R)(P®(QR)(ØP(Q«R)0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 110011001111101111111100111110001由真值表可知，公式(P&#

5、174;(QR)(ØP(Q«R)为可满足式，其相应的成真赋值为000、001、010、011、111：成假赋值为：100、101、110。三、推理证明题（10分）1）ØPQ，ØQR，R®SP®S。证明：(1)P 附加前提(2)ØPQ P(3)Q T(1)(2)，I（析取三段论）(4)ØQR P(5)R T(3)(4)，I（析取三段论）(6)R®S P(7)S T(5)(6)，I（假言推理）(8)P®S CP2) "x(P(x)®Q(y)R(x)，$xP(x)ÞQ(y

6、)$x(P(x)R(x)证明（1）$xP(x)(2)P(a)(3)"x(P(x)®Q(y)R(x)(4)P(a)®Q(y)R(a)(5)Q(y)R(a)(6)Q(y)(7)R(a)(8)P(a)(9)P(a)R(a)(10)$x(P(x)R(x)(11)Q(y)$x(P(x)R(x)五、已知A、B、C是三个集合，证明(AB)C(AC)(BC) （10分）证明：因为(AB)CÛ(AB)C Û(AB)ÏCÛ(AB)ÏCÛ(AÏC)(BÏC)Û(AC)(BC)Û(AC)(

7、BC)所以，(AB)C(AC)(BC)。八、证明整数集I上的模m同余关系R=<x,y>|xºy(mod m)是等价关系。其中，xºy(mod m)的含义是x-y可以被m整除（15分）。X(modm)=y(modm)证明：1）"xI，因为（x-x）/m=0，所以xºx(mod m)，即xRx。2）"x,yI，若xRy，则xºy(mod m)，即（x-y）/m=kI，所以（y - x）/m=-kI，所以yºx(mod m)，即yRx。3）"x,y,zI，若xRy，yRz，则（x-y）/m=uI，（y-z）/

8、m=vI，于是（x-z）/m=（x-y+y-z）/m=u+v I，因此xRz。九、若f:AB和g:BC是双射，则（gf）-1=f-1g-1（10分）。证明：因为f、g是双射，所以gf：AC是双射，所以gf有逆函数（gf）-1：CA。同理可推f-1g-1：CA是双射。因为<x,y>f-1g-1Û存在z（<x,z>g-1Ù<z,y>f-1）Û存在z（<y,z>fÙ<z,x>g）Û<y,x>gfÛ<x,y>（gf）-1,所以（gf）-1=f-1g-1。离散数

9、学考试试题(B卷及答案）一、证明题（10分）1)(PQ)Ø(ØP(ØQØR)(ØPØQ)(ØPØR)ÛT证明: 左端Û(PQ)(P(QR)Ø(PQ)(PR)(摩根律) Û (PQ)(PQ)(PR)Ø(PQ)(PR)(分配律) Û (PQ)(PR)Ø(PQ)(PR) (等幂律) ÛT(代入)2) "x"y(P(x)®Q(y)Û($xP(x)®"yQ(y)证明："x&qu

10、ot;y(P(x)®Q(y)Û"x"y(ØP(x)Q(y)Û"x(ØP(x)"yQ(y)Û"xØP(x)"yQ(y)ÛØ$xP(x)"yQ(y)Û($xP(x)®"yQ(y)二、求命题公式(ØP®Q)®(PØQ) 的主析取范式和主合取范式（10分）解：(ØP®Q)®(PØQ)ÛØ(ØP®Q

11、)(PØQ)ÛØ(PQ)(PØQ)Û(ØPØQ)(PØQ) Û(ØPPØQ)(ØQPØQ)Û(PØQ)ÛM1析取要使之为假，即赋真值001，即M1Ûm0m2m3使之为真三、推理证明题（10分）1)(P®(Q®S)(ØRP)QÞR®S证明：(1)R(2)ØRPp(3)PT（1）（2）析取三段论(4)P®(Q®S)p(5)Q®S T（3）（4

12、）I假言推理(6)QP(7)ST（5）（6）I假言推理(8)R®SCP2) $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() T(3)ES(5)B()®C() T(4）US(6)A(a)®B() T(2)US(7)A(a)®C(

13、) T(5)(6)I假言三段论(8)"xA(x)®C() T(7)UG(9)"xA(x)®$yC(y) T(8)EG四、只要今天天气不好，就一定有考生不能提前进入考场，当且仅当所有考生提前进入考场，考试才能准时进行。所以，如果考试准时进行，那么天气就好（15分）。解 ：设P：今天天气好，Q：考试准时进行，A(e)：e提前进入考场，个体域：考生的集合，则命题可符号化为：ØP®$xØA(x)，"xA(x)«QQ®P。(1)ØP®$xØA(x) P(2)ØP&#

14、174;Ø"xA(x) T(1)E(3)"xA(x)®P T(2)E (4)"xA(x)«Q P(5)("xA(x)®Q)(Q®"xA(x) T(4)E(6)Q®"xA(x) T(5)I(7)Q®P T(6)(3)I五、已知A、B、C是三个集合，证明A(BC)=(AB)(AC) （10分）证明：xÎ A（BC）Û xÎ AxÎ（BC）Û xÎ A（xÎBxÎC）Û（ x

15、6; AxÎB）（xÎ AxÎC）Û xÎ（AB）xÎ ACÛ xÎ（AB）（AC）A（BC）=（AB）（AC）六、A= x1,x2,x3 ，B= y1,y2，R=<x1, y1>,<x2, y2>,<x3, y2>，求其关系矩阵及关系图（10分）。有就是1，没就是0七、设R=<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>，求r(R)、s(R)和t(R)，并作出它们及R的关系图（15分

16、）。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>,<3,4>,<4,4>,<5,2>,<1,2>,<4,2>,<4,3>（对称闭包）t(R)=<2,1>,<2,5>,<2,4>,<3,4>

17、;,<4,4>,<5,2>,<2,2>,<5,1>,<5,4>,<5,5>（传递闭包）九、设f：A®B，g：B®C，h：C®A，证明：如果hogofIA，fohogIB，gofohIC，则f、g、h均为双射，并求出f1、g1和h1（10分）。解 因IA恒等函数，由hogofIA可得f是单射，h是满射；因IB恒等函数，由fohogIB可得g是单射，f是满射；因IC恒等函数，由gofohIC可得h是单射，g是满射。从而f、g、h均为双射。由hogofIA，得f1hog；由fohogIB，得g1foh；由gofohIC，得h1gof。5. (12分)令X=x1,x2,.,xm,Y=y1,y2,.,yn,问:(1) 有多少不同的由X到Y的关系?(2) 有多少不同的由X到Y的影射?(3) 有多少不同的由X到Y的单射，双射?（12分）<G,*>是个群，uG，定义G中的运算“D”为aDb=a