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

《离散数学考试试题(A、B卷及答案)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、离散数学考试试题(A卷及答案）一、证明题（10分）1)(P∧Q∧A®C)∧(A®P∨Q∨C)Û(A∧(P«Q))®C。P<->Q=(p->Q)合取（Q->p）证明:(P∧Q∧A®C)∧(A®P∨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∧(P«Q))∨CÛ(A∧(P«Q))®C2)Ø(PQ)ÛØP¯ØQ。证明：Ø(PQ)ÛØ(Ø(P∧Q))ÛØ(ØP∨ØQ)

2、)ÛØP¯ØQ。二、分别用真值表法和公式法求(P®(Q∨R))∧(ØP∨(Q«R))的主析取范式与主合取范式，并写出其相应的成真赋值和成假赋值（15分）。主析取范式与析取范式的区别：主析取范式里每个括号里都必须有全部的变元。主析取范式可由析取范式经等值演算法算得。证明：公式法：因为(P®(Q∨R))∧(ØP∨(Q«R))Û(Ø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

3、∨ØR)Û(ØP∨Q∨R)∧(ØP∨Q∨ØR)∧(ØP∨ØQ∨R)Û∧∧使（非P析取Q析取R）为0所赋真值，即100，二进制为4Û∨∨∨∨所以，公式(P®(Q∨R))∧(ØP∨(Q«R))为可满足式，其相应的成真赋值为000、001、010、011、111：成假赋值为：100、101、110。真值表法：PQRQ«RP®(Q∨R)ØP∨(Q«R)(P®(Q∨R))∧(ØP∨(Q«R))00000101001110010111011110011001111101111111100111110001由真值表可知，公式(P®(Q∨R))∧(ØP∨

4、(Q«R))为可满足式，其相应的成真赋值为000、001、010、011、111：成假赋值为：100、101、110。三、推理证明题（10分）1）ØP∨Q，ØQ∨R，R®SP®S。证明：(1)P附加前提(2)ØP∨QP(3)QT(1)(2)，I（析取三段论）(4)ØQ∨RP(5)RT(3)(4)，I（析取三段论）(6)R®SP(7)ST(5)(6)，I（假言推理）(8)P®SCP2)"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

5、(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－C)∪(B－C)（10分）证明：因为∈(A∪B)－CÛ∈(A∪B)－CÛ∈(A∪B)∧ÏCÛ(∈A∨∈B)∧ÏCÛ(∈A∧ÏC)∨(∈B∧ÏC)Û∈(A－C)∨∈(B－C)Û∈(A－C)∪(B－C)所以，(A∪B)－C＝(A－C)∪(B－C)。八、证明整数集I上的模m同余关系R

6、={

7、xºy(modm)}是等价关系。其中，xºy(modm)的含义是x-y可以被m整除（15分）。X(modm)=y(modm)证明：1）"x∈I，因为（x-x）/m=0，所以xºx(modm)，即xRx。2）"x,y∈I，若xRy，则xºy(modm)，即（x-y）/m=k∈I，所以（y-x）/m=-k∈I，所以yºx(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

8、是双射，则（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)ÛT证明:左端Û((P∨Q)∧(P∨(Q∧R))

9、)∨Ø((P∨Q)∧(P∨R))(摩根律)Û((P∨Q)∧(P∨Q)∧(P∨R))∨Ø((P∨Q)∧(P∨R))(分配律)Û((P∨Q)∧(P∨R))∨Ø((P∨Q)∧(P∨R))(等幂律)Û