(完整版)离散数学试卷及答案.pdf

《(完整版)离散数学试卷及答案.pdf》由会员分享，可在线阅读，更多相关《(完整版)离散数学试卷及答案.pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 1 离散数学试题（A 卷答案）一、（10 分）求(PQ)(P(QR)的主析取范式 解：(PQ)(P(QR)(PQ)(PQR)(PQ)(PQR)(PQP)(PQQ)(PQR)(PQ)(PQR)(PQ(RR)(PQR)(PQR)(PQR)(PQR)0M1M 2m3m4m5m6m7m 二、（10 分）在某次研讨会的休息时间，3 名与会者根据王教授的口音分别作出下述判断：甲说：王教授不是苏州人，是上海人。乙说：王教授不是上海人，是苏州人。丙说：王教授既不是上海人，也不是杭州人。王教授听后说：你们 3 人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？解 设设 P：王教授

2、是苏州人；Q：王教授是上海人；R：王教授是杭州人。则根据题意应有：甲：PQ 乙：QP 丙：QR 王教授只可能是其中一个城市的人或者 3 个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有QP，因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为：2(PQ)(QR)(QR)(QP)(QR)(PQQR)(PQQR)(QPQR)(PQR)(PQR)PQR T 因此，王教授是上海人。三、（10 分）证明 tsr(R)是包含 R 的且具有自反性、对称性和传递性的最小关系。证明 设 R 是非空集合 A 上的二元关系，则由定理 4.19 知

3、，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 分）集合 Aa，b，c，d，e上的二元关系 R 为 R，(1)写出 R 的关系矩阵。(2)判断 R 是不是偏序关系，为什么？解 (1)R 的关系矩阵为：1000011000101001011011111)(RM(2)由关系矩阵可知，对角线上所有元素全为 1，故 R

4、是自反的；ijrjir1，故 R 是反对称的；可计算对应的关系矩阵为：3)(1000011000101001011011111)(2RMRM 由以上矩阵可知 R 是传递的。五、（10 分）设 A、B、C 和 D 为任意集合，证明(AB)C(AC)(BC)。证明：因为(AB)Cx(AB)yC(xAxB)yC(xAyCxB)(xAyCyC)(xAyC)(xByC)(xAyC)(xByC)(AC)(BC)(AC)(BC)所以，(AB)C(ACBC)。六、（10 分）设 f：AB，g：BC，h：CA，证明：如果 hgfIA，fhgIB，gfhIC，则 f、g、h 均为双射，并求出 f1、g1和 h1。

5、解 因 IA恒等函数，由 hgfIA可得 f 是单射，h 是满射；因 IB恒等函数，由 fhgIB可得 g 是单射，f 是满射；因 IC恒等函数，由 gfhIC可得 h 是单射，g 是满射。从而 f、g、h 均为双射。由 hgfIA，得 f1hg；由 fhgIB，得 g1fh；由 gfhIC，得 h1gf。七、（15 分）设是一代数系统，运算*满足交换律和结合律，且 a*x 4 a*yxy，证明：若 G 有限，则 G 是一群。证明 因 G 有限，不妨设 G1a，2a，na。由 a*xa*yxy 得，若 xy，则 a*xa*y。于是可证，对任意的 aG，有 aGG。又因为运算*满足交换律，所以

6、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 中结点为1v、2v、nv。由连通性，必存在与1v相邻的结点，不妨设它

7、为2v（否则可重新编号），连接1v和2v，得边1e，还是由连通性，在3v、4v、nv中必存在与1v或2v相邻的结点，不妨设为3v，将其连接得边2e，续行此法，nv必与1v、2v、1nv中的某个结点相邻，得新边1ne，由此可见 G 中至少有 n1条边。（2）给定简单无向图 G，且|V|m，|E|n。试证：若 n21mC2，则 G 是哈密尔顿图。证明 若 n21mC2，则 2nm23m6 （1）。若存在两个不相邻结点u、v使得 d(u)d(v)m，则有 2nVwwd)(m(m2)(m3)mm23m6，与（1）矛盾。所以，对于 G 中任意两个不相邻结点u、v都有 d(u)d(v)m。由定理 10.2

8、6 可知，G 是哈密尔顿图。5 离散数学试题（B 卷答案）一、（10 分）使用将命题公式化为主范式的方法，证明(PQ)(PQ)(QP)(PQ)。证明：因为(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(QP)(PQ)(QP)(PQ)6(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、

9、D 分别表示 B、C、D 愉快；则推理化形式为：ABC，BA，DC AD(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)7 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，

10、1，1，1，1 P(B)0，0，0，0，00，0，0，0，0 P(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 的关系矩阵为：0111011100000111)(RM(3)对于 R 的关系矩阵，由于对角线上不全为 1，R 不是自反的；由于对角线上存在非 0 元，R 不是反自反的；由于矩阵不对称，R 不是对称的；经过计算可得)(0111011100000111)(2RMRM，所以 R

11、是传递的。六、（15 分）设函数 f：RRRR，f 定义为：f()。8(1)证明 f 是单射。(2)证明 f 是满射。(3)求逆函数 f1。(4)求复合函数 f1f 和 ff。证明 (1)对任意的 x，y，x1，y1R，若 f()f()，则，xyx1y1，xyx1y1，从而 xx1，yy1，故 f是单射。(2)对任意的RR，令 x2wu，y2wu，则 f()，所以 f 是满射。(3)f1()。(4)f1f()f1(f()f1()ff()f(f()f()。七、（15 分）给定群，若对 G 中任意元 a 和 b，有 a3*b3(a*b)3，a4*b4(a*b)4，a5*b5(a*b)5，试证是 A

12、bel 群。证明 对 G 中任意元 a 和 b。因为 a3*b3(a*b)3，所以1a*a3*b3*1b1a*(a*b)3*1b，即得 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。9 八、（15 分）（1）证明在 n 个结点的连通图 G 中，至少有 n1 条边。证明 不妨设 G 是无向连通图（若 G 为有向图，可略去边的方向讨论对应的无向图）。设 G 中结点为1v、2v、nv。由连通性，必存在与1v相邻的结点，不妨设它为2v（否则可重新编号），连接1v和2v，得边1e，还是由连通性，在3v、4v、nv中必存在与1v或2v相邻的结点，不妨设为3v，将其连接得边2e，续行此法，nv必与1v、2v、1nv中的某个结点相邻，得新边1ne，由此可见 G 中至少有 n1条边。（2）试给出|V|n，|E|21(n1)(n2)的简单无向图 G是不连通的例子。解 下图满足条件但不连通。