山东大学网络教育离散数学卷(2)-参考答案

山东大学网络教育离散数学卷2参考答案一、选择题1、请指出下列选项中哪一个是错误的：（2）（1）（2）（3）}{（4）}{2、对任意集合CBA,,，下述论断正确的是：（1）（1）若CBBA,，则CA（2）若CBBA,，则CA（3）若CBBA,，则CA（4）若CBBA,，则CA3、假设},,{cbaA上的关系},,,,{accabaaaR，那么，R是：（4）（1）反自反的（2）反对称的（3）可传递的（4）不可传递的4、非空集合A上的空关系R不具备下列哪个性质：（1）（1）自反性（2）反自反性（3）对称性（4）传递性5、若CBgBAf:,:是满射函数，则复合函数fg必是：（3）（1）双射函数（2）单射函数（3）满射函数（4）不单射也不满射6、假设},,{cbaA，}2,1{B，下列哪个关系是A到B的函数：（3）（1）}2,1,2,1,2,1,{ccbbaaf（2）},,,,,,{ccacbbabbaaaf（3）}1,2,1,{cbaf（4）},1,2,1{cbaf7、一个无向简单图G有m条边，n个顶点，则图中顶点的总度数为：（3）（1）2m（2）2n（3）m2（4）n28、一个图是哈密顿图是指：（3）（1）图中包含一条回路经过图中每条边一次且仅一次；（2）图中包含一条路经过图中每条边一次且仅一次；（3）图中包含一条回路经过图中每个顶点一次且仅一次；（4）图中包含一条路经过图中每个顶点一次且仅一次。9、一棵树有2个2度顶点，1个3度顶点，3个4度顶点，则其1度的顶点数为：（2）（1）5（2）7（3）8（4）910、完全m叉树中有l片叶，i个分支点，则有关系式是：（2）（1）1li（2）lim1)1(（3）lim)1(（4）1)1(ilm二、填空题1、假设}}{},,{{cbaA，}}{},{},{{cbaB试求出：A的幂集)(A{,{{a,b}},{{c}},{{a,b},{c}}}；2、假设},30|{2正整数xxxA，}20|{xxxB是正奇数，，}5,3,1{C（1）)()(ABAC{7,9,11,13,15,17,19}；（2）ACB)(；3、假设}4,3,2,1{A上的关系}3,2{R，则：（1）)(Rr{1,1,2,2,2,3,3,3,4,4}；（2）)(Rs{2,3,3,2}；（3）)(Rt{2,3}；4、假设}3,2,1{A，hgf,,是A到A的函数，其中：（a）1)3()2()1(fff；（b）1)1(g，3)2(g，2)3(g；（c）3)1(h，1)3()2(hh；则：（1）g是满射；（2）g是双射；5、设无向图G有36条边，有6个3度的顶点，其余顶点度数均小于3，则G中至少有33个顶点。6、假设P：今天天气好，Q：我就去锻炼身体。（1）命题“如果今天天气好，我就去锻炼身体”符号化为PQ；三、假设A、B是任意两个集合，证明：)()()(BABA。证明：对)()(BpApX，则)(ApX且)(BpX所以AX并且BX由交集的定义，则BAX所以)(BApX因此)()()(BApBpAp反之，假设)(BApX则BAX所以AX并且BX所以)(ApX且)(BpX由交集定义，则)()(BpApX故)()()(BpApBAp综上)()()(BABA四、证明定义在实数集合R上的关系}3,,|,{是整数yxRyxyxS是一个等价关系。证明：对Rx，则3xx是整数，所以S是自反的；对Ryx,，并且设Syx,，则qyx3是整数而qxy3也是整数，所以Sxy,，S是对称的；对Rzyx,,，并且设Syx,，Szy,则qyx3，rzy3，rq,是整数；而rqzyyxzyyxzx3333也是整数所以Szx,因此S是传递的综上，S是等价关系。五、对下列集合在整除关系下构成的偏序集，画出Hasse图，并写出最大元，最小元，极大元，极小元。（1）}36,24,12,6,3,2{1A（2）}30,15,10,6,5,3,2,1{2A（3）}9,6,3,1{3A解：（1）无最大元，极大元为：24，36；无最小元，极小元为：2，3；（2）最大元和极大元为：30；最小元和极小元为：1（3）无最大元，极大元为：6，9；最小元和极小元为：15963130156321336241262（1）（2）（3）10六、设无向图G中有9个顶点，每个顶点的度数不是5就是6，试证明G中至少有5个6度顶点或至少有6个5度顶点。解：假设图G中最多有4个6度顶点，并且最多有有5个5度顶点则度为奇数的顶点只能为偶数个，所以5度顶点应该为4个，而6度顶点最多也为4个，所以与命题条件有9个顶点产生矛盾；因此G中至少有5个6度顶点或至少有6个5度顶点。