离散数学期末试题

1 离散数学考试试题（A卷及答案） 一、（1 0 分）求(PQ)(P∧(Q∨R))的主析取范式 解：(PQ)(P∧(Q∨R))(( P∨Q))∨(P∧Q∧R)) (P∨Q)∨(P∧Q∧R)) (P∨Q∨P)∧(P∨Q∨Q)∧(P∨Q∨R) (P∨Q)∧(P∨Q∨R) (P∨Q∨(R∧R))∧(P∨Q∨R) (P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R) 0M ∧1M 2m ∨3m ∨4m ∨5m ∨6m ∨7m 二、（1 0 分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断： 甲说：王教授不是苏州人，是上海人。 乙说：王教授不是上海人，是苏州人。 丙说：王教授既不是上海人，也不是杭州人。 王教授听后说：你们 3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？ 解 设设 P：王教授是苏州人；Q：王教授是上海人；R：王教授是杭州人。则根据题意应有： 甲：P∧Q 乙：Q∧P 丙：Q∧R 王教授只可能是其中一个城市的人或者 3个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有Q∧P，因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为： ((P∧Q)∧((Q∧R)∨(Q∧R)))∨((Q∧P)∧(Q∧R)) (P∧Q∧Q∧R)∨(P∧Q∧Q∧R)∨(Q∧P∧Q∧R) (P∧Q∧R)∨(P∧Q∧R) P∧Q∧R T 因此，王教授是上海人。 三、（1 0 分）证明 tsr(R)是包含 R 的且具有自反性、对称性和传递性的最小关系。 证明 设 R 是非空集合 A 上的二元关系，则 tsr(R)是包含 R 的且具有自反性、对称性和传递性的关系。 若'R 是包含 R 的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知 r(R)'R 。则 2 sr(R)s( 'R )＝'R ，进而有tsr(R)t( 'R )＝'R 。 综上可知，tsr(R)是包含R 的且具有自反性、对称性和传递性的最小关系。 四、（1 5 分）集合A＝{a，b，c，d，e}上的二元关系R 为R＝{，，，，，，，，，，，，，}， (1)写出R 的关系矩阵。 (2)判断R 是不是偏序关系，为什么？ 解 (1) R 的关系矩阵为： 1000011000101001011011111)(RM (2)由关系矩阵可知，对角线上所有元素全为1，故R 是自反的；ijr ＋jir ≤1，故R 是反对...