《离散数学综合练习含答案》由会员分享，可在线阅读，更多相关《离散数学综合练习含答案（4页珍藏版）》请在金锄头文库上搜索。
1、离散数学综合练习二一、单项选择题一、单项选择题（每题 2 分 ）16 %1. 设 P：4 大于 2，Q：3 大于 2，命题“4 大于 2 仅当 3 大于 2”符号化为 ( )(A)(B)( )(D)PQQPC PQPQ 2 设 F(x)：x 是金属，G(y)：y 是液体，H(x,y)：x 溶解在 y 中，那么命题“任何金属都可以溶解在某种液体中”符号化为 ( )(A) (B) ( ( )( ( )( , )x F xy G yH x y( ( )( ( )( , )x F xy G yH x y (C) (D) ( ( )( ( )( , )x F xy G yH x y ( ( )( )(
2、, )x y F xG yH x y 3. 命题公式是 ( )()pqp(A) 重言式 (B) 矛盾式 (C) 可满足式 (D) 以上 3 种都不是4. 下列各式命题为假的是 ( )(A) (B) (C) (D) 5. 设函数且，则是 ( ) :fRR3( )215f xxxf(A) 满射,非单射 (B)单射，非满射 (C) 双射 (D)非单射，非满射6. 与命题公式等值的公式是（ ）()pqr(A) (B) ()pqr()pqr(C) (D) ()pqr()pqr7. 设 A=a,b,c，A 上的关系 R=,，则 R 是 ( )（A）自反的 （B）反自反的 （C）反对称的 （D）等价的8.
3、设无向图是哈密顿图, 则对于任意的且,均有,GV E1VV1V 。上述给出的是哈密顿图的（ ）11()P GVV（A）充分条件 （B）必要条件 （C）充分必要条件 （D）都不是1. 设是人，犯错误，则命题“没有不犯错误的人”的符号化是 ( ):F xx( ):G xxadebcf图1，其前束范式为 。2. 命题“整数列（2,2,3,4,5）可简单图化”的真值为 。3.设 D为 4 阶有向图，邻接矩阵为 A(D)1234 ,Vv v v v=，那么 D 中顶点的出度为 。 11001000 11000121 4v4. 设全集 U=1,2,3,4,5,6,7，A=1,3,5,7，B=1,2,6,7
4、，则 B- A= 。5. 设集合 A=a,b,c，R 为 A 上的关系，R=,，则 R 的对称闭包是 。( )s R6. 完全二部图为欧拉图，则应满足 。, r sK, r s7. 图的通路中顶点不重复的通路是 通路。8. 设图和,若 则是的,GV E,GV EGG生成子图。三、化简计算题三、化简计算题 51 %得分1. （6 分）设，试求幂集。 , Ab c( )P AA2. （10 分）用等值演算法求公式的主析取范式，并求成真赋值。()pqr3. （9 分）化简集合表达式：。()()()ABCABCBACIIUIUI4. （10 分）右图是偏序集的哈斯图，分别写出集合 A 和偏序关系的,A
5、 R集合表达式，并指出 A 的极大元、极小元、最大元和最小元。5. （10 分）右图所示无向图 G 中，实线边所示子图为 G 的一棵生成树 T，求G 对应 T 的基本割集系统。6. （6 分）已知无向图 G 中，有 4 个 2 度顶点，有 2个 3 度顶点，1 个 4 度顶点，其余的顶点为树叶，求 T 的树叶数。 四、证明题四、证明题 15 %得分baedcfghijk1.（8 分）用直接法证明下面推理：前提：，结论：, , qs rp qrps2.（7 分）构造推理证明，前题：，结论：( ( )( )x F xG x( )( )xF xxG x 离散数学综合练习二一、一、 单项选择题（每题单
6、项选择题（每题 2 分，共分，共 16 分）分） （1）A （2）C （3）A （4）D （5）C （6）B （7）C （8）B 二、二、 填空题填空题 （每空（每空 2 分，共分，共 18 分）分）1，( ( )( )x F xG x( ( )( )x F xG x2 0 3 4 4 1,75,a aa bb cc ab ac ba c 6r,s 均为正偶数 7 初级 8 ,VV EE三、化简计算题（共三、化简计算题（共 51 分）分）1. (6 分) ( ) , , , , P Abcb c( ), , , , , , , , ,P AAbcb bb cc bccb c bb cc 2 .
7、(10 分)解：主析取范式 原式=6713513567()()() ()()()()()() ()pqrrppqqr pqrpqrpqrpqrpqrpqr mmmmmmmmmm 成真赋值为：001，011，101，110，111 3. (9 分)解：原式=()()()()()()()()() ()() ()() ()ABCABCABCABCABCABCABCBCAAACBB BCEACE BCAC ABC IIUIIUIIIIUIIUIIUIIIIUUIIU IIUII IUI UI4. (10 分)解：Aa,b,c,d,e,f, ,ARa ba ca da ea fb ec ec fd fI
8、 U5 分极大元：e,f ，极小元：a；最大元：无，最小元：a。 5. (10 分) 解：b,c,f,g,h,i 为树枝，它们对应的基本割集为 S1=b,a, S2=c,d,j, S3=f,e,k, S4=g,a,e,k, S5=h,d,e,j,k, S6=i,d,e; 每个各 1.5 分 基本割集系统为 S1，S2，S3，S4, S5 ,S6 6(6 分) 解： T 的树叶数有 x 个，根据握手定理可得 14 22 3 1 42( )2(6)ni ixmd vx 解得： 6x 四、证明题（共 15 分） 1.（8 分） 证明： 前提引入rp 置换pr 前提引入qr 置换rq 假言三段论pq 前提引入qs 假言三段论ps 置换ps2. （7 分）证明： 附加前提引入( )xF x 置换( )x F x ( )F c 前提引入( ( )( )x F xG x ( )( )F cG c 析取三段论( )G c ( )xG x
