文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 工学 > 《离散数学》期终试题-计算机系-2002
侵权投诉

《离散数学》期终试题-计算机系-2002

。。

《离散数学》期终试题

南京大学计算机系 2002年7月

共10题,每题10分。

1. 设A, B, C为任意集合,证明

1.1 A B=A B A=B

证明: 对任意x, 若x A, 则x A B=A B, x B, A B; 同理可

得: B A, A=B。

显然。

1.2 (A-B) (A-C)= A (B C)

证明: 若A是空集,结论成立。

若A非空,任取x A, 假设x B C, 则A-B=A-C=A ,与前提矛盾, x B C, A (B C)

假设(A-B) (A-C) , 任取x (A-B) (A-C), 则:x A, 但x B且x C, x (B C), 这与A (B C)矛盾。 (A-B) (A-C)= 。

2. 设R A B, S B C, T B C

2.1 证明(R S)-(R T) R (S-T)

证明:任给(a,c), 若a A, c C, 且(a,c) (R S)-(R T), 则(a,c) R S, 但

(a,c) R T, 即存在b B, 满足:(a,b) R, (b,c) S, 但(b,c) T, 于是(b,c) S-T, (a,c) R (S-T), (R S)-(R T) R (S-T)

2.2 举例说明上式反包含关系不成立

证明:寻找反例的线索:如果试图证明R (S-T) (R S)-(R T), (a,b) R,

(b,c) S, 但(b,c) T并不能保证(a,c) R T, 因为可能存在另一个b’ B, 满足(a,b’) R, (b’,c) T。

反例:A={a}, B={b,b’}, C={c}, R={(a,b), (a,b’)}, S={(b,c), (b’,c)}, T={(b’c)}, 则(a,c) R (S-T), 但(a,c) (R S)-(R T)。

3. 设A为有穷集合,f为从A到A的映射

3.1 证明f为单射(1-1) f为满射(onto)

证明:设|A|=n,f(A)={y|存在x A, 使得f(x)=y}

假设f非满射,则存在x A, x不是f下任何元素的象,即|f(A)|<n, 根据鸽巢原理,至少有两个不同元素有相同的象,

这与f是单射矛盾, f是满射。

假设f非单射,则存在x,y A, 满足x y, 但f(x)=f(y), 则|f(A)|<n, 这与f是满射矛盾, f是单射

3.2 举例说明上述结论对无穷集不成立

证明:反例:令A为自然数集,f(x)=2x, 则f是单射,但非满射。

4. 写出(Z8, +8)所有子群,这里Z8={0,1,…,7}, +8为模8加法。 解:({0},+8), ({0,4},+8), ({0,2,4,6},+8), (Z8,+8), 共有4个子群。

第1页

你可能喜欢

  • 电大离散数学考试
  • 概率论与数理统计期末试题
  • 南京大学考研
  • 计算机网络期末考试试题及答案
  • 离散数学试题及答案
  • 离散数学期末考试试题
  • 自考离散数学
  • 教育统计与测量试题

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email