离散数学--函数.ppt

《离散数学--函数.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章函数1主要内容6.1函数的概念6.2复合函数与逆函数6.3基数的概念6.4基数的比较26.1函数的概念定义6.1.1函数一种特殊的关系亦称映射或变换设A和B是非空集合,f是一个从A到B的关系，如果对于每一个a∈A，均存在唯一的b∈B，使得∈f，则称关系f是由A到B的一个函数。记作f:A→B。特殊地，当A=B时，称f是A上的函数∈f通常记作f(x)=y3例：判断以下关系是否为函数4例例6.1.3设E是全集，AE，那么A的特征函数ΧA是E到{0,1}的函数：a∈E，例设E=

2、｛a,b,c,d｝,A=｛b,d｝ΧA:E→｛0,1｝ΧA={,,,}5设A和B是全集E的任意两个子集,对所有x∈E,下列关系式成立x(ΧA(x)=0)A=Φx(ΧA(x)=1)A=Ex(ΧA(x)≤ΧB(x))ABx(ΧA(x)=ΧB(x))A=BΧ~A(x)=1－ΧA(x)ΧA∩B(x)=ΧA(x)ΧB(x)ΧA∪B(x)=ΧA(x)+ΧB(x)－ΧA∩B(x)ΧA－B(x)=ΧA∩~B(x)=ΧA(x)－ΧA∩B(x)6函数的定义域和值域

3、设f:X→YX——f的前域(定义域domf)Y——f的陪域(值域ranfY)f(x)=yx——函数的自变元y——自变元x的函数值，也称为x的像domf=Xranf=f(X)如果f(x)=y1和f(x)=y2,那么y1=y27设f:X→YX’Xf(X’)={y

4、∃x(x∈X’∧f(x)=y)}⊆Y称f(X’)为X’的象称X’为f(X’)的原象例f:N→N,f(x)=2x.A’=N偶={0,2,4,6,…}={2k

5、k∈N},f(A’)={0,4,8,12,…}={4k

6、k∈N}B’={2+4k

7、k∈

8、N}={2,6,10,14,…},B’的原象={1+2k

9、k∈N}={1,3,5,7,…}=N奇象(image)与原象(preimage)8例假定f:｛a,b,c,d｝→｛1,2,3,4｝f(｛a｝)=｛1｝;f(｛a,b｝)=｛1,3｝;f(｛a,b,c｝)=｛1,3｝;ranf=f(｛a,b,c,d｝)=｛1,3,4｝;9定义6.1.2设f:X→Y,g:W→Z,如果X=W,Y=Z,且对每一x∈X有f(x)=g(x)则称f=g.函数相等的定义和关系相等的定义一致必须有相同的前域与陪域和相等的序偶集合

10、例f:I→I,f(x)=x2g:｛1,2,3｝→I,g(x)=x2是两个不同的函数10通常用BA表示从集合A到集合B的所有函数的集合,读作B上ABA={f

11、f:A→B}设｜A｜=m,｜B｜=n，共有多少个A到B的函数？｜BA｜=nm例：设A＝{a,b,c}，B＝{0,1}。则共有８个A到B的函数(它们分别是A的８个子集的特征函数)，它们是f1＝{,,}f2＝{,,}f3＝{,,}f4＝{,,<

12、c,1>}f5＝{,,}f6＝{,,}f7＝{,,}f8＝{,,}11函数是特殊的关系，故也可用关系图或关系矩阵来表示函数例：集合A＝{1,2,3,4}上的函数f＝{<1,2>,<2,3>,<3,4>,<4,1>}12特殊函数类满射、入射和双射定义6.1.3设f是从X到Y的函数如果x≠x’蕴含着f(x)≠f(x’)(即f(x)=f(x’),那么x=x’),那么f是入射(injecti

13、on,单射，一对一的，1-1)如果f(X)=Y,那么f是满射(surjection,映上的,onto)如果f既是满射又是入射,那么f是双射(bijection,1-1,onto)双射常称作一一对应，又称集合同构(setisomorphism)13例6.1.9设A和B是两个集合，若存在b∈B使得对任意a∈A皆有f(a)＝b，则称f是常函数一般说来，常函数不是入射，也不是满射(除非B是一个一元集合)。例6.1.10设R是一集合X上的等价关系,函数g:X→X／R,g(x)=［x］R叫做从X到商集X／R的规范

14、映射.例设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)=3f诱导的X上的等价关系R有等价类｛a,c｝,｛b｝，｛d｝从X到X／R的规范映射g:｛a,b,c,d｝→｛｛a,c｝,｛b｝,｛d｝｝g(a)=｛a,c｝,g(b)=｛b｝g(c)=｛a,c｝,g(d)=｛d}14定理6.1.1若f是Ａ到Ｂ的函数，其中Ａ和Ｂ都是非空有限集，且#Ａ＝#Ｂ，那么：f是一个入射ifff是一个满射。证明