2013年9月份考试离散数学第三次作业

2013年9月份考试离散数学第三次作业一、填空题（本大题共10分，共5小题，每小题2分）1.群满足结合律和______。2.设p,q的真值为0；r,s的真值为1，求命题公式（rs)(pq)的真值______。3.设A={a,b,c},A上的二元关系R={a,b,b,c}，则r(R)=______；s(R)=______。4.在代数系统A,*中，A={a}，*是A上的二元运算，则该代数系统的单位元是______,零元是______。5.设无向图中有6条边，3度与5度顶点各1个，其余顶点都是2度结点，该图有______个顶点。二、作图题（本大题共20分，共4小题，每小题5分）1.试画出结点数为3的（1）强连通图（2）单向连通图（3）弱连通图（4）非连通图2.求下图所示带权图的最小生成树：3.某城市拟在六个区之间架设有限电话网，其网点间的距离如下有权矩阵，请绘出有权图，给出架设线路的最优方案，并计算线路的长度。4.画出下图的最小生成树，并求出该最小生成树的权。三、计算题（本大题共20分，共2小题，每小题10分）1.符号化以下命题：假如上午不下雨，我就去看电影，否则就在家里读书或看报。2.下图给出的赋权图表示五个城市及对应两个城镇间公路的长度。是给出一个最优的设计方案使各城市间有公路连通。四、简答题（本大题共20分，共4小题，每小题5分）1.判断下图是否欧拉图，若是，找出一个欧拉回路。2.形式化表达：假如上午不下雨，我就去看电影，否则就在家里读书或看报。3.在个体域D={a,b,c}消去公式的量词。4.航海家都教育自己的孩子成为航海家，有一个人教育他的孩子去做飞行员，证明：这个人一定不是航海家。五、分析题（本大题共20分，共2小题，每小题10分）1.一棵树中，度数为2的结点有2个，度数为3的结点有3个，。。。度数为k的结点有k个，其余的是度数为1的结点，求度数为1的结点的个数。2.求出下式的主合取范式和主析取范式((x1→x2)→x3)→x4六、证明题（本大题共10分，共1小题，每小题10分）设f1,f2都是从代数系统A,到代数系统B,*的同态。设g是从A到B的一个映射，使得对任意a∈A，都有g(a)=f1(a)*f2(a)。证明：如果是一个可交换半群，那麽g是一个由代数系统A,到代数系统B,*的同态。答案：一、填空题（10分，共5题，每小题2分）1.参考答案：消去律解题方案：评分标准：答案正确得满分，错误不得分2.参考答案：0解题方案：评分标准：3.参考答案：{,,,,},s(R)={,,,}解题方案：评分标准：4.参考答案：a,a解题方案：评分标准：5.参考答案：4解题方案：评分标准：二、作图题（20分，共4题，每小题5分）1.参考答案：解题方案：评分标准：2.参考答案：此图的最小生成树为：该最小生成树的权为：1+3+2+2+1=9解题方案：评分标准：3.参考答案：根据矩阵画出无向图为：根据题意求出最小生成树如下：该最小生成树的权重为：1+2+3+5+7=18因此本题中线路的长度为18解题方案：评分标准：4.参考答案：解题方案：评分标准：三、计算题（20分，共2题，每小题10分）1.参考答案：设：P：上午不下雨；Q：我去看电影R：我在家读书；M：我在家看报则有：（P→Q）→（R∨M）解题方案：评分标准：262.参考答案：该图的最小生成树为：1+1+2+3=7解题方案：评分标准：四、简答题（20分，共4题，每小题5分）1.参考答案：是；欧拉回路为：解题方案：评分标准：2.参考答案：设：P：上午不下雨；Q：我去看电影；R：我在家读书；M：我在家看报，则有：（P→Q）→（RM）解题方案：评分标准：233.参考答案：解题方案：评分标准：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)由以上的推证可以知道，这个人一定不是航海家。解题方案：设个体域为人的集合。谓词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)由以上的推证可以知道，这个人一定不是航海家。评分标准：41五、分析题（20分，共2题，每小题10分）1.参考答案：设度数为1的结点有x个，则该树中有x+2+3+…+k个顶点，从而有x+2+3+…+k-1条边则有：x*1+2*2+…k*k=2(x+2+3…k-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+3…k-1)则x=∑i2-2Si+2=∑(i2-2i+1)+(3-k)=∑i2+(3-k)评分标准：3342.参考答案：主合取范式：(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)解题方案：评分标准：55六、证明题（10分，共1题，每小题10分）0.参考答案：因为对于任意的a，b∈A，都有g(a★b)=f1(a★b)*f2(a★b)=f1(a)*f1(b)*f2(a)*f2(b)=g(a)*g(b)所以，g是由到的同态。解题方案：评分标准：