离散试卷及答案
离散数学（A卷及答案）
一、（10分）求PQP∧Q∨R的主析取范式解：PQP∧Q∨RP∨Q∨P∧Q∧RP∨Q∨P∧Q∧RP∨Q∨P∧P∨Q∨Q∧P∨Q∨RP∨Q∧P∨Q∨RP∨Q∨R∧R∧P∨Q∨RP∨Q∨R∧P∨Q∨R∧P∨Q∨RM0∧M1m2∨m3∨m4∨m5∨m6∨m7二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断：
甲说：王教授不是苏州人，是上海人。乙说：王教授不是上海人，是苏州人。丙说：王教授既不是上海人，也不是杭州人。王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？解设设P：王教授是苏州人；Q：王教授是上海人；R：王教授是杭州人。则根据题意应有：
甲：P∧Q乙：Q∧P丙：Q∧R王教授只可能是其中一个城市的人或者3个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有Q∧P，因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为：P∧Q∧Q∧R∨Q∧R∨Q∧P∧Q∧RP∧Q∧Q∧R∨P∧Q∧Q∧R∨Q∧P∧Q∧RP∧Q∧R∨P∧Q∧RP∧Q∧RT因此，王教授是上海人。
第1页共26页
f离散试卷及答案
三、（10分）证明tsrR是包含R的且具有自反性、对称性和传递性的最小关系。
证明设R是非空集合A上的二元关系，则由定理419知，tsrR是包含R的且具有自反性、对称性和传递性的关系。若R是包含R的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知rRR。由定理415和由定理416得srRsR＝R，进而有tsrRtR＝R。综上可知，tsrR是包含R的且具有自反性、对称性和传递性的最小关系。四、（15分）集合A＝a，b，c，d，e上的二元关系R为R＝a，a，a，b，a，c，a，d，a，e，b，b，b，c，b，e，c，c，c，d，c，e，d，d，d，e，e，e，1写出R的关系矩阵。2判断R是不是偏序关系，为什么？

解
1R的关系矩阵为：
10MR000
11111101010100110001
2由关系矩阵可知，对角线上所有元素全为1，故R是自反的；rij＋rji≤1，故R是反对称的；可计算对应的关系矩阵为：
102MR000
由以上矩阵可知R是传递的。
111111010101Mr