离散数学 4.2复合函数与逆函数.ppt

《离散数学 4.2复合函数与逆函数.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、复习定义4-1.1设X，Y为任何两个集合，如果f为X到Y的关系（fXY），且对每一xX，都有唯一的yY，使f。则称f是X到Y的函数（functions），记为f：X→Y，当X=X1…Xn时，称f为n元函数。函数也称映射（mapping）或变换(transformation）。若f，则x称为自变元，y称为在f作用下x的象，f记作y=f(x)。由所有xX的象构成的象集合称为函数的值域ranf，即ranf=f(X)={f(x)

2、xX}Y前域（定义域）domX，值域(象集合)ranf，陪域（共域）Y由函数的定义可知，函数是特殊的关系，特殊点有以

3、下两点：（1）函数的定义域是X，而不是X的真子集。即任意xX都有象yY存在（象存在性）。（2）一个x只能对应唯一的一个y（象唯一性）。函数的定义式还可以写成：f={

4、xX∧yY∧f(x)=y}定义4-1.2设函数f:A→B，g:C→D，如果A=C，B=D，且对所有xA和xC，都有f(x)=g(x)，则称函数f等于函数g,记为f=g。如果AC，B＝D，且对每一xA，f(x)＝g(x)。则称函数f包含于函数g，记为fg。因为函数是序偶的集合，故两个函数相等可用集合相等的概念予以定义。设X和Y都为有限集，分别有m个和n个不同元素，由于从X到Y任意一个函数的定义域是X，

5、在这些函数中每一个恰有m个序偶。另外任何元素xX，可以有Y的n个元素中任何一个作为它的象，故共有nm个不同的函数。在上例中n=2,m=3,故应有23个不同的函数。今后我们用符号YX表示从X到Y的所有函数的集合，甚至当X和Y是无限集时，也用这个符号。Y中的每一元素都有原象几类特殊情况：设f：X→Y，如果对任意yY，均有xX，使y=f(x)，即ranf=Y，则称f为X到Y的满射函数(surjection)，满射函数也称到上映射。定义4-1.3对于f：X→Y的映射中，如果ranf=Y，即Y的每一个元素是X中一个或多个元素的象点，则称这个映射为满射（或到上映射）。Y中元素若有原象则原象唯一定

6、义4-1.4从X到Y的映射中，X中没有两个元素有相同的象，则称这个映射为入射（或一对一映射）。设f：X→Y，如果对任意x1，x2X,x1x2蕴涵f(x1)f(x2)。则称f为X到Y的单射函数(injection)，单射函数也称一对一的函数或入射函数。Y中的每一元素都有原象且原象唯一定义4-1.5如果f既是X到Y的单射，又是X到Y的满射，则称f为X到Y的双射函数（bejection）。双射函数也称一一对应。151页(6)设A和B是有穷集合,有多少不同入射函数和多少不同的双射函数?解设

7、A

8、=m，

9、B

10、=n，要使映射f：A→B为入射，必须有

11、A

12、≤

13、B

14、，即m≤n。在B中任意选出m个元素

15、的任一全排列，就能形成的一个不同的入射，故的不同入射共有：设A={a1,a2,…,am}，B=={b1,b2,…,bm}，则对a1对应的元素共有m种取法，a2对应的元素共有m-1种取法，……am-1对应的元素共有2种取法，am对应的元素共有1种取法。故f：A→B的不同双射共有m(m-1)(m-2)…2·1=m!（个）（个）要使映射f：A→B为双射，必须

16、A

17、=

18、B

19、。定理4-2.1设f:X→Y是一个双射函数，那么fc为Y到X的双射函数，即有fc:Y→X。证明：a).先证fc是一个函数（需要证存在性和唯一性）设f={

20、xX∧yY∧f(x)=y}和fc={

21、

22、f}因f是双射，所以f是满射，即所有的yY都有x与它对应，这正是fc的存在性。又因f是双射，所以f是入射，即所有的yY都只有唯一的x与它对应，这正是fc的唯一性。b).二证fc是一个满射又因ranfc=domf=X,fc是满射。c).三证fc是一个单射反设若y1≠y2,有fc(y1)=fc(y2)因为fc(y1)=x1,fc(y2)=x2,得x1=x2，故f(x1)=f(x2)，即y1=f(x1)=f(x2)=y2。得出矛盾，假设不成立。定义4-2.1设f:X→Y是一个双射函数，称Y→X的双射函数fC为f的逆函数，记为f-1。与复合关系的记法正好相反定义4-2.2设函数f:X→Y,g:

23、W→Z,若f(X)W，则gf={

24、xX∧zZ∧(y)(yY∧y=f(x)∧z=g(y))},称g在函数f的左边可复合。定理4-2.2设两个函数的复合是一个函数。证明：设g:W→Z,f:X→Y为左复合,即f(X)W，a).先证象存在性对于任意xX,因为f为函数，故必有唯一的序偶使y=f(x)成立。而f(x)f(X)，即f(x)W，又因为g是函数，故必有唯一的序偶使z=g(y