离散数学习题集十五套含答案.doc

1、 1 离散数学试题与答案试卷一 一、填空 20% （每小题 2 分） 1设 7|) ,5()(| xExxBxNxxA 且且（ N：自然数集， E+ 正偶数） 则 BA 0， 1， 2， 3， 4， 6 。 2 A， B， C 表示三个集合，文图中阴影部分的集合表达式为 ACB )( 。 3设 P， Q 的真值为 0， R， S 的真值为 1，则 )()( SRPRQP 的真值 = 1 。 4公式 PRSRP )()( 的主合取范式为 )()( RSPRSP 。 5若解释 I 的论域 D 仅包含一个元素，则 )()( xxPxxP 在 I 下真值为 1 。 6设 A=1， 2， 3， 4， A

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

3、C ） A 4， 3 ； B ， 3， 4； C 4， ， 3， 3； D 3， 4。 3、设 A=1， 2， 3，则 A 上的二元关系有（ C ）个。 A 23 ； B 32 ； C 332 ； D 223 。 4、设 R， S 是集合 A 上的关系，则下列说法正确的是（ A ） A若 R， S 是自反的， 则 SR 是自反的； B若 R， S 是反自反的， 则 SR 是反自反的； A B C 2 C若 R， S 是对称的， 则 SR 是对称的； D若 R， S 是传递的， 则 SR 是传递的。 5、设 A=1， 2， 3， 4， P（ A）（ A 的幂集）上规定二元系如下 |(|)(,|,

4、 tsAptstsR 则 P（ A） / R=（ D ） A A ； B P(A) ； C 1， 1， 2， 1， 2， 3， 1， 2， 3， 4； D ， 2， 2， 3， 2， 3， 4， A 6、设 A= ， 1， 1， 3， 1， 2， 3则 A 上包含关系“ ”的哈斯图为（ C ） 7、下列函数是双射的为（ A ） A f : I E , f (x) = 2x ； B f : N N N, f (n) = ； C f : R I , f (x) = x ； D f :I N, f (x) = | x | 。 （注： I 整数集， E 偶数集， N 自然数集， R 实数集） 8、图

5、中 从 v1到 v3 长度为 3 的通路有（ D ）条。 A 0； B 1； C 2； D 3。 9、下图中既不是 Eular 图，也不是 Hamilton 图的图是（ B ） 10、在一棵树中有 7 片树叶， 3 个 3 度结点，其余都是 4 度结点则该树有（ A ）个 4 度结点。 A 1； B 2； C 3； D 4 。 三、证明 26% 1、 R 是集合 X 上的一个自反关系，求证 ： R 是对称和传递的，当且仅当 和 在 R 中有 在 R 中。（ 8 分） 1、 证 ：“ ” Xcba , 若 R c,ab,aa,bc,bb,ac,ac,ba,ab,aa,bb,acb,ab,c,a到

6、 的同态映射，证明 是 的一个子群。其中C= )()(| 1 xgxfGxx 且 (8 分 ) 证 Cba , ，有 )()(),()( bgbfagaf ，又)()(,)()( 1111 bgbgbfbf )()()()( 1111 bgbgbfbf af( agbgagbfafb ()(*)()(*)() 111 )1b a Cb 1 是 的子群。 3 、 G= (|V| = v， |E|=e ) 是每一个面至少由 k（ k 3）条边围成的连通平面图，则 2)2( kvke ， 由此证明彼得森图（ Peterson）图是非平面图。（ 11 分） 证： 设 G 有 r 个面，则 rkFder

7、i i 1 )(2 ，即 ker 2 。而 2 rev 故keevrev 22 即得 2)2( kvk 。（ 8 分） 彼得森图为 10,15,5 vek ， 这样 2)2( kvke 不成立， 所以彼得森图非平面图。（ 3 分） 四、逻辑推演 16% 用 CP 规则证明下题（每小题 8 分） 1、 FAFEDDCBA , 证明： A P（附加前提） BA T I DCBA P DC T I D T I ED T I FED P F T I FA CP 2、 )()()()( xxQxxPxQxPx )(xxP P（附加前提） )(cP US )()( xQxPx P )()( cQcP US

8、 )(cQ T I )(xxQ UG )()( xxQxxP CP 五、计算 18% 1、设集合 A=a， b， c， d上的关系 R= , , , 用矩阵运算求出 R 的传递闭包 t (R)。 （ 9 分） 解： 0000100001010010RM， 00000000101001012 RRR MMM 4 000000000101101023 RRR MMM ，000000001010010134 RRR MMM 0000100011111111432)( RRRRRt MMMMM t (R)= , , , , , , , , 2、如下图所示的赋权图表示某七个城市 721 , vvv 及预

9、先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。 （分） 解： 用库斯克（ Kruskal）算法求产生的最优树。算法略。结果如图： 树权 C(T)=23+1+4+9+3+17=57 即为总造价。 试卷二试题与答案 一、填空 20% （每小题 2 分） 1、 P：你努力， Q：你失败。“除非你努力，否则你将失败”的翻译为 QP ；“虽然你努力了，但还是失败了”的翻译为 QP 。 2、论域 D=1， 2，指定谓词 P 则公式 ),( xyyPx 真值为 T 。 P (1,1) P (1,2) P (2,1) P (2,2) T T F F 3 、设

10、S=a1 ， a2 ， ， a8 ， Bi 是 S 的 子 集 ， 则 由 B31 所 表 达 的 子 集 是 , 876540001111131 aaaaaBB 。 4 、设 A=2 ， 3 ， 4 ， 5 ， 6 上 的 二 元 关 系 |, 是质数xyxyxR ，则 R= R=,（列举法）。 5 R 的关系矩阵 M R= 0000011111110001111111111。 5、设 A=1， 2， 3，则 A 上既不是对称的又不是反对称的关系 R= R=,； ； A 上既是对称的又是反对称的关系 R= R=, 。 6、设代数系统 ，其中 A=a， b， c,则幺元是 A ；是否有幂等性

11、否 ； 是否有对称性 有 。 7、 4 阶群必是 Klein 四元群 群或 循环群 群。 8、下面偏序格是分配格的是 B 。 9、 n 个结点的无向完全图 Kn的边数为 )1(21 nn ，欧拉图的充要条件是 图中无奇度结点且连通。 10、公式 RQPQPP )()( 的根树表示为 二、选择 20% （每小题 2 分） 1、在下述公式中是重言式为（ BD ） A )()( QPQP ； B )()()( PQQPQP ； C QQP )( ； D )( QPP 。 2、命题公式 )()( PQQP 中极小项的个数为（ D），成真赋值的个数为（ D ）。 A 0； B 1； C 2； D 3 。

12、 3、设 2,1,1,S ，则 S2 有（ D ）个元素。 A 3； B 6； C 7； D 8 。 4、设 3 ,2 ,1 S ，定义 SS 上的等价关系 , | , cbdaSSdcSSbadcbaR 则由 R 产 生的SS 上一个划分共有（ B ）个分块。 A 4； B 5； C 6； D 9 。 * a b c a b c a b c b b c c c b 6 5、设 3 ,2 ,1 S ， S 上关系 R 的关系图为则 R 具有（ D ）性质。 A自反性、对称性、传递性； B反自反性、反对称性； C反自反性、反对称性、传递性； D自反性 。 6、设 , 为普通加法和乘法，则（ A

13、） ,S 是域。 A ,3| QbabaxxS B ,2| ZbanxxS C ,12| ZnnxxS D 0| xZxxS = N 。 7、下面偏序集（ B ）能构成格。 8、在如下的有向图中，从 V1 到 V4长度为 3 的道路有（ B ）条。 A 1； B 2； C 3； D 4 。 9、在如下各图中（ B ）欧拉图。 10、设10、 R 是实数集合，“ ”为普通乘法，则代数系统 是（ C ）。 A群； B独异点； C半群 。 三、证明 46% 1、 设 R 是 A 上一个二元关系， ),(),(|, RbcRcaAcAbabaS 且有对于某一个试证明若 R是 A 上一个等价关系，则 S

14、 也是 A 上的一个等价关系。（ 9 分） 1、（ 9 分） （ 1） S 自反的 Aa ，由 R 自反， ),(),( RaaRaa ， Saa , （ 2） S 对称的 传递对称定义RSabRRbcRcaSRbcRcaSbaAba,),(),(),(),(,7 （ 3） S 传递的 定义传递SScaRRcbRbaRceRebRbdRdaScbSbaAcba,),(),(),(),(),(),(,由（ 1）、（ 2）、（ 3）得； S 是等价关系。 2、用逻辑推理证明：所有的舞蹈者都很有风度，王华是个学生且是个舞蹈者。因此有些学生很有风度。 证明：设 P(x)： x 是个舞蹈者； Q(x)

15、： x很有风度； S(x)： x是个学生； a：王华 上述句子符号化为： 前提： )()( xQxPx 、 )()( aPaS 结论： )()( xQxSx 3 分 )()( aPaS P )()( xQxPx P )()( aQaP US )(aP T I ).(aQ T I )(aS T I )()( aQaS T I )()( xQxSx EG 3 、若 BAf : 是从 A 到 B 的 函 数 ， 定 义 一 个 函 数 ABg 2: 对任意 Bb 有)()(|)( bxfAxxbg ，证明：若 f 是 A 到 B 的满射，则 g是从 B 到 A2 的单射。（ 10分） 证明 ： )(

16、, 2121 bbBbb Aaaf 21 ,满射 21212211 ,),()(,)(,)( aafafafbafbaf 是函数由于且使 )()()(),()(),( )()(|)() ,)()(|)( 2112212211 2211 bgbgbgabgabgabga bxfAxxbgbxfAxxbg 但又 为单射任意性知由 gbb , 21 。 4、若无向图 G 中只有两个奇数度结点，则这两个结点一定连通。（ 8 分） 证明：设 G 中两奇数度结点分别为 u 和 v，若 u， v 不连通，则 G 至少有两个连通 分支 G1、 G2 ，使得 u 和 v 分别属于 G1和 G2，于是 G1和 G

17、2中各含有 1 个奇数度结点，这与图论基本定理矛盾，因而 u， v一定连通。 5、 设 G 是具有 n 个结点的无向简单图，其边数 2)2)(1(21 nnm ，则 G 是 Hamilton 图（ 8 分） 证明： 证 G 中任何两结点之和不小于 n。 反证法：若存在两结点 u， v 不相邻且 1)()( nvdud ,令 , vuV ，则 G-V1 是具有 n-2个结点的简单图，它的边数 )1(2)2)(1(21 nnnm ,可得 13)(2(21 nnm ，这与 G1=G-V1为 n-2 个结点为简单图的题设矛盾，因而 G 中任何两个相邻的结点度数和不少于 n。 所以 G 为 Hamilt

18、on 图 . 四、 计算 1、设 是一个群， 这里 +6 是模 6 加法， Z6=0 ， 1， 2， 3， 4， 5，试求出 的所有子群及其相应左陪集。解：子群有 ； ； ； 0的左陪集： 0， 1； 2， 3； 4， 5 0， 3的左陪集： 0， 3； 1， 4； 2， 5 0， 2， 4的左陪集： 0， 2， 4； 1， 3， 5 2、 权数 1， 4， 9， 16， 25， 36， 49， 64， 81， 100 构造一棵最优二叉树。（ 7 分） 8 试卷三试题与答案 一、 填空 20% （每空 2 分） 1、 设 f， g是自然数集 N 上的函数 xxgxxfNx 2)(,1)(, ，

19、 则 )(xgf 2(x+1) 。 2、 设 A=a， b， c， A 上二元关系 R= , , , 则 s（ R） = a, c,a, b,c, c,c, a,b, a,a, a 。 3、 A=1， 2， 3， 4， 5， 6， A 上二元关系 |, 是素数yxyxT ，则用列举法 T= 3,6,2,6,2,4,5 , 1,3 , 1,2 , 1 ； T 的关系图为 ； T 具有 反对称性、反自反性 性质。 4、 集合 2,2,A 的幂集 A2 = 2,2, ,2 ,2, 。 5、 P， Q 真值为 0 ； R， S 真值为 1。则 )()()( SRQPSRPw f f 真值为 1。 6、

20、 RRQPwf f )( 的主合 )()()( RQPRQPRQP 。 7、 设 P（ x）： x 是素数， E(x)： x 是偶数， O(x)： x 是奇数 N (x,y)： x 可以整数 y。则谓词),()()( xyNyOyxPxwf f 的自然语言是 任意 x，如果 x是素数则存在一个 y， y 是奇数且 y 整除 x 。 8、 谓词 ),(),(),( uyxuQzyPzxPzyxwf f 的前束范式为 ),(),(),( uyxQzyPzxPuzyx 。 二、 选择 20% （每小题 2 分） 1、 下述命题公式中，是重言式的为（ C ）。 A、 )()( qpqp ； B、 )(

21、)()( pqqpqp ； C、 qqp )( ； D、 qpp )( 。 2、 rqpwf f )( 的主析取范式中含极小项的个数为（ C ）。 A 、 2； B、 3； C、 5； D、 0； E、 8 。 3、 给定推理 )()( xGxFx P )()( yGyF US )(xxF P )(yF ES )(yG T I )(xxG UG )()()( xxGxGxFx 推理过程中错在（ C ）。 A、 - ; B、 - ; C、 - ; D、 - ; E、 - 4、 设 S1=1， 2， 8， 9， S2=2， 4， 6， 8， S3=1， 3， 5， 7， 9， S4=3， 4， 5

22、， S5=3， 5，在条件 31 SXSX 且 下 X 与（ C ）集合相等。 A、 X=S2或 S5 ； B、 X=S4或 S5； C、 X=S1， S2或 S4； D、 X 与 S1， S5中任何集合都不等。 5、 设 R 和 S 是 P 上的关系， P 是所有人的集合， ,|, 的父亲是 yxPyxyxR ，,|, 的母亲是 yxPyxyxS 则 RS 1 表示关系 （ A ）。 A、 ,|, 的丈夫是 yxPyxyx ； B、 ,|, 的孙子或孙女是 yxPyxyx ； C、 ； D、 ,|, 的祖父或祖母是 yxPyxyx 。 6、 下面函数（ B ）是单射而非满射。 A、 12)(

23、,: 2 xxxfRRf ； B、 xxfRZf ln)(,: ； C、 的最大整数表示不大于 xxxxfZRf ,)(,: ； D、 12)(,: xxfRRf 。 其中 R 为实数集， Z 为整数集， R+， Z+分别表示正实数与正整数集。 9 7、设 S=1， 2， 3， R 为 S 上的关系，其关系图为则 R 具有（ D ）的性质。 A、自反、对称、传递； B 什么性质也没有； C、反自反、反对称、传递； D、自反、对称、反对称、传递。 8、设 2,1,1,S ，则有（ A ） S 。 A、 1,2 ； B、 1,2 ； C、 1 ； D、 2 。 9、设 A=1 ,2 ,3 ，则 A

24、 上有（ D ）个二元关系。 A、 23 ； B、 32 ； C、 32 ； D、 232 。 10、全体小项 合取式为（ C ）。 A、可满足式； B、矛盾式； C、永真式； D、 A， B， C 都有可能。 三、 用 CP 规则证明 16% （每小题 8 分） 1、 FAFEDDCBA , A P（附加前提） BA T I DCBA P DC T I D T I ED T I FED P F T I FA CP 2、 )()()()( xxQxxPxQxPx )()()()( )()()()()( xxQxxPxQxPx xxQxPxxxQxxP 本题可证 )( xxP P（附加前提） )

25、( xPx T E )(aP ES )()( xQxPx P )()( aQaP US )(aQ T I )(xxQ EG )()( xxQxxP CP 四、 （ 14%） 集合 X=, , , ， R=,|x1+y2 = x2+y1 。 1、 证明 R 是 X 上的等价关系。 （ 10 分） 2、 求出 X 关于 R 的商集。（ 4 分） 1. 证明：（ 1）自反性： yxyxXyx 由于, 自反RRyxyx , （ 2）对称性： XyxXyx 2211 , 时当 Ryxyx 2211 , 21121221 yxyxyxyx 也即即 有对称性故 RRyxyx 1122 , （ 3）传递性：

26、XyxXyxXyx 332211 , 时且当 RyxyxRyxyx 33222211 , )2( )1(23321221 yxyx yxyx即23123221)2()1( yxyxyxyx 即 1331 yxyx 有传递性故 RRyxyx 3311 , 由（ 1）（ 2）（ 3）知： R 是 X 上的先等价关系。 2、 X/R= 2,1 R 10 五、（ 10%） 设集合 A= a ,b , c , d 上关系 R= , , , 要求 1、写出 R 的关系矩阵和关 系图。（ 4 分） 2、用矩阵运算求出 R 的传递闭包。（ 6 分） 0000100001010010RM； 0000000010

27、1001012 RRR MMM 关系图 2、 000000000101101023 RRR MMM 2340000000010100101RRRR MMMM , 4635 RRRR MMMM 0000100011111111432)( RRRRRt MMMMMt (R)= , , , , , , , , 。 六、（ 20%） 1、（ 10 分）设 f 和 g是函数，证明 gf 也是函数。 2、（ 10 分）设函数 STfTSg : ，证明 STf : 有一左逆函数当且仅当 f 是入射函数。 1、（ 1） )()(|,)()(|, xgxfyd o m gd o m fxyx xgyxfyd o

28、 m gxd o m fxyxgf )()(,| xgxfd o m gd o m fxxd o m hgd o m f gfh 令 （ 2） )()()(|, xgxfxhyd o mgd o mfxyxh 使得若有对 21 , yydo m hx )()()(,)()()( 21 xgxfxhyxgxfxhy 21,)( yygf 有是函数或由于 )( xhyydo m hx 使得有唯一即 也是函数gf 。 2、证明： ttfgTtgf )(,“ 则对有一左逆若 是入射所以是入射故 ffg , 。 的左逆元是故则且若或只有一个值则对令若此时令使入射由定义如下是入射fgtsgtfgstfctsgSsTcsgTfstsgstfTtfTfsSTff,)()()()(,)()(,)()(,|,),(:,“ 左逆函数为使必能构造函数入射即若 fggf , 。