离散数学2023秋综合练习题

离散数学综合练习题一、判断下列命题是否正确．如果正确，在题后括号内填“\/”；否则，填“”（1）空集是任何集合的真子集．（）（2）是空集．（）（3）（）（4）如果，则或．（）（5）设集合，，则（）（6）设集合，则是到的关系．（）（7）关系的复合运算满足交换律．（）（8）设为集合上的等价关系,则也是集合上的等价关系()（9）设是集合上的等价关系,则当时，()（10）设为集合上的等价关系,则()（11）集合A上的任一运算对A是封闭的．（）（12）设A是集合，，，则是可结合的．（）（13）设是群．如果对于任意，有则是阿贝尔群．（）（14）设a是群的元素，记则是的子群．（）（15）<{0，1，2，3，4}，max，min>是格．（）（16）设a，b是格的任意两个元素，则．（）（17）设是布尔代数，则是格．（）（18）设集合，则是格．（）（19）设是布尔代数，则对任意，有．（）（20）设是布尔代数，则对任意，都有，使得．（）（21）n阶完全图的任意两个不同结点的距离都为1.（）（22）在有向图中，结点到结点的有向短程即为到的有向短程．（）（23）强连通有向图一定是单向连通的．（）（24）不论无向图或有向图，初级回路一定是简单回路．（）（25）设图G是连通的，则任意指定G的各边方向后所得的有向图是弱连通的．（）（26）设A是某个无向图的邻接矩阵，则(是的转置矩阵)．（）（27）设有向图D的可达矩阵为则是单向连通的．（）（28）有生成树的无向图是连通的．（）（29）由r棵树组成的森林的结点数n与边数m有下列关系：m=n-r.（）（30）如果有向图D仅有一个结点的入度为0，其余结点的入度都为1，则D是有向树．（）（31）“如果8＋7＞2，则三角形有四条边”是命题．（）（32）设都是命题公式，则也是命题公式．（）（33）命题公式的真值分别为0，1，则的真值为0（以上是在对所包含的命题变元的某个赋值下）．（）（34）逻辑结论是正确结论．（）（35）设都是谓词公式，则也是谓词公式．（）（36）设都是谓词公式，，则是永真式．（）（37）设都是命题公式，则也是命题公式．（）（38）命题公式的真值分别为0，1，则的真值为0（以上是在对所包含的命题变元的某个赋值下）．（）（39）设是个体域中某个元素，则其中都是谓词．（）（40）（）二、填空题（1）设有个元素，则集合的幂集中有个元素。（2）设，则=.（3）设集合中元素的个数分别为，，且，则集合中元素的个数.（4）设集合，，则中元素的个数为.(5)设为集合上的二元关系,则.(6)集合上的二元关系为传递的充分必要条件是．(7)设：称为母亲，：称为父亲，则：,(8)设为自然数的集合，“”为自然数的小于等于关系，的子集，则的下确界为，下确界为,(9)设10人集合{赵茵，钱小滨，孙丽春，赵萍，钱浩，李靖华，李秀娟，钱钰，李惠芝，李莉}上的同姓关系为，则等价类[赵]=，[钱]=，(10)设,是上的包含于关系，,则有=.(11)设为非空有限集，代数系统中，对运算的单位元为，零元为.(12)循环群的生成元为.(13)循环群的所有子群为.(14)代数系统中（其中为整数集合，+为普通加法），对任意的，其.(15)在整数集合上定义运算为，则的单位元为.(16)设,在代数系统中，的单位元为，可逆元为.(17)设是群，则对于任意的，方程和有唯一解。(18)设是群，对任意，如果，则.(19)设是群，为单位元，若元素满足，则.(20)在整数集合上定义运算为，则的单位元为.(21)设为树，中有4度，3度，2度分支点各1个，问中有片树叶。(22)为了从（n，m）连通无向图得到一棵生成树，必须删除G的条边．(23)设树T中有7片树叶，3个3度结点，其余都是4度结点，问T中有个4度结点。(24)无环有向图的关联矩阵的所有元素之和为．(25)n阶完全图的任意两个不同结点的距离都为．(26)图为阶无向完全图，则共有条边。(27)设为图，则图中结点度数的总和为。(28)设图有6结点，若各结点的度数分别为：1，4，4，3，5，5，则共有条边。(29)无向图是由棵树组成的森林，至少要添加条边才能使成为一棵树。(30)在任何图中，奇数结点必为个。(31)设天气很冷，老王还是来了，则命题“虽然天气很冷,但老王还是来了”符号化为.(32)设天下雨，我骑自行车上班，则命题“如果天不下雨,我就骑自行车上班”符号化为.(33)设经一事,长一智，则命题“不经一事,不长一智”符号化为.(34)设的真值为0，的真值为1，则命题公式的真值为.(35)设的真值为0，的真值为1，则命题公式的真值为.(36)由个命题变项可以组成个不等值的命题公式。(37)设个体域，公式在上消去量词后应为.(38)设是自然数，是奇数，是偶数，则命题“任何自然数不是奇数就是偶数”符号化为.(39)设是素数，是偶数，，则命题“2既是偶数又是素数”符号化为.(40)设是金子，是发光的，则命题“金子是发光的,但发光的不一定是金子”符号化为.三、选择题（每题后面有四个选项，四个选项中只有一个是正确的，请将正确的所对应的字母填在括号内）（1）设为实数集合，下列集合中哪一个不是空集（）A.B．C.D.（2）设为集合，若，则一定有（）A.B．C.D.（3）下列各式中不正确的是（）A.B．C.D.（4）设，则下列各式中错误的是（）A.B．C.D.（5）设，，，则为（）A.B．C.D.（6）设，，则的恒等关系为（）A.B．C.D.（7）集合上的二元关系，则的性质为（）A.自反的；B．对称的；C.反对称的；D.反自反的.（8）设上的二元关系如下，则具有传递性的为（）A.B．C.D.（9）设为集合上的等价关系，对任意，其等价类为（）A.空集；B．非空集；C.是否为空集不能确定；D..（10）映射的复合运算满足（）A.交换律B．结合律C.幂等律D.分配律（11）在整数集上，下列哪种运算是可结合的（）A.B．C.D.（12）设集合，下面定义的哪种运算关于集合不是封闭的（）A.B．C.，即的最大公约数D.，即的最小公倍数（13）下列哪个集关于减法运算是封闭的（）A.（自然数集）；B．；C.；D..（14）设是有理数集，在定义运算为，则的单位元为（）A.；B．；C.1；D.0（15）下列代数系统中，哪一个不构成群（）A.是模11乘法；B.是模3加法；C.普通加法；D.普通乘法.（16）循环群的生成元为1和2，它们的周期为（）A.5B．6C.3D.9（17）循环群的所有子群为（）A.B．C.和D.（18）循环群的所有生成元为（）A.1，0B．-1，2C.1，2D.1，-1（19）有限布尔代数的元素个数必定等于（）A.；B．；C.；D..（20）在下面偏序集的哈斯图中，哪一个是格（）ABCD（21）仅由孤立点组成的图称为（）A.零图；B．平凡图；C.完全图；D.多重图.（22）仅由一个孤立点组成的图称为（）A.零图；B．平凡图；C.多重图；D.子图.（23）在任何图中必有偶数个（）A.度数为偶数的结点；B．度数为奇数的结点；C.入度为奇数的结点；D.出度为奇数的结点.（24）设为有个结点的无向完全图，则的边数为（）A.B．C.D.（25）图和的结点和边分别存在一一对应关系是（同构）的（）A.充分条件；B．必要条件；C.充分必要条件；D.既不充分也不必要条件.（26）给定下列序列，哪一个可构成无向简单图的结点度数序列（）A.B．C.D.（27）在有个结点的连通图中，其边数（）A.最多条；B．至少条；C.最多条；D.至少条.（28）是无向图的关联矩阵，是中的孤立点，则（）A.对应的一行元素全为0；B．对应的一行元素全为1；C.对应的一列元素全为0；D.对应的一列元素全为1.（29）任何无向图中结点间的连通关系是（）A.偏序关系；B．等价关系；C.既是偏序关系又是等价关系；D.既不是偏序关系也不是等价关系.（30）有向图，其中，，则有向图是（）A.强连通图；B．单向连通图；C.弱连通图；D.不连通图.（31）下面哪个联结词不可交换（）A.；B．；C.；D..（32）命题公式是（）A.矛盾式；B．非永真式的可满足式；C.重言式；D.等价式.（33）下列哪一组命题公式是等值的（）A.，；B．，；C.，；D.，（34）下面哪一个命题是假命题（）A.如果2是偶数，那么一个公式的析取范式唯一；B．如果2是偶数，那么一个公式的析取范式不唯一；C.如果2是奇数，那么一个公式的析取范式唯一；D.如果2是奇数，那么一个公式的析取范式不唯一.（35）设论域为整数集，下列公式中哪个值为真（）A.；B.；C.；D..（36）设谓词是奇数，是偶数，谓词公式在哪个论域中是可满足的（）A.自然数；B．整数；C.实数；D.以上均不成立.（37）命题“没有不犯错误的人”符号化为(设是人,犯错误)（）A.；B.；C.；D..（38）设个体域，公式在上消去量词后应为（）A.；B.；C.；D..（39）在谓词演算中，下列各式中，哪一个是正确的（）A.；B.；C.；D..（40）“学习有如逆水行舟，不进则退”。设学习如逆水行舟，学习进步，学习退步。则命题符号化为（）A.；B．；C.；D..四、解答题1.设上的关系试（1）写出的关系矩阵；（2）验证是上的等价关系；（3）求出的各元素的等价类。2.设，上的整除关系，画出的哈斯图。3.设集合,是上的整除关系,画出的哈斯图；4.设集合,是上的整除关系，试求：集合的最大元，最小元子集和的上界、下界、上确界和下确界。5.在下面的无向图中，回答下列问题（1）写出之间的所有初级通路；（2）写出之间的所有短程，并求；（3）判断无向图是否为欧拉图并说明理由。6.下列各图是否为欧拉图，是否为哈密尔顿图？为什么？(1)(2)7.下列图形中最少需添加几条边才能成为欧拉图．aabebdcdc（1）（2）8.有向图如下图所示(1)求的邻接矩阵；(2)求中长度为4的通路数和回路数，并找出中从到长度为4的所有通路。(3)是哪类连通图？9.设有向图，，其邻接矩阵为画出有向图；中长度为4的通路有多少条？其中有多少条为回路？是那类连通图？10.设连通图如下图所示，求它的一棵生成树．abcef答案不唯一。五、构造下列推理的证明1.证明2.证明3.证明4.证明5.构造下列推理的证明：每个学术委员会的成员都是专家并且是大学生，有些成员是青年人，所以有些成员是青年专家。6.“有些病人相信所有的医生，病人都不相信骗子，所以医生都不是骗子。”在一阶逻辑中证明以上推理是正确的。六、证明题1.设为集合上的等价关系,试证也是集合上的等价关系。2.设为无向连通图中任意两个顶点，证明：若，则存在顶点，使得3.证明下面四个矩阵关于矩阵乘法运算构成群。，，，4.设是一个群，试证是交换群当且仅当对任意的,有.5.设是群的元素，记，证明是的子群．6.设是一个群，取定，定义，证明是一个群。离散数学综合练习题答案判断下列命题是否正确（1）错误；（2）错误；（3）正确；（4）错误；（5）错误；（6）正确；（7）错误；（8）正确；（9）正确；（10）错误；（11）正确；（12）正确；（13）正确；（14）正确；（15）正确；（16）正确；（17）正确；（18）正确；（19）正确；（20）正确；（21）正确；（22）错误；（23）正确；（24）正确；（25）正确；（26）正确；（27）正确；（28）正确；（29）正确；（30）错误；（31）正确；（32）错误；（33）错误；（34）错误；（35）错误；（36）正确；（37）正确；（38）正确；（39）错误；（40）错误.填空题（1）；（2）；（3）3；（4）40；(5)(6)；(7)称为外祖父；(8)5，9；(9)[赵]={赵茵，赵萍}，[钱]={钱小滨，钱浩，钱钰}，[孙]={孙丽春}，[李]={李靖华，李秀娟，李惠芝，李莉}.(10)(11)；(12)1和2；(13)，，，；(14)；(15)–2；(16)1，1；(17)，；(18)；(19)；(20)0；(21)5；(22)m-n＋1；(23)1；(24)0；(25)1；(26)；(27)；(28)11；(29)；(30)偶数；(31)；(32)；(33)；(34)0；(35)0；(36)；(37)；(38)；(39)；(40).选择题（1）A；（2）C；（3）C；（4）B；（5）B；（6）A；（7）B；（8）D；（9）B；（10）B；（11）B；（12）D；（13）B；（14）D；（15）D；（16）C；（17）C；（18）D；（19）C；（20）A；（21）A；（22）B；（23）B；（24）C；（25）B；（26）B；（27）B；（28）A；（29）B；（30）C；（31）B；（32）C；（33）B；（34）A；（35）A；（36）D；（37）D；（38）B；（39）B；（40）B.解答题1.解（1）的关系矩阵为（2）从的关系矩阵可知：是自反的和对称的。又由于所以是传递的。因为是自反的、对称的和传递的，所以是上的等价关系。（3），2.解：2481246233.解：3224161286234.解：由于是上的整除关系，所以是上的偏序关系，的哈斯图为462351（1）集合的最大元：无，最小元：1（2）子集上界下界上确界下确界无1无161615.解：（1）之间的所有初级通路共有7条，分别为，，，，，，（2）之间的长度最短的通路只有1条，即，因而它是之间唯一的短程，（3）由于无向图中有两个奇度顶点，所以无向图没有欧拉图回路，因而不是欧拉图。6.解：图（1）中各顶点的度数为，，，，，，，，由于图（1）中各顶点的度数均为偶数，所以图（1）为欧拉图。回路为经过图（1）中每个结点一次且仅一次的回路，所以回路为哈密尔顿回路，因此图（1）是哈密尔顿图。图（2）中各顶点的度数为，，，，，，，，由于图（2）中有两个奇度顶点，所以图（2）存在欧拉图通路，但是没有欧拉图回路，因此图（2）不是欧拉图。回路为经过图（2）中每个结点一次且仅一次的回路，所以回路为哈密尔顿回路，因此图（2）是哈密尔顿图。7.解由于(1)只有两个奇度结点，b,e.因此，要由(1)得到一个欧拉图，必须使它们的度数都为偶数。最少需添加一条边才能使(1)为欧拉图。由于(2)有4个奇度结点，因此，要由(2)得到一个欧拉图，必须使它们的度数都为偶数。最少需添加两条边才能使(2)为欧拉图。例如，可在(1)中添加边(b,e),在(2)中添加边(a,b),(c,d)aabebdcdc（1）（2）8.解：(1)求的邻接矩阵；(2),,中长度为4的通路数为，其中对角元素之和为3，中长度为4的回路有3条。由于中，所以中到长度为4的通路有4条。即，，，，其中为简单通路。(3)由于由可知道是单向连通图。9.解：(1)有向图为(2)由于中长度为4的通路数为32。因对角元素之和为0，故中无长度为4的回路。(4)从图可得的可达矩阵为从可知是强连通的。10.解：abcef构造下列推理的证明1.证明：①前提引入；②前提引入；③①②析取三段论；④前提引入；⑤