《离散数学卷（3）-参考答案》山东大学测试答案
离散数学模拟3参考答案一、选择题
1、假设，下列选项错误的是：（2）
（1）（2）（3）（4）
2、对任意集合，下述论断正确的是：（1）
（1）若，则 （2）若，则
（3）若，则 （4）若，则
3、假设上的关系如下，具有传递性的关系是：（4）
（1）
（2）
（3）
（4）
4、假设和是集合上的任意关系，则下列命题为真的是：（1）
（1）若和是自反的，则也是自反的；
（2）若和是反自反的，则也是反自反的；
（3）若和是对称的，则也是对称的；
（4）若和是传递的，则也是传递的。
5、若是满射函数，则复合函数必是：（3）
（1）双射函数 （2）单射函数 （3）满射函数 （4）不单射也不满射
6、假设，，令：，则不同的函数个数为：（2）
（1）2+3个 （2）个 （3）个 4）个
7、一个无向简单图有条边，个顶点，则图中顶点的总度数为：（3）
（1） （2） （3） （4）
8、一个图是半欧拉图是指：（2）
（1）图中包含一条回路经过图中每条边一次且仅一次；
（2）图中包含一条路经过图中每条边一次且仅一次；
（3）图中包含一条回路经过图中每个顶点一次且仅一次；
（4）图中包含一条路经过图中每个顶点一次且仅一次。
9、下面哪一种图不一定是树：（3）
（1）无回路的连通图 （2）有个顶点条边的连通图
（3）每一对顶点之间都有通路 （4）连通但删去一条边则不连通的图.
10、完全叉树中有片叶，个分支点，则它们之间的关系表达式是：（2）
（1） （2） （3）（4）
二、填空题
1、假设，，
（1）{5，7}；（2）{5}；
2、假设上的关系，则：（1）；（2）；（3）；
3、假设，是到的函数，其中：（a）；（b）；（c）。则：（1）_g_是满射；（2）_g_是双射；4、设无向图有24条边，有4个3度的顶点，其余顶点度数均小于3，则中至少有22个顶点。5、一棵树有2个2度顶点，1个3度顶点，3个4度顶点，则有 7 片叶。
6、假设：我有时间，：我去体育馆。
（1）命题“如果我有时间，我就去体育馆”符号化为 ；
三、假设、是非空集合，并且。证明：。
证明：对任意的，有，所以
因为，所以
所以 ，因此
故
同理可证
综上 。
四、假设R,S是集合A上的等价关系，证明R(S也是集合A上的等价关系。
证明：对任意的，因为R,S是集合A上的等价关系，所以是自反、对称、传递的。
故有 ，所以，是自反的；
对任意的，并且假设，有
所以 ，因此，是对称的；
对任意的，并且假设，
有，并且
所以有
因此，是传递的。
综上是集合A上的等价关系。五、对下列集合在整除关系下构成的偏序集，画出Hasse图，并写出最大元，最小元，极大元，极小元。
（1）
（2）
（3）
解：
（1）无最大元，有极大元是24、36，无最小元，有极小元2，3；
（2）无最大元，有极大元30，42，70，有最小元和极小元2；
（3）有最大元和极大元18，有最小元和极小元3
六、假设图是个顶点条边的简单无向图，则。
证明：若图是连通图，由于图是简单图，所以边数不会超过完全图的边数，
因此 ；
若图是非连通图，则至少存在两个连通分支和
假设和的顶点数和边数分别为，和
则有 和
而
命题得证。www.ap5u.com
页:
[1]