集合、映射与运算

离散数学 (Discrete Mathematics),邓辉文编著 清华大学出版社 2006.10 ISBN 7-302-13711-0/TP·8265,离散数学研究的对象: 离散量及其之间的关系. 离散量与连续量及其之间的转换. 现今计算机的处理对象是非常特殊的离散量: 0和1. 学习离散数学的目的: 1.培养各种能力. 2.为后继专业课程的学习作知识上的准备.,离散数学的基本内容: 1.集合与关系 Chapter 1 集合、映射与运算 Chapter 2 关系 2.数理逻辑 Chapter 3 命题逻辑 Chapter 4 谓词逻辑 3.代数结构 Chapter 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,集合是现代数学的最基本概念(?). 映射又称为函数, 它是现代数学的基本概念, 可以借助于集合下定义. 运算本质上是映射, 但其研究有其特殊性. 集合、映射、运算及关系(Chapter 2)是贯穿于本书的一条主线.,1.1 集合的有关概念,1. 1.1 集合 集合(用处?)已渗透到自然科学以及社会科学的各个研究领域, 在信息的表示及处理中,可以借助于集合去实现数据的删节、插入、排序以及描述数据间的关系. 在一定范围内, 集合(set)是其具有某种特定性质的对象汇集成的一个整体, 其中的每一个对象都称为该集合的元素(element). 这里所指范围是全集U(见图1-1).(避免悖论!) 在数学中常用{ }表示整体. 若x是集合A中元素,则记xA, 否则xA.,常见的数的集合用正+黑体字母表示: 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}. 2.集合之间的元素原则上是没有次序的, 如 A = {a, {a, b}, b, c}就是 {a, b, c , {a, b}}; 3.集合中的元素原则上不重复, 如{a, {a, b}, b, b, c}还是集合A. 不含有任意元素的集合称为空集, 记为或{ }.,思考 所有不以自身为元素的集合能构成集合吗？ 【罗素悖论简介】 1900年前后,在数学的集合论中出现了三个著名悖论，理发师悖论就是罗素悖论的一种通俗表达方式。

此外还有康托尔悖论、布拉利—福尔蒂悖论这些悖论特别是罗素悖论，在当时的数学界与逻辑界内引起了极大震动触发了第三次数学危机理发师悖论】 在某个城市中有一位理发师，他的广告词是这样写的：“本人的理发技艺十分高超，誉满全城我将为本城所有不给自己刮脸的人刮脸，我也只给这些人刮脸我对各位表示热诚欢迎！”来找他刮脸的人络绎不绝，自然都是那些不给自己刮脸的人可是，有一天，这位理发师从镜子里看见自己的胡子长了，他本能地抓起了剃刀，你们看他能不能给他自己刮脸呢？如果他不给自己刮脸，他就属于“不给自己刮脸的人”，他就要给自己刮脸，而如果他给自己刮脸呢？他又属于“给自己刮脸的人”，他就不该给自己刮脸1.1.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, b, c}}. 课堂练习: 4, 5. 1.1.3 幂集 X = {a, b}  P(X) = {, {a}, {b}, {a, b}}.,,Theorem 1-4 Proof 由乘法原理证明?,加法原理：如果完成某件事的方法可区分成k个类別, 而第j(j=1,2,……,k)个类別有mj种方法, 且每个类別互不相干, 那么完成这件事的方法共有 m1+m2+……+mk种。

