。。
《离散数学》期终试题
南京大学计算机系 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/2 相关文档推荐... 离散数学期中试题 (计算机系本科 2003 年 4 月) 1.证明 ? ( A ? B )...
2008 级计算机《离散数学》期末试卷 A 答案一、单项选择题:(20%,每空 2 分) 1.设 A={1,2,3,4,5},下面( C A、{1,2,3,4,5,6} C、{x x ...
《离散数学》期终试题-软件学院-2005-1-中文版 隐藏>> 《离散数学》期末考试...B 。 2. 某系 120 名学生中有 100 人选修德语、法语和俄语三门课中的至少...
( ? x)A(x)→( ? y)B(y) 7、若 s={1,2,3,4},S 上关系 R 的关系图为: 2009 级计算机《离散数学》期中试卷答案 级计算机《 期中试卷答案题序 ...
7计算机专业本科函授离散数学期末复习B试题_理学_高等教育_教育专区。《离散数学》一、单项选择题(本大题共 7 小题,每小题 3 分,共 21 分) 1. 下面联结词...
08计算机《离散数学》期中试卷答案_工学_高等教育_教育专区。泉州师院 2009-...? ? i ?1 {0 } 系 6、下列等值式不正确的是( C 3.令 p:今天下雪了...
贵州大学信息学院计算机专业2004级《离散数学》试卷A_工学_高等教育_教育专区。... 贵州大学有机化学期末考... 12页 2下载券 贵州大学C语言A试卷 7页 1下载...
华中科技大学2013——2014年《离散数学》试卷B卷_工学_高等教育_教育专区。计算机学院 2013 — 2014 学年《离散数学》考试试卷 B卷 专业题号 题分 得分 一 20...
计算机专业《离散数学》教学研究_专业资料。离散数学是计算机科学与技术专业的主要基础课程,但是,大多数院校以数学理论的方式来教学,不能有效地和计算机专业的特性相...
热门文档