離散數(shù)學(xué)：第八章 函數(shù)

第八章:函數(shù)主要內(nèi)容函數(shù)的定義與性質(zhì)函數(shù)運(yùn)算函數(shù)的逆函數(shù)的合成雙射函數(shù)與集合的基數(shù)1計(jì)算機(jī)科學(xué)與工程學(xué)院8.1函數(shù)的定義與性質(zhì)函數(shù)的歷史：十七世紀(jì)伽俐略提出過(guò)非形式化的函數(shù)概念笛卡爾的解析幾何中討論一個(gè)變量對(duì)另一個(gè)變量的依賴關(guān)系萊布尼茲、牛頓在幾何和微積分中都使用函數(shù)…康托在集合論中用“集合”和“對(duì)應(yīng)”的概念給出了近代函數(shù)定義2計(jì)算機(jī)科學(xué)與工程學(xué)院8.1函數(shù)的定義與性質(zhì)函數(shù)是具有特殊性質(zhì)的二元關(guān)系也稱(chēng)為映射(mapping)或變換(transformation)本章定義一般函數(shù)類(lèi)和各種特殊子類(lèi)側(cè)重討論離散函數(shù)3計(jì)算機(jī)科學(xué)與工程學(xué)院8.1函數(shù)的定義與性質(zhì)函數(shù)(映射)F：F為二元關(guān)系，滿足x∈domF都存在唯一的y∈ranF使xFy成立F在x的值y：xFy記做y＝F(x)x稱(chēng)為F的自變量函數(shù)相等：設(shè)F，G是函數(shù)F＝GFG∧GF4計(jì)算機(jī)科學(xué)與工程學(xué)院8.1函數(shù)的定義與性質(zhì)A到B的函數(shù)f：設(shè)A，B是集合，如果f為函數(shù)，且domf=A,ranfB記為f:A→B存在性唯一性5計(jì)算機(jī)科學(xué)與工程學(xué)院8.1函數(shù)的定義與性質(zhì)例：f:{a,b,c,d}→{1,2,3}f(a)=1xf(x)f(b)=2或a1f(c)=2b2f(d)=1c2d1abcd1236計(jì)算機(jī)科學(xué)與工程學(xué)院8.1函數(shù)的定義與性質(zhì)皮亞諾后繼函數(shù)f:N→N,f(n)=n+1投影函數(shù)X和Y是非空集合，f:X×Y→X,f(x,y)=x7計(jì)算機(jī)科學(xué)與工程學(xué)院8.1函數(shù)的定義與性質(zhì)A到B的函數(shù)集合BA

(B上A)

BA={f|f:A→B}例：設(shè)A={1,2,3},B={a,b}，求BA解：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>}8計(jì)算機(jī)科學(xué)與工程學(xué)院8.1函數(shù)的定義與性質(zhì)若A=Ф，B是任意集合，那么BA

={Ф}Ф×B=ФФ滿足函數(shù)定義的條件若A≠Ф而B(niǎo)=Ф，不存在從A到B的函數(shù)討論9計(jì)算機(jī)科學(xué)與工程學(xué)院8.1函數(shù)的定義與性質(zhì)函數(shù)的像：設(shè)f是從A到B的函數(shù)，A’A，B’Bf(A’)={f(x)|x∈A’}叫做函數(shù)f下A’的像f(A)為函數(shù)f的像(f的值域)

f－1(B’)={x|x∈A∧f(x)∈B’},稱(chēng)f－1(B’)為B’在f下的完全原像性質(zhì)：A’f－1(f(A’))（驗(yàn)證）A’

≠f－1(f(A’))例：f:{1,2,3}{0,1},

f(1)=f(2)=0,f(3)=1

考慮A’={1}10計(jì)算機(jī)科學(xué)與工程學(xué)院8.1函數(shù)的定義與性質(zhì)例設(shè)f：{a,b,c,d}→{1,2,3}

f({a})={1}

f({a,b})={1,2}f(Ф)=Фf-1({1})={a,d}321dcba11計(jì)算機(jī)科學(xué)與工程學(xué)院8.1函數(shù)的定義與性質(zhì)滿(單、雙)射：設(shè)f是從A到B的函數(shù)滿射：ranf=B單射：x≠x’

f(x)≠f(x’)或者：f(x)=f(x’)

x=x’雙射：f是滿射且是單射12計(jì)算機(jī)科學(xué)與工程學(xué)院8.1函數(shù)的定義與性質(zhì)例：判斷函數(shù)類(lèi)型f:R→R,f(x)=2x+5解：y∈R存在x=(y-5)/2使得f(x)=y,

