第1章集合、映射与运算.ppt
《第1章集合、映射与运算.ppt》由会员分享,可在线阅读,更多相关《第1章集合、映射与运算.ppt(87页珍藏版)》请在三一文库上搜索。
1、离散数学 Discrete Mathematics,邓辉文编著 清华大学出版社 2006.10 ISBN 978-7-302-13711-5,离散数学是计算机各专业的专业基础课. 离散数学研究的对象: 离散量及其之间的关系. 离散量与连续量及其之间的转换. 现今计算机的处理对象是非常特殊的离散量: 0和1. 学习离散数学的目的: 1.培养各种能力. 2.为后继专业课程的学习作知识上的准备.,离散数学的基本内容: 1.集合与关系 Chapter 1 集合、映射与运算 Chapter 2 关系 2.数理逻辑 Chapter 3 命题逻辑 Chapter 4 谓词逻辑 3.代数结构 Chapter
2、5 群、环和域 Chapter 6 格与布尔代数 4.图论 Chapter 7 图论 Chapter 8 几类特殊的图,学习离散数学的方法: 1.预习. 2.听课. 3.复习. 4.作业. 参考文献: 耿素云 屈婉玲,离散数学(修订版),高等教育出版社,2004. Kenneth H. Rosen, Discrete Mathematics and Its Applications (Fourth Edition), McGraw-Hill Companies, Inc.1998.(有中译本,2002),Chapter 1 Sets, Mappings and Operations,集合是现代
3、数学的最基本概念(?). 映射又称为函数, 它是现代数学的基本概念, 可以借助于集合下定义. 运算本质上是映射, 但其研究有其特殊性. 集合、映射、运算及关系(Chapter 2)是贯穿于本书的一条主线.,1.1 集合的有关概念,1. 集合 集合(用处?)已渗透到自然科学以及社会科学的各个研究领域, 在信息的表示及处理中,可以借助于集合去实现数据的删节、插入、排序以及描述数据间的关系. 在一定范围内, 集合(set)是其具有某种特定性质的对象汇集成的一个整体, 其中的每一个对象都称为该集合的元素(element). 这里所指范围是全集U(见图1-1).(避免悖论!) 在数学中常用 表示整体.
4、若x是集合A中元素,则记xA, 否则xA.,常见的数的集合用黑正体字母表示: N是自然数集合,包括数0;Z是整数集合;Q是有理数集合;R是实数集合;C是复数集合. 表示集合的常用方法: (1)列举法:0, 2, 4, 6, 8, N = 0, 1, 2, 3, . (2)描述法:x|x满足的条件. (3)递归法 自然数集合N可递归定义, 在后面章节定义命题公式及谓词公式时还会用此法. 有限集合A的元素个数|A|.,Remarks 1.集合中的元素可以是集合, 例如A = a, a, b, b, c. a, bA, a, bA. 2.集合之间的元素原则上是没有次序的, 如 A = a, a, b
5、, b, c就是 a, b, c , a, b; 3.集合中的元素原则上不重复, 如a, a, b, b, b, c还是集合A. 不含有任意元素的集合称为空集(empty set), 记为或 .,2.子集 A B, 特别地是任意集合的子集. A = B. Theorem 1-2(P3) (1) A A. (2) A B, B A A = B. (3) A B, B C A C. Theorem 1-3 A = B A B 且 B A.,注意 与 的不同. 例1-2 由A B, B C可否得出A C? Solution 不成立,例如A = a, b, B = a, b, c, C = a, a,
6、 b, c. 课堂练习: 4, 5. 3. 幂集(power set) X = a, b P(X) = , a, b, a, b. P(P() = P() = , (P5, 6(1). , , (P5, 2),Theorem 1-4 Proof 由乘法原理证明?,4.n元组 Def 1-4 将n个元素(?)x1, x2, xn按一定顺序排列就得到一个n元(有序)组(n-tuple). 在数据结构中就是一个线性表.,n = 2: (x, y). n = 3: (x, y, z) 4元组? 显然, 一般说来(x, y) (y, x). 注意区别(a, b, c), (a, b), c), (a,
7、(b, c)的不同.,n维向量是n元组, 长度为n的线性表是n元组, 抽象数据结构Data_Structure = (D, S) 本身是一个2 元组. 2元组常称为有序对(ordered pair)或序偶. 5.笛卡儿积(cross product),例1-4(P4) 设A = a, b, B = 1, 2, C = , 求AB, BA, BC, ABC. Solution BC = (1, ), (2, ) AB C = (a, 1, ), (b, 1, ), (a, 2, ), (b, 2, ).,Remark A = A = . P5, 10? Theorem Hint 可推广到更多个集
8、合的笛卡儿积的情形: 作业 习题1.1 6, 9, 10.,1.2 映射的有关概念,1.映射的定义 映射mapping=函数function. C语言是一种函数型语言: 从main开始. Def,A,B,函数的表示: (1)解析式 (2)图形 (3)表格(数值计算中出现较多) 函数符号的选取(P6):f, g, F,G, , sin, exp, main, add, average, 注意区别函数f与函数表达式f(x). 映射的两个特点: (1)全函数; (2)唯一性.,B上A: 例1-5 Theorem 1-6 注意B上A的记号与该结论的关系.,x1 x2 x3,y1 y2,像与原像,X,f
9、(X),Y,f-1(Y),n元函数(n 1): float average(float array, int n),2.映射的性质 (1)单射(injection),(2)满射(surjection) 例1-7 是Z到N的满射, 但不是Z到Z的满射(?).,(3)双射(bijection, one-to-one correspondence) 双射又称为一一对应:既单又满. 例1-8 例1-9(P8),例1-10 Def 1-11 有限集合A上自身的双射称为A上的置换(permutation). A = 1, 2, 3, 4上的所有置换有多少个? 4!,1 2 3,1 2 3,3. 逆映射 设
10、f: AB, 将对应关系f逆转(改变方向), 一般来说, 不能得到B到A的映射:,a b c,1 2 3,Def 1-12 设f: AB, 若将对应关系f逆转后能得出一个得到B到A的映射, 则称该映射为f的逆映射(invertible function), 记为f-1.,a b c,1 2 3,Theorem 1-7 f 的逆映射存在的充要条件是f是双射. 对于y = sin x, 当 时, 有反函数, 常记为 当 时, y = sin x仍有反函数, 但不能 记为arcsin. 显然, 当 时, 无反函数.,4. 复合映射(composition function) Theorem1-8 设
11、f: A B, g: B C: 则h: A C.,x,y=f(x),z=g(y)= g(f(x),Def 1-13 例1-12,a b c,1 2 3, ,Remarks (1) y = sin u, u = x2 未引入运算符号,有时是不方便的. (2)顺序问题: 有些专业书 但会出现一些混乱.,例1-13(P9) f: RR, f(x) = x2, g: RR, g(x) = x + 2, 求fg和gf. Solution x R: (fg)(x) = g(f(x) = g(x2) = x2 + 2. (gf)(x) = f(g(x) = f(x+2) = (x+2)2. Remark f
12、g gf.,IA: A A Theorem 1-9 理解:,a b c,1 2 3,a b c,1 2 3,a b c,1 2 3,Theorem 1-10 (1)若f和g是单射, 则fg是单射. (2)若f和g是满射, 则fg是满射. (3)若f和g是双射, 则fg是双射. Proof (2)任意z C, 由于g是满射, 存在y B, 使得z = g(y). 又由于f是满射, 存在x A, 使得y = f(x). 于是z = g(y) = g(f(x) = (fg)(x). 故fg是满射(see below).,Theorem 1-11 (1)若fg是单射, 则f是单射, g不一定. (2)
13、若fg是满射, 则g是满射, f 不一定. (3)若fg是双射, 则f是单射且g是满射. Proof (1)任意x1, x2 A, 若f(x1) = f(x2),显然, g(f(x1) = g(f(x2), 即(fg)(x1) = (fg)(x2). 由于fg是单射, 因此 x1 = x2. 故f是单射. g不一定(见上图)?,一般来说fg gf, 但 Theorem 1-12 作业 习题1.2: 3, 4, 7, 8, 12. Hint 7. 使用定理1-10和第3题. 8. 使用第7题结论. 12.使用第7题结论.,1.3 运算的定义及性质,运算是讨论对象之间有何联系的一种方法. 其实,我
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 集合 映射 运算
链接地址:https://www.31doc.com/p-2093579.html