离散数学例题分析

离散数学例题分析第一页，共三十七页，编辑于2023年，星期一例题分析一、选择（10×2）1．下述式子错误的是（）A．B．C．D．答案C

第二页，共三十七页，编辑于2023年，星期一例题分析答案C

2．若是A上的等价关系，则不是（）A．自反的B．对称的C．反自反的D．传递的第三页，共三十七页，编辑于2023年，星期一例题分析答案D

3．已知,试问为:（）A．内射B．满射C．双射D．非内射、非满射第四页，共三十七页，编辑于2023年，星期一例题分析4．为一个代数系统，下列说法不正确的是（）。A．若*有左单位元且有右单元，那么*有单位元，B．若*有左零元和右零元，那么*有零元。C．若*有元数a对*有左逆元，和右逆元，则a有逆元。D．若为群，则*只有单位元而没有零元。答案C第五页，共三十七页，编辑于2023年，星期一例题分析答案C

5．下列能构成独异点的是（）A．（N；+）B．（N；-）C．（N；·）D．（N；|）第六页，共三十七页，编辑于2023年，星期一例题分析答案Ｄ

6．如果（）为一个格，那么二元运算不一定满足（）A．交换律B．结合律C．吸收律D．分配律第七页，共三十七页，编辑于2023年，星期一例题分析答案C

7．是3个结点的完全图，则（）A．有6个边B．有5个边C．是欧拉图D．不是哈蜜顿图第八页，共三十七页，编辑于2023年，星期一例题分析答案D8．下述语句是命题的是（）A．B．你喜欢春天吗？C．天气好暖和呀！D．我不喜欢春天。第九页，共三十七页，编辑于2023年，星期一例题分析答案A9．下述公式正确的是（）A．B．C．D．第十页，共三十七页，编辑于2023年，星期一例题分析答案A10．若T是一个（n,m）树，则（）A．m=n-1B．n=m-1C．n-m+k=2D．m=2n-1第十一页，共三十七页，编辑于2023年，星期一例题分析二、填空（10×2）1、已知，那么=______________________答案第十二页，共三十七页，编辑于2023年，星期一例题分析2、设{（0，0）、（0，2），（2，0），（3，2）}则的定义域为______________________，值域为______________________

。

答案第十三页，共三十七页，编辑于2023年，星期一例题分析3、已知（n<m）问存在____________个不同的Ａ到Ｂ上的内射。

答案第十四页，共三十七页，编辑于2023年，星期一例题分析答案减法和除法

4、整数集上的四则运算中不能保证封闭性的是______________________

第十五页，共三十七页，编辑于2023年，星期一例题分析5、写出群中生成元的定义______________________

答案g为生成元,则任给群中的一元素,那么存在整数r,使得第十六页，共三十七页，编辑于2023年，星期一例题分析答案

互补律、分配律和同一律或是有补格且是分配格

6、如果一个格要求成为布尔代数，那么还需要满足的条件

______________________第十七页，共三十七页，编辑于2023年，星期一例题分析答案偶数

7、若G是欧拉图那么G中每个结点的度均为

______________________第十八页，共三十七页，编辑于2023年，星期一例题分析8、将“每个人都会死亡的”符号化：______________________

答案第十九页，共三十七页，编辑于2023年，星期一例题分析答案所有的回路均为偶数长

9、二部图的充要条件是：______________________

第二十页，共三十七页，编辑于2023年，星期一例题分析答案７10、设代数系统，其中定义，则Ｖ有____________个子代数。

第二十一页，共三十七页，编辑于2023年，星期一例题分析三、简答题（3×10）1、说明：答案第二十二页，共三十七页，编辑于2023年，星期一例题分析2、,试问有多少个由A1到A2的不同关系？为什么？答案共有个到上的二元关系,因为:依据二元关系的定义,到上的二元关系是与的笛卡尔积的任意一个子集,而与的笛卡尔积共有个元素,再依据幂集的定义,知共有个关系。

第二十三页，共三十七页，编辑于2023年，星期一例题分析3、F=是什么类型的公式？说明理由。答案所以F为重言式。第二十四页，共三十七页，编辑于2023年，星期一例题分析四、证明题（3×10）1、证明设是到的满同态，则如果

*是可交换的，则也是可交换的。证明由于h为A到B上的满射,故,使得

,则故满足交换律。

第二十五页，共三十七页，编辑于2023年，星期一例题分析2、试证明链也是一个分配格。证明(1)设是一个链,则是一个偏序集,且对有或,于是若,则

,,若,则,,所以是格。(2)设任取,由于L为一个链,故有

或或或或,不妨取,

第二十六页，共三十七页，编辑于2023年，星期一例题分析那么,,由定理7-3得

而所以

满足分配律,所以链是一个分配格。

第二十七页，共三十七页，编辑于2023年，星期一例题分析证明证法一由于G中所有结点的度均为2,那么对G中任一连通分图来讲,它必然是一个欧拉图,并且每个结点在欧拉回路中只出现一次,换句话说G的每个分图均是环,所以G是由环构成的。3、若图G的所有结点的度为2，则G的每个分图含环。第二十八页，共三十七页，编辑于2023年，星期一例题分析证法二设G有r个分图,不妨设为图,假设不含环,则是树,于是,又每个结点度数为2,所以由握手定理,,矛盾,因此必是含环。第二十九页，共三十七页，编辑于2023年，星期一例题分析五、简答题（3×10）1、一棵树有1个结点度数为5，2个结点度数为4，5个结点度数为2，14个结点度数为1，问度数为3的结点有几个？答案设T是(n,m)图,度为3的结点数为，则,由握手定理2m=

所以,有5个度数为3的点。

第三十页，共三十七页，编辑于2023年，星期一例题分析2、判断下面两个图是否为平面图，若认为是平面图，请画出其相应的平面图解，否则说明它为什么不是平面图。第三十一页，共三十七页，编辑于2023年，星期一例题分析答案在图中选子图在度为2的结点内与同构,所以是非平面图。

可以画在平面上无交叉,故是平面图。

第三十二页，共三十七页，编辑于2023年，星期一例题分析3、,且和都是可逆的，证明函数复合运算满足：答案由于，均为可逆函数,也是双射函数,所以,使得,同理,使得,因此,由函数复合的定义知

也为可逆函数,即,而所以第三十三页，共三十七页，编辑于2023年，星期一例题分析六、证明题（3×10）1、试证明群<G;*>的两个子群的交集也构成<G;*>的子群。

证明设为的任意两个子群,那么,且G的单位元,因此,那么,且,而为群,故,因此有,同理

,因此,故也是G的子群。第三十四页，共三十七页，编辑于2023年，星期一例题分析2、若G是连通平面图，则G中必有一个结点V，使得deg(V)≤5证明设G(m,n)中,那么而由握手定理