f是滿射x1,x2∈R,x1≠x2,有2x1+5≠2x2+5,即f(x1)≠f(x2),f是單射f是雙射13計(jì)算機(jī)科學(xué)與工程學(xué)院8.1函數(shù)的定義與性質(zhì)例：判斷f:AB是否構(gòu)成函數(shù)，如果是，是否為單射、滿射和雙射A={1,2,3,4,5},

B={6,7,8,9,10},f={<1,8>,<4,9>,<4,10>,<2,6>,<3,9>}A,B同上,f={<1,7>,<2,6>,<4,5>,<1,9>,<5,10>}A=B=R×R,f(<x,y>)=<x+y,x-y>14計(jì)算機(jī)科學(xué)與工程學(xué)院8.1函數(shù)的定義與性質(zhì)常函數(shù)：f:A→B滿足如果存在y∈B使對(duì)每一x∈A有f(x)=y

恒等函數(shù)IA:A→A，對(duì)每一x∈A有f(x)=x恒等函數(shù)是雙射函數(shù)15計(jì)算機(jī)科學(xué)與工程學(xué)院8.1函數(shù)的定義與性質(zhì)(嚴(yán)格)單調(diào)遞增：設(shè)<A,?>，<B,?>為偏序集，f:A→B單調(diào)遞增：如果對(duì)任意的x，y∈A，x?y，就有f(x)?f(y)嚴(yán)格單調(diào)遞增：如果對(duì)任意的x，y∈A，x?y,就有f(x)?f(y)16計(jì)算機(jī)科學(xué)與工程學(xué)院8.1函數(shù)的定義與性質(zhì)特征函數(shù)：設(shè)A’A，函數(shù)χA’:A’→{0,1}定義為

χA’(x)=1如果x∈A’0如果xA’稱(chēng)它是集合A’的特征函數(shù)例：設(shè)A={a,b,c,d},A’={b,d}

χA’:A’→{0,1}則χA’(a)=0,χA’(b)=1

χA’(c)=0,χA’(d)=18.1函數(shù)的定義與性質(zhì)如果函數(shù)f:A→B的前域A非空，那么集合族{f-1({y})|y∈B∧f-1({y})≠Ф}形成A的一個(gè)劃分，與此劃分相關(guān)聯(lián)的等價(jià)關(guān)系R可如下定義：

x1Rx2f(x1)=f(x2)可以證明R符合等價(jià)條件稱(chēng)R為f誘導(dǎo)的A上的等價(jià)關(guān)系定義:設(shè)R是一集合A上的等價(jià)關(guān)系，函數(shù)

g:A→A/R,g(x)=[x]R叫做從A到商集A/R的自然映射18計(jì)算機(jī)科學(xué)與工程學(xué)院8.1函數(shù)的定義與性質(zhì)例設(shè)A={a,b,c,d},B={0,1,2,3,4}f(a)=1,f(b)=0,f(c)=1,f(d)=3f誘導(dǎo)的等價(jià)關(guān)系R的等價(jià)類(lèi){a,c},,5lr5t7l從A到A/R的自然映射gg:{a,b,c,d}→{{a,c},,zz5brx7}g(a)={a,c}g(b)=g(c)={a,c}g(d)=7vbtlb543210dcba19計(jì)算機(jī)科學(xué)與工程學(xué)院8.2函數(shù)的復(fù)合與反函數(shù)函數(shù)的復(fù)合：關(guān)系的右復(fù)合性質(zhì)1：FG還是一個(gè)函數(shù)證明：對(duì)任一xdom(FG)，假設(shè)<x,y1>FG

且<x,y2>FGt1(<x,t1>F<t1,y1>G)

t2(<x,t2>F<t2,y2>G)t1t2(t1=t2<t1,y1>G<t2,y2>G)y1=y220計(jì)算機(jī)科學(xué)與工程學(xué)院8.2函數(shù)的復(fù)合與反函數(shù)性質(zhì)2：domFG={x|xdomFF(x)dom(G)}證明：對(duì)任一xdom(FG)

ty(<x,t>F<t,y>G)ty(xdomFt=F(x)tdomG)t(xdomFF(x)domG)x{x|xdomFF(x)dom(G)}21計(jì)算機(jī)科學(xué)與工程學(xué)院8.2函數(shù)的復(fù)合與反函數(shù)性質(zhì)3：xdomFG有FG(x)=G(F(x))證明：xdomFF(x)dom(G)<x,F(x)>F<F(x),G(F(x))>G<x,G(F(x))>FGxdomFGFG(x)=G(F(x))推論1：給定函數(shù)F,G,H,