例：从甲地到乙地有飞机、火车与巴士等三种交通工具可到达，其中飞机每天有3班，火车每天有15班，巴士每天25班，若A先生欲从甲地至乙地, 很明显地, 可看出此问题的A先生只能选择一种交通工具的某个班次, 故共有3+15+25=43个交通班次可选择乘法原理：如果完成某件事情可依序分成k个步骤, 而第j(j=1,2,……,k)个步骤有mj种方法可以完成它, 那么完成这件事的方法共有m1×m2×……×mk种 例：教室里有n张椅子，有n位同学依次选择座位，共有多少种不同的选择法很明显：第一位同学从n张椅子中，选1个，有n种选法；第二位同学从n-1张椅子中，选取1个，有n-1种选法；……以此类推，共有n×(n-1)×……×2×11.1.4 n元组 Def 1-4 论域U中选取的n个元素x1, x2,…, xn按一定顺序排列就得到一个n元有序组，简称n元组，记为. n元组在数据结构中就是一个线性表.,n = 2: (x, y). n = 3: (x, y, z) 显然, 一般说来(x, y)  (y, x). 注意区别(a, b, c), ((a, b), c), (a, (b, c))的不同.,,,,,,,,,,,,,n维向量是n元组, 长度为n的线性表是n元组, 抽象数据结构Data_Structure = (D, S) 本身是一个2 元组. 2元组常称为有序对或序偶. 1.1.5 笛卡儿积,例1-4(P4) 设A = {a, b}, B = {1, 2}, C = {}, 求AB, BA, BC, CAB. Solution BC = {(1, ), (2, )} CAB = {(, a, 1), (, b, 1), (, a, 2), (, b, 2)}.,,,Theorem Hint 可推广到更多个集合的笛卡儿积的情形. 作业 习题1.1 6, 9, 10.,1.2 映射的有关概念,12.1 映射的定义 映射=函数,它也是现代数学中的基本概念,要求我们在各学科中都要会使用映射的观点. 函数在信息科学中得到了充分的应用,大家熟悉的C语言是一种函数型语言. Def 1-6,A,B,,,,,,,函数的表示: (1)解析式 (2)图形 (3)表格(数值计算中出现较多) 函数符号的选取. 注意区别函数f与函数表达式f(x). 映射的两个特点: (1)全函数; (2)唯一性.,B上A: 例1-5 Theorem 1-6 注意B上A的记号与该结论的关系.,x1 x2 x3,y1 y2,,,,,X,f(X),,,,Y,f-1(Y),,,n元函数(n 1): n = 0: C语言中的无参函数?,1.2.2 映射的性质 1.单射,,,,,,,,2.满射 例如, 是Z到N的满射, 但不是Z到Z的满射(?).,,,,,3.双射 双射又称为一一对应:既单又满. 例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,,1.2.3 逆映射 设f: AB, 将对应关系f逆转(改变方向), 一般来说, 不能得到B到A的映射: Def 1-12 设f: AB, 若将对应关系f逆转后能得出一个得到B到A的映射, 则称该映射为f的逆映射, 记为f-1.,a b c,1 2 3,,,,Theorem 1-7 f 的逆映射存在的充要条件是f是双射. 对于y = sin x, 当 时, 有反函数, 常记为 当 时, y = sin x仍有反函数, 但不能 记为arcsin. 显然, 当 时, 无反函数.,,1.2.4 复合映射 设f: A  B, g: B  C: 例1-12,a b c,1 2 3,   ,,,,,,,例1-13(P9) f: RR, f(x) = x2, g: RR, f(x) = x + 2, 求f◦g和g◦f. Solution x  R: (f◦g)(x) = g(f(x)) = g(x2) = x2 + 2. (g◦f)(x) = f(g(x)) = f(x+2) = (x+2)2. Remark f◦g  g◦f.,Theorem 1-9 Theorem 1-10 (1)若f和g是单射, 则f◦g是单射. (2)若f和g是满射, 则f◦g是满射. (3)若f和g是双射, 则f◦g是双射. Proof (2)任意z  C, 由于g是满射, 存在y  B, 使得z = g(y). 又由于f是满射, 存在x  A, 使得y = f(x). 于是z = g(y) = g(f(x)) = (f◦g)(x). 故f◦g是满射(see below).,Theorem 1-11 (1)若f◦g是单射, 则f是单射, g不一定. (2)若f◦g是满射, 则g是满射, f 不一定. (3)若f◦g是双射, 则f是单射且g是满射. Proof (1)任意x1, x2 A, 若f(x1) = f(x2),,,,,,,,,,,显然, g(f(x1)) = g(f(x2)), 即(f◦g)(x1) = (f◦g)(x2). 由于f◦g是单射, 因此 x1 = x2. 故f是单射. g不一定(见上图)?,,,,,,,,,,,,,,,,,一般来说f◦g  g◦f, 但 Theorem 1-12 作业 习题1.2 4, 7, 12.,1.3 运算的定义及性质,运算是讨论对象之间有何联系的一种方法. 其实，我们已经接触过很多运算,如数之间的加法运算、多项式之间的乘法运算、矩阵的逆运算、向量的线性运算等.在讨论离散数据结构时也会经常遇到各种各样的运算，如在下节即将研究的集合间的运算. 虽然运算本质上是映射，但研究的侧重点不同，在运算中更注重于运算满足的一些运算性质，而根据这些性质可以对一些离散对象分门别类进行讨论. 因此，有必要先把运算的一般定义及其性质进行讨论.,1.3.1 运算的定义 (1)定义 A1, A2,…, An到B的n元运算: A到B(或A上)的n元运算: A上的n元封闭运算(代数运算): 几个例子.,(2)运算符号的选取 (3)运算符号的位置 (4)运算表 A = {a, b, c}, *: 思考 A上封闭的1元运算, 2元运算和3元运算的个数是多少?,1.3.2 运算的性质 (1)对合(involutive)性 Def 1-15 设*是A上的1元代数运算, 例,(2)幂等(idempotent)性 幂等元x: A关于*具有幂等性: A中每个元素对于*都是幂等元. 两个例子:,(3)交换(commutative)性 Def 设*是A上的2元代数运算, 若对于任意的x, y  A, 均有 。