离散数学第5章_第1页
离散数学第5章_第2页
离散数学第5章_第3页
离散数学第5章_第4页
离散数学第5章_第5页
已阅读5页,还剩38页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

第五章 映射与无限集1映射(函数)计算机科学通过研究映射的性质获取描述处理对象的技术.所谓映射,其实是一个集合到另一个集合元素之间所对应关系的一种指定规则.映射也称为函数。由于映射有很多情形,概括的说有四类: ①多对一; ②一对一;③多对多; ④一对多2映射定义一个映射函数f:X→Y是一个满足下列两个条件的关系:1.对每个x∈X,必存在y∈Y,使得(x,y)∈f2.对每个x∈X,仅存在一个y,使(x,y)∈f我们把y称为x在映射f下的象把x称为y的原象3映射表示方法表示映射的方法:1.f:X→Y2.X→Y3.Y=f(x)={f(x)|x∈X}实例

f:N→N,f(x)=2x是从N到N的函数

g:N→N,g(x)=2也是从N到N的函数f4例1X={x1,x2,x3}Y={y1,y2}F1={<x1,y1>,<x2,y2>,<x3,y2>}F2={<x1,y1>,<x1,y2>}F3={<x1,y2>,<x3,y2>}

F1是函数,F2不是函数,F3不是函数5例2R为实数的集合,X=Y=R,并设f={(x,y)|x,y∈R,y=x2}g={(x,y)|x,y∈R,y2=x}f是X到Y的映射g不是映射,违反唯一性6函数相等定义设F,G为函数,则

F=G

F(x)=G(x)

如果两个函数F和G相等,一定满足下面两个条件:

(1)D(F)=D(G)

(2)

x[x∈D(F)∧x∈D(G

)]都有F(x)=G(x)

实例函数

F(x)=(x2

1)/(x+1),G(x)=x

1

不相等,因为x=-1,F(-1)=0,G(-1)=-2.7函数的性质定义设f:A→B,

(1)若R(f)=B,则称f:A→B是满射的.

(2)若任意x1,x2A

而且不相等,都有f(x1)与f(x2)不相等,则称f:A→B是单射的.

(3)若f:A→B既是满射又是单射的,则称f:

A→B是双射的(一一到上的)f

满射意味着:

y

B,都存在x使得

f(x)=y.f单射意味着:f(x1)=f(x2)

x1=x28练习:例4判断下面函数是否为单射,满射,双射的,为什么?

(1)f:R→R,f(x)=

x2+2x

1

(2)f:Z+→R,f(x)=lnx,Z+为正整数集

(3)f:R→Z,f(x)=

x

(4)f:R→R,f(x)=2x+1

(5)f:R+→R+,f(x)=(x2+1)/x,其中R+为正实数集.

9解(1)f:R→R,f(x)=

x2+2x

1

在x=1取得极大值0.既不单射也不满射.

(2)f:Z+→R,f(x)=lnx

单调上升,是单射.但不满射,ranf={ln1,ln2,…}.(3)f:R→Z,f(x)=

x

满射,但不单射,例如f(1.5)=f(1.2)=1.

(4)f:R→R,f(x)=2x+1

满射、单射、双射,因为它是单调的并且ranf=R.

(5)f:R+→R+,f(x)=(x2+1)/x

有极小值f(1)=2.该函数既不单射也不满射.

练习(续)10一一对应定义:集合X和Y间,存在从X到Y上的双射,则称集合X和Y一一对应。集合X和Y一一对应,则:1.X中每个元素在Y中有唯一的象。2.X中不同元素的象各不相同。3.Y中每个元素在X上都有原象。11实例判断从{a,b,c,d}到{1,2,3,4,5}是否一一对应。f为:f(a)=4,f(b)=5,f(c)=1,f(d)=3不是一一对应的关系。虽然是单射,但不是满射。所以不是双射。所以不是一一对应的关系。12映射(函数)的复合对关系而言,有关系的复合;函数是关系,所以函数也是可复合的。已知映射:f:X→Y,和g:Y→Z,由这两个映射可构成新映射:h,记为g◦f,称为f和g的复合映射。h=g◦f=g(f(x)){(x,z)|

x∈X,

z∈Z,

y∈Y,y=f(x),z=g(y)}13映射(函数)的复合例:X={x1,x2,x3},Y={y1,y2},Z={z1,z2}

