离散数学试卷及答案.pdf

离散数学试题（ A 卷答案） 一、 （10 分）求 (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) M 0 ∧ M 1 m2 ∨m3 ∨ m4 ∨ m5 ∨m6 ∨ m7 二、 （10 分）在某次研讨会的休息时间， 3 名与会者根据王教授的口音分 别作出下述判断： 甲说：王教授不是苏州人，是上海人。 乙说：王教授不是上海人，是苏州人。 丙说：王教授既不是上海人，也不是杭州人。 王教授听后说：你们 3 人中有一个全说对了，有一人全说错了，还有一个 人对错各一半。试判断王教授是哪里人？ 解 设设 P：王教授是苏州人； Q：王教授是上海人； R：王教授是杭州人。 则根据题意应有： 甲： P∧Q 乙： Q ∧P 丙： Q ∧ R 王教授只可能是其中一个城市的人或者 3 个城市都不是。所以，丙至少说 对了一半。 因此，可得甲或乙必有一人全错了。 又因为， 若甲全错了， 则有 Q ∧P，因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教 授的话符号化为： 1 (( 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 因此，王教授是上海人。 三、 （10 分）证明 tsr( R) 是包含 R 的且具有自反性、对称性和传递性的最 小关系。 证明 设 R 是非空集合 A 上的二元关系，则由定理 4.19 知，tsr( R) 是包 含 R 的且具有自反性、对称性和传递性的关系。 若 R 是包含 R 的且具有自反性、 对称性和传递性的任意关系， 则由闭包的 定义知 r ( R) R 。由定理 4.15 和由定理 4.16 得 sr( R) s( R ) ＝ R ，进而有 tsr( R) t( R ) ＝ R 。 综上可知， tsr( R) 是包含 R 的且具有自反性、对称性和传递性的最小关系。 四、（15 分）集合 A ＝{ a ，b，c ，d，e} 上的二元关系 R 为 R＝{ a ，a， a ，b，a，c