第1章 集合映射与运算精选文档.ppt

《第1章 集合映射与运算精选文档.ppt》由会员分享，可在线阅读，更多相关《第1章 集合映射与运算精选文档.ppt（87页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第1章 集合映射与运算本讲稿第一页，共八十七页n n离散数学是计算机各专业的专业基础课.n n离散数学研究的对象:离散量及其之间的关系.离散量与连续量及其之间的转换离散量与连续量及其之间的转换.现今计算机的处理对象是非常特殊的离散量现今计算机的处理对象是非常特殊的离散量:0:0和和1.1.n n学习离散数学的目的:n n1.培养各种能力.n n2.为后继专业课程的学习作知识上的准备.本讲稿第二页，共八十七页n n离散数学的基本内容离散数学的基本内容:n n1.1.集合与关系集合与关系 Chapter 1 Chapter 1 集合、映射与运算集合、映射与运算 Chapter 2 Chapter

2、2 关系关系n n2.2.数理逻辑数理逻辑 Chapter 3 Chapter 3 命题逻辑命题逻辑 Chapter 4 Chapter 4 谓词逻辑谓词逻辑n n3.3.代数结构代数结构 Chapter 5 Chapter 5 群、环和域群、环和域 Chapter 6 Chapter 6 格与布尔代数格与布尔代数n n4.4.图论图论 Chapter 7 Chapter 7 图论图论 Chapter 8 Chapter 8 几类特殊的图几类特殊的图本讲稿第三页，共八十七页n n学习离散数学的方法:1.1.预习预习.2.2.听课听课.3.3.复习复习.4.4.作业作业.n n参考文献:耿素云耿

3、素云 屈婉玲屈婉玲,离散数学离散数学(修订版修订版),),高等教育出高等教育出版社版社,2004.,2004.Kenneth H.Rosen,Discrete Mathematics and Kenneth H.Rosen,Discrete Mathematics and Its Applications(Fourth Edition),McGraw-Hill Its Applications(Fourth Edition),McGraw-Hill Companies,Inc.1998.(Companies,Inc.1998.(有中译本有中译本,2002),2002)本讲稿第四页，共八十七页C

4、hapter 1 Sets,Mappings and Operationsn n集合是现代数学的集合是现代数学的最最基本概念基本概念(?).(?).n n映射又称为函数映射又称为函数,它它是现代数学的基本概念是现代数学的基本概念,可以借助可以借助于集合下定义于集合下定义.n n运算本质上是映射运算本质上是映射,但但其研究有其特殊性其研究有其特殊性.n n集合、映射、运算及关系集合、映射、运算及关系(Chapter 2)(Chapter 2)是贯穿于本书的一是贯穿于本书的一条主线条主线.本讲稿第五页，共八十七页1.1 集合的有关概念集合的有关概念n n1.1.集合集合n n集合集合(用处用处?)

5、?)已渗透到自然科学以及社会科学的各个已渗透到自然科学以及社会科学的各个研究领域研究领域,在在信息的表示及处理中信息的表示及处理中,可以借助于集合可以借助于集合去实现数据的删节、插入、排序以及描述数据间的关去实现数据的删节、插入、排序以及描述数据间的关系系.n n在一定范围内在一定范围内,集合集合(set)(set)是其具有某种特定性质的对是其具有某种特定性质的对象汇集成的一个整体象汇集成的一个整体,其中的每一个对象都称为该其中的每一个对象都称为该集合的元素集合的元素(element).(element).n n这里所指范围是全集这里所指范围是全集U U(见图见图1-1).(1-1).(避免悖

6、论避免悖论!)!)n n在数学中常用在数学中常用 表示整体表示整体.若若x x是集合是集合A A中元素中元素,则记则记x x A A,否则否则x x A A.本讲稿第六页，共八十七页n n常见的数的集合用黑正体字母表示:N是自然数集合,包括数0；Z是整数集合；Q是有理数集合；R是实数集合；C是复数集合.n n表示集合的常用方法:n n(1)列举法:0,2,4,6,8,N=0,1,2,3,.n n(2)描述法:x|x满足的条件.n n(3)递归法 自然数集合自然数集合N N可递归定义可递归定义,在后面章节定义命题公在后面章节定义命题公式及谓词公式时还会用此法式及谓词公式时还会用此法.n n有限集

