离散数学期末试题

1、 ) r ，进而有 tsr(r)t( r ) r离散数学考试试题（ a 卷及答案） 一、（10 分）求(pq)(p(qr)的主析取范式解：(pq)(p(qr)( pq)(pqr)(pq)(pqr)(pqp)(pqq)(pqr)(pq)(pqr)(pq(rr)(pqr)(pqr)(pqr)(pqr)m0m1 m m m m m m2 3 4 5 67二、（10 分）在某次研讨会的休息时间，3 名与会者根据王教授的口音分别作出下述判断： 甲说：王教授不是苏州人，是上海人。2 说：王教授不是上海人，是苏州人。3 说：王教授既不是上海人，也不是杭州人。王教授听后说：你们 3 人中有一个全说对了，有一人

2、全说错了，还有一个人对错各一半。试判断王 教授是哪里人？解设设 p：王教授是苏州人；q：王教授是上海人；r：王教授是杭州人。则根据题意应有：1 ：pq2 ：qp3 ：qr王教授只可能是其中一个城市的人或者 3 个城市都不是。所以，丙至少说对了一半。因此，可得甲 或乙必有一人全错了。又因为，若甲全错了，则有qp，因此，乙全对。同理，乙全错则甲全对。所 以丙必是一对一错。故王教授的话符号化为：(pq)(qr)(qr)(qp)(qr)(pqqr)(pqqr)(qpqr)(pqr)(pqr)pqrt因此，王教授是上海人。三、（10 分）证明 tsr(r)是包含 r 的且具有自反性、对称性和传递性的最小

3、关系。证明 设 r 是非空集合 a 上的二元关系，则 tsr(r)是包含 r 的且具有自反性、对称性和传递性的关 系。若 r 是包含 r 的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知 r(r)r 。则sr(r)s(r 。abc1 1 1aabbcc1 1 1abc综上可知，tsr(r)是包含 r 的且具有自反性、对称性和传递性的最小关系。四、（15 分）集合 aa，b，c，d，e上的二元关系 r 为 r， ，(1) 写出 r 的关系矩阵。(2) 判断 r 是不是偏序关系，为什么？解 (1) r 的关系矩阵为：101 1 1 11 1 0 1m ( r ) = 0 00 1 0 1

4、0 0 1 100 0 0 1(2)由关系矩阵可知，对角线上所有元素全为 1，故 r 是自反的；rijrji1，故 r 是反对称的；可计算对应的关系矩阵为：101 1 1 11 1 0 1m ( r 2 ) = 0 00 1 0 1 =m ( r )0 0 1 100 0 0 1由以上矩阵可知 r 是传递的。五、（10 分）设 a、b、c 和 d 为任意集合，证明(ab)c(ac)(bc)。 证明：因为(ab)cx(ab)yc( x a x b) y c(xaycxb)(xaycyc)(xayc)(xbyc)( x a y c)( x b y c)(ac)(bc)(ac)(bc)所以，(ab)

5、c(acbc)。六、（10 分）设 f：ab，g：bc，h：ca，证明：如果 hogofi ，fohogi ，gofohi ，则 f、 g、h 均为双射，并求出 f 、g 和 h 。解因 i 恒等函数，由 hogofi 可得 f 是单射，h 是满射；因 i 恒等函数，由 fohogi 可得 g 是单射，f 是满射；因 i 恒等函数，由 gofohi 可得 h 是单射，g 是满射。从而 f、g、h 均为双射。 由 hogofi ，得 f hog；由 fohogi ，得 g foh；由 gofohi ，得 h gof。七、（15 分）设是一代数系统，运算*满足交换律和结合律，且 a*xa*yxy，

6、证明：若 g2cm -12有限，则 g 是一群。证明 因 g 有限，不妨设 g a ， a ， a 。由 a*xa *yxy 得，若 xy，则 a*xa *y。1 2 n于是可证，对任意的 ag，有 agg。又因为运算*满足交换律，所以 aggga。令 eg 使得 a*e a。对任意的 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 是

7、一群。八、（20 分）（1）证明在 n 个结点的连通图 g 中，至少有 n1 条边。证明 不妨设 g 是无向连通图（若 g 为有向图，可略去边的方向讨论对应的无向图）。设 g 中结点为 v 、 v 、 v 。由连通性，必存在与 v 相邻的结点，不妨设它为 v （否则可重新编1 2 n 1 2号），连接v1和v2，得边e1，还是由连通性，在v3、v4、vn中必存在与v1或v2相邻的结点，不妨设为 v ，将其连接得边 e ，续行此法， v 必与 v 、 v 、 3 2 n 1 2vn -1中的某个结点相邻，得新边en-1，由此可见 g 中至少有 n1 条边。（2）给定简单无向图 g，且|v|m，|

8、e|n。试证：若 n 图。m -12，则 g 是哈密尔顿证明 若 n c 22，则 2nm3m6 （1）。若存在两个不相邻结点 u 、 v 使得 d( u )d( v )m，则有 2nd ( w)m(m2)(m3)mm2wv3m6，与（1）矛盾。所以，对于 g 中任意两个不相邻结点 u 、 v 都有 d( u )d( v )m。由定理 10.26 可知，g 是哈密尔顿图。离散数考试试题（b 卷及答案）一、（10 分）使用将命题公式化为主范式的方法，证明(pq)(pq)(qp)(pq)。 证明：因为(pq)(pq)(pq)(pq)(pq)(pq)(qp)(pq)(qp)(pq)(pq)(qq)(

9、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，dc ad(1) a(2) abc (3)bc (4)ba (5)ab (6)b(7) c(8) dc(9) d (10)ad附加前提pt(1)(2)，ipt(4)，et(1)(5)

10、，it(3)(6)，ipt(7)(8)，icp三、（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，11111 133 3 4 4 4 5 5 5，(1) 画出 r 的关

11、系图。(2) 写出 r 的关系矩阵。(3) 说明 r 是否是自反、反自反、对称、传递的。 解 (1)r 的关系图如图所示：(2) r 的关系矩阵为：m ( r ) =10111 1 00 0 01 1 01 1 0(3)对于 r 的关系矩阵，由于对角线上不全为 1，r 不是自反的；由于对角线上存在非 0 元，r 不是 反自反的；由于矩阵不对称，r 不是对称的；经过计算可得m ( r2) =10111 1 00 0 01 1 01 1 0=m ( r )，所以 r 是传递的。六、（15 分）设函数 f：rrrr，f 定义为：f()。(1) 证明 f 是单射。(2) 证明 f 是满射。(3) 求逆

12、函数 f 。(4) 求复合函数 f of 和 fof。证明 (1)对任意的 x，y，x ，y r，若 f()f()，则，1 1 1 1 1 1 1 1xyx y ，xyx y ，从而 xx ，yy ，故 f 是单射。1 1 1 1 1 1(2)对任意的rr，令 xu +w u -w u +w u -w u +w ，y ，则 f()，所以 f 是满射。(3)f ()。2 2(4)f of()f (f()f() 2 2fof()f(f()f()。七、（15 分）给定群，若对 g 中任意元 a 和 b，有 a *b (a*b) ，a *b (a*b) ，a *b (a*b) ， 试证是 abel 群

13、。证明 对 g 中任意元 a 和 b。3 3 33 3*b (b*a) 。同理，由 a *b4 3 3 3 5 5 5 4 4 43 3 4 4 4 4 4 2 2 3 3 33 33 4 4 3 3 31因为 a*b (a*b) ，所以a-1*a*b *b-1a-1*(a*b)3*b-1，即得 a2 2 2 4 4(a*b)可得，a *b (b*a) 。由 a *b (a*b) 可得，a *b (b*a) 。b于是 (a *b )*(b*a)(b*a) a *b ，即 b *aa*b 。同理可得， (a *b )*(b*a)(b*a) a *b ，即 *aa*b 。由于(a*b)*ba*b b *ab*(b *a)b*(a*b )(b*a)*b ，故 a*bb*a。八、（15 分）（1）证明在 n 个结点的连通图 g 中，至少有 n1 条边。证明 不妨设 g 是无向连通图（若 g 为有向图，可略去边的方向讨论对应的无向图）。设 g 中结点为 v 、 v 、 v 。由连通性，必存在与 v 相邻的结点，不妨设它为