2019年離散數(shù)學(xué)512函數(shù)課件.ppt

《2019年離散數(shù)學(xué)512函數(shù)課件.ppt》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第5章函數(shù)1課件第5章函數(shù)5.1函數(shù)定義及其性質(zhì)5.2函數(shù)的復(fù)合與反函數(shù)2課件5.1函數(shù)定義及其性質(zhì)5.1.1函數(shù)的定義函數(shù)定義從A到B的函數(shù)5.1.2函數(shù)的像與完全原像5.1.3函數(shù)的性質(zhì)函數(shù)的單射、滿射、雙射性構(gòu)造雙射函數(shù)3課件函數(shù)定義定義5.1設(shè)f為二元關(guān)系,若?x∈domf都存在唯一的y∈ranf使xfy成立,則稱f為函數(shù).對于函數(shù)f,如果有xfy,則記作y=f(x),并稱y為f在x的值.例如f1={,,}f2={,}f1是函數(shù),f2不是函數(shù)4課件函數(shù)相等定義5.2設(shè)f

2、,g為函數(shù),則f=g?f?g∧g?f如果兩個(gè)函數(shù)f和g相等,一定滿足下面兩個(gè)條件：(1)domf=domg(2)?x∈domf=domg都有f(x)=g(x)實(shí)例函數(shù)f(x)=(x2?1)/(x+1),g(x)=x?1不相等,因?yàn)閐omf?domg.5課件從A到B的函數(shù)定義5.3設(shè)A,B為集合,如果(1)f為函數(shù)(2)domf=A(3)ranf?B,則稱f為從A到B的函數(shù),記作f:A→B.實(shí)例f:N→N,f(x)=2x是從N到N的函數(shù)g:N→N,g(x)=2也是從N到N的函數(shù)6課件B上A定義5.4所有從A到B的函數(shù)的集合記作BA,讀作“B上A”符號化

3、表示為BA={f

4、f:A→B}計(jì)數(shù)：

5、A

6、=m,

7、B

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

9、BA

10、=nm.A=?,則BA=B?={?}.A≠?且B=?,則BA=?A=?.7課件實(shí)例解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>

11、,<3,a>}f7={<1,b>,<2,b>,<3,b>}例1設(shè)A={1,2,3},B={a,b},求BA.8課件重要函數(shù)的定義定義5.5(1)設(shè)f：A→B,如果存在c∈B使得對所有的x∈A都有f(x)=c,則稱f:A→B是常函數(shù).(2)稱A上的恒等關(guān)系IA為A上的恒等函數(shù),對所有的x∈A都有IA(x)=x.(3)設(shè),為偏序集，f:A→B，如果對任意的x1,x2∈A,x1?x2,就有f(x1)?f(x2),則稱f為單調(diào)遞增的；如果對任意的x1,x2∈A,x1?x2,就有f(x1)?f(x2),則稱f為嚴(yán)格單調(diào)遞增的.類似的也可以

12、定義單調(diào)遞減和嚴(yán)格單調(diào)遞減的函數(shù).9課件重要函數(shù)的定義(續(xù))(4)設(shè)A為集合,對于任意的A’?A,A’的特征函數(shù)?A’:A→{0,1}定義為實(shí)例：設(shè)A={a,b,c},A的每一個(gè)子集A'都對應(yīng)于一個(gè)特征函數(shù),不同的子集對應(yīng)于不同的特征函數(shù).如??={,,}，?{a,b}={,,}.10課件(5)設(shè)R是A上的等價(jià)關(guān)系,令g:A→A/Rg(a)=[a],?a∈A稱g是從A到商集A/R的自然映射.重要函數(shù)的定義(續(xù))11課件實(shí)例給定集合A和A上的等價(jià)關(guān)系R,就可以確定一個(gè)自然映射g:A→A/

13、R.不同的等價(jià)關(guān)系確定不同的自然映射,其中恒等關(guān)系所確定的自然映射是雙射,而其他的自然映射一般來說只是滿射.例如：A={1,2,3},等價(jià)關(guān)系:R1={<1,2>,<2,1>}∪IA自然映射：g1(1)=g1(2)={1,2},g1(3)={3}等價(jià)關(guān)系：IA自然映射：g2(1)={1},g2(2)={2},g2(3)={3}12課件重要函數(shù)的定義(續(xù))W:Z+?Z+作為算法的時(shí)間復(fù)雜度函數(shù)W(n)的含義：對于規(guī)模為n的輸入，該算法在最壞情況下所執(zhí)行的基本運(yùn)算次數(shù)是W(n).復(fù)雜度函數(shù)f(n)的階的表示：f(n)=O(g(n))?f(n)的階不超過g(n)的

14、階f(n)=?(g(n))?f(n)=O(g(n))且g(n)=O(f(n))例如:f(n)=n2+n=?(n2),g(n)=nlogn=O(n2)其中l(wèi)ogn是log2n的簡寫算法：二分搜索W(n)=O(logn)歸并排序W(n)=O(nlogn)13課件函數(shù)的像與完全原像定義5.6設(shè)函數(shù)f:A→B,A1?A,B1?B,稱f(A1)={f(x)

15、x∈A1}為A1在f下的像，f(A)稱為函數(shù)的像.f?1(B1)={x

16、x∈A∧f(x)∈B1}為B1在f下的完全原像注意:函數(shù)的像與值的區(qū)別：函數(shù)值f(x)∈B,像f(A1)?B.A1?f?1(f(A1))，f(

17、f?1(B1))?B1.實(shí)例{1}?{1,2}=f?