f:X→Y,g:Y→Z,h=g◦fx1x2x3y1y2z1z2注意g和f的位置14函数复合运算的性质

定理

设f

:A→B,g

:B→C.

(1)如果g,f都是满射的,则

g∘f

:A→C也是满射的.

(2)如果g,f

都是单射的,则g∘f

:A→C也是单射的.

(3)如果g,f

都是双射的,则g∘f

:A→C也是双射的.

15练习:1.下列哪些关系可以构成函数?a.f={(x,y)|x,y∈N,x+y<10}b.f={(x,y)|x,y∈R,x2=y}2.判断下列函数是单射、满射或双射?a.f:N→N,f(x)=x+2;b.f:N→N,f(x)=x(mod2);c.f:N→ρ(N),f(x)={x};不能能单射单射什么都不是16练习:3.已知:f:X→Y,g:Y→Z,h=g∘f,f是满射,h是单射,求证g是单射。17证明3:已知:f:X→Y,g:Y→Z,h=g∘f,f是满射,h是单射.求证g是单射。证:假设g不是单射,1.则存在y1≠y2,而g(y1)=g(y2);2.而f是满射,每个y都一定有对应的x,所以对于y1和y2,必存在y1=f(x1),y2=f(x2)3.y1≠y2所以f(x1)≠f(x2),所以x1≠x2;4.h(x1)=g(f(x1))=g(y1)h(x2)=g(f(x2))=g(y2)所以h(x1)=h(x2)对于不同的x,h函数具有相同值,显然就不是单射了,与已知条件矛盾!所以原假设不成立!18逆函数(反函数)对关系R来说,都存在逆关系;但是对映射(函数)来说,不一定存在逆函数!需要依据一定的条件来判断!19反函数存在的条件任给函数F,它的逆F

1不一定是函数,是二元关系.实例:F={<a,b>,<c,b>},F

1={<b,a>,<b,c>}判断函数F的逆函数是否存在,则转而判断F是否是双射函数。如果F是双射函数,则存在逆函数。否则,不存在逆函数!20反函数的性质定理

设f:A→B是双射的,则f

1:B→A也是双射函数.

证因为f是函数,所以f

1是关系,且

domf

1=ranf=B,ranf

1=domf

=A,

对于任意的y∈B=domf

1,假设有x1,x2∈A使得

<y,x1>∈f

1∧<y,x2>∈f

1成立,则由逆的定义有

<x1,y>∈f∧<x2,y>∈f根据f的单射性可得x1=x2,从而证明了f

1是函数,且是满射的.下面证明f

1

的单射性.

若存在y1,y2∈B使得f

1(y1)=f

1(y2)=x,从而有

<y1,x>∈f

1∧<y2,x>∈f

1

<x,y1>∈f∧<x,y2>∈f

y1=y2

21反函数的性质定理

设f:A→B是双射的,则

f

1∘f=IA,f∘f

1=IB

对于双射函数f:A→A,有

f

1∘f=f∘f

1=IA

22例题:构造下列函数的反函数:1.f(x)=sinx2.f(x)=x2,x∈(-∞,0)3.A={1,2,3},B={a,b,c},f:A→B,f={(1,a),(2,c),(3,b)}23例题(续):1.f(x)=sinx

f-1(x)=arcsinx2.f(x)=x2,x∈(-∞,0)

f-1(x)=-x1/23.A={1,2,3},B={a,b,c},f:A→B,f={(1,a),(2,c),(3,b)}f-1={(a,1),(c,2),(b,3)}24函数复合与反函数的计算例设f:R→R,g:R→R

