《离散试卷有答案 (4)》由会员分享，可在线阅读，更多相关《离散试卷有答案 (4)（26页珍藏版）》请在金锄头文库上搜索。
1、离散试卷及答案第 1 页 共 28 页离散数学（A 卷及答案）1、 （10 分）求(P Q)(P( QR)的主析取范式解：(PQ)( P(QR )( PQ )( PQR)(PQ )(P QR )(PQ P )(PQ Q)(PQ R)(PQ )(P QR )(PQ ( RR) (PQR)(PQ R )(PQ R)( PQ R) 0M1 2m3456m72、 （10 分）在某次研讨会的休息时间，3 名与会者根据王教授的口音分别作出下述判断：甲说：王教授不是苏州人，是上海人。乙说：王教授不是上海人，是苏州人。丙说：王教授既不是上海人，也不是杭州人。王教授听后说：你们 3人中有一个全说对了，有一人全说
2、错了，还有一个人对错各一半。试判断王教授是哪里人？解 设设 P：王教授是苏州人；Q ：王教授是上海人；R：王教授是杭州人。则根据题意应有：甲：P Q乙：QP丙：QR王教授只可能是其中一个城市的人或者 3个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有QP，因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为：(P Q)( QR )( QR)(QP )(QR)(PQQR)(PQQ R)(Q PQR)(PQR)(PQR)PQRT因此，王教授是上海人。离散试卷及答案第 2 页 共 28 页3、 （10 分）证明 tsr(R)是包含
3、 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 的关系矩阵为
4、： 1011)(RM(2)由关系矩阵可知，对角线上所有元素全为 1，故 R 是自反的； 1，故 R 是反对称的；可ijrji计算对应的关系矩阵为： )(10)(2 RMRM由以上矩阵可知 R 是传递的。5、 （10 分）设 A、B、C 和 D 为任意集合，证明(AB)C(AC)(BC )。证明：因为(AB)C (AB) Cxyxy( A B) C( A C B)( A C C)xy( A C)( B C)xy离散试卷及答案第 3 页 共 28 页( A C)( B C)xyxy(AC)(BC)(AC)(BC)所以，(AB )C(ACBC )。6、 （10 分）设 f：AB，g：BC，h：CA
5、，证明：如果 hgfI A，fh gI B，gf hI C，则f、g、h 均为双射，并求出 f1 、g 1 和 h1 。解 因 IA 恒等函数，由 hgfI A 可得 f 是单射，h 是满射；因 IB 恒等函数，由 fhgI B 可得 g 是单射，f 是满射；因 IC 恒等函数，由 gfhI C 可得 h 是单射， g 是满射。从而 f、g、h 均为双射。由 hgfI A，得 f1 hg；由 fhgI B，得 g1 fh；由 gfhI C，得 h1 g f。7、（15 分）设是一代数系统，运算 *满足交换律和结合律，且 a*xa*yx y，证明：若 G有限，则 G 是一群。证明 因 G 有限，
6、不妨设 G ， ， 。由 a*xa*yxy 得，若 xy，则 a*xa*y 。1a2n于是可证，对任意的 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 是一群。8、 （20 分） （1）证明在 n 个结点的连通图 G 中，至少有 n1 条
7、边。证明 不妨设 G 是无向连通图（若 G 为有向图，可略去边的方向讨论对应的无向图） 。设 G 中结点为 、 、 。由连通性，必存在与 相邻的结点，不妨设它为 （否则可重新编1v2nv1v 2v号） ，连接 和 ，得边 ，还是由连通性，在 、 、 中必存在与 或 相邻的结点，不妨设为12e3v4n1v，将其连接得边 ，续行此法， 必与 、 、 中的某个结点相邻，得新边 ，由此可见 G3v nv121 1ne中至少有 n1 条边。（2）给定简单无向图 G，且|V|m ，|E|n。试证：若 n 2，则 G 是哈密尔顿图。1mC证明 若 n 2，则 2nm 23m 6 （1） 。1mC若存在两个不
8、相邻结点 、 使得 d( )d( )m ，则有 2n m(m2)(m3)uvuvVwd)mm 23m6，与（1）矛盾。所以，对于 G 中任意两个不相邻结点 、 都有 d( )d( )m。由uvuv定理 10.26可知，G 是哈密尔顿图。离散试卷及答案第 4 页 共 28 页离散数考试试题（B 卷及答案）1、 （10 分）使用将命题公式化为主范式的方法，证明(PQ)(PQ )(QP)(PQ)。证明：因为(PQ)(PQ)(PQ)(P Q )(PQ)( PQ)(QP)(P Q)(QP )(P Q)(PQ)( QQ)(P P ) (PQ )(PQ)P(PQ)( P(QQ)(PQ)( PQ)(PQ )(
9、PQ)( PQ)所以，(PQ)(PQ)(QP)(PQ )。2、 （10 分）证明下述推理： 如果 A 努力工作，那么 B 或 C 感到愉快；如果 B 愉快，那么 A 不努力工作；如果 D 愉快那么 C 不愉快。所以，如果 A 努力工作，则 D 不愉快。解 设 A： A 努力工作；B 、C 、D 分别表示 B、C 、D 愉快；则推理化形式为：AB C，B A，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
10、 分）证明x y(P(x)Q(y)(xP(x)yQ(y)。xy(P(x)Q(y)xy(P(x)Q (y)离散试卷及答案第 5 页 共 28 页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
11、是否是自反、反自反、对称、传递的。解 (1)R 的关系图如图所示：(2) R 的关系矩阵为： 01)(RM(3)对于 R 的关系矩阵，由于对角线上不全为 1，R 不是自反的；由于对角线上存在非 0元，R 不是反自反的；由于矩阵不对称，R 不是对称的；经过计算可得，所以 R 是传递的。)(01)(2MM6、 （15 分）设函数 f：RR RR，f 定义为：f ()。(1)证明 f 是单射。(2)证明 f 是满射。(3)求逆函数 f1 。(4)求复合函数 f1 f 和 ff。证明 (1)对任意的 x，y，x 1，y 1R，若 f()f ()，则离散试卷及答案第 6 页 共 28 页，xyx 1y
12、1，xyx 1y 1，从而 xx 1，yy 1，故 f 是单射。(2)对任意的RR，令 x ，y ，则 f()，所以 f 是满射。2(3)f1 ()。2u(4)f1 f()f 1 (f()f 1 ()2yx2)(ff()f(f()f()。7、 （15 分）给定群，若对 G 中任意元 a 和 b，有 a3*b3(a*b) 3，a 4*b4(a*b) 4，a 5*b5(a*b)5，试证是 Abel 群。证明 对 G 中任意元 a 和 b。因为 a3*b3(a*b) 3，所以 *a3*b3* *(a*b)3* ，即得 a2*b2(b*a) 2。同理，由111a4*b4(a*b) 4可得，a 3*b3
13、(b*a) 3。由 a5*b5(a*b) 5可得，a 4*b4(b*a) 4。于是(a 3*b3)*(b*a)(b*a) 4a 4*b4，即 b4*aa*b 4。同理可得，(a 2*b2)*(b*a)(b*a) 3a 3*b3，即b3*aa*b 3。由于(a*b)*b 3a*b 4b 4*ab*(b 3*a)b*(a*b 3)(b*a)*b 3，故 a*bb*a。8、 （15 分） （1）证明在 n 个结点的连通图 G 中，至少有 n1 条边。证明 不妨设 G 是无向连通图（若 G 为有向图，可略去边的方向讨论对应的无向图） 。设 G 中结点为 、 、 。由连通性，必存在与 相邻的结点，不妨设它为 （否则可重新编1v2nv1v 2v号） ，连接 和 ，得边 ，还是由连通性，在 、 、 中必存在与 或 相邻的结点，不妨设为12e3v4n1v，将其连接得边 ，续行此法， 必与 、 、 中的某个结点相邻，得
