离散数学试卷及答案.doc

离散数学试题（A卷答案）一、（10分）求(PQ)(P(QR)的主析取范式解：(PQ)(P(QR)( PQ)(PQR)(PQ)(PQR)(PQP)(PQQ)(PQR)(PQ)(PQR)(PQ(RR)(PQR)(PQR)(PQR)(PQR)二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断：甲说：王教授不是苏州人，是上海人。乙说：王教授不是上海人，是苏州人。丙说：王教授既不是上海人，也不是杭州人。王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？解 设设P：王教授是苏州人；Q：王教授是上海人；R：王教授是杭州人。则根据题意应有：甲：PQ乙：QP丙：QR王教授只可能是其中一个城市的人或者3个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有QP，因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为：(PQ)(QR)(QR)(QP)(QR)(PQQR)(PQQR)(QPQR)(PQR)(PQR)PQRT因此，王教授是上海人。三、（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的且具有自反性、对称性和传递性的最小关系。四、（15分）集合Aa，b，c，d，e上的二元关系R为R，(1)写出R的关系矩阵。(2)判断R是不是偏序关系，为什么？解 (1) R的关系矩阵为：(2)由关系矩阵可知，对角线上所有元素全为1，故R是自反的；1，故R是反对称的；可计算对应的关系矩阵为：由以上矩阵可知R是传递的。五、（10分）设A、B、C和D为任意集合，证明(AB)C(AC)(BC)。证明：因为(AB)C(AB)C(AB)C(ACB)(ACC)(AC)(BC)(AC)(BC)(AC)(BC)(AC)(BC)所以，(AB)C(ACBC)。六、（10分）设f：AB，g：BC，h：CA，证明：如果hogofIA，fohogIB，gofohIC，则f、g、h均为双射，并求出f1、g1和h1。解 因IA恒等函数，由hogofIA可得f是单射，h是满射；因IB恒等函数，由fohogIB可得g是单射，f是满射；因IC恒等函数，由gofohIC可得h是单射，g是满射。从而f、g、h均为双射。由hogofIA，得f1hog；由fohogIB，得g1foh；由gofohIC，得h1gof。七、（15分）设是一代数系统，运算*满足交换律和结合律，且a*xa*yxy，证明：若G有限，则G是一群。证明 因G有限，不妨设G，。由a*xa*yxy得，若xy，则a*xa*y。于是可证，对任意的aG，有aGG。又因为运算*满足交换律，所以aGGGa。令eG使得a*ea。对任意的bG，令c*ab，则b*e(c*a)*ec*(a*e)c*ab，再由运算*满足交换律得e*bb，所以e是关于运算*的幺元。对任意aG，由aGG可知，存在bG使得a*be，再由运算*满足交换律得b*ae，所以b是a的逆元。由a的任意性知，G中每个元素都存在逆元。故G是一群。八、（20分）（1）证明在n个结点的连通图G中，至少有n1条边。证明 不妨设G是无向连通图（若G为有向图，可略去边的方向讨论对应的无向图）。设G中结点为、。由连通性，必存在与相邻的结点，不妨设它为（否则可重新编号），连接和，得边，还是由连通性，在、中必存在与或相邻的结点，不妨设为，将其连接得边，续行此法，必与、中的某个结点相邻，得新边，由此可见G中至少有n1条边。（2）给定简单无向图G，且|V|m，|E|n。试证：若n2，则G是哈密尔顿图。证明 若n2，则2nm23m6 （1）。若存在两个不相邻结点、使得d()d()m，则有2nm(m2)(m3)mm23m6，与（1）矛盾。所以，对于G中任意两个不相邻结点、都有d()d()m。由定理10.26可知，G是哈密尔顿图。离散数学试题（B卷答案）一、（10分）使用将命题公式化为主范式的方法，证明(PQ)(PQ)(QP)(PQ)。证明：因为(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(QP)(PQ)(QP)(PQ)(PQ)(QQ)(PP) (PQ)(PQ)P(PQ)(P(QQ)(PQ)(PQ)(PQ)(PQ)(PQ) 所以，(PQ)(PQ)(QP)(PQ)。二、（10分）证明下述推理： 如果A努力工作，那么B或C感到愉快；如果B愉快，那么A不努力工作；如果D愉快那么C不愉快。所以，如果A努力工作，则D不愉快。解 设A：A努力工作；B、C、D分别表示B、C、D愉快；则推理化形式为：ABC，BA，DCAD(1)A 附加前提(2)ABC P(3)BC T(1)(2)，I(4)BA P(5)AB T(4)，E(6)B T(1)(5)，I(7)C T(3)(6)，I(8)DC P(9)D T(7)(8)，I(10)AD CP三、（10分）证明xy(P(x)Q(y)($xP(x)yQ(y)。xy(P(x)Q(y)xy(P(x)Q(y)x(P(x)yQ(y)xP(x)yQ(y)$xP(x)yQ(y)($xP(x)yQ(y)四、（10分）设A，1，1，B0，0，求P(A)、P(B)0、P(B)B。解 P(A)，1，1，1，1，1，1，1，1P(B)0，0，0，0，00，0，0，0，0P(B)B，0，0，0，00，0，0，0，0，0五、（15分）设X1，2，3，4，R是X上的二元关系，R，(1)画出R的关系图。(2)写出R的关系矩阵。(3)说明R是否是自反、反自反、对称、传递的。解 (1)R的关系图如图所示：(2) R的关系矩阵为：(3)对于R的关系矩阵，由于对角线上不全为1，R不是自反的；由于对角线上存在非0元，R不是反自反的；由于矩阵不对称，R不是对称的；经过计算可得，所以R是传递的。六、（15分）设函数f：RRRR，f定义为：f()。(1)证明f是单射。(2)证明f是满射。(3)求逆函数f1。(4)求复合函数f1of和fof。证明 (1)对任意的x，y，x1，y1R，若f()f()，则，xyx1y1，xyx1y1，从而xx1，yy1，故f是单射。(2)对任意的RR，令x，y，则f()，所以f是满射。(3)f1()。(4)f1of()f1(f()f1()fof()f(f()f()。七、（15分）给定群，若对G中任意元a和b，有a3*b3(a*b)3，a4*b4(a*b)4，a5*b5(a*b)5，试证是Abel群。证明 对G中任意元a和b。因为a3*b3(a*b)3，所以*a3*b3*(a*b)3*，即得a2*b2(b*a)2。同理，由a4*b4(a*b)4可得，a3*b3(b*a)3。由a5*b5(a*b)5可得，a4*b4(b*a)4。于是(a3*b3)*(b*a)(b*a)4a4*b4，即b4*aa*b4。同理可得，(a2*b2)*(b*a)(b*a)3a3*b3，即b3*aa*b3。由于(a*b)*b3a*b4b4*ab*(b3*a)b*(a*b3)(b*a)*b3，故a*bb*a。八、（15分）（1）证明在n个结点的连通图G中，至少有n1条边。证明 不妨设G是无向连通图（若G为有向图，可略去边的方向讨论对应的无向图）。设G中结点为、。由连通性，必存在与相邻的结点，不妨设它为（否则可重新编号），连接和，得边，还是由连通性，在、中必存在与或相邻的结点，不妨设为，将其连接得边，续行此法，必与、中的某个结点相邻，得新边，由此可见G中至少有n1条边。（2）试给出|V|n，|E|(n1)(n2)的简单无向图G是不连通的例子。解 下图满足条件但不连通。9