(离散数学)自测题

《(离散数学)自测题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、离散数学自测题2011.12一、单项选择题(每题2分)16%1.设P：2>1,Q：3>2,则命题“只有2<1,才有3>2”符号化为()(A)P—>—yQ(B)—iP—>Q(C)P<->—Q(D)Q—P2设F(x)：兀是运动员，G(y)：y是世界,动员游玩过整个世界”符号化为()(A)Vx(F(x)^3y(G(y)A//(x,y)))H(x,y)：兀游玩过y,那么命题“某些运(B)玉(F(兀)aVy(G(y)THgy)))(C)玉(F⑴T0y(G(刃人Hgy)))(D)玉Vy((F(兀)TG(y))人Hg

2、y))3.命题公式—)(pTq)/q是(4.(A)矛盾式(B)重言式(C)可满足式(D)蕴涵式若A-B二①，则下列结论不可能正确的是((D)3uA(A)A=0(B)B=05.设A={a,b,c},A上的关系/?={,,,},(A)自反的(B)传递的(C)对称的(D)反对称的6.设函数广RtZ且/(x)=

3、_xj，则/是((A)单射，非满射(B)满射，非单射(C)双射(D)非单射，非满射7.设G是由5个顶点组成的完全图，则从图G中删去()条边可以得到树。(A)4(B

4、)5(C)6(D)8)条件。8.无向图G=是连通图且没有奇度顶点是欧拉图的(A)充分必要条件(B)充分条件(C)必要条件(D)都不是二、填空题(每空2分)18%9.设F(x):x是汽车，G(y):y是火车，x比y快，则命题“说凡是火车就比汽车快是不对的”符号化是其另一种等值形式为8.设个体域D二{Q0,c},公式-JxX/yGCOviFO））的消去量词后等值式为11•一棵树有3个2度顶点，2个3度顶点，1个4度顶点，其余都是树叶，则其树叶数为12.命题“整数列（2,2,3,3,5,5）可图化”的

5、真值为110012013•设D=为4阶有向图，《=山*2，叫,儿}，邻接矩阵为A（D）=011101那么D中顶点v2的入度为14.在1到400的整数屮（包含1和400）满足各条件整除个数：可以被3整除但不能被5整除的是；可以被5整除，但不能被3整除的是o15.设集合A二{d,b,c},/?为A上的关系，R={,,},则/?的传递闭包r（R）是o三、计算题54%16.（6分）设A,B,C是Z子集，其中A={xx=2k^keZA0

6、x2<80axg

7、Z],用列元素法表示集合B-A。17.（6分）设集合4={b,c},试求幕集P（A）xA。18.（10分）用等值演算法求公式的主析取范式，并求成真赋值。19.（8分）画出偏序集,,,,,,,,}U厶20.（14分）右图所示无向图G中，实线边所示子图为G的一棵生成树丁，求G对应卩的基本回路系统和基本割集系统。21

8、.（10分）己知有向图D如右图所示，求（1）邻接矩阵A（D）；（2）D中长度是2的回路数；（3）0中从血到巾长度是3的通路数；（4）D是哪类连通图，为什么?a四、证明题12%16.(5分)证明对任意集合A,B,C,有(A—B)—C=(4-C)—(B—C)。17.(7分)在自然推理系统P中构造推理证明：前提：(pv(y)^r,r^(5vw),w—->(5vr),结论：一«g补充题:1.(8分)右上图是偏序集vA,心〉的哈斯图，分别写出集合A和偏序关系心的2.右下图无向图是()图。集合表达式，并指出A的极大元

9、、极小元、最大元和最小元。(A)欧拉图(B)哈密顿图(C)既是欧拉图，又是哈密顿图(D)都不是3.设B不含有x,VXA(x)B)等值于()(A)Vx4(x)tB(B)lr(A(x)vB)(C)(D)3x(A(x)aB)4•设集合从{d,b,c0},/?/和&为A上的关系，其中Ri={y},/?2二{,,},贝9R2。片为。5.(12分)设7个字母在通信中出现的频率如下：A:30%,B:20%,C:13%,D:12%,E:10%,F:9%,G:6%用Huff

10、man算法求传输它们的最佳前缀码。要求画出最优树，指出每个字母对应的编码。并指出传输100个按上述频率出现字母所需二进制数字个数。6.(10分)将下列命题推理符号化并给岀形式证明：若张超与李志都是计算机系学生，则王红是中文系学生，若王红是中文系学生，则她爱看小说，可是王红不爱看小说，张超是计算机系学生，所以李志不是计算机系的学生。7.(8分)证明对任意集合A,B,C,有(AUB)㊉(AUC)=(B㊉C)-A。8.(15分)在1