离散数学期末考试含答案

1、离散数学综合练习题一一、单项选择题(每题2分)16%设P:王强是南方人，Q:他怕热.命题“王强不怕热是因为他是南方人”符号化为()(A)PQ(B)PQ(C)QP(D)QP2设F(x)：x是熊猫，G(y):y是竹子，H(x,y)：x喜欢y.那么命题“有些熊猫喜欢各种的竹子”符号化为()(A)x(F(x)y(G(y)H(x,y)(B)x(F(x)y(G(y)H(x,y)(C)x(F(x)y(G(y)H(x,y)(D)yx(F(x)(G(y)H(x,y)3 .命题公式(pq)p是()(A)重言式(B)矛盾式(C)可满足式(D)以上3种都不是4 .设集合A=a,b,c,d,e则下列各式为真的是()(A

2、)CA(B)cCA(C)c,d,eA(D)a,bA5 .设函数f:NN且f(x)3x,则f是()(A)单射，非?t射(B)满射,非单射(C)双射(D)非单射，非满射6 .设E为全集，A,B为非空集，且BA,则空集为()(A)AIB(B):AIB(C)AI:B(D):AI:B7 .设A=0,1,2,3,A上的关系R=,则R是()(A)自反的(B)对称的(C)反对称的(D)可传递的8 .无向图K3,3是()(A)哈密顿图(B)欧拉图(C)完全图(D)平面图二、填空题(每空2分)18%1 .设F(x):x是火车，G(y):y是汽车，H(x,y)：x比y快，则命题”说所有火车比有的汽车快是不对的“符号

3、化是,其另一种等值形式为。2 .设个体域D=a,b,公式x(F(x)y(G(y)的消去量词后为13.设有向图D= 的邻接矢I阵为 A(D)= 0002000110100，那么| E|=104 .n阶m条边的无向连通图G,要确定G的一棵生成树T必须删去G中的边数5 .设集合A=a,b,c,R为A上的关系，R=,则R的传递闭包t(R)6 .设G是n阶无向简单哈密顿图，则对于任意不相邻的顶点v,Vj均有d（vjd（Vj）n,此结论正确吗答。7 .设X1,2,3,4,Ya,b,c,f1,a,2,b,3,c，则“f是从X到Y的函数”的真值为。8 .命题“整数列（2,2,3,3,4,4）可简单图化”的真值

4、为。三、化简计算题56%1. （12分）用等值演算法求公式（pq）（pr）的主合取范式，并求成假赋值。2. （6分）一棵无向树T有8片树叶，2个3度支点，其余的分支点都是小于4度顶点，问T至少有几个顶点。3. （8分）对于集合A=2,3,4,5,6,9,10,12,18,20,60与整除关系R,画出偏序集A,R的哈斯图，并求A的极大元、极小元、最大元、最小元。4. （10分）已知有向图D如右图所示，求（1）邻接矩阵A（D）;（2）D是哪类连通图，为什么（2）D中从V3到V2长度是2的通路数；（3）D中从V2到V2长度是3的回路数。ac5. （10分）右图所示无向图G中，实线边所示子图为G的一棵

5、生成树T,求G对应T的基本割集系统。6. （10分）求在1和1000之间（包含1和1000在内）不能被5或6整除，也不能被8整除的数的个数。（必须写出解题过程）四、证明题10%（10分）在自然推理系统中构造下面推理的证明：若张超和李志都是计算机系学生，则王红是中文系学生；若王红是中文系学生，则她爱看小说；可是王红不爱看小说；张超是计算机系学生；所以李志不是计算机系的学生。离散数学综合练习题一（答案）(5) A (6) B D (8) A-、单项选择题（每题2分，共16分）（1）BC（3）C（4）D填空题（每空2分，共18分）1.x(F(x)y(G(y)H(x,y),x(F(x)y(G(y)H(

6、x,y)2.(F(a) F(b) G(a)5 . a,b , b,a , a,a6 .不正确 7.0 3三、化简计算题(共 56分)1.(10分)解:主合取范式：(p q) (p r) (p(P p) ( p r)(p r p ( q q) rp qp q ( r r)q r( p p) q r原式=(p q r) ( p q成假赋值为：010, 011, 100,G(b) 3.74.,b,b , c, c 假) 8.1 (或真)q) (p r) ( p q) q p) ( q r) ( p(p q r) ( p q(pqr) (pq(pq r) (pqr) (p q r) (p110m-n+

7、1(p r)r) (p q) ( q r)r)r)r)q r) M2 M3 M4 M62. （6分）解：设3度顶点为x个，则阶数n 8 握手定理得 2m 18 2x ； 1d（V） 1 8 n 8 2 4 14。2 x 10 x,边数 m n 1 9 x,由3 2 3 x 14 3x,解得x 4,于是3. （8分）解:哈斯图如下图，极大元:0 14.解：A(D)= 0 11 11 01 11 0 , A2(D)= a xa=0 10 021102 12 12 21 1121, A3(D)= A2 XA= 213125 4 34 3 25 3 32 1 118,60极小元：2,3,5;最大元和最

8、小元均无。从矩阵A（D）和A2（D）中可知，从V3到V2长度等于2的通路数有2条，从V2到V2长度等于3的回路数有4条。强连通图，因为存在经过每个顶点至少一次的回路.5. (10分)解：树枝有5条，分别是a,b,e,f,h,基本割集系统S1,S2,S3,S4,S5S1=a,c,i,j,S2=b,c,i,S3=e,c,d,i,j,S4=f,c,d,g,S5=h,g,i,j6. （10分）解：设1到1000的整数构成全集U,用ABC分别表示能被5,6,8整除的数构成的集合，如左面文氏图所示：则有SxAxxSx能被5整除,BxxSx能被6整除CxxSx能被8整除1x1000,AL1000/5200,BL1000/6166,C11000/8125,AIBL1000/lcm(5,6)33,AICL1000/lcm(5,8)25,BICL1000/lcm(6,8)41,AIBICL1000/lcm(5,6,8)8AlBIC|SABCAIBAICBICAIBIC10002001661253