離散數(shù)學(xué)函數(shù)

離散數(shù)學(xué)函數(shù)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ù)函數(shù)定義定義5、1設(shè)f為二元關(guān)系,若

x∈domf都存在唯一得y∈ranf使xfy成立,則稱f為函數(shù)、對于函數(shù)f,如果有xfy,則記作y=f(x),并稱y為f在x得值、例如f1={<x1,y1>,<x2,y2>,<x3,y2>}

f2={<x1,y1>,<x1,y2>}

f1就是函數(shù),f2不就是函數(shù)

函數(shù)相等定義5、2設(shè)f,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、

從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ù)B上A定義5、4所有從A到B得函數(shù)得集合記作BA,讀作“B上A”符號化表示為

BA={f|f:A→B}計(jì)數(shù):

|A|=m,|B|=n,且m,n>0,|BA|=nm、A=

,則BA=B

={

}、

A≠

且B=

,則BA=

A=

、

實(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>,<3,a>}

f7={<1,b>,<2,b>,<3,b>}

例1設(shè)A={1,2,3},B={a,b},求BA、重要函數(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è)<A,?>,<B,?>為偏序集,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)遞增得、

類似得也可以定義單調(diào)遞減與嚴(yán)格單調(diào)遞減得函數(shù)、重要函數(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,0>,<b,0>,<c,0>},

{a,b}={<a,1>,<b,1>,<c,0>}、(5)設(shè)R就是A上得等價(jià)關(guān)系,令

g:A→A/R

g(a)=[a],

a∈A

稱g就是從A到商集A/R得自然映射、重要函數(shù)得定義(續(xù))實(shí)例給定集合A與A上得等價(jià)關(guān)系R,就可以確定一個(gè)自然映射g:A→A/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}大家學(xué)習(xí)辛苦了，還是要堅(jiān)持繼續(xù)保持安靜重要函數(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)得階

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)函數(shù)得像與完全原像定義5、6設(shè)函數(shù)f:A→B,A1

A,

B1

B,稱

f(A1)={f(x)|x∈A1}

為A1在f下得像,f(A)稱為函數(shù)得像、

f

1(B1)={x|x∈A∧f(x)∈B1}為B1在f下得完全原像注意:函數(shù)得像與值得區(qū)別:函數(shù)值f(x)∈B,像f(A1)

B、A1

f

1(f(A1)),f(f

1(B1))

B1、

實(shí)例{1}

{1,2}=f

1({a})=f

1(f({1}))f(f

1({b,c}))=f({3})={b,c}實(shí)例1、設(shè)f:N→N,且令A(yù)={0,1},B={2},那么有

f(A)=f({0,1})={f(0),f(1)}={0,2}

f(B)={f(2)}={1}2、A={1,2,3},B={a,b,c},f={<1,a>,<2,a>,<3,b>},則

f

1({a,b})={1,2,3},f

1({b,c})={3},函數(shù)得性質(zhì)定義5、7設(shè)f:A→B,

(1)若ranf=B,則稱f:A→B就是滿射得、

(2)若

y∈ranf都存在唯一得x∈A使得f(x)=y,則稱f:A→B就是單射得、

(3)若f:A→B既就是滿射又就是單射得,則稱f:A→B就是雙射得f

滿射意味著:

y

B,都存在x

A

使得

f(x)=y、f單射意味著:f(x1)=f(x2)

x1=x2實(shí)例例2判斷下面函數(shù)就是否為單射,滿射,雙射得,為什么?

(1)f:R→R,f(x)=

x2+2x

1

(2)f:Z+→R,f(x)=lnx,Z+為正整數(shù)集

