离散数学试卷及答案.doc

《离散数学试卷及答案.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、.离散数学试题（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名与会者根据王教授的口音分别作出下述判断：甲说：王教授不是苏州人，是上海人。乙说：王教授不是上海人，是苏州人。丙说：王教授既不

2、是上海人，也不是杭州人。王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？解设设P：王教授是苏州人；Q：王教授是上海人；R：王教授是杭州人。则根据题意应有：甲：ØP∧Q乙：ØQ∧P丙：ØQ∧ØR王教授只可能是其中一个城市的人或者3个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有ØQ∧P，因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为：..((ØP∧Q)∧((Q∧ØR)∨(ØQ∧R)))∨((ØQ∧P)∧(ØQ∧R))Û(

3、Ø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)Í。由定理4.15和由定理4.16得sr(R)Ís()＝，进而有tsr(R)Ít()＝。综上可知，tsr(R)是包含R的且具有自反性、

4、对称性和传递性的最小关系。四、（15分）集合A＝{a，b，c，d，e}上的二元关系R为R＝{，，，，，，，，，，，，，}，(1)写出R的关系矩阵。(2)判断R是不是偏序关系，为什么？解(1)R的关系矩阵为：(2)由关系矩阵可知，对角线上所有元素全为1，故R是自反的；＋≤1，故R是反对称的；可计算对应的关系矩阵为：..由以上矩阵可知R是传递的。五、（10分）设A、B、C和D为任意集合，证明(A－B)×C＝(A

5、×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，证明：如果hogof＝IA，fohog＝IB，gofoh＝IC，则f、g、h均为双射，并求出f－1、g－1和h－1。解因IA恒等函数，由hogof＝IA可得f是单射，h是满射；因I

6、B恒等函数，由fohog＝IB可得g是单射，f是满射；因IC恒等函数，由gofoh＝IC可得h是单射，g是满射。从而f、g、h均为双射。由hogof＝IA，得f－1＝hog；由fohog＝IB，得g－1＝foh；由gofoh＝IC，得h－1＝gof。七、（15分）设是一代数系统，运算*满足交换律和结合律，且a*x＝a*yÞx＝y，证明：若G有限，则G是一群。证明因G有限，不妨设G＝{，，…，}。由a*x＝a*yÞx＝y得，..若x≠y，则a*x≠a*y。于是可证，对任意的a∈G，有aG＝G。又因为运算*满足交换律，所以aG＝G＝Ga。

7、令e∈G使得a*e＝a。对任意的b∈G，令c*a＝b，则b*e＝(c*a)*e＝c*(a*e)＝c*a＝b，再由运算*满足交换律得e*b＝b，所以e是关于运算*的幺元。对任意a∈G，由aG＝G可知，存在b∈G使得a*b＝e，再由运算*满足交换律得b*a＝e，所以b是a的逆元。由a的任意性知，G中每个元素都存在逆元。故G是一群。八、（20分）（1）证明在n个结点的连通图G中，至少有n－1条边。证明不妨设G是无向连通图（若G为有向图，可略去边的方向讨论对应的无向图）。设G中结点为、、…、。由连通性，必存在与相邻的结点，不妨设它为（否则可重新编号），

8、连接和，得边，还是由连通性，在、、…、中必存在与或相邻的结点，不妨设为，将其连接得边，续行此法，必与、、…、中的某个结点相邻，得新边，由此可见G中至少