离散数学--5.1-2函数

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

1、第5章函数1第5章函数5.1函数定义及其性质5.2函数的复合与反函数25.1函数定义及其性质5.1.1函数的定义函数定义从A到B的函数5.1.2函数的像与完全原像5.1.3函数的性质函数的单射、满射、双射性构造双射函数3函数定义定义5.1设f为二元关系,若x∈domf都存在唯一的y∈ranf使xfy成立,则称f为函数.对于函数f,如果有xfy,则记作y=f(x),并称y为f在x的值.例如f1={,,}f2={,}f1是函数,f2不是函数4函数相等定义5.2设f,g为函数

2、,则f=gfg∧gf如果两个函数f和g相等,一定满足下面两个条件：(1)domf=domg(2)x∈domf=domg都有f(x)=g(x)实例函数f(x)=(x21)/(x+1),g(x)=x1不相等,因为domfdomg.5从A到B的函数定义5.3设A,B为集合,如果(1)f为函数(2)domf=A(3)ranfB,则称f为从A到B的函数,记作f:A→B.实例f:N→N,f(x)=2x是从N到N的函数g:N→N,g(x)=2也是从N到N的函数6B上A定义5.4所有从A到B的函数的集合记作BA,读作“B上A”符号化表示为

3、BA={f

4、f:A→B}计数：

5、A

6、=m,

7、B

8、=n,且m,n>0,

9、BA

10、=nm.A=,则BA=B={}.A≠且B=,则BA=A=.7实例解BA={f0,f1,…,f7},其中f0={<1,a>,<2,a>,<3,a>}f1={<1,a>,<2,a>,<3,b>}f2={<1,a>,<2,b>,<3,a>}f3={<1,a>,<2,b>,<3,b>}f4={<1,b>,<2,a>,<3,a>}f5={<1,b>,<2,a>,<3,b>}f6={<1,b>,<2,b>,<3,a

11、>}f7={<1,b>,<2,b>,<3,b>}例1设A={1,2,3},B={a,b},求BA.8重要函数的定义定义5.5(1)设f：A→B,如果存在c∈B使得对所有的x∈A都有f(x)=c,则称f:A→B是常函数.(2)称A上的恒等关系IA为A上的恒等函数,对所有的x∈A都有IA(x)=x.(3)设,为偏序集，f:A→B，如果对任意的x1,x2∈A,x1≺x2,就有f(x1)≼f(x2),则称f为单调递增的；如果对任意的x1,x2∈A,x1≺x2,就有f(x1)≺f(x2),则称f为严格单调递增的.类似的也可以定义单调

12、递减和严格单调递减的函数.9重要函数的定义(续)(4)设A为集合,对于任意的A’A,A’的特征函数A’:A→{0,1}定义为实例：设A={a,b,c},A的每一个子集A'都对应于一个特征函数,不同的子集对应于不同的特征函数.如={,,}，{a,b}={,,}.10(5)设R是A上的等价关系,令g:A→A/Rg(a)=[a],a∈A称g是从A到商集A/R的自然映射.重要函数的定义(续)11实例给定集合A和A上的等价关系R,就可以确定一个自然映射g:A→A/R.不同的等价

13、关系确定不同的自然映射,其中恒等关系所确定的自然映射是双射,而其他的自然映射一般来说只是满射.例如：A={1,2,3},等价关系:R1={<1,2>,<2,1>}∪IA自然映射：g1(1)=g1(2)={1,2},g1(3)={3}等价关系：IA自然映射：g2(1)={1},g2(2)={2},g2(3)={3}12重要函数的定义(续)W:Z+Z+作为算法的时间复杂度函数W(n)的含义：对于规模为n的输入，该算法在最坏情况下所执行的基本运算次数是W(n).复杂度函数f(n)的阶的表示：f(n)=O(g(n))f(n)的阶不超过g(n)的阶f(n)=

14、(g(n))f(n)=O(g(n))且g(n)=O(f(n))例如:f(n)=n2+n=(n2),g(n)=nlogn=O(n2)其中logn是log2n的简写算法：二分搜索W(n)=O(logn)归并排序W(n)=O(nlogn)13函数的像与完全原像定义5.6设函数f:A→B,A1A,B1B,称f(A1)={f(x)

15、x∈A1}为A1在f下的像，f(A)称为函数的像.f1(B1)={x

16、x∈A∧f(x)∈B1}为B1在f下的完全原像注意:函数的像与值的区别：函数值f(x)∈B,像f(A1)B.A1f1(f(A1))，f(f1(B

17、1))B1.实例{1}{1,2}=f1({a})=f1(f({1}))f(f1({b