电大离散数学期末考试试题与答案.ppt

离散数学期末考试 2007年元月8日 1. (6分) 已知 A={{a},a,b}, B={{b}, a}, 求 A×B, A?B, P(A). 解: A×B={({a},{b}), ({a},a), (a, {b}), (a, a), (b, {b}), (b, a)} A?B=(A-B) ∪(B-A)={{a}, b, {b}} P(A)={?, {a}, a, b, {{a}, a}, {{a},b}, {a,b}, A}. 2. (4分) 已知R1,R2是A上的对称关系, R1°R2对称吗? 证明或举反例说明. 解: 一般地, R1°R2≠ R1°R2. 反例: R1={(1,3), (3,1)} 对称! R2={(3,2), (2,3)} 对称! R1°R2 ={(1,2)} 不对称! 3. (6分) G是一个群, H是G的子群. ?g1,g2?G, (g1,g2) ?R ? g1g2-1 ?H. 证明R是G上等价关系. 证明: ◆对于任意的a?G，∵ a·a-1=e?H， ∴ (a,a) ? R，故R是自反的。 ◆对于任意的a，b?G，若(a,b) ? R， ∴ a·b-1?H，∴(a·b-1)-1=b·a-1?H， ∴ (b,a) ? R，故R是对称的。 ◆对于任意的a,b,c?G，若(a,b) ? R，(b,c) ? R， ∴ a·b-1?H且 b·c-1?H， ∴ (a·b-1)·(b·c-1)=a·c-1?H， ∴ (a,c) ? R，故R是传递的。 4. (6分) A={1,2,3,5,10,15,30}, ?x,y?A, x?y?x|y. (1) 画出(A, ?)的哈斯图 (2) 判断(A, ?)是格否?分配格吗?有补格?布尔格吗? 5. 已知 f: A→B, g: B→C, f是单射,g是单射,证明g°f 是单射. 若g°f是满射,证明g是满射. 证明: (1) 对于任意的x1,x2?A, 若g°f (x1)= g°f (x2), 即有 g(f(x1))= g(f(x2)). 由于g是单射,故有f(x1)=f(x2). 由于f是单射,故有x1=x2. 因而, g°f 是单射. (2) 对于任意z?C, 存在x?A, 使得 g°f (x)=z, 即 g(f(x))=z. 故存在 y=f(x) ?B, 使得 g(y)=z. 故 g是满射. 6. (4分) 已知: A是可数无限集，B是有限集， 且A∩B=?， 求证：|A|=|A∪B| 证明: 不妨记 A={a1, a2, a3, …,an, …} B={b1, b2, b3, …, bm} 作映射 φ: A→A∪B φ(ai)=bi (i=1,…,m) φ(ai)=ai-m (i=m+1,m+2,…) 则可以说明φ为A→A∪B的双射， 故结论得证。 （如果只用一句话说， A∪B也是可数无限集，可以得2分） 7. (5分) 画出5个顶点的自互补图。证明当n=4k 或4k+1时才有. 若一个图和它的补图同构，说它是自互补图。 8. (5分) 证明: G或者G有一个是连通图。 9. (4分) 一个有奇数条边、偶数个顶点的欧拉图，但不是哈密尔顿图。 10 (6分) 画出K4,4，判断K4,4是否平面图. 11. (5分) 证明: 多于一个顶点的树，至少有两片树叶。 12. (8分) (G, ·)是一个群，取定u ? G. ?g1,g2?G，定义：  g1*g2= g1·u-1·g2. 证明: (G,*)是群。 证明: (1) 封闭性 (2) 可以结合性 (3) 幺元 e*=u. 事实上, g*e*=g*u=g·u-1·u=g·e=g e**g=u*g=u·u-1·g=e·g=g (4) 逆元 对于?g?G, 在代数运算*下的逆元记为g*-1 于是, g*-1=u·g-1·u 这里, g-1是在代数运算·下的逆元 13. (5分) G是一个群,H,K是G正规子群. 证明: H∩K是G正规子群. 证明: (1) (3分) ?a,b? H?K,就有a,b? H, a,b? K， 因为H, K是群G的子群， 所以，a*b-1?H，a*b-1?K，因此a*b-1? H?K。故 H?K是G的子群。 (2) (2分) 对于?a? H