1、1离散数学考试试题（A 卷及答案）一、 （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 2m3456m7二、 （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因此，王教授是上海人。三、 （10 分）证明 tsr(R)是包含 R 的且具有自反性、对称性和传递性的最小关系。证明 设 R
3、是非空集合 A 上的二元关系，则 tsr(R)是包含 R 的且具有自反性、对称性和传递性的关系。若 是包含 R 的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知 r(R) 。则 sr(R) 2s( ) ，进而有 tsr(R)t( ) 。R 综上可知，tsr(R)是包含 R 的且具有自反性、对称性和传递性的最小关系。四、 （15 分）集合 Aa，b，c，d，e 上的二元关系 R 为R，(1)写出 R 的关系矩阵。(2)判断 R 是不是偏序关系，为什么？解 (1) R 的关系矩阵为： 1011)(RM(2)由关系矩阵可知，对角线上所有元素全为 1，故 R 是自反的； 1，故 R 是反对称
4、的；可ijrji计算对应的关系矩阵为： )(10)(2 RMRM由以上矩阵可知 R 是传递的。五、 （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( A C)( B C )(AC)(BC)xy(AC)(BC )xy所以，(AB )C(ACBC )。六、 （10 分）设 f：AB，g：BC，h：CA ，证明：如果 hgfI A，fh gI B，gf hI C，则f、g、h 均为双射，并求出 f1 、g 1 和 h1 。解 因 IA 恒等函数
5、，由 hgfI A 可得 f 是单射，h 是满射；因 IB 恒等函数，由 fhgI B 可得 g 是单3射，f 是满射；因 IC 恒等函数，由 gfhI C 可得 h 是单射， g 是满射。从而 f、g、h 均为双射。由 hgfI A，得 f1 hg；由 fhgI B，得 g1 fh；由 gfhI C，得 h1 g f。七、（15 分）设是一代数系统，运算 *满足交换律和结合律，且 a*xa*yx y，证明：若G 有限，则 G 是一群。证明 因 G 有限，不妨设 G ， ， 。由 a*xa*yx y 得，若 xy，则 a*xa*y。1a2n于是可证，对任意的 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 中结点为 、 、 。由连通性，必存在与 相
7、邻的结点，不妨设它为 （否则可重新编1v2nv1v 2v号） ，连接 和 ，得边 ，还是由连通性，在 、 、 中必存在与 或 相邻的结点，不妨设为12e3v4n1v，将其连接得边 ，续行此法， 必与 、 、 中的某个结点相邻，得新边 ，由此可见 G3v nv121 1ne中至少有 n1 条边。（2）给定简单无向图 G，且|V|m ，|E|n。试证：若 n 2，则 G 是哈密尔顿图。1mC证明 若 n 2，则 2nm 23m 6 （1） 。1mC若存在两个不相邻结点 、 使得 d( )d( )m ，则有 2n m (m2)(m3)uvuvVwd)(mm 23m6，与（1）矛盾。所以，对于 G 中
8、任意两个不相邻结点 、 都有 d( )d( )m。由uvuv定理 10.26 可知，G 是哈密尔顿图。4离散数考试试题（ B卷及答案）一、 （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 )(PQ)( PQ)所以，(PQ)(PQ)(QP)(PQ )。二、 （10 分）证明下述推理： 如果 A 努力工作，那么 B 或 C 感到愉快；如果 B 愉快，那么 A 不努
9、力工作；如果 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 分）证明x y(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
10、)(xP(x)yQ(y)5四、 （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 的关系矩阵为： 01)(RM(3)对于 R 的关系矩阵，由于对角线上不全为 1，R 不是自反的；由于对角线上存在非 0 元，R
11、不是反自反的；由于矩阵不对称，R 不是对称的；经过计算可得，所以 R 是传递的。)(01)(2MM六、 （15 分）设函数 f：RRRR，f 定义为：f ()。(1)证明 f 是单射。(2)证明 f 是满射。(3)求逆函数 f1 。(4)求复合函数 f1 f 和 ff。证明 (1)对任意的 x，y，x 1，y 1R，若 f()f()，则，xyx 1y 1，xyx 1y 1，从而 xx 1，yy 1，故 f 是单射。(2)对任意的RR，令 x ，y ，则 f()，所以 f 是满射。2(3)f1 ()。2u6(4)f1 f()f 1 (f()f 1 ()2yx2)(ff()f(f()f()。七、
12、（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(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
13、 3。由于(a*b)*b 3a*b 4b 4*ab*(b 3*a)b*(a*b 3)(b*a)*b 3，故 a*bb*a。八、 （15 分） （1）证明在 n 个结点的连通图 G 中，至少有 n1 条边。证明 不妨设 G 是无向连通图（若 G 为有向图，可略去边的方向讨论对应的无向图） 。设 G 中结点为 、 、 。由连通性，必存在与 相邻的结点，不妨设它为 （否则可重新编1v2nv1v 2v号） ，连接 和 ，得边 ，还是由连通性，在 、 、 中必存在与 或 相邻的结点，不妨设为12e3v4n1v，将其连接得边 ，续行此法， 必与 、 、 中的某个结点相邻，得新边 ，由此可见 G3v nv121 1ne中至少有 n1 条边。（2）试给出|V|n，|E| (n1)(n2)的简单无向图 G是不连通的例子。2解 下图满足条件但不连通。
