
离散数学期末考试试题及答案.doc
30页离散数学试题(B卷答案1)一、证明题(10分)1)(ØP∧(ØQ∧R))∨(Q∧R)∨(P∧R)ÛR证明: 左端Û(ØP∧ØQ∧R)∨((Q∨P)∧R)Û((ØP∧ØQ)∧R))∨((Q∨P)∧R)Û(Ø(P∨Q)∧R)∨((Q∨P)∧R)Û(Ø(P∨Q)∨(Q∨P))∧RÛ(Ø(P∨Q)∨(P∨Q))∧RÛT∧R(置换)ÛR2) $x (A(x)®B(x))Û "xA(x)®$xB(x)证明 :$x(A(x)®B(x))Û$x(ØA(x)∨B(x))Û$xØA(x)∨$xB(x)ÛØ"xA(x)∨$xB(x)Û"xA(x)®$xB(x)二、求命题公式(P∨(Q∧R))®(P∧Q∧R)的主析取范式和主合取范式(10分)证明:(P∨(Q∧R))®(P∧Q∧R)ÛØ(P∨(Q∧R))∨(P∧Q∧R))Û(ØP∧(ØQ∨ØR))∨(P∧Q∧R)Û(ØP∧ØQ)∨(ØP∧ØR))∨(P∧Q∧R)Û(ØP∧ØQ∧R)∨(ØP∧ØQ∧ØR)∨(ØP∧Q∧ØR))∨(ØP∧ØQ∧ØR))∨(P∧Q∧R)Ûm0∨m1∨m2∨m7ÛM3∨M4∨M5∨M6三、推理证明题(10分)1) C∨D, (C∨D)® ØE, ØE®(A∧ØB), (A∧ØB)®(R∨S)ÞR∨S证明:(1) (C∨D)®ØE P(2) ØE®(A∧ØB) P(3) (C∨D)®(A∧ØB) T(1)(2),I(4) (A∧ØB)®(R∨S) P(5) (C∨D)®(R∨S) T(3)(4), I(6) C∨D P(7) R∨S T(5),I 2) "x(P(x)®Q(y)∧R(x)),$xP(x)ÞQ(y)∧$x(P(x)∧R(x))证明(1)$xP(x) P(2)P(a) T(1),ES(3)"x(P(x)®Q(y)∧R(x)) P(4)P(a)®Q(y)∧R(a) T(3),US(5)Q(y)∧R(a) T(2)(4),I(6)Q(y) T(5),I(7)R(a) T(5),I(8)P(a)∧R(a) T(2)(7),I(9)$x(P(x)∧R(x)) T(8),EG(10)Q(y)∧$x(P(x)∧R(x)) T(6)(9),I四、某班有25名学生,其中14人会打篮球,12人会打排球,6人会打篮球和排球,5人会打篮球和网球,还有2人会打这三种球。
而6个会打网球的人都会打另外一种球,求不会打这三种球的人数(10分)解:A,B,C分别表示会打排球、网球和篮球的学生集合则|A|=12,|B|=6,|C|=14,|A∩C|=6,|B∩C|=5,|A∩B∩C|=2先求|A∩B|∵6=|(A∪C)∩B|=|(A∩B)∪(B∩C)|=|(A∩B)|+|(B∩C)|-|A∩B∩C|=|(A∩B)|+5-2,∴|(A∩B)|=3于是|A∪B∪C|=12+6+14-6-5-3+2=20不会打这三种球的人数25-20=5五、已知A、B、C是三个集合,证明A-(B∪C)=(A-B)∩(A-C) (10分)证明:∵xÎ A-(B∪C)Û xÎ A∧xÏ(B∪C)Û xÎ A∧(xÏB∧xÏC)Û(xÎ A∧xÏB)∧(xÎ A∧xÏC)Û xÎ(A-B)∧xÎ(A-C)Û xÎ(A-B)∩(A-C)∴A-(B∪C)=(A-B)∩(A-C)六、已知R、S是N上的关系,其定义如下:R={
七、设R={,,
九、若f:A→B和g:B→C是双射,则(gf)-1=f-1g-1(10分)证明:因为f、g是双射,所以gf:A→C是双射,所以gf有逆函数(gf)-1:C→A同理可推f-1g-1:C→A是双射因为
证明:(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() 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)«®P1)ØP®$xØA(x) P(2)ØP®Ø"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∩(B∪C)=(A∩B)∪(A∩C) (10分)证明:∵xÎ A∩(B∪C)Û xÎ A∧xÎ(B∪C)Û xÎ A∧(xÎB∨xÎC)Û( xÎ A∧xÎB)∨(xÎ A∧xÎC)Û xÎ(A∩B)∨xÎ A∩CÛ xÎ(A∩B)∪(A∩C)∴A∩(B∪C)=(A∩B)∪(A∩C)六、A={ x1,x2,x3 },B={ y1,y2},R={
七、设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>,<4,4>,<5,5>}s(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,2>,<4,2>,<4,3>}R2=R5={<2,2>,<2,4>,<3,4>,<4,4>,<5,1>,<5,5>,<5,4>}R3={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<5,4>}R4={<2,2>,<2,4>,<3,4>,<4,4>,<5,1>,<5,5>,<5,4>}t(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<2,2>,<5,1>,<。
