离散数学试题(A卷及答案）一、证明题（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(2)E(A∧B)(3)(C∨D)(A∧B)(4)(A∧B)(R∨S)(5)(C∨D)(R∨S)(6)C∨D(7)R∨S2)x(P(x)Q(y)∧R(x))，xP(x)Q(y)∧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是三个集合，证明A-(B∪C)=(A-B)∩(A-C)（15分）证明 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={<x,y>|x,yN∧y=x2}，S={<x,y>|x,yN∧y=x+1}。求R-1、R*S、S*R、R{1,2}、S[{1,2}]（10分）解：R-1={<y,x>|x,yN∧y=x2}，R*S={<x,y>|x,yN∧y=x2+1}，S*R={<x,y>|x,yN∧y=（x+1）2}，七、若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是双射。因为<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。R{1,2}={<1,1>,<2,4>}，S[{1,2}]={1,4}。离散数学试题(B卷及答案）一、证明题（10分）1)((P∨Q)∧(P∧(Q∨R)))∨(P∧Q)∨(P∧R)T证明左端((P∨Q)∧(P∨(Q∧R)))∨((P∨Q)∧(P∨R))(摩根律)((P∨Q)∧(P∨Q)∧(P∨R))∨((P∨Q)∧(P∨R))(分配律)((P∨Q)∧(P∨R))∨((P∨Q)∧(P∨R))(等幂律)T(代入)2)x(P(x)Q(x))∧xP(x)x(P(x)∧Q(x))证明x(P(x)Q(x))∧xP(x)x((P(x)Q(x)∧P(x))x((P(x)∨Q(x)∧P(x))x(P(x)∧Q(x))xP(x)∧xQ(x)x(P(x)∧Q(x))二、求命题公式(PQ)(P∨Q)的主析取范式和主合取范式（10分）解：(PQ)(P∨Q)(PQ)∨(P∨Q)(P∨Q)∨(P∨Q)(P∧Q)∨(P∨Q)(P∨P∨Q)∧(Q∨P∨Q)(P∨Q)M1m0∨m2∨m3三、推理证明题（10分）1)(P(QS))∧(R∨P)∧QRS证明：（1）R附加前提(2)R∨PP(3)PT(1)(2),I(4)P(QS)P(5)QST(3)(4),I(6)QP(7)ST(5)(6),I(8)RSCP2)x(P(x)∨Q(x))，xP(x)xQ(x)证明：(1)xP(x)P(2)P(c)T(1),US(3)x(P(x)∨Q(x))P(4)P(c)∨Q(c)T(3),US(5)Q(c)T(2)(4),I(6)xQ(x)T(5),EG五、已知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）六、={A1，A2，…，An}是集合A的一个划分，定义R={<a，b>|a、b∈Ai，I=1，2，…，n}，则R是A上的等价关系（15分）。证明：a∈A必有i使得a∈Ai，由定义知aRa，故R自反。a,b∈A，若aRb，则a,b∈Ai，即b,a∈Ai，所以bRa，故R对称。a,b,c∈A，若aRb且bRc，则a,b∈Ai及b,c∈Aj。因为i≠j时Ai∩Aj=，故i=j，即a,b,c∈Ai，所以aRc，故R传递。总...