7、合A的元素个数|A|.本讲稿第七页，共八十七页n nRemarks n n1.集合中的元素可以是集合,例如A=a,a,b,b,c.n na,bA,a,bA.n n2.集合之间的元素原则上是没有次序的,如 A=a,a,b,b,c就是 a,b,c,a,b;n n3.集合中的元素原则上不重复,如a,a,b,b,b,c还是集合A.n n不含有任意元素的集合称为空集不含有任意元素的集合称为空集(empty set),(empty set),记为记为或或.本讲稿第八页，共八十七页n n2.子集n nA B,特别地是任意集合的子集.n nA=B.n nTheorem 1-2(P3)n n(1)A A.n n

8、(2)A B,B A A=B.n n(3)A B,B C A C.n nTheorem 1-3 A=B A B 且 B A.本讲稿第九页，共八十七页n n注意 与 的不同.n n例1-2 由A B,B C可否得出A C?n nSolution 不成立,例如A=a,b,B=a,b,c,C=a,a,b,c.n n课堂练习:4,5.n n3.幂集(power set)n nX=a,b P(X)=,a,b,a,b.n nP(P()=P()=,(P5,6(1).n n,(P5,2)本讲稿第十页，共八十七页n nTheorem 1-4 n nProof n n由乘法原理证明?本讲稿第十一页，共八十七页n

9、n4.n元组n nDef 1-4 将n个元素(?)x1,x2,xn按一定顺序排列就得到一个n元(有序)组(n-tuple).n n在数据结构中就是一个线性表.本讲稿第十二页，共八十七页n n n=2:(x,y).n=3:(x,y,z)n n4元组?n n显然,一般说来(x,y)(y,x).n n注意区别(a,b,c),(a,b),c),(a,(b,c)的不同.本讲稿第十三页，共八十七页n nn维向量是n元组,长度为n的线性表是n元组,抽象数据结构Data_Structure=(D,S)本身是一个2 元组.n n2元组常称为有序对(ordered pair)或序偶.n n5.笛卡儿积(cross

10、 product)本讲稿第十四页，共八十七页n n例1-4(P4)设A=a,b,B=1,2,C=,求AB,BA,BC,ABC.n nSolution BC=(1,),(2,)A A B B C=(=(a a,1,1,),(),(b b,1,1,),(),(a a,2,2,),(),(b b,2,2,).).本讲稿第十五页，共八十七页n nRemark A=A =.n nP5,10?n nTheorem n nHint n n可推广到更多个集合的笛卡儿积的情形:n n作业 习题1.1 6,9,10.本讲稿第十六页，共八十七页1.2 1.2 映射的有关概念映射的有关概念n n1.映射的定义n n映

11、射mapping=函数function.n nC语言是一种函数型语言:从main开始.n nDefAB本讲稿第十七页，共八十七页n n函数的表示:(1)(1)解析式解析式 (2)(2)图形图形(3)(3)表格表格(数值计算中出现较多数值计算中出现较多)n n函数符号的选取(P6):f,g,F,G,sin,exp,main,add,average,n n注意区别函数f与函数表达式f(x).n n映射的两个特点:(1)(1)全函数全函数;(2)(2)唯一性唯一性.本讲稿第十八页，共八十七页n nB上A:n n例1-5 n nTheorem 1-6 n n注意B上A的记号与该结论的关系.x1x2x3

12、y1y2本讲稿第十九页，共八十七页n n 像与原像Xf(X)Y f-1(Y)本讲稿第二十页，共八十七页n nn元函数(n 1):n nfloat average(float array,int n)本讲稿第二十一页，共八十七页n n2.映射的性质n n(1)单射(injection)本讲稿第二十二页，共八十七页n n(2)满射(surjection)n n例1-7 是Z到N的满射,但不是Z到Z的满射(?).本讲稿第二十三页，共八十七页n n(3)双射(bijection,one-to-one correspondence)(bijection,one-to-one correspondence

13、)n n双射又称为一一对应:既单又满.n n例1-8n n例1-9(P8)本讲稿第二十四页，共八十七页n n例1-10n nDef 1-11 有限集合A上自身的双射称为A上的置换(permutation).n nA=1,2,3,4上的所有置换有多少个?n n4!123123本讲稿第二十五页，共八十七页n n3.逆映射n n设f:AB,将对应关系f逆转(改变方向),一般来说,不能得到B到A的映射:abc123本讲稿第二十六页，共八十七页n nDef 1-12 设f:AB,若将对应关系f逆转后能得出一个得到B到A的映射,则称该映射为f的逆映射(invertible function),记为f-1.

14、abc123本讲稿第二十七页，共八十七页n nTheorem 1-7 f 的逆映射存在的充要条件是f是双射.n n对于y=sin x,当 时,有反函数,常记为n n当 时,y=sin x仍有反函数,但不能 记为arcsin.显然,当 时,无反函数.本讲稿第二十八页，共八十七页n n4.复合映射(composition function)n nTheorem1-8 设f:A B,g:B C:n n则h:A C.xy=f(x)z=g(y)=g(f(x)本讲稿第二十九页，共八十七页n nDef 1-13 n n例1-12abc123本讲稿第三十页，共八十七页n nRemarksn n(1)y=sin

15、 u,u=x2n n未引入运算符号,有时是不方便的.n n(2)顺序问题:n n有些专业书n n但会出现一些混乱.本讲稿第三十一页，共八十七页n n例1-13(P9)f:RR,f(x)=x2,n ng:RR,g(x)=x+2,求fg和gf.n nSolution x R:n n(fg)(x)=g(f(x)=g(x2)=x2+2.n n(gf)(x)=f(g(x)=f(x+2)=(x+2)2.n nRemark fg gf.本讲稿第三十二页，共八十七页n nIA:A An nTheorem 1-9n n理解:abc123abc123abc123本讲稿第三十三页，共八十七页n nTheorem 1

16、-10n n(1)若f和g是单射,则fg是单射.n n(2)若f和g是满射,则fg是满射.n n(3)若f和g是双射,则fg是双射.n 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).本讲稿第三十四页，共八十七页n nTheorem 1-11n n(1)若fg是单射,则f是单射,g不一定.n n(2)若fg是满射,则g是满射,f 不一定.n n(3)若fg是双射,则f是单射且g是满射.n nProof(1)任意x1,x2 A,若f(x1)=

17、f(x2),本讲稿第三十五页，共八十七页n n显然,g(f(x1)=g(f(x2),即(fg)(x1)=(fg)(x2).由于fg是单射,因此 x1=x2.故f是单射.n ng不一定(见上图)?本讲稿第三十六页，共八十七页n n一般来说fg gf,但n nTheorem 1-12n n作业 习题1.2:3,4,7,8,12.n nHint n n7.使用定理1-10和第3题.n n8.使用第7题结论.n n12.使用第7题结论.本讲稿第三十七页，共八十七页1.3 运算的定义及性质运算的定义及性质 n n运算是讨论对象之间有何联系的一种方法运算是讨论对象之间有何联系的一种方法.其实，我其实，我们

18、已经接触过很多运算们已经接触过很多运算,如数之间的加法运算、多项式如数之间的加法运算、多项式之间的乘法运算、矩阵的逆运算、向量的线性运算等之间的乘法运算、矩阵的逆运算、向量的线性运算等.在在讨论离散数据结构时也会经常遇到各种各样的运算，如在讨论离散数据结构时也会经常遇到各种各样的运算，如在下节即将研究的集合间的运算下节即将研究的集合间的运算.n n虽然运算本质上是映射，但研究的侧重点不同，在运算中虽然运算本质上是映射，但研究的侧重点不同，在运算中更注重于运算满足的一些运算性质，而根据这些性质可以更注重于运算满足的一些运算性质，而根据这些性质可以对一些离散对象分门别类进行讨论对一些离散对象分门别

19、类进行讨论.n n因此，有必要先把运算的一般定义及其性质进行讨论因此，有必要先把运算的一般定义及其性质进行讨论.本讲稿第三十八页，共八十七页n n1.运算的定义n n(1)定义 A1,A2,An到B的n元运算(n-ary operation):A A到到B B(或或A A上上)的的n n元运算元运算:A A上的上的n n元封闭运算元封闭运算(代数运算代数运算):):本讲稿第三十九页，共八十七页n n例1-14 f:Z N,f(x)=|x|.n n例1-15 f:Z N,f(x)=x(mod k),n n x=qk+r,0 r 1.n nProof(?)本讲稿第七十七页，共八十七页n n2.集合

20、的覆盖n nDef 设A是集合,由A的若干非空子集构成的集合称为A的覆盖(covering),如果这些非空子集的并等于A.n na,b,b,c本讲稿第七十八页，共八十七页n n集合的划分 集合的覆盖,但反过来不成立.n nA=a,b,c上所有不同的覆盖有哪些?n n作业 习题1.5 1,4,7.本讲稿第七十九页，共八十七页1.6 集合的对等集合的对等n n集合的对等,它是集合间的另一种关系.通过集合对等以及相关内容的学习,加深对函数概念的理解,提高正确使用函数工具作为研究手段的能力.n n1.集合对等(equivalent)n nDef A B:存在双射f:A B.本讲稿第八十页，共八十七页n

21、 nN E.n nZN?n n(0,1)R.n nN N N.n nTheorem 1-28(对等的性质)n n(1)A A.n n(2)A B B A.n n(3)A B,B C A C.本讲稿第八十一页，共八十七页n n2.无限集合n n有了集合对等的概念,就可以给出无限集合及有限集合的严格定义.n nDef 设A是集合,若存在A的一个子集与自然数集合N对等,则称A为无限集合(infinite set),否则称A为有限集合(finite set).n nN.n n0,1.本讲稿第八十二页，共八十七页n n3.集合的基数n n有限集合的基数就是的元素个数.借助于集合对等概念,可以将其扩展到无

22、限集合.n nDef 若集合A和B对等,则称这两个集合的基数(cardinality)相同.n n|A|.本讲稿第八十三页，共八十七页n n4.可列集合n nDef 能与自然数集合N对等的集合称为可列集合(countable set).n n根据无限集合的定义知：任意无限集合均存在一个可列的子集合.根据这一点,可以证明无限集合的特征性质.n nTheorem 设A是无限集合,则存在A的一个真子集B,使得 A B.本讲稿第八十四页，共八十七页n nProof 因为A是无限集合,存在可列的子集合n n考虑n nQ是可列集合.本讲稿第八十五页，共八十七页n n5.不可列集合n n是否所有无限集合都是可列的?答案是否定的.n n例 证明:(0,1)是不可列集合.n nProof(反证)n n取本讲稿第八十六页，共八十七页n n6.基数的比较n nDef 给定集合A和B,若存在A到B的单射,则称A的基数小于等于B的基数,记为|A|B|.若进一步,不存在A到B的双射,则称A的基数小于B的基数,记为|A|B|.n n由定义易知,若存在B到A的满射,则|B|A|.n n显然,n nProblem 是否存在集合A,满足n n(著名的连续统假设?!)n n作业 习题1.6 2,4,6.本讲稿第八十七页，共八十七页