A2007,1离散数学AB标准答案.docVIP

课程名称: 离散数学A卷标准答案 考试时间: 第 21 周星期五 ( 2007年1月 26日) 一、单项选择题(本大题共8小题，每小题2分，共16分) 1 2 3 4 5 6 7 8 A A C C D D B B 二、填空题(本大题共8小题，每空3分，共24分) 1.无（或没有，或空） 2. 1（或T，或真） 3. 2 4. [n(n-1)/2]-m 5. {2,{2}} 6. 4!（或24） 7. 24（或16） 8.{(1,1),(2,2),(3,3),(4,4)} 三、(10分) 证明：如果图G是连通图，问题得证。 2分 如果G不是连通图，不妨设图G由K个连通分支G1,G2,…,Gk构成。现证G的补图是连通图。 2分 在补图中任取两点u和v，由于补图和原图有相同的顶点，所以u和v也是图G的点。下面分两种情况讨论。 1. u和v分别是不同的连通分支Gi和Gj的点（见下图1）。易知，连接u和v的边在补图中，即在补图中，u和v之间有通路相连。 3分 图1 图2 2. u和v是同一连通分支Gi中的点（见上图2）。则可在另一连通分支Gj中任取一点x，易见边ux和边vx是补图中的边，由此可知点u和v之间在补图中有通路uxv相连。 3分 综上所述，补图是连通图。证毕。 四、(10分) 证明：①￢s P 1分 ②p→s P 1分 ③￢p T①② 1分 ④p(q P 1分 ⑤q T③④ 1分 ⑥q→r P 1分 ⑦r T⑤⑥ 1分 T规则应用正确：2分； P规则应用正确：1分； 五、(10分) 解： 1.X＝{a,b,c,d,e,f} 2分 ≤={(a,b)，(a,c)，(a,d)，(a,e)，(a,f)，(b,e)，(c，e), (c,f)，(d,f)}∪Ix 4分，其中错一个、多一个、漏一个元素均扣0.5分，直至4分扣完。 2.极大元e； 1分 极小元a； 1分 最大元不存在； 1分 最小元a。 1分 六、(10分) 证明： ①由已知，运算显然封闭； 2分 ②对(x，y，z(Z有： (x*y)*z=(x+y-2)*z=(x+y-2)+z-2=x+y+z-4 1分 x*(y*z)=x*(y+z-2)=x+(y+z-2)-2=x+y+z -4 1分 所以，*满足结合律； ③对(x (Z有：x*2=x+2-2=0， 1分 且2*x=2+x-2=0 1分 所以，存在单位元：2 ④对(x (Z有：x*(4-x)=x+4-x-2=2， 1分 且(4-x)*x=4-x+x-2=2 1分 所以，对(x (Z有x的逆元是：4-x 1分 由①②③④可知，（Z，*）是群。