求f

g,g

f.如果f和g存在反函数,求出它们的反函数.

f:R→R不是双射的,不存在反函数.g:R→R是双射的,它的反函数是g

1:R→R,g

1(x)=x

225由映射产生的等价关系定义: 设X,Y两个集合,f是X到Y上的映射。若X中有2个元素x1和x2,f(x1)=f(x2),则x1和x2具有关系R,记为x1Rx2

。现在检验关系R是否是等价关系:1)对于X中任意x,f(x)=f(x).自反性成立。2)若f(x1)=f(x2),则f(x2)=f(x1),对称性。3)若f(x1)=f(x2),f(x2)=f(x3),则f(x1)=f(x3),满足传递性。所以是一种等价关系!26由映射产生的等价关系因此,可以划分出集合的等价类。集合X的等价类为:[x]={s|f(s)=f(x)}——具有相同y值的自变量构成一个等价类。所以X的商集X/E={[x],[y],[z],…}[x][y]ab27由映射产生的等价关系例题:设S是由一群学生所组成的集合。对这群学生检查发育情况,分为三个等级:优、良、差。集合X={优,良,差}映射表示检查状态。对于集合S中,如果学生x1,x2,f(x1)=f(x2),则说明两个学生发育状态一样。他们位于同一个等价类中。28规范映射设R是集合X到集合Y上的映射f产生的等价关系,映射g:X→X/R则是从集合X到商集X/R的规范映射。构造规范映射的准则:g(x)=[x]29规范映射例:集合X={a,b,c,d},集合Y={0,1,2,3,4},映射f:X→Y是:f(a)=1,f(b)=0,f(c)=1,f(d)=31)由f产生的等价关系R为:

R={(a,a),(b,b),(c,c),(d,d),(a,c),(c,a)}2)对应等价类:[a]={a,c},[b]={b},[d]={d}3)商集:{[a],[b],[d]}4)规范映射g:g:X→X/Rg(a)=[a],g(c)=[a],g(b)=[b],g(d)=[d]30练习:已知x={a,b,c},Y={1,2,3,4}f:X→Y如图所示,试构造函数g:Y→X,使得g·f=Ixabc1234g={(1,a),(2,c),(3,b),(4,a)}315-2无限集可用1-1对应法则讨论无限集的势1638,Galilo(意)指出:对于每个自然数,都有且只有一个平方数与之对应1,2,3,4,……,,……1,4,9,16,……,,……类似地,自然数与奇数、与偶数、与整数之间均可1-1对应,因而等势

32等势定义:当且仅当集合A的元素和集合B的元素之间一一对应。集合A和B就是等势的,记为A~B。例如:f(n)=2n,n为自然数。则自然数和偶数之间可以建立一一对应的关系。所以自然数和偶数之间就是等势的。33等势所以,如果A,B是任意集合1.如果存在A到B的双射,则A,B等势。|A|=|B|2.如果存在A到B的单射,|A|≤|B|。3.如果存在A到B的单射,但不存在双射函数,|A|<|B|。34集合的势势是衡量集合大小的一个量对于有限集,可有两种方法知道集合的大小“数数”——一个一个地数。个数即势(也称基数)与已知集合比较——1-1对应的方法35Hilbert旅馆一旅店有无穷多个房间,各房间编号依次为

#1,#2,#3,……现所有房间已住满了人。这时来了一位新客人要求住店。怎么安排?

店主人把#1房的客人移到#2房,把#2房的客人移到#3房,依此类推,新客人就住进了已腾空的#1房间

接着,又来了第二位新客人,旅店主也照此办理,使第二位客人得到落实

紧接着,来了一个有无限多个游客的旅游团要求定住房间,怎么办

36店主人把#1房的客人移到#2房,把#2房的客人移到#4房,#3房的客人移到#6房,等等,所有奇数号的房间全部腾空了,新的无限多个客人就全住进了旅店

紧接着发生了更为严重

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论