則F(GH)和(FG)H都是函數(shù)，且F(GH)=(FG)H22計(jì)算機(jī)科學(xué)與工程學(xué)院8.2函數(shù)的復(fù)合與反函數(shù)例：集合A={1,2,3},A上的兩個(gè)函數(shù)f={<1,3>,<2,1>,<3,2>}g={<1,2>,<2,1>,<3,3>}321321321gf321321321fgfg={<1,3>,<2,2>,<3,1>}gf={<1,1>,<2,3>,<3,2>}ff={<1,2>,<2,3>,<3,1>}fff={<1,1>,<2,2>,<3,3>}=IA23計(jì)算機(jī)科學(xué)與工程學(xué)院8.2函數(shù)的復(fù)合與反函數(shù)例：A上的三個(gè)函數(shù)f(a)=3-a,g(a)=2a+1,h(a)=a/3我們有：(fg)(a)=g(f(a))=g(3-a)=2(3-a)+1=7-2a(gf)(a)=f(g(a))=f(2a+1)=2-2ah(g(f(a)))=h(7-2a)=(7-2a)/324計(jì)算機(jī)科學(xué)與工程學(xué)院8.2函數(shù)的復(fù)合與反函數(shù)推論2：設(shè)f:A→B,g:B→C,則fg：A→C,且

x∈A都有fg(x)=g(f(x))證明：由性質(zhì)1，fg是函數(shù);

由性質(zhì)2,dom(fg)={x|x∈domff(x)∈domg}={x|x∈domff(x)∈B}=A,ran(fg)ran(g)C由性質(zhì)3，fg(x)=g(f(x))25計(jì)算機(jī)科學(xué)與工程學(xué)院8.2函數(shù)的復(fù)合與反函數(shù)定理：設(shè)函數(shù)f:A→B,g:B→C則:若f和g都是滿射,則fg

也是滿射若f和g都是單射,則fg也是單射若f和g都是雙射,則fg也是雙射26計(jì)算機(jī)科學(xué)與工程學(xué)院8.2函數(shù)的復(fù)合與反函數(shù)定理：設(shè)函數(shù)f:A→B,g:B→C

則:若f和g都是滿射,則fg也是滿射證明：任取cC

g是滿射存在bB,g(b)=c

f是滿射存在aA,f(a)=b

由性質(zhì)3

fg(a)=g(f(a))=g(b)=c

從而證明fg是滿射27計(jì)算機(jī)科學(xué)與工程學(xué)院8.2函數(shù)的復(fù)合與反函數(shù)xyzabcd12ABCfgxyzabcd123ABCfgfg是滿射,f不是滿射fg是單射,g不是單射28計(jì)算機(jī)科學(xué)與工程學(xué)院8.2函數(shù)的復(fù)合與反函數(shù)定理：給定函數(shù)f:A→B,有f＝fIB＝IAf證明：首先易證fIB和IAf都是函數(shù)

<x,y>f<x,y>fyB<x,y>f<y,y>IB<x,y>fIB

同理可以證明

<x,y>fIB<x,y>f29計(jì)算機(jī)科學(xué)與工程學(xué)院8.2函數(shù)的復(fù)合與反函數(shù)給定函數(shù)F，F(xiàn)-1不一定是函數(shù)例：A={a,b,c},B={1,2,3}f={<a,3>,<b,3>,<c,1>}f非單射非滿射f-1={<3,a>,<3,b>,<1,c>}f-1不是函數(shù)討論：任給單射函數(shù)f:A→Bf-1是函數(shù)f-1:ranf→A的雙射函數(shù)f-1不一定是B到A的雙射函數(shù)30計(jì)算機(jī)科學(xué)與工程學(xué)院8.2函數(shù)的復(fù)合與反函數(shù)定理：函數(shù)f:A→B是雙射函數(shù)f-1:B→A是雙射函數(shù)證明：由關(guān)系逆(定理7.1)的性質(zhì)

domf-1=ranf=Branf-1=domf=AxB，假設(shè)有y1,y2A，使得

<x,y1>f-1<x,y2>f-1則<y1,x>f<y2,x>ff是單射，故y1=y2，所以f-1是函數(shù)同樣可以證明f-1是單射和滿射31計(jì)算機(jī)科學(xué)與工程學(xué)院8.2函數(shù)的復(fù)合與反函數(shù)定理：函數(shù)f:A→B是雙射函數(shù)f-1f=IB，ff-1=IA證明：首先易證f-1f是B到B的函數(shù)。<x,y>,<x,y>f-1ft(<x,t>f-1<t,y>f)t(<t,x>f<t,y>f)x=yx,yB<x,y>IB

同理可以證明IBf-1f32計(jì)算機(jī)科學(xué)與工程學(xué)院8.3集合的基數(shù)等勢(shì)：