(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+為正實(shí)數(shù)集、

解(1)f:R→R,f(x)=

x2+2x

1

(2)f:Z+→R,f(x)=lnx

(3)f:R→Z,f(x)=

x

(4)f:R→R,f(x)=2x+1

(5)f:R+→R+,f(x)=(x2+1)/x

實(shí)例(續(xù))在x=1取得極大值0、既不就是單射也不就是滿射得、單調(diào)上升,就是單射得、但不滿射,ranf={ln1,ln2,…}、就是滿射得,但不就是單射得,例如f(1、5)=f(1、2)=1、就是滿射、單射、雙射得,因?yàn)樗褪菃握{(diào)函數(shù)并且ranf=R、有極小值f(1)=2、該函數(shù)既不就是單射得也不就是滿射得、構(gòu)造從A到B得雙射函數(shù)有窮集之間得構(gòu)造例3A=P({1,2,3}),B={0,1}{1,2,3}解

A={

,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}、

B={f0,f1,…,f7},其中

f0={<1,0>,<2,0>,<3,0>},f1={<1,0>,<2,0>,<3,1>},

f2={<1,0>,<2,1>,<3,0>},f3={<1,0>,<2,1>,<3,1>},

f4={<1,1>,<2,0>,<3,0>},f5={<1,1>,<2,0>,<3,1>},

f6={<1,1>,<2,1>,<3,0>},f7={<1,1>,<2,1>,<3,1>}、

令f:A→B,f(

)=f0,f({1})=f1,f({2})=f2,f({3})=f3,f({1,2})=f4,f({1,3})=f5,f({2,3})=f6,f({1,2,3})=f7實(shí)數(shù)區(qū)間之間構(gòu)造雙射構(gòu)造方法:直線方程例4A=[0,1]

B=[1/4,1/2]

構(gòu)造雙射f:A→B

構(gòu)造從A到B得雙射函數(shù)(續(xù))解令f:[0,1]→[1/4,1/2]f(x)=(x+1)/4

A與自然數(shù)集合之間構(gòu)造雙射方法:將A中元素排成有序圖形,然后從第一個(gè)元素開始按照次序與自然數(shù)對應(yīng)構(gòu)造從A到B得雙射函數(shù)(續(xù))例5A=Z,B=N,構(gòu)造雙射f:A→B將Z中元素以下列順序排列并與N中元素對應(yīng):

Z:0

11

22

33…

↓↓↓↓↓↓↓

N:0123456…

則這種對應(yīng)所表示得函數(shù)就是:

5、2函數(shù)得復(fù)合與反函數(shù)5、2、1函數(shù)得復(fù)合函數(shù)復(fù)合得基本定理及其推論函數(shù)復(fù)合得性質(zhì)5、2、2反函數(shù)反函數(shù)存在得條件反函數(shù)得性質(zhì)函數(shù)復(fù)合得基本定理定理5、1設(shè)f,g就是函數(shù),則f°g也就是函數(shù),且滿足

(1)dom(f°g)={x|x∈domf

f(x)∈domg}

(2)

x∈dom(f°g)有f°g(x)=g(f(x))

證先證明f°g就是函數(shù)、

因?yàn)閒,g就是關(guān)系,所以f°g也就是關(guān)系、

若對某個(gè)x∈dom(f°g),xf°gy1與xf°gy2,則

<x,y1>∈f°g

<x,y2>∈f°g

t1(<x,t1>∈f

<t1,y1>∈g)

t2(<x,t2>∈f

<t2,y2>∈g)

t1

t2(t1=t2

<t1,y1>∈g

<t2,y2>∈g)

y1=y2

所以f°g為函數(shù)、證明

再證明結(jié)論(1)與(2)、任取x,

x∈dom(f°g)

t

y(<x,t>∈f∧<t,y>∈g)

t(x∈domf∧t=f(x)∧t∈domg)

x∈{x|x∈domf∧f(x)∈domg}任取x,

x∈domf∧f(x)∈domg

<x,f(x)>∈f∧<f(x),g(f(x))>∈g

<x,g(f(x))>∈f°g

x∈dom(f°g)∧f°g(x)＝g(f(x))所以(1)與(2)得證、推論推論1設(shè)f,g,h為函數(shù),則(f°g)°h與f°(g°h)都就是函數(shù),且

(f°g)°h=f°(g°h)證由上述定理與關(guān)系合成運(yùn)算得可結(jié)合性得證、推論2設(shè)f:A→B,g:B→C,則f°g:A→C,且

x∈A都有

f°g(x)=g(f(x))、證由上述定理知f°g就是函數(shù),且

dom(f°g)={x|x∈domf∧f(x)∈domg}

={x|x∈A∧f(x)∈B}=A

ran(f°g)

rang

C因此f°g:A→C,且

x∈A有f°g(x)=g(f(x))、函數(shù)復(fù)合得性質(zhì)定理5、2設(shè)f:A→B,g:B→C、

(1)如果f:A→B,g:B→C都就是滿射得,則f°g:A→C也就是滿射得、

(2)如果f:A→B,g:B→C都就是單射得,則f°g:A→C也就是單射得、

(3)如果f:A→B,g:B→C都就是雙射得,則f°g:A→C也就是雙射得、

證明(1)任取c∈C,由g:B→C得滿射性,

b∈B使得g(b)=c、對于這個(gè)b,由f:A→B得滿射性,

a∈A使得f(a)=b、由定理5、1有

f°g(a)=g(f(a))=g(b)=c從而證明了f°g:A→C就是滿射得、(2)假設(shè)存在x1,x2∈A使得

f°g(x1)=f°g(x2)