离散数学2017秋综合练习题

1离散数学综合练习题一、判断下列命题是否正确．如果正确，在题后括号内填“\/”；否则，填“”（1）空集是任何集合的真子集．（）（2）是空集．（）（3）aaa},{（）（4）如果BAa，则Aa或Ba．（）（5）设集合},,{321aaaA，},,{321bbbB，则},,,,,{332211bababaBA（）（6）设集合}1,0{A，则}1},0{,0},0{,1,,0,{是A2到A的关系．（）（7）关系的复合运算满足交换律．（）（8）设21,为集合A上的等价关系,则21也是集合A上的等价关系()（9）设是集合A上的等价关系,则当ba,时，][][ba()（10）设21,为集合A上的等价关系,则2121~~()（11）集合A上的任一运算对A是封闭的．（）（12）设A是集合，AAA:，bba，则是可结合的．（）（13）设,G是群．如果对于任意Gba,，有222)(baba则,G是阿贝尔群．（）（14）设a是群,G的元素，记}|{yaayGyyH且则,H是,G的子群．（）（15）{0，1，2，3，4}，max，min是格．（）（16）设a，b是格,,L的任意两个元素，则ababba．（）（17）设,,,B是布尔代数，则,,B是格．（）（18）设集合},{baA，则,},},{},{,{Aba是格．（）（19）设,,,B是布尔代数，则对任意Bba,，有baba．（）（20）设,,,B是布尔代数，则对任意Ba，都有Bb，使得0,1baba．（）（21）n阶完全图的任意两个不同结点的距离都为1.（）（22）在有向图中，结点iv到结点jv的有向短程即为jv到iv2的有向短程．（）（23）强连通有向图一定是单向连通的．（）（24）不论无向图或有向图，初级回路一定是简单回路．（）（25）设图G是连通的，则任意指定G的各边方向后所得的有向图是弱连通的．（）（26）设A是某个无向图的邻接矩阵，则TAA(TA是A的转置矩阵)．（）（27）设有向图D的可达矩阵为1000110011101111P则G是单向连通的．（）（28）有生成树的无向图是连通的．（）（29）由r棵树组成的森林的结点数n与边数m有下列关系：m=n-r.（）（30）如果有向图D仅有一个结点的入度为0，其余结点的入度都为1，则D是有向树．（）（31）“如果8＋7＞2，则三角形有四条边”是命题．（）（32）设QP,都是命题公式，则QP也是命题公式．（）（33）命题公式QP,的真值分别为0，1，则QP的真值为0（以上是在对QP,所包含的命题变元的某个赋值下）．（）（34）逻辑结论是正确结论．（）（35）设BA,都是谓词公式，则BA也是谓词公式．（）（36）设BA,都是谓词公式，BA，则BA是永真式．（）（37）设CBA,,都是命题公式，则)()(CACBA也是命题公式．（）（38）命题公式QP,的真值分别为0，1，则QP的真值为0（以上是在对QP,所包含的命题变元的某个赋值下）．（）（39）设c是个体域中某个元素，则)()()()(cQcPxxQxxP其中QP,都是谓词．（）（40）),(),(yxxAyyxyAx（）二、填空题（1）设A有n个元素，则集合A的幂集)(AP中有个元素。（2）设}}{,{A，则A2=.（3）设集合BA,中元素的个数分别为5#A，7#B，且9)(#BA，则集合BA中元素的个数)(#BA.（4）设集合}4,1001|{ZxxxxA的倍数，是，}5,1001|{ZxxxxB的倍数，是，则BA中元素的个数为.3(5)设21,为集合A上的二元关系,则21.(6)集合A上的二元关系为传递的充分必要条件是．(7)设1：a称b为母亲，2：b称c为父亲，则21：,(8)设N为自然数的集合，“”为自然数的小于等于关系，N的子集}9,7,5{A，则A的下确界为，下确界为,(9)设10人集合E{赵茵，钱小滨，孙丽春，赵萍，钱浩，李靖华，李秀娟，钱钰，李惠芝，李莉}上的同姓关系为，则等价类[赵]=，[钱]=，(10)设},{baA,是A2上的包含于关系，,则有=.(11)设S为非空有限集，代数系统),(SP中，)(SP对运算的单位元为，零元为.(12)循环群33,I的生成元为.(13)循环群66,I的所有子群为.(14)代数系统,Z中（其中Z为整数集合，+为普通加法），对任意的Ix，其1x.(15)在整数集合Z上定义运算为baba2，则,Z的单位元为.(16)设}10,,4,3,2,1{T,在代数系统max,T中，max,T的单位元为，可逆元为.(17)设,G是群，则对于任意的Gba,，方程和有唯一解。(18)设,G是群，对任意Gcba,,，如果,caba，则.(19)设,G是群，e为单位元，若G元素a满足aa2，则a.(20)在整数集合Z上定义运算为abbaba，则,Z的单位元为.(21)设EVT,为树，T中有4度，3度，2度分支点各1个，问T中有片树叶。(22)为了从（n，m）连通无向图得到一棵生成树，必须删除G的条边．(23)设树T中有7片树叶，3个3度结点，其余都是4度结点，问T中有个4度结点。(24)无环有向图的关联矩阵的所有元素之和为．(25)n阶完全图的任意两个不同结点的距离都为．(26)图G为n阶无向完全图，则G共有条边。(27)设G为),(mn图，则图中结点度数的总和为。(28)设图G有6结点，若各结点的度数分别为：1，4，4，3，5，5，则G共有条边。(29)无向图G是由)2(kk棵树组成的森林，至少要添加条边才能使G成为一棵树。(30)在任何图EVG,中，奇数结点必为个。(31)设:p天气很冷，:q老王还是来了，则命题“虽然天气很冷,但老王还是来了”符号化为.(32)设:p天下雨，:q我骑自行车上班，则命题“如果天不下雨,我就骑自行车上班”符号化为.(33)设:p经一事,:q长一智，则命题“不经一事,不长一智”符号化为.4(34)设qp,的真值为0，r的真值为1，则命题公式)(rqp的真值为.(35)设qp,的真值为0，sr,的真值为1，则命题公式)()(sqrp的真值为.(36)由n个命题变项可以组成个不等值的命题公式。(37)设个体域},,,{21naaaA，公式)()(xFx在A上消去量词后应为.(38)设xxN:)(是自然数，xxF:)(是奇数，xxG:)(是偶数，则命题“任何自然数不是奇数就是偶数”符号化为.(39)设xxF:)(是素数，xxG:)(是偶数，2:a，则命题“2既是偶数又是素数”符号化为.(40)设xxG:)(是金子，xxF:)(是发光的，则命题“金子是发光的,但发光的不一定是金子”符号化为.三、选择题（每题后面有四个选项，四个选项中只有一个是正确的，请将正确的所对应的字母填在括号内）（1）设R为实数集合，下列集合中哪一个不是空集（）A.Rxxx且,01|2B．Rxxx且,09|2C.Rxxxx且,1|D.Rxxx且,1|2（2）设BA,为集合，若BA\，则一定有（）A.BB．BC.BAD.BA（3）下列各式中不正确的是（）A.B．C.D.}{,（4）设}{,aaA，则下列各式中错误的是（）A.Aa2B．Aa2C.Aa2}{D.Aa2}{（5）设2,1A，cbaB,,，dcC,，则)(CBA为（）A.cc,2,1,B．cc,2,,1C.2,,,1ccD.2,,1,cc（6）设bA,0，3,,1bB，则BA的恒等关系为（）A.3,3,,,1,1,0,0bbB．3,3,1,1,0,0C.3,3,,,0,0bbD.0,3,3,,,1,1,0bb（7）集合}10,,2,1{A上的二元关系},10|),{(Ayxyxyx且，则的性质为（）A.自反的；B．对称的；C.反对称的；D.反自反的.（8）设cbaA,,上的二元关系如下，则具有传递性的为（）A.abbaacca,,,,,,,1B．acca,,,2C.cbabccba,,,,,,,3D.aa,4（9）设为集合A上的等价关系，对任意Aa，其等价类a为（）A.空集；B．非空集；C.是否为空集不能确定；D.}|{Axx.5（10）映射的复合运算满足（）A.交换律B．结合律C.幂等律D.分配律（11）在整数集Z上，下列哪种运算是可结合的（）A.babaB．},max{babaC.baba2D.||baba（12）设集合10,,4,3,2,1A，下面定义的哪种运算关于集合A不是封闭的（）A.},max{yxyxB．},min{yxyxC.},{GCDyxyx，即yx,的最大公约数D.},{LCMyxyx，即yx,的最小公倍数（13）下列哪个集关于减法运算是封闭的（）A.N（自然数集）；B．)}(|2{整数集Ixx；C.}|12{Ixx；D.}|{是质数xx.（14）设Q是有理数集，在Q定义运算为abbaba，则,Q的单位元为（）A.a；B．b；C.1；D.0（15）下列代数系统,G中，哪一个不构成群（）A.},10,1{G是模11乘法；B.},2,1,0{G是模3加法；C.),(有理数集QG普通加法；D.,QG普通乘法.（16）循环群33,I的生成元为1和2，它们的周期为（）A.5B．6C.3D.9（17）循环群55,I的所有子群为（）A.55,IB．5},0{C.55,I和5},0{D.（18）循环群,Z的所有生成元为（）A.1，0B．-1，2C.1，2D.1，-1（19）有限布尔代数的元素个数必定等于（）A.n2；B．2n；C.n2；D.n4.（20）在下面偏序集的哈斯图中，哪一个是格（）ABCD（21）仅由孤立点组成的图称为（）A.零图；B．平凡图；C.完全图；D.多重图.6（22）仅由一个孤立点组成的图称为（）A.零图；B．平凡图；C.多重图；D.子图.（23）在任何图G中必有偶数个（）A.度数为偶数的结点；B．度数为奇数的结点；C.入度为奇数的结点；D.出度为奇数的结点.（24）设G为有n个结点的无向完全图，则G的边数为（）A.)1(nnB．)1(nnC.2)1(nnD.2)1(n（25）图G和G的结点和边分别存在一一对应关系是GG（同构）的（）A.充分条件；B．必要条件；C.充分必要条件；D.既不充分也不必要条件.（26）给定下列序列，哪一个可构成无向简单图的结点度数序列（）A.)3,2,2,1,1(B．)2,2,2,1,1(C.)3,3,3,1,0(D.)5,4,4,3,1(（27）在有n个结点的连通图G中，其边数（）A.最多1n条；B．至少1n条；C.最多n条；D.至少n条.（28）mnijmM是无向图EVG,的关联矩阵，Vvi是G中的孤立点，则（）A.iv对应的一行元素全为0；B．iv对应的一行元素全为1；C.iv对应的一列元素全为0；D.iv对应的一列元素全为1.（29）任何无向图G中结点间的连通关系是（）A.偏序关系；B．等价关系