《自考（网络教育）离散数学作业题及解析》由会员分享，可在线阅读，更多相关《自考（网络教育）离散数学作业题及解析（8页珍藏版）》请在金锄头文库上搜索。
1、 离散数学离散数学 一、填空题（本大题共一、填空题（本大题共 1010 分，共分，共 5 5 小题，每小题小题，每小题 2 2 分）分） 1. 群满足结合律和 _ 。 2. 设 p,q 的真值为 0；r,s 的真值为 1，求命题公式 （rs)(pq)的真值 _ 。 3. 设 A=a,b,c,A 上的二元关系 R=,，则 r(R)= _ ；s(R)= _ 。 4. 在代数系统中，A=a，*是 A 上的二元运算，则该代数系统的单位元 是 _ ,零元是 _ 。 5. 设无向图中有 6 条边，3 度与 5 度顶点各 1 个，其余顶点都是 2 度结点，该 图有 _ 个顶点。 二、作图题（本大题共二、作图
2、题（本大题共 2020 分，共分，共 4 4 小题，每小题小题，每小题 5 5 分）分） 1. 试画出结点数为 3 的 （1）强连通图 （2）单向连通图 （3）弱连通图 （4）非连通图 2. 求下图所示带权图的最小生成树：3. 某城市拟在六个区之间架设有限电话网，其网点间的距离如下有权矩阵，请 绘出有权图，给出架设线路的最优方案，并计算线路的长度。4. 画出下图的最小生成树，并求出该最小生成树的权。三、计算题（本大题共三、计算题（本大题共 2020 分，共分，共 2 2 小题，每小题小题，每小题 1010 分）分） 1. 符号化以下命题： 假如上午不下雨，我就去看电影，否则就在家里读书或 看报
3、。 2. 下图给出的赋权图表示五个城市及对应两个城镇间公路的长度。是给出一个 最优的设计方案使各城市间有公路连通。四、简答题（本大题共四、简答题（本大题共 2020 分，共分，共 4 4 小题，每小题小题，每小题 5 5 分）分） 1. 判断下图是否欧拉图，若是，找出一个欧拉回路。2. 形式化表达：假如上午不下雨，我就去看电影，否则就在家里读书或看报。3. 在个体域 D=a,b,c消去公式的量词。 4. 航海家都教育自己的孩子成为航海家，有一个人教育他的孩子去做飞行员， 证明：这个人一定不是航海家。五、分析题（本大题共五、分析题（本大题共 2020 分，共分，共 2 2 小题，每小题小题，每小
4、题 1010 分）分） 1. 一棵树中，度数为 2 的结点有 2 个，度数为 3 的结点有 3 个，。度数为 k 的结点有 k 个，其余的是度数为 1 的结点，求度数为 1 的结点的个数。 2. 求出下式的主合取范式和主析取范式 (x1x2)x3)x4六、证明题（本大题共六、证明题（本大题共 1010 分，共分，共 1 1 小题，每小题小题，每小题 1010 分）分） 设 f1,f2 都是从代数系统到代数系统的同态。设 g 是从 A 到 B 的 一个映射，使得对任意 aA，都有 g(a)= f1 (a)* f2 (a) 。证明：如果是一 个可交换半群，那麽 g 是一个由代数系统到代数系统的同态
5、。答案：答案：一、填空题（一、填空题（1010 分，共分，共 5 5 题，每小题题，每小题 2 2 分）分）1. 参考答案：参考答案： 消去律 解题方案：解题方案：评分标准：评分标准： 答案正确得满分，错误不得分 2. 参考答案：参考答案： 0 解题方案：解题方案：评分标准：评分标准：3. 参考答案：参考答案： ,s(R)=, 解题方案：解题方案：评分标准：评分标准：4. 参考答案：参考答案： a,a 解题方案：解题方案：评分标准：评分标准：5. 参考答案：参考答案： 4 解题方案：解题方案：评分标准：评分标准：二、作图题（二、作图题（2020 分，共分，共 4 4 题，每小题题，每小题 5
6、5 分）分）1. 参考答案：参考答案：解题方案：解题方案：评分标准：评分标准：2. 参考答案：参考答案： 此图的最小生成树为：该最小生成树的权为：1+3+2+2+1=9 解题方案：解题方案：评分标准：评分标准：3. 参考答案：参考答案： 根据矩阵画出无向图为：根据题意求出最小生成树如下：该最小生成树的权重为：1+2+3+5+7=18 因此本题中线路的长度为 18 解题方案：解题方案：评分标准：评分标准：4. 参考答案：参考答案：解题方案：解题方案：评分标准：评分标准：三、计算题（三、计算题（2020 分，共分，共 2 2 题，每小题题，每小题 1010 分）分）1. 参考答案：参考答案： 设：
7、P：上午不下雨； Q：我去看电影 R：我在家读书； M：我在家看报则有： （PQ）（RM） 解题方案：解题方案：评分标准：评分标准： 2 6 2. 参考答案：参考答案：该图的最小生成树为：1+1+2+3=7 解题方案：解题方案：评分标准：评分标准：四、简答题（四、简答题（2020 分，共分，共 4 4 题，每小题题，每小题 5 5 分）分）1. 参考答案：参考答案： 是；欧拉回路为：解题方案：解题方案：评分标准：评分标准：2. 参考答案：参考答案： 设：P：上午不下雨； Q：我去看电影； R：我在家读书； M：我在家看报，则有：（PQ）（RM） 解题方案：解题方案：评分标准：评分标准： 2 3
8、 3. 参考答案：参考答案：解题方案：解题方案：评分标准：评分标准：4. 参考答案：参考答案： 设个体域为人的集合。谓词 S(x):x 是航海家； E(x):x 教育他的孩子成为航 海家。 前提： x(S(x) E(x), x( E(x) 结论： x( E(x) S(x) 推理过程为： (1) x( E(x) P (2) E(c) ES(1) (3) x(S(x) E(x) P (4)S(c) E(c) US(3) (5) S(c) T(2)(4) (6) E(c) S(c) T(2)(5) (7) x( E(x) S(x) EG(6) 由以上的推证可以知道，这个人一定不是航海家。 解题方案：
9、解题方案： 设个体域为人的集合。谓词 S(x):x 是航海家； E(x):x 教育他的孩子成为航 海家。 前提： x(S(x) E(x), x( E(x) 结论： x( E(x) S(x) 推理过程为： (1) x( E(x) P (2) E(c) ES(1) (3) x(S(x) E(x) P (4)S(c) E(c) US(3) (5) S(c) T(2)(4) (6) E(c) S(c) T(2)(5) (7) x( E(x) S(x) EG(6) 由以上的推证可以知道，这个人一定不是航海家。 评分标准：评分标准： 4 1五、分析题（五、分析题（2020 分，共分，共 2 2 题，每小题
10、题，每小题 1010 分）分）1. 参考答案：参考答案： 设度数为 1 的结点有 x 个，则该树中有 x+2+3+k 个顶点，从而有 x+2+3+k-1 条边 则有： x*1+2*2+k*k=2(x+2+3k-1) 则 x=i2-2Si+2 =(i2-2i+1)+(3-k) =i2+(3-k) 解题方案：解题方案： 设度数为 1 的结点有 x 个，则该树中有 x+2+3+k 个顶点，从而有 x+2+3+k-1 条边 则有： x*1+2*2+k*k=2(x+2+3k-1) 则 x=i2-2Si+2 =(i2-2i+1)+(3-k) =i2+(3-k) 评分标准：评分标准： 3 3 4 2. 参考
11、答案：参考答案：主合取范式： (x1 x2 x3 x4) (x1 x2 x3 x4) ( x1 x2 x3 x4) ( x1 x2 x3 x4) ( x1 x2 x3 x4) 主析取范式： ( x1 x2 x3 x4) ( x1 x2 x3 x4) ( x1 x2 x3 x4) ( x1 x2 x3 x4) ( x1 x2 x3 x4) ( x1 x2 x3 x4) (x1 x2 x3 x4) (x1 x2 x3 x4) (x1 x2 x3 x4) (x1 x2 x3 x4) (x1 x2 x3 x4) 解题方案：解题方案：评分标准：评分标准： 5 5六、证明题（六、证明题（1010 分，共分，共 1 1 题，每小题题，每小题 1010 分）分）0. 参考答案：参考答案： 因为对于任意的 a，bA，都有 g(ab)= f1(ab)* f2(ab)= f1(a)* f1(b) * f2(a) * f2(b)=g(a)*g(b) 所以，g 是由到的同态。解题方案：解题方案：评分标准：评分标准：
