离散数学复习题

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 及 D以上全不对4设，R是A上相等关系“=”，由R产生等价类有( )

2、A10个 B50个 C100个 D1个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为实数集；下列代数结构为群的是( ). (1) (2) (3) (4) A无 B(1)、(4) C(1)、(3)、(4) D全体都是9. 设i

3、是虚数，是复数乘法运算，则G=是群，下列是G的子群是( )A. B.-1, C.i, D.-i,10.在下列关于图论的命题中，为真的命题是（）A.一个强连通的有向图一定是欧拉图； B. 完全图Kn都是欧拉图C.完全二部图都是哈密顿图 D.完全图Kn（n2）都是哈密顿图。二 填空题（2分1020分）1.设，A上的关系，则_。2设G是具有个结点，条边的连通图，则G的生成树T有_个结点，_条边。3一个班有50个人，在第一次考试中有26人得优秀，在第二次考试中有21人得优秀，如果两次考试都得优秀的有14人，问两次考试都没有得优秀的有_人？4设A=a，b，c，A上二元关系R= , , , 则R的对称闭包

4、s（R）= 。5 一个无向图是欧拉图的充要条件是 。6. 设A为非空集合1,2,3，P(A)为A的幂集，则对于P(A)中的二元运算：对称差，群P(A)，中，1-3=_7一个无向图为二部图的充要条件是 8将公式化为等价的前束范式: (x)F(x)(x)G(x)_.9 矛盾式的主析取范式为_.10 一个n（n1）阶无向简单图G中，n为奇数，已知G中有r个奇数度顶点，则G的补图有_个奇数度顶点。三 （1） 判定公式的类型（10分）（2）求(PQ)R的主析取范式与主合取范式，并写出其相应的成真赋值和成假赋值。（10分）四 （20分）设为一个偏序集，其中，A = 1, 2, 3, 4, 6, 8, 9,

5、 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的无向完全图，其边的数目为 ；3 完全二部图K4,5有_条边, 匹配数是_

6、.4 设M(x):x是人，D(x):x是要死的，则命题“所有的人都是要死的”可符号化为(x) _,其中量词(x)的辖域是_。5. 已知n阶无向简单图G有m条边，则G的补图有_条边。6设，则A的幂集有元素_个。7. 重言式的主合取范式为 _, 矛盾式的主析取范式为_.8. 一个有向图为欧拉图的充要条件是 .9整数集合上关于普通加法运算所构成的群Z，中，元素(-2)-3_10设A=a，b，c，A上二元关系R= , , , 则自反闭包r（R）= 。11 一个班有45个人，在第一次考试中有26人得优秀，在第二次考试中有21人得优秀，如果两次考试都得优秀的有14人，问两次考试都没有得优秀的有_人？12

7、设无向图中有6条边，有一个3度顶点和一个5度顶点，其余顶点度为2，则该图的顶点数是_。二. (15分) 设集合A1, 2, 3，R和S是A上的两个关系，它们的关系矩阵为：写出关系R和S 的集合表达式，(2) 画出R和S的关系图，(3) 说明R和S满足关系的哪些特性.三（1）. 判定公式的类型 (10分) (pqq)（2） (10分)求下列公式的主合取范式及主析取范式(PQ)R四 .(10分) 设集合A1, 2, 3, 4, 6, 8, 12，R是A上的整除关系，（1）画出偏序集(A, R)的哈斯图；（2）写出集合A的极大元，极小元，最大元，最小元。五 (10分)设Z是整数集合，在Z上定义二元运

8、算如下：x * y = x + y 2，证明：Z，*是群。复习题答案（一）一、 单项选择题（每题2分，共20分）1-5 ACBCC 6-10 CABAD 二、 填空题（每题2分，共20分）(1) （2）n，n1（3）17 （4） , , ，, (5) 连通且所有顶点的度数都是偶数 (6) 1(7) G中无奇数度长度的回路 (8) （9）0 （10）r三（共20分）（1） 所以该式是永真式。2）(PQ)R(PQ)R(PQ)R(P(QQ)R)(PP)QR)(PQR)(PQR)(PQR)(PQR) 主析取范式为： 主合取范式为：其相应的成真赋值为000、001、011、101、111成假赋值为：01

9、0、100、110 。四（共20分）（2）极大元：6，9，16 极小元：1 （3）最小上界：不存在，最大下界：2 （4）构不成格，因为集合中任意两元素构成的集合并不是都有最小上界和最大下界。例如4,6无最小上界。 五 （20分）*01234000000101234202413303142404321（2）零元是0，幺元是1. O无逆元，1的逆元是1，2和3互为逆元，4的逆元是4；（3） 是独异点，因为满足结合律，有幺元，但是不是所有元素有逆元。复习题答案（二）一填空题（每空3分，共45分）(1) （2）（3）20，4 （4），(5) (6) 8 (7) 1，0 (8) 连通且所有顶点的入度等于

10、初度（9）6 （10） , , ， （11）12 （12）4二 （15分）R= , , ，, S= , , 关系图略关系R：自反； 关系S：反对称，传递三 （20分）（1）(pqq)所以该式是矛盾式。2）(PQ)R(PQ)R(PQ)R(P(QQ)R)(PP)QR)(PQR)(PQR)(PQR)(PQR) 主析取范式为： 主合取范式为：其相应的成真赋值为000、001、011、101、111成假赋值为：010、100、110四（共10分）哈斯图略极小元：1 极大元：8，12 最小元：1 最大元：不存在五（10分）证明：要证Z，*是群, 即要证*运算在整数集合上满足结合律，有幺元，每个元素都有逆元。（3分）任取整数x, y, z， x * y* z = （x + y 2）*