离散数学第5章

第五章 映射与无限集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房，等等，所有奇数号的房间全部腾空了，新的无限多个客人就全住进了旅店

紧接着发生了更为严重