《离散数学复习题参考带答案》由会员分享，可在线阅读，更多相关《离散数学复习题参考带答案（12页珍藏版）》请在金锄头文库上搜索。
1、一、选择题：（每题2）1、下列语句中不是命题的有（ ）。A离散数学是计算机专业的一门必修课。B鸡有三只脚。C太阳系以外的星球上有生物。D你打算考硕士研究生吗?2、命题公式A与B是等价的，是指（ ）。A A与B有相同的原子变元 B A与B都是可满足的C 当A的真值为真时，B的真值也为真D A与B有相同的真值3、所有使命题公式P(QR)为真的赋值为（ ）。A 010，100，101，110，111B 010，100，101，111C 全体赋值D 不存在4、合式公式(PQ)R的主析取范式中含极小项的个数为（ ）。A2B3C5D0 5、一个公式在等价意义下，下面哪个写法是唯一的（ ）。A析取范式 B合
2、取范式 C主析取范式 D以上答案都不对6、下述公式中是重言式的有（ ）。A(PQ) (PQ)B(PQ) ( PQ)(QP)C(P Q)QDP (PQ)7、命题公式 (PQ) (QP) 中极小项的个数为（ ），成真赋值的个数为（ ）。A0B1C2D3 8、若公式 (PQ)(PR) 的主析取范式为 m001m011m110m111 则它的主合取范式为（ ）。Am001m011m110m111BM000M010M100M101CM001M011M110M111Dm000m010m100m1019、下列公式中正确的等价式是（ ）。A($x)A(x) ($x)A(x)B(x) (y)A(x, y) ($
3、y) (x) A(x, y)C(x)A(x) ($x)A(x)D(x) (A(x) B(x) (x) A(x) (x) B(x)10、下列等价关系正确的是（ ）。Ax ( P(x) Q(x) ) x P(x) x Q(x)B$x ( P(x) Q(x) ) $x P(x) $x Q(x)Cx ( P(x) Q ) x P(x) QD$x ( P(x) Q ) $x P(x) Q11、设个体域为整数集，下列真值为真的公式是（）。Ax$y（xy=1）B$xy（xy=0）Cxy（xy=y）D$xy（x+y=2y）12、设S=,1,1,2，则有（ ）S。A1,2 B1,2 C1 D2 13、下列是真命
4、题的有（ ）。Aaa B,C, D, 推荐精选14、设S=,1,1,2，则2S 有（ ）个元素。A3B6 C7D8 15、已知幂集的基数|r( A)|=2048，则集合A的基数|A|为（ ）。A11B12C10D916、设A=1，2，3，则A上的二元关系有（ ）个。A 23 B 32 C233D32217、设A=a, b, c, d，A上的等价关系R=,IA，则对应于R的A的划分是（ ）。Aa, b, c, d Ba, b, c, dCa, b, c, d Da, b, c, d18、设R，S是集合A上的关系，则下列说法正确的是（ ）。A若R、S是自反的，则RS是自反的B若R、S是反自反的，则
5、RS是反自反的C若R、S是对称的，则RS是对称的D若R、S是传递的，则RS是传递的19、集合A上的相容关系R的关系矩阵M(R)的对角线元素（ ）。A全是1B全是0C有的是1，有的是0D有的是220、设集合 A=1，2，3，A上的关系R=，则R不具备（ ）。A 自反性B 传递性C 对称性D 反对称性21、设，S上关系R的关系图为（如图所示），则R具有（ ）性质。A自反性、对称性、传递性 B反自反性、反对称性 C反自反性、反对称性、传递性 D自反性 22、设S=1，2，3，R为S上的关系，其关系图为 则R具有（ ）的性质。A自反、对称、传递 B什么性质也没有 C反自反、反对称、传递 D自反、对称、
6、反对称、传递23、设A=1, 2, 3，B=a, b，下列各二元关系中是A到B的函数的是（ ）。AR=,BR=,CR=,DR=,推荐精选24、设R为实数集，映射f：RR，f(x)= -x2+2x-1，则f是（ ）。A单射而非满射 B满射而非单射C双射 D既不是单射，也不是满射25、设A=F，1，1，3，1，2，3则A上包含关系“”的哈斯图为（ ）。 AB CD26、N是自然数集合，定义f：NN，f (x) = x mod 3（即x除以3的余数），则 f 是（ ）。A满射不是单射B单射不是满射C双射D不是单射也不是满射27、设S=,1,1,2，则有（ ）S。A1,2 B1,2 C1 D2 28、
7、集合A=x | x=2nnN 对（ ）运算封闭。A加法B减法C乘法D|xy|29、设*是集合A上的二元运算，称Z是A上关于运算*的零元，若（ ）。Ax A，有x*Z=Z*x=ZBZ A，且x A有x*Z=Z*x=ZCZ A，且x A有x*Z=Z*x=xDZ A，且$x A有x*Z=Z*x=Z30、下面偏序集（ ）能构成格。31、在（ ）中，补元是唯一的。A有界格B有补格 C分配格D有补分配格。32、下面四组数能构成无向简单图的度数序列的有（ ）。A(2, 2, 2, 2, 2)B(1, 1, 2, 2, 3) C(1, 1, 2, 2, 2)D(1, 1, 3, 3, 3)33、无向图结点之间
8、的连通性，是结点集之间的一个（ ）。A 连通关系B 偏序关系C 等价关系D 函数关系34、已知图G的相邻矩阵为：推荐精选则G有（ ）。A5点，8边B6点，7边C5点，7边D6点，8边35、下列四组数为结点度序列，能构成无向图的是（ ）。A2, 3, 4, 5, 6, 7B1, 2, 2, 3, 4C2, 1, 1, 1, 2 D3, 3, 5, 6, 036、下列几个图是简单图的有（ ）。AG1=(V1,E1)，其中 V1=a, b, c, d, e，E1=(a,b), (b,e), (e,b), (a,e), (d,e)BG2=(V2,E2)，其中V2=V1，E2=, , , , , CG3
9、=(V3,E3)，其中V3=V1，E3=(a,b), (b,e), (e,d), (c,c)DG4=(V4,E4)，其中V4=V1，E4=, , , , 37、在一棵树中有7片树叶，3个3度结点，其余都是4度结点则该树有（ ）个4度结点。A1B2C3D4 38、一棵树有2个4度结点，3个3数度结点，其余是树叶，则该树中树叶的个数是（ ）。A8B9C10D1139、设图G是有6个顶点的连通图，总度数为20，则从G中删去（ ）边后使之变成树。A10B 5C 3D 240、下面那一个图可一笔画出（ ）。41、在如下各图中（ ）欧拉图。42、下图中既不是欧拉图，也不是哈密尔顿图的是（ ）。推荐精选43
10、、在如下的有向图中，从V1到V4长度为3 的道路有（ ）条。A1B2C3D4 44、图 中 从v1到v3长度为3 的通路有（ ）条。A0B1C2D3二、判断题（每题 1分）1。 （ Y ）2设A，B， C是任意三个集合。（1）若AB且BC，则AC。 （ Y ） （2）若AB且BC，则AC。（ N ）（3）若AB且BC，则AC。 （ N ） （4）(AB)C=(AC) (BC)。（ Y ）（5）A(BC)= (AB)(AC)。 （ N ）3A，B，C为任意集合，若AB=AC，则B = C 。（ N ）4可能有某种关系，既不是自反的，也不是反自反的。（ Y ）5可能有某种关系，既是对称的，又是反对
11、称的。（ Y ）6设R是实数集，R上的关系S=|x-y|2x,yR，S是相容关系。（ Y ）7若集合A上的关系R是对称的，则Rc也是对称的。（ Y ）8数集合上的不等关系（）可确定A的一个划分（ N ）9设集合A、B、C为任意集合，若AB = AC，则B = C。（ N ）10函数的复合运算“ ”满足结合律。（ Y ）11集合A上的恒等关系是一个双射函数。（ Y ）12任何一个循环群必定是阿贝尔群。（ Y ）13任何循环群必定是阿贝尔群，反之亦真。（ N ）14设是偏序集，BA，则B的极大元bB且唯一。（ N ）15群是每个元素都有逆元的半群。（ N ）16在代数系统 中，若一个元素的逆元是唯一的，其运算*必是可结合的。（ N ）17每一个有限整环一定是域，反之也对。（ N ）推荐精选18设是
