离散数学试题及答案.doc

1、离散数学考试试题（A 卷及答案）一、 （10 分）某项工作需要派 A、B、C 和 D 4 个人中的 2 个人去完成，按下面 3 个条件，有几种派法？如何派？(1)若 A 去，则 C 和 D 中要去 1 个人；(2)B 和 C 不能都去；(3)若 C 去，则 D 留下。解 设 A：A 去工作；B：B 去工作；C：C 去工作；D：D 去工作。则根据题意应有：ACD，(B C)，CD 必须同时成立。因此(ACD)(BC)(CD )(A (C D)(CD)( BC)( CD)(A (C D)(CD)(BC)( BD ) C(C D)(A BC)(A B D )( AC )(AC D)(C DBC)(

2、C D BD)( C DC )(C DC D)(CDBC)( CD BD)( CDC )( CDC D)FF (A C)F F (C DB)FF (CDB)F(CD)F(A C)(BC D)( CDB)(CD)(A C)(BC D)( CD)T故有三种派法：BD，AC，AD 。二、 （15 分）在谓词逻辑中构造下面推理的证明：某学术会议的每个成员都是专家并且是工人，有些成员是青年人，所以，有些成员是青年专家。解：论域：所有人的集合。 ( )： 是专家； ( )： 是工人； ( )： 是青年人；则推理化形SxWxYx式为：( ( ) ( )， ( ) ( ( ) ( )xSWxYSY下面给出证明

3、：(1) ( ) PY(2) (c) T(1)，ES(3) ( ( ) ( ) PxSWx(4) ( c) ( c) T(3)，US(5) ( c) T(4)，I(6) ( c) (c) T(2)(5)，ISY(7) ( ) ( ) T(6) ，EGxx三、 （10 分）设 A、B 和 C 是三个集合，则 AB(BA)。证明：A Bx(xAx B )x(xBx A)x(xAxB) x(xBxA)x(xA xB )x (xBxA)x( xAxB) x(xAxB)(x(xAx B)x(x AxB) (x(xAx B) x(xBxA)(BA)。四、 （15 分）设 A1，2，3，4，5，R 是 A

4、上的二元关系，且R，求 r(R)、s(R)和 t(R)。解 r(R)R I A， ，s(R)RR 1 ，R2，R3，R4，R 2t(R) Ri ， ， ，。1五、 （10 分）R 是非空集合 A 上的二元关系，若 R 是对称的，则 r(R)和 t(R)是对称的。证明 对任意的 x、yA，若 xr(R)y，则由 r(R)RI A 得，xRy 或 xIAy。因 R 与 IA 对称，所以有yRx 或 yIAx，于是 yr(R)x。所以 r(R)是对称的。下证对任意正整数 n，R n对称。因 R 对称，则有 xR2yz(xRzzRy )z(zRxyRz) yR2x，所以 R2对称。若 对称，则nx y

5、z(x zzRy) z(z xyRz)y x，所以 对称。因此，对任意正整数 n， 对称。1nnn1nR1n R对任意的 x、yA，若 xt(R)y，则存在 m 使得 xRmy，于是有 yRmx，即有 yt(R)x。因此，t (R)是对称的。六、 （10 分）若 f：AB 是双射，则 f1 ：BA 是双射。证明 因为 f：AB 是双射，则 f1 是 B 到 A 的函数。下证 f1 是双射。对任意 xA，必存在 yB 使 f(x)y，从而 f1 (y)x，所以 f1 是满射。对任意的 y1、y 2B，若 f1 (y1)f 1 (y2)x，则 f(x)y 1，f(x) y 2。因为 f：AB 是函

6、数，则y1y 2。所以 f1 是单射。综上可得，f 1 ：BA 是双射。七、 （10 分）设是一个半群，如果 S 是有限集，则必存在 aS，使得 a*aa。证明 因为是一个半群，对任意的 bS，由*的封闭性可知，b2b*bS，b 3b 2*bS，b nS，。因为 S 是有限集，所以必存在 ji ，使得 。令 pj i，则 * 。所以对 qi ，有ibj jpj * 。qbpq因为 p1，所以总可找到 k1，使得 kpi 。对于 S，有 * *( * )kpbkpbkppbk* 。kb令 a ，则 aS 且 a*aa。p八、 （20 分） （1）若 G 是连通的平面图，且 G 的每个面的次数至少

7、为 l(l3)，则 G 的边数 m 与结点数 n 有如下关系：m (n2)。2l证明 设 G 有 r 个面，则 2m lr。由欧拉公式得，n mr2。于是， m (n2)。riifd1)( 2l（2）设平面图 G是自对偶图，则| E|2(|V|1)。证明 设 G*是连通平面图 G的对偶图，则 G* G，于是|F|V*|V|，将其代入欧拉公式|V|E|F|2 得，|E|2(|V|1)。离散数学考试试题（B 卷及答案）一、（10 分）证明(PQ) ( PR)(QS) SR证明 因为 SR RS，所以，即要证( PQ )( PR)(QS) RS。(1)R 附加前提(2)PR P(3)P T(1)(2

8、)，I(4)PQ P(5)Q T(3)(4)，I(6)QS P(7)S T(5)(6)，I(8)RS CP(9)SR T(8)，E二、 （15 分）根据推理理论证明：每个考生或者勤奋或者聪明，所有勤奋的人都将有所作为，但并非所有考生都将有所作为，所以，一定有些考生是聪明的。设 P(e)：e 是考生，Q(e) ：e 将有所作为，A(e)：e 是勤奋的，B(e) ：e 是聪明的，个体域：人的集合，则命题可符号化为：x (P(x)(A(x)B( x)，x(A( x)Q(x)，x(P( x)Q(x) x(P(x)B( x)。(1)x(P(x)Q(x) P(2)x(P(x) Q(x) T(1)，E(3)

9、x(P(x)Q (x) T(2)，E(4)P(a)Q( a) T(3)，ES(5)P(a) T(4)，I(6)Q(a) T(4)，I(7)x(P(x)(A(x)B(x ) P(8)P(a)(A(a)B(a) T(7)，US(9)A(a)B (a) T(8)(5)，I(10)x(A(x)Q(x) P(11)A(a)Q(a) T(10)，US(12)A(a) T(11)(6)，I(13)B(a) T(12)(9)，I(14)P(a)B (a) T(5)(13)，I(15)x(P(x)B(x) T(14)，EG三、 （10 分）某班有 25 名学生，其中 14 人会打篮球，12 人会打排球，6 人会

10、打篮球和排球，5 人会打篮球和网球，还有 2 人会打这三种球。而 6 个会打网球的人都会打另外一种球，求不会打这三种球的人数。解 设 A、B 、C 分别表示会打排球、网球和篮球的学生集合。则：|A|12，|B|6，|C |14，|AC |6，|B C|5，|ABC| 2，|(AC)B|6。因为|( AC)B|(AB )(BC)|(AB)|(BC)|ABC| |(AB)|526，所以|(AB)| 3。于是 |A BC |126 14653220， 25205。故，不会打这三种球的共|5 人。四、 （10 分）设 A1、A 2 和 A3 是全集 U 的子集，则形如 Ai(Ai为 Ai 或 )的集合

11、称为由 A1、A 2 和 A331i产生的小项。试证由 A1、A 2 和 A3 所产生的所有非空小项的集合构成全集 U 的一个划分。证明 小项共 8 个，设有 r 个非空小项 s1、s 2、s r(r8)。对任意的 aU，则 aA i 或 a ，两者必有一个成立，取 Ai为包含元素 a 的 Ai 或 ，则i ia Ai，即有 a si，于是 U si。又显然有 siU，所以 U si。31r1r1r1r1任取两个非空小项 sp 和 sq，若 sps q，则必存在某个 Ai 和 分别出现在 sp 和 sq 中，于是isps q。综上可知，s 1，s 2，s r是 U 的一个划分。五、 （15 分

12、）设 R 是 A 上的二元关系，则：R 是传递的R *RR。证明 (5)若 R 是传递的，则R*Rz( xRzzSy )xRccSy ，由 R 是传递的得 xRy，即有 R，所以 R*RR。反之，若 R*RR，则对任意的 x、y、zA，如果 xRz 且 zRy，则R*R，于是有R，即有 xRy，所以 R 是传递的。六、 （15 分）若 G 为连通平面图，则 nm r2，其中，n、m 、r 分别为 G 的结点数、边数和面数。证明 对 G 的边数 m 作归纳法。当 m0 时，由于 G 是连通图，所以 G 为平凡图，此时 n1，r1，结论自然成立。假设对边数小于 m 的连通平面图结论成立。下面考虑连

13、通平面图 G 的边数为 m 的情况。设 e 是 G 的一条边，从 G 中删去 e 后得到的图记为 G，并设其结点数、边数和面数分别为 n、m和r。对 e 分为下列情况来讨论：若 e 为割边，则 G有两个连通分支 G1 和 G2。G i 的结点数、边数和面数分别为 ni、m i 和 ri。显然n1n 2n n，m 1m 2m m 1，r 1r 2r1r1 。由归纳假设有n1m 1r 12，n 2m 2r 22，从而( n1n 2)(m 1m 2)( r1r 2)4，n(m1) (r1)4，即nmr2。若 e 不为割边，则 nn，mm1，rr1，由归纳假设有 nmr2，从而 n(m1)r 1 2，

14、即 nmr2。由数学归纳法知，结论成立。七、 （10 分）设函数 g：AB，f ：BC，则：(1)fg 是 A 到 C 的函数；(2)对任意的 xA，有 fg(x)f(g(x)。证明 (1)对任意的 xA，因为 g：AB 是函数，则存在 yB 使g。对于 yB，因f：B C 是函数，则存在 zC 使f 。根据复合关系的定义，由g 和f 得g*f，即 fg 。所以 DfgA 。对任意的 xA，若存在 y1、 y2C，使得、fgg*f，则存在 t1 使得g 且f，存在 t2 使得g 且f 。因为 g：AB 是函数，则 t1t 2。又因 f：BC 是函数，则 y1y 2。所以 A 中的每个元素对应

15、C 中惟一的元素。综上可知，fg 是 A 到 C 的函数。(2)对任意的 xA，由 g：AB 是函数，有g 且 g(x)B，又由 f：BC 是函数，得f，于是 g*ff g。又因 fg 是 A 到 C 的函数，则可写为 fg(x)f(g(x) 。八、 （15 分）设 是的子群，定义 R|a、bG 且 a1 *bH，则 R 是 G 中的一个等价关系，且a RaH。证明 对于任意 aG，必有 a1 G 使得 a1 *aeH，所以R。若R ，则 a1 *bH。因为 H 是 G 的子群，故(a 1 *b)1 b 1 *aH。所以R。若R ， R，则 a1 *bH，b 1 *cH 。因为 H 是 G 的

16、子群，所以(a 1 *b)*(b1 *c)a 1 *cH，故 R。综上可得，R 是 G 中的一个等价关系。对于任意的 ba R，有R，a 1 *bH，则存在 hH 使得 a1 *bh，ba*h，于是baH， aRaH。对任意的 baH，存在 hH 使得 ba*h，a 1 *bhH，R ， 故 aHaR。所以， aRaH 。发到哪？给个邮箱啊一、填空 20% （每小题 2 分）1设 （N：自然数集，E+ 正偶数） 则 。2A，B，C 表示三个集合，文图中阴影部分的集合表达式为 。3设 P，Q 的真值为 0，R，S 的真值为 1，则的真值= 。4公式 的主合取范式为。5若解释 I 的论域 D 仅包

17、含一个元素，则 在 I 下真值为。6设 A=1， 2，3，4 ，A 上关系图为则 R2 = 。7设 A=a， b，c，d，其上偏序关系 R 的哈斯图为则 R= 。8图 的补图为 。9设 A=a， b，c，d ， A 上二元运算如下：* a b c dabcd a b c db c d ac d a bd a b c那么代数系统的幺元是 ，有逆元的元素为 ，它们的逆元分别为 。10下图所示的偏序集中，是格的为 。二、选择 20% （每小题 2 分）1、下列是真命题的有（ ）A ； B ；C ； D 。2、下列集合中相等的有（ ）A 4，3 ；B ，3，4 ；C4， ，3，3；D 3，4。3、设

18、A=1， 2，3，则 A 上的二元关系有（ ）个。A 23 ； B 32 ； C ； D 。4、设 R，S 是集合 A 上的关系，则下列说法正确的是（ ）A若 R，S 是自反的， 则 是自反的；B若 R，S 是反自反的， 则 是反自反的；C若 R，S 是对称的， 则 是对称的；D若 R，S 是传递的， 则 是传递的。5、设 A=1， 2，3，4 ，P（A）（A 的幂集）上规定二元系如下则 P（ A）/ R=（ ）AA ；BP(A) ；C 1，1，2，1，2 ， 3，1，2 ，3，4；D ，2 ，2，3 ，2，3，4，A6、设 A= ，1，1，3 ，1，2，3 则 A 上包含关系 “ ”的哈斯图

19、为（ ）7、下列函数是双射的为（ ）Af : I E , f (x) = 2x ； Bf : N N N, f (n) = ；Cf : R I , f (x) = x ； Df :I N, f (x) = | x | 。（注：I整数集，E偶数集， N自然数集，R 实数集）8、图 中 从 v1 到 v3 长度为 3 的通路有（ ）条。A 0； B 1； C 2； D 3。9、下图中既不是 Eular 图，也不是 Hamilton 图的图是（ ）10、在一棵树中有 7 片树叶，3 个 3 度结点，其余都是 4 度结点则该树有（ ）个 4 度结点。A1； B2； C3； D4 。三、证明 26% 1

20、、 R 是集合 X 上的一个自反关系，求证：R 是对称和传递的，当且仅当和在 R 中有在 R 中。（8 分）2、 f 和 g 都是群到的同态映射，证明是 的一个子群。其中 C= (8 分)3、 G= (|V| = v，|E|=e ) 是每一个面至少由 k（k 3）条边围成的连通平面图，则 ， 由此证明彼得森图（Peterson ）图是非平面图。（11 分）四、逻辑推演 16%用 CP 规则证明下题（每小题 8 分）1、 2、 五、计算 18%1、设集合 A=a，b，c，d上的关系 R= , , , 用矩阵运算求出 R 的传递闭包 t (R)。 （9 分）2、如下图所示的赋权图表示某七个城市 及

21、预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。 （9 分）试卷一答案：一、填空 20% （每小题 2 分）1、0 ， 1，2 ，3 ，4，6； 2、 ；3、1； 4、 ； 5、1；6 、, , , ；7、, IA ；8、9、a ；a , b , c ,d ；a , d , c , d ；10、c; 二、选择 20% （每小题 2 分）题目 1 2 3 4 5 6 7 8 9 10答案 C D B、C C A D C A D B A三、证明 26%1、 证：“ ” 若 由 R 对称性知 ，由 R 传递性得 “ ” 若 ， 有 任意 ，因 若 所

22、以 R 是对称的。若 ， 则 即 R 是传递的。2、 证 ，有 ，又 是 的子群。3、 证：设 G 有 r 个面，则 ，即 。而 故 即得 。（ 8 分）彼得森图为 ，这样 不成立，所以彼得森图非平面图。（3 分） 二、 逻辑推演 16%1、 证明： P（附加前提） TI P TI TI TI P TI CP2、证明 P（附加前提） US P US TI UG CP三、 计算 18%1、 解：， ， t (R)= , , , , , , , , 2、 解： 用库斯克（ Kruskal）算法求产生的最优树。算法略。结果如图：树权 C(T)=23+1+4+9+3+17=57 即为总造价。面给出证明:(1) Some x is Y(x) P (2) Y(c) (1) T(1)，ES (3)Some(S(x)W(x) P(4)S(c)W(c) T(3),US(5)S(c) T(4),I(6)S(c)Y(c) T(2)(5),I(7)(Every)S(x)Y(x) T(6),EG