离散数末试题.docVIP

离散数学考试试题（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) (∧ (∨∨∨∨∨ 二、（10分）在某次研讨会的休息时间，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 因此，王教授是上海人。 三、（10分）证明tsr(R)是包含R的且具有自反性、对称性和传递性的最小关系。 证明 设R是非空集合A上的二元关系，则tsr(R)是包含R的且具有自反性、对称性和传递性的关系。 若是包含R的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r(R)(。则sr(R)(s()＝，进而有tsr(R)(t()＝。 综上可知，tsr(R)是包含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是不是偏序关系，为什么？ 解 (1) R的关系矩阵为： (2)由关系矩阵可知，对角线上所有元素全为1，故R是自反的；＋≤1，故R是反对称的；可计算对应的关系矩阵为： 由以上矩阵可知R是传递的。 五、（10分）设A、B、C和D为任意集合，证明(A－B)×C＝(A×C)－(B×C)。 证明：因为 ，∈(A－B)×C(∈(A－B)∧∈C ((∈A∧(B)∧∈C ((∈A∧∈C∧(B)∨(∈A∧∈C∧(C) ((∈A∧∈C)∧((B∨(C) ((∈A∧∈C)∧((∈B∧∈C) (，∈(A×C)∧，((B×C) (，∈(A×C)－(B×C) 所以，(A－B)×C＝(A×C－B×C)。 六、（10分）设f：A(B，g：B(C，h：C(A，证明：如果h(g(f＝IA，(h(g＝IB，(f(h＝IC，(g(f＝IA可得f是单射，h是满射；因IB恒等函数，由f(h(g＝IB可得g是单射，f是满射；因IC恒等函数，由g(f(h＝IC可得h是单射，g是满射。从而f、g、h均为双射。 由h(g(f＝IA，(g；由f(h(g＝IB，(h；由g(f(h＝IC，(f。 七、（15分）设G，*是一代数系统，运算*满足交换律和结合律，且a*x＝ay(x＝y，，…，}。由a*x＝ay(x＝yx≠y，则a*x≠a*y。于是可证，对任意的a∈G，有aG＝G。又因为运算*满足交换律，所以aG＝G＝Ga。令e∈G使得a*e＝a＝＝＝＝＝＝＝＝、、…、。由连通性，必存在与相邻的结点，不妨设它为（否则可重新编号），连接和，得边，还是由连通性，在、、…、中必存在与或相邻的结点，不妨设为，将其连接得边，续行此法，必与、、…、中的某个结点相邻，得新边，由此可见G中至少有n－1条边。 （2）给定简单无向图G＝V，E，且|V|＝m，|E|＝n。试证：若n≥＋2，则G是哈密尔顿图。 证明 若n≥＋2，则2n≥m2－3m＋6 （1）。 若存在两个不相邻结点、使得d()＋d()＜m，则有2n＝＜m＋(m－2)(m－3)＋m＝m2－3m＋6，与（1）矛盾。所以，对于G中任意两个不相邻结点、都有d()＋d()≥m。由定理10.26可知，G是哈密尔顿图。 离散数考试试题（B卷及答案） 一、（10分）使用将命题公式化为主范式的方法，证明(P(Q)((P∧Q)((Q(P)∧(P∨Q)。 证明：因为(P(Q)((P∧Q)((((P∨Q)∨(P∧Q) ((P∧(Q)∨(P∧Q) (Q(P)∧(P∨Q)(((Q∨P)∧