离散数学复习题

《离散数学复习题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、复习题（一）一单项选择题（每题2分，共20分）题号12345678910答案1.下述命题公式中，是重言式的为（）。A、；B、；C、；D、。2.设S1={1，2，…，8，9}，S2={2，4，6，8}，S3={1，3，5，7，9}，S4={3，4，5}，S5={3，5}，在条件下X与（）集合相等。A、X=S1，S2或S4；B、X=S2或S4；C、X=S1，S2，S3或S4；D、X与S1，…，S5中任何集合都不等。3.设A为有限集，元素个数为n个，P(A)为A的幂集，则P(A)的元素个数及的元素个数为()A．　B．及　C．及　

2、　D．以上全不对4．设，R是A上相等关系“=”，由R产生等价类有()A．10个　B．50个　C．100个　D．1个5.若供选择答案中的数值表示一个简单图中各个顶点的度，能画出图的是().A.(1,2,2,3,4,5)B.(1,2,3,4,5,5)C.(1,1,1,2,3)D.(2,3,3,4,5,6).6．设有函数（R表示实数集），且，则复合数函数是（）A．满射B．单射C．双射7.若无向图为树，其中，，则等价于以下叙述中的（）A．连通且B．连通且C．当且仅当连通D．当且仅当无回路8设I为整数集，Q为有理数集，R为实数集；下

3、列代数结构为群的是().(1)(2)(3)(4)A．无　B．(1)、(4)　C．(1)、(3)、(4)　　D．全体都是9.设i是虚数，·是复数乘法运算，则G=<{1,-1,i,-i},·>是群，下列是G的子群是()A.<{1},·>B.〈{-1},·〉C.〈{i},·〉D.〈{-i},·〉10.在下列关于图论的命题中，为真的命题是（　　　）A.一个强连通的有向图一定是欧拉图；B.完全图Kn都是欧拉图C.完全二部图都是哈密顿图D.完全图Kn（n>2）都是哈密顿图。二填空题（2分×10＝20分）1.设，A上的关系，则_____

4、____。2．设G是具有个结点，条边的连通图，则G的生成树T有_____个结点，____条边。3．一个班有50个人，在第一次考试中有26人得优秀，在第二次考试中有21人得优秀，如果两次考试都得优秀的有14人，问两次考试都没有得优秀的有_____人？4设A={a，b，c}，A上二元关系R={,,,},则R的对称闭包s（R）=。5一个无向图是欧拉图的充要条件是。6.设A为非空集合{1,2,3}，P(A)为A的幂集，则对于P(A)中的二元运算：对称差，群〈P(A)，〉中，{1}-3=___

5、__7一个无向图为二部图的充要条件是8将公式化为等价的前束范式:(x)F(x)→(x)G(x)Û_____________________________.9矛盾式的主析取范式为____________________________.10一个n（n>1）阶无向简单图G中，n为奇数，已知G中有r个奇数度顶点，则G的补图有_____个奇数度顶点。三（1）判定公式的类型（10分）（2）求(P∨Q)®R的主析取范式与主合取范式，并写出其相应的成真赋值和成假赋值。（10分）四（20分）设为一个偏序集，其中，A={1,2,

6、3,4,6,8,9,16},R是A上的整除关系。（1）画出R的哈斯图；（2）求A的极大元和极小元；（3）求B={4,6}的最小上界和最大下界。（4）集合A关于整除偏序关系是否能构成格？为什么？五（20分）设A={0，1，2，3，4}，定义*运算如下：,(1)列出*的运算表；(2)*是否有零元、幺元？如有，则求出相应值，求出具有逆元的元素和相应的逆元。（3）构成何种代数系统？复习题（二）一填空题（每空3分，共45分）1.设谓词公式：，个体域：{1,2}，将其中的量词消去，写出与之等价的命题公式为.2.一个结点为n的

7、无向完全图，其边的数目为；3完全二部图K4,5有____________条边,匹配数是__________.4设M(x):x是人，D(x):x是要死的，则命题“所有的人都是要死的”可符号化为(x)_____________,其中量词(x)的辖域是_____________。5.已知n阶无向简单图G有m条边，则G的补图有_________________________条边。6．设，则A的幂集有元素_____________个。7.重言式的主合取范式为______,矛盾式的主析取范式为______.8.一个有向图为欧拉图的充

8、要条件是.9．整数集合上关于普通加法运算所构成的群〈Z，＋〉中，元素(-2)-3＝_____10设A={a，b，c}，A上二元关系R={,,,},则自反闭包r（R）=。11一个班有45个人，在第一次考试中有26人得优秀，在第二次考试中有21人得优秀，如果两次考试都