集合A和B等勢(shì)如果存在從A到B的雙射函數(shù)記作AB例：ZNf:ZN，使得f(x)=2x，x≥0f(x)=-2x-1,x<0例：N×NNf:N×NN，使得f(<m,n>)=(m+n+1)(m+n)/2+m33計(jì)算機(jī)科學(xué)與工程學(xué)院8.3集合的基數(shù)定理：對(duì)任意集合A,B,CAA若AB，則BA若AB，BC，則AC證明？總結(jié)NZQN×NR[0,1](0,1)NR?34計(jì)算機(jī)科學(xué)與工程學(xué)院8.3集合的基數(shù)康托定理：NR對(duì)任意集合A都有，AP(A)35計(jì)算機(jī)科學(xué)與工程學(xué)院8.3集合的基數(shù)優(yōu)勢(shì)于：B優(yōu)于A(A?·B):存在從A到B的單射函數(shù)B真優(yōu)于A(A?·B):A?·B且BA例：N?·N,N?·R,A?·P(A)N?·R,

A?·P(A)定理：給定任意集合A,B,CA?·A若A?·B且B?·A，則AB若A?·B且B?·C，則A?·C36計(jì)算機(jī)科學(xué)與工程學(xué)院8.3集合的基數(shù)對(duì)于有限集：集合中不同元素的個(gè)數(shù)。對(duì)于無(wú)限集呢？是否所有無(wú)限集的基數(shù)都一樣？為了比較兩個(gè)集合的“大小”，確定有限集和無(wú)限集的概念，引進(jìn)自然數(shù)集合給定集合A，A+=A{A}，稱(chēng)A+是A的后繼集合利用后繼集合的概念來(lái)定義自然數(shù)集合{0，1，2，}37計(jì)算機(jī)科學(xué)與工程學(xué)院8.3集合的基數(shù)有窮集：

一個(gè)集合是有窮的它與某個(gè)自然數(shù)等勢(shì)否則為無(wú)窮例：有窮集：{a,b,c}無(wú)窮集：N,R三類(lèi)不同基數(shù)有窮集合A:cardA=nAn自然數(shù)集N：cardN=?0實(shí)數(shù)集R:cardR=?38計(jì)算機(jī)科學(xué)與工程學(xué)院8.3集合的基數(shù)基數(shù)相等和大?。航o定集合A和BcardA=cardBABcardA≤cardBA?·BcardA<cardB

cardA≤cardBcardA≠cardB例：cardN=cardQ=cardN×N=?0cardP(N)=card2N=card[a,b]=card(a,b)=??0<?39計(jì)算機(jī)科學(xué)與工程學(xué)院8.3集合的基數(shù)可數(shù)集：A為可數(shù)集如果cardA≤?0例：可數(shù)集：{a,b,c},N,Z,Q不可數(shù)集：R,(0,1)命題：可數(shù)集的任何子集是可數(shù)集兩個(gè)可數(shù)集的并是可數(shù)集兩個(gè)可數(shù)集的笛卡爾積是可數(shù)集無(wú)窮集的冪集不是可數(shù)集40計(jì)算機(jī)科學(xué)與工程學(xué)院補(bǔ)充材料：8.3集合的基數(shù)

——集合等勢(shì)示例例：(0,1)Rf:(0,1)R，使得f(x)=tanπ(2x-1/2)例：[0,1](0,1)f:[0,1](0,1)，使得f(x)=1/2,x=0f(x)=1/4,x=1f(x)=1/2n+2,x=1/2nf(x)=x,其他x41計(jì)算機(jī)科學(xué)與工程學(xué)院補(bǔ)充材料：8.3集合的基數(shù)

——集合等勢(shì)示例例：[0,1][a,b]，對(duì)任何a<b,a,bRf:[0,1][a,b]，使得f(x)=(b-a)x+a例：P(A){0,1}Af:P(A){0,1}A，使得f(A’)=χA’,A’P(A)42計(jì)算機(jī)科學(xué)與工程學(xué)院補(bǔ)充材料：8.3集合的基數(shù)

——康托定理證明康托定理：NR對(duì)任意集合A都有，AP(A)證明：設(shè)g:AP(A)是函數(shù)?？梢詷?gòu)造

B={x|xAxg(x)}則BP(A)，對(duì)任意xA有

xBxg(x)故B≠g(x)，所以B不在rang中43計(jì)算機(jī)科學(xué)與工程學(xué)院補(bǔ)充材料：8.3集合的基數(shù)

——康托定理證明康托定理：NR對(duì)任意集合A都有，AP(A)證明：只需證明N[0,1]任一[0,1]間實(shí)數(shù)必可寫(xiě)成無(wú)限的十進(jìn)制小數(shù)

x=0.x1x2…,0·xi

·9設(shè)f:N[0,1]是從N到[0,1]的任何一個(gè)函數(shù)，則可列出f的所有函數(shù)值如下44計(jì)算機(jī)科學(xué)與工程學(xué)院補(bǔ)充材料：8.3集合的基數(shù)

——康托定理證明康托定理：NR對(duì)任意集合A都有，AP(A)證明：…則可列出f

的所有函數(shù)值如下

f(0)=0.a(1)1a(1)2……