离散数学试题A卷答案
一、证明题（10分）
1P∨Q∧P∧Q∨R∨P∧Q∨P∧RT证明左端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代入
2xPxQx∧xPxxPx∧Qx证明：xPxQx∧xPxxPxQx∧PxxPx∨Qx∧PxxPx∧QxxPx∧xQxxPx∧Qx
二、求命题公式PQP∨Q的主析取范式和主合取范式（10分）。解：PQP∨QPQ∨P∨QP∨Q∨P∨QP∧Q∨P∨QP∨P∨Q∧Q∨P∨QP∨QM1m0∨m2∨m3
三、推理证明题（10分）
1PQS∧R∨P∧QRS证明：（1）R附加前提
（2）R∨P（3）P
PT12，I
（4）PQS（5）QS（6）Q
PT34，IP
（7）S
T56，I
（8）RS
CP
2xPx∨Qx，xPxxQx
证明：1xPx
P
2Pc
T1，US
3xPx∨QxP
4Pc∨Qc
T3，US
5Qc
T24，I
6xQx
T5，EG
四、在边长为1的正方形内任意放置九个点，证明其中必存在三个点，使得由它们组成的三
角形（可能是退化的）面积不超过18（5分）。
f证明：把边长为1的正方形分成四个全等的小正方形，则至少有一个小正方形内有三个
点，它们组成的三角形（可能是退化的）面积不超过小正方形的一半，即18。
五、已知A、B、C是三个集合，证明A∩B∪CA∩B∪A∩C（10分）。
证明：∵xA∩（B∪C）xA∧x（B∪C）
xA∧（xB∨xC）
（xA∧xB）∨（xA∧xC）
x（A∩B）∨xA∩C
x（A∩B）∪（A∩C）
∴A∩（B∪C）（A∩B）∪（A∩C）
六、Ax1，x2，x3，By1，y2，Rx1，y1，x2，y2，x3，y2，求其关系矩阵
及关系图（10分）。
解：关系矩阵为
100010010
七、设R2，1，2，5，2，4，3，4，4，4，5，2，求rR、sR和tR，并作出它们及R的关系图（15分）。
解：rR2，1，2，5，2，4，3，4，4，4，5，2，1，1，2，2，3，3，4，4，5，5
sR2，1，2，5，2，4，3，4，4，4，5，2，1，2，4，2，4，3R2R52，2，2，4，3，4，4，4，5，1，5，5，5，4R32，1，2，5，2，4，3，4，4，4，5，2，5，4R42，2，2，4，3，4，4，4，5，1，5，5，5，4tR2，1，2，5，2，4，3，4，4，4，5，2，2，2，5，1，5，4，5，5八、A1，A2，…，A
是集合A的一个划分，定义Ra，ba、b∈Ai，I1，2，…，
，则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∈Air