1/6离散数学考试试题(A卷及答案）一、证明题（10分）1)(P∧Q∧AC)∧(AP∨Q∨C)(A∧(PQ))C。P<->Q=(p->Q)合取（Q->p）证明:(P∧Q∧AC)∧(AP∨Q∨C)(P∨Q∨A∨C)∧(A∨P∨Q∨C)((P∨Q∨A)∧(A∨P∨Q))∨C反用分配律((P∧Q∧A)∨(A∧P∧Q))∨C(A∧((P∧Q)∨(P∧Q)))∨C再反用分配律(A∧(PQ))∨C(A∧(PQ))C2)(PQ)PQ。证明：(PQ)((P∧Q))(P∨Q))PQ。二、分别用真值表法和公式法求(P(Q∨R))∧(P∨(QR))的主析取范式与主合取范式，并写出其相应的成真赋值和成假赋值（15分）。主析取范式与析取范式的区别：主析取范式里每个括号里都必须有全部的变元。主析取范式可由析取范式经等值演算法算得。证明：公式法：因为(P(Q∨R))∧(P∨(QR))(P∨Q∨R)∧(P∨(Q∧R)∨(Q∧R))(P∨Q∨R)∧(((P∨Q)∧(P∨R))∨(Q∧R))分配律(P∨Q∨R)∧(P∨Q∨Q)∧(P∨Q∨R)∧(P∨R∨Q)∧(P∨R∨R)(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)4M∧5M∧6M使（非P析取Q析取R）为0所赋真值，即100，二进制为40m∨1m∨2m∨3m∨7m所以，公式(P(Q∨R))∧(P∨(QR))为可满足式，其相应的成真赋值为000、001、010、011、111：成假赋值为：100、101、110。2/6真值表法：PQRQRP(Q∨R)P∨(QR)(P(Q∨R))∧(P∨(QR))00000101001110010111011110011001111101111111100111110001由真值表可知，公式(P(Q∨R))∧(P∨(QR))为可满足式，其相应的成真赋值为000、001、010、011、111：成假赋值为：100、101、110。三、推理证明题（10分）1）P∨Q，Q∨R，RSPS。证明：(1)P附加前提(2)P∨QP(3)QT(1)(2)，I（析取三段论）(4)Q∨RP(5)RT(3)(4)，I（析取三段论）(6)RSP(7)ST(5)(6)，I（假言推理）(8)PSCP2)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)3/6(10)x(P(x)∧R(x))(11)Q(y)∧x(P(x)∧R(x))五、已知A、B、C是三个集合，证明(A∪B)－C＝(A－C)∪(B－C)（10分）证明：因为x∈(A∪B)－Cx∈(A∪B)－Cx∈(A∪B)∧xC(x∈A∨x∈B)∧xC(x∈A∧xC)∨(x∈B∧xC)x∈(A－C)∨x∈(B－C)x∈(A－C)∪(B－C)所以，(A∪B)－C＝(A－C)∪(B－C)。八、证明整数集I上的模m同余关系R={|xy(modm)}是等价关系。其中，xy(modm)的含义是x-y可以被m整除（15分）。X(modm)=y(modm)证明：1）x∈I，因为（x-x）/m=0，所以xx(modm)，即xRx。2）x,y∈I，若xRy，则xy(modm)，即（x-y）/m=k∈I，所以（y-x）/m=-k∈I，所以yx(modm)，即yRx。3）x,y,z∈I，若xRy，yRz，则（x-y）/m=u∈I，（y-z）/m=v∈I，于是（x-z）/m=（x-y+y-z）/m=u+v∈I，因此xRz。九、若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是双射。因为∈f-1g-1存在z（∈g-1∈f-1）存在z（∈f∈g）∈gf∈（gf）-1,所以（gf）-1=f-1g-1。离散数学考试试题(B卷及答案）一、证明题（10分）1)((P∨Q)∧(P∧(Q∨R)))∨(P∧Q)∨(P∧R)T4/6证明:左端((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)xy(P(x)Q(y))(xP(x)yQ(y))证明：xy(P(x)Q(y))xy(P(x)∨Q(y))x(P(x)∨yQ(y))xP(x)∨yQ(y)xP(x)∨yQ(y)(xP(x)yQ(y))二、求命题公式(PQ)(P∨Q)的主析取范式和主合取范式（10分）解：(PQ)(P∨Q)(PQ)∨(P∨Q)(P∨Q)∨(P∨Q)(P∧Q)∨(P∨Q)(P∨P∨Q)∧(Q∨P∨Q)(P∨Q)M1析取要使之为假，即赋真值001，即M1m0∨m2∨m3使之为真三、推理证明题（10分）1)(P(QS))∧(R∨P)∧QRS证明：(1)R(2)R∨Pp(3)PT（1）（2）析取三段论(4)P(QS)p(5)QST（3）（4）I假言推理(6)QP(7)ST（5）（6）I假言推理(8)RSCP2)x(A(x)yB(y))，x(B(x)yC(y))xA(x)yC(y)。证明：(1)x(A(x)yB(y))P5/6(2)A(a)yB(y)T(1)ES(3)x(B(x)yC(y))P(4)x(B(x)C(c))T(3)ES(5)B(b)C(c)T(4）US(6)A(a)B(b)T(2)US(7)A(a)C(c)T(5)(6)I假言三段论(8)xA(x)C(c)T(7)UG(9)xA(x)yC(y)T(8)EG四、只要今天天气不好，就一定有考...
