集合映射与运算.ppt

离散数学 Discrete Mathematics 邓辉文编著 清华大学出版社 2010. 3 ISBN 978-7-302-21193-8 十一五国家级规划教材 计算机系列教材 n离散数学是计算机各专业的专业基础课. n(1) 程序设计语言 n(2) 离散数学 n(3) 数据结构与算法 n(4) 计算机组成原理 n(5) 计算机网络 n(6) 操作系统 n(7) 数据库 n(8) 软件工程 n离散数学研究的对象: 离散量及其之间的关 系. 离散量与连续量及其之间的转换. 现今计算机的处理对象是非常特殊的离散量: 0 和1. n学习离散数学的目的: n1.培养各种能力. n2.为后继专业课程的学习作知识上的准备. n离散数学的主要内容: n1. 集合与关系 Chapter 1 集合、映射与运算 Chapter 2 关系 n2. 数理逻辑 Chapter 3 命题逻辑 Chapter 4 谓词逻辑 n3. 代数结构(Chapter 5) n4. 图论 Chapter 6 图论 Chapter 7 几类特殊的图 n5. 组合计数(Chapter 8) n学习离散数学的方法: 1.预习. 2.听课. 3.复习. 4. (分组)作业. n参考文献: 屈婉玲,耿素云, 张立昂, 离散数学, 高等教育出 版社, 2007. (108144学时) 傅彦, 顾小丰, 王庆先, 离散数学及其应用, 高等 教育出版社, 2008. (两个学期) Chapter 1 Sets, Mappings and Operations n集合是现代数学的最基本概念(?). n映射又称为函数, 它是现代数学的基本概念, 可以 借助于集合下定义. n运算本质上是映射, 但其研究有其特殊性. n(关系也是集合)集合、映射、运算及关系(Chapter 2)是贯穿于本书的一条主线. 1.1 集合的有关概念 n1. 集合 n在一定范围内, 集合(set)是其具有某种特定 性质的对象汇集成的一个整体, 其中的每一 个对象都称为该集合的元素(element). n这里所指范围是全集U(见图1-1).(避免悖论 !) n在数学中常用 表示整体. n若x是集合A中元素,则记xA, 否则xA. nFuzzy set ? n集合通常用大写字母A, B, C, D,表示. nN是自然数集合,包括数0；Z是整数集合；Q 是有理数集合；R是实数集合；C是复数集 合. nP : 2, 3, 5, 7, 11, 13, 17, 19, 23等. n(1) m|n: n = mq. n(2) Dn. n(3) 素数测试与Mersenne素数: 2p - 1. n表示集合的常用方法: n(1)列举法:0, 2, 4, 6, 8, N = 0, 1, 2, 3, . n(2)描述法:x|x满足的条件. n可简记: 直角三角形, 所有人 n(3)递归法 n自然数集合N可递归定义, 在后面章节定义 命题公式及谓词公式时还会用此法. n有限集合A的元素个数|A|, card(A). nRemarks n1.集合中的元素可以是集合, 例如A = a, a, b, b, c. na, bA, a, bA. n2.集合之间的元素原则上是没有次序的, 如 A = a, a, b, b, c就是 a, b, c , a, b; n3.集合中的元素原则上不重复, 如a, a, b, b, b, c还是集合A. n不含有任意元素的集合称为空集(empty set), 记为或 . n2.子集 nA B, 特别地是任意集合的子集. nA = B. nTheorem 1-2(P3) n(1) A A. n(2) A B, B A A = B. n(3) A B, B C A C. nTheorem 1-3 A = B A B 且 B A. n注意 与 的不同. n例1-2 由A B, B C可否得出A C? nSolution 不成立,例如A = a, b, B = a, b, c, C = a, a, b, c. n课堂练习: 4, 5. n3. 幂集(power set) nX = a, b P(X) = , a, b, a, b. nP(P() = P() = , (P5, 6(1). n, , (P5, 2) nTheorem 1-4 nProof(加法原理) n由乘法原理证明? n4.n元组 nDef 1-4 将n个元素(?)x1, x2, xn按一定顺序 排列就得到一个n元(有序)组(n-tuple). n线性代数中的n维向量(?): nn = 2, n = 3(see below) n n = 2: (x, y). n = 3: (x, y, z) n4元组? n显然, 一般说来(x, y) (y, x). n注意区别(a, b, c), (a, b), c), (a, (b, c)的不同. nn维向量是n元组, 长度为n的线性表是n元组, 抽象数据结构Data_Structure = (D, S) 本身是 一个2 元组. n2元组常称为有序对(ordered pair)或序偶. n5.笛卡儿积(cross product) n例1-4(P4) 设A = a, b, B = 1, 2, C = , 求A B, B A, A B C , B C. nSolution nAB C = (a, 1, ), (b, 1, ), (a, 2, ), (b, 2, ). nBC = (1, ), (2, ) nRemark A = B = . nP5, 10? nTheorem nHint n可推广到更多个集合的笛卡儿积的情形: n作业 习题1.1 6, 9, 10. 1.2 映射的有关概念 n1.映射的定义 n映射mapping = 函数function. nC语言是一种函数型语言: 从main开始. nDef nA, B: A B nCeiling function: nFloor function: n(取整函数) n复杂度: n函数的表示: (1)解析式 (2)图形 (3)表格(数值计算中出现较多) n函数符号的选取(P6):f, g, F,G, , sin, exp, main, add, average, n注意区别函数f与函数表达式f(x). n映射的两个特点: (1)全函数; (2)唯一性. nB上A: n例1-5 nTheorem 1-6 n注意B上A的记号与该结论的关系. x1 x2 x3 y1 y2 n X f(X) Y f-1(Y) nn元函数(n 1): nfloat average(flot array, int n) nn = 0: C语言中的无参函数? 一般处理方式: A到B的一个0元函数是B中某一个元素(see P136). n2.映射的性质 n(1)单射(injection) n(2)满射(surjection) n例1-7 是Z到N的满射, 但不是Z到 Z的满射(?). n(3)双射(bijection, one-to-one correspondence) n双射又称为一一对应:既单又满. n例1-8 n例1-9(P8) nDef 1-11 有限集合A上自身的双射称为A上 的置换(permutation). n例1-10 n第一种方式: 1 2 3 1 2 3 n第二种方式: nA = 1, 2, 3, 4上的所有置换有多少个? n4! n3. 逆映射 n设f: AB, 将对应关系f逆转(改变方向), 一般 来说, 不能得到B到A的映射: a b c 1 2 3 nDef 1-12 设f: AB, 若将对应关系f逆转后能 得出一个得到B到A的映射, 则称该映射为f 的逆映射(invertible function), 记为f-1. a b c 1 2 3 nTheorem 1-7 f 的逆映射存在的充要条件是f 是双射. n对于y = sin x, 当 时, 有反函数, 常记为 n当 时, y = sin x仍有反函数, 但不能 记为arcsin. 显然, 当 时, 无反函数. n4. 复合映射(composition function) nTheorem1-8 设f: A B, g: B C: n则h: A C. x y=f(x)z=g(y)= g(f(x) nDef 1-13 n例1-12 a b c 1 2 3 nRemarks n(1) y = sin u, u = x2 n未引入运算符号,有时是不方便的. n(2)顺序问题: n有些专业书 n但会出现一些混乱. n例1-13(P9) f: RR, f(x) = x2, ng: RR, g(x) = x + 2, 求fg和gf. nSolution x R: n(fg)(x) = g(f(x) = g(x2) = x2 + 2. n(gf)(x) = f(g(x) = f(x+2) = (x+2)2. nRemark fg gf. nIA: A A nTheorem 1-9 n理解: a b c 1 2 3 a b c 1 2 3 a b c 1 2 3 nTheorem 1-10 n(1)若f和g是单射, 则fg是单射. n(2)若f和g是满射, 则fg是满射. n(3)若f和g是双射, 则fg是双射. nProof (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). nTheorem 1-11 n(1)若fg是单射, 则f是单射, g不一定. n(2)若fg是满射, 则g是满射, f 不一定. n(3)若fg是双射, 则f是单射且g是满射. nProof (1)任意x1, x2 A, 若f(x1) = f(x2), n显然, g(f(x1) = g(f(x2), 即(fg)(x1) = (fg)(x2). 由于fg是单射, 因此 x1 = x2. 故f是单射. ng不一定(见上图)? n一般来说fg gf, 但 nTheorem 1-12 n作业 习题1.2: 3, 4, 7, 8, 12. nHint n7. 使用定理1-10和第3题. n8. 使用第7题结论. n12.使用第7题结论. 1.3 运算的定义及性质 n运算是讨论对象之间有何联系的一种方法. 其实 ，我们已经接触过很多运算,如数之间的加法运算 、多项式之间的乘法运算、矩阵的逆运算、向量 的线性运算等.在讨论离散数据结构时也会经常遇 到各种各样的运算，如在下节即将研究的集合间 的运算. n虽然运算本质上是映射，但研究的侧重点不同， 在运算中更注重于运算满足的一些运算性质，而 根据这些性质可以对一些离散对象分门别类进行 讨论. n因此，有必要先把运算的一般定义及其性质进行 讨论. n1. 运算的定义 n(1)定义 A1, A2, An到B的n元运算(n-ary operation): A到B(或A上)的n元运算: A上的n元封闭运算(代数运算): n(n = 0? 一般处理方式: A到B的一个0元运算 可理解为B中某一个元素.) n例1-14 f: Z N, f(x) = |x|. n例1-15(模运算) f: Z N, f(x) = x(mod k), n x = qk + r, 0 r 1. nProof (?) n2. 集合的覆盖 nDef 设A是集合, 由A的若干非空子集构成的 集合称为A的覆盖(covering), 如果这些非空 子集的并等于A. na, b, b, c n集合的划分 集合的覆盖, 但反过来不成 立. nA = a, b, c上所有不同的覆盖有哪些? n作业 习题1.5 1, 4, 7. 1.6 集合的对等 n集合的对等, 它是集合间的另一种关系. 通 过集合对等以及相关内容的学习, 加深对函 数概念的理解, 提高正确使用函数工具作为 研究手段的能力. n1.集合对等(equivalent) nDef A B: 存在双射f : A B. nN E. nZN? n(0, 1) R. nG. Cantor. nN N N. nTheorem 1-28(对等的性质) n(1) A A. n(2) A B B A. n(3) A B, B C A C. n2. 无限集合 n有了集合对等的概念, 就可以给出无限集合 及有限集合的严格定义. nDef 设A是集合, 若存在A的一个子集与自然 数集合N对等, 则称A为无限集合(infinite set), 否则称A为有限集合(finite set). nN. n0, 1. n3. 集合的基数 n有限集合的基数就是的元素个数. 借助于集 合对等概念, 可以将其扩展到无限集合. nDef 若集合A和B对等, 则称这两个集合的基 数(cardinality)相同. n|A|, card(A), #(A). nG. Cantor被这些问题所折磨难以自拔, 1884年后 患精神病(受到很多人的批评和攻击, 包括他的老 师, ,用脑过度?) n4. 可数集合 nDef 能与自然数集合N对等的集合称为可数 集合(countable set). n根据无限集合的定义知：任意无限集合均 存在一个可列的子集合. 根据这一点, 可以 证明无限集合的特征性质. nTheorem 设A是无限集合, 则存在A的一个真 子集B, 使得 A B. nProo