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

Content第五章函數(shù)本章主要介紹函數(shù)的概念函數(shù)的復(fù)合逆函數(shù)函數(shù)在集合的基數(shù)中的應(yīng)用。1/5/20241Definition5-1函數(shù)的基本概念一.概念[定義]：X與Y集合，f是從X到Y(jié)的關(guān)系，如果任何x∈X，都存在唯一y∈Y，使得<x,y>∈f

,則稱f是從X到Y(jié)的函數(shù)，(變換、映射)，記作f

:X→Y,或X→Y。

如果f

:X

X是函數(shù),也稱f是X上的函數(shù).X：定義域/domainoffx:y的原像/pre-imageY：陪域/codomainoffy:x的像/imagef（X）：值域（Rf

、ranf)/rangeoff1/5/20242下面是大家熟悉的實(shí)數(shù)集合上的幾個(gè)關(guān)系，哪些是R到R的函數(shù)？

f={<x,y>|x,y∈R∧y=}g={<x,y>|x,y∈R∧x2+y2=4}h={<x,y>|x,y∈R∧y=x2}r={<x,y>|x,y∈R∧y=lgx}v={<x,y>|x,y∈R∧y=}Definition1/5/20243二.函數(shù)的表示方法

同關(guān)系的表示方法，也有枚舉法、有向圖、矩陣、謂詞描述法。這里不再贅述。函數(shù)的矩陣的特點(diǎn)：每行必有且只有一個(gè)1。三.從X到Y(jié)函數(shù)的集合YX：

YX={f|f:XY}YX：它是由所有的從X到Y(jié)函數(shù)構(gòu)成的集合Definition1/5/20244例X={1,2,3}Y={a,b}所有的從X到Y(jié)函數(shù):f1X

Yf3。。。。。123abX

Yf2。。。。。123abf8X

Yf4。。。。。123abX

Yf5。。。。。123abX

Yf6。。。。。123abX

Yf7。。。。。123abX

Y。。。。。123abX

Y。。。。。123abYX={f1,f2,f3,f4,f5,f6,f7,f8}

如果X和Y是有限集合，|X|=m,|Y|=n,因?yàn)閄中的每個(gè)元素對應(yīng)的函數(shù)值都有n種選擇，于是可構(gòu)成nm個(gè)不同的函數(shù)，因此|YX|=|Y||X|=nm,1/5/20245四.特殊函數(shù)

1.常值函數(shù)：函數(shù)f:XY，如果

y0∈Y,使得對

x∈X,有f(x)=y0,即ranf={y0},稱f是常值函數(shù)。如上例的f

1和f

8。2.恒等函數(shù)：恒等關(guān)系IX是X到X函數(shù)，即IX:XX,稱之為恒等函數(shù)。顯然對于x∈X，有IX(x)=x。五.兩個(gè)函數(shù)相等設(shè)有兩個(gè)函數(shù)f:ABg:CD,f=g

當(dāng)且僅當(dāng)A=C，B=D，且對任何x∈A，有f(x)=g(x)。

即它們的定義域相等、陪域相等、對應(yīng)規(guī)律相同。1/5/20246六.函數(shù)的類型1234abc1234abc123dabc23bca1一對一一對一滿射的映內(nèi)的入射的單射的一對一的雙射的一一對應(yīng)的1/5/20247思考題如果f:XX是入射的函數(shù)，則必是滿射的，所以f也是雙射的。此命題成立嗎？答案是：不一定。例如f:NN,f(n)=2n,f是入射的，但不是滿射的函數(shù)。只有當(dāng)X是有限集合時(shí)，上述命題才成立。本節(jié)重點(diǎn)掌握：函數(shù)的定義、函數(shù)的類型的判定和證明。作業(yè)P151(1),(3),(5),(6)1/5/202485-2函數(shù)的復(fù)合

[定義]

f

:X

Y,g:Y

Z是函數(shù),則定義

g

f

＝{<x,z>|x

X

z

Z

y(y

Y

<x,y>

f

<y,z>

g)}則稱g

f

為f與g的復(fù)合函數(shù)(左復(fù)合)。

g

f:XZ,即g

f是X到Z的函數(shù).這樣寫是為了照顧數(shù)學(xué)習(xí)慣:g

f(x)=g(f(x))1/5/20249復(fù)合函數(shù)的計(jì)算

計(jì)算方法同復(fù)合關(guān)系的計(jì)算，

但要注意是左復(fù)合。例

f:X

Y,g:Y

ZX={1,2,3}Y={1,2,3,4,}Z={1,2,3,4,5,}f={<1,2>,<2,4>,<3,1>}g={<1,3>,<2,5>,<3,2>,<4,1>}g

f={<1,3>,<2,5>,<3,2>,<4,1>}

{<1,2>,<2,4>,<3,1>}={<1,5>,<2,1>,3,3>}用有向圖復(fù)合:。3。2。13214。3。2。1。4。5。3。2。1。4。5。3。2。11/5/202410例令f和g都是實(shí)數(shù)集合R上的函數(shù),如下:f={<x,y>|x,y∈R∧y=3x+1}g={<x,y>|x,y∈R∧y=x2+x}分別求g

f

、f

g、f

f

、g

g

g

f(x)=g(f(x))=(3x+1)2+(3x+1)=9x2+9x+2f

g(x)=f(g(x))=3(x2+x)

+1=3x2+3x+1f

f(x)=f(f(x))=3(3x+1)

+1=9x+4g

g(x)=g(g(x))=(x2+x)2+(x2+x)=x4+2x3+2x2+

x

可見復(fù)合運(yùn)算不滿足交換性。1/5/202411函數(shù)復(fù)合的性質(zhì)1.定理5-2.1滿足可結(jié)合性f:X

Y,g:Y

Z,h:Z

W是函數(shù),則(h

g)

f=h

(g

f)2.定理5-2.2f:X

Y,g:Y

Z是兩個(gè)函數(shù),則

⑴如果f和g是滿射的，則g

f也是滿射的；

⑵如果f和g是入射的，則g

f也是入射的；

⑶如果f和g是雙射的，則g

f也是雙射的。1/5/202412定理2證明：⑴

設(shè)f和g是滿射的，因g

f:XZ,任取z∈Z,因g:Y

Z是滿射的，所以存在y∈Y,使得z=g(y),又因f:X

Y是滿射的，所以存在x∈X,使得y=f(x),于是有z=g(y)=g(f(x))=g

f(x),所以g

f

是滿射的。⑵

設(shè)f和g是入射的，因g

f:XZ,任取x1,x2∈X,x1≠x2因f:X

Y是入射的，f(x1)≠f(x2),而f(x1),f(x2)∈Y，

因g:Y

Z是入射的，g(f(x1))≠g(f(x2))

即g

f(x1)≠g

f(x2)所以g

f

也是入射的。

⑶由⑴⑵可得此結(jié)論。1/5/2024133.定理5-2.3⑴如果gf

是滿射的，則g是滿射的；⑵如果gf

是入射的，則f是入射的；

⑶如果gf

是雙射的，則f是入射的和g是滿射的。此定理的證明是作業(yè)題P156(3)。4.定理5-2.4f:X

Y是函數(shù),則

f

IX=f且IY

f=f

。1/5/202414定理4證明：

先證明定義域、陪域相等。因?yàn)镮X:X

X，f:XY，

∴fIX:XY,IY

f:XY

可見fIX、IY

f

與f具有相同的定義域和陪域。再證它們的對應(yīng)規(guī)律相同：任取x∈X，

fIX(x)=f(IX(x))=f(x)IY

f(x)=IY(f(x))=f(x)所以fIX

=f且

IY

f=f

。1/5/2024155-3逆函數(shù)[定義]：設(shè)f:Xy是雙射的函數(shù)，fC:YX也是函數(shù),稱之為f

的逆函數(shù)。并用f

-1代替f

C

。f

-1存在，也稱f

可逆。顯然，f-1也是雙射的函數(shù)。

R是A到B的關(guān)系，其逆關(guān)系RC是B到A的關(guān)系。

f:XyfC:YX,是否是個(gè)函數(shù)？請看下面的例子：。3。2。1。c。b。a。3。2。1。c。b。af:XYfC:YX1/5/202416性質(zhì)1.定理5-3.1設(shè)f:XY是雙射的函數(shù)，則(f-1)-1=f。2.定理5-3.2設(shè)f:XY是雙射的函數(shù)，則有

f-1

f=IX

且f

f-1=IY。證明：先證明定義域、陪域相等。因?yàn)閒:XY是雙射的，f-1:YX也是雙射的，所以

f-1

f:X

X;IX:X

X

可見f-1

f與IX

具有相同的定義域和陪域。

再證它們的對應(yīng)規(guī)律相同：

x∈X,因f:XY,yY,

使得y=f(x),又f可逆，故f-1(y)=x，于是

f-1

f(x)=f-1(f(x))=f-1(y)=x=IX(x)

同理可證

f

f-1

=IY。

1/5/2024173.定理5-3.3令f:X

Y,g:Y

X是兩個(gè)函數(shù),如果g

f=IX

且f

g=IY,則g=f-1

。證明：⑴證f和g都可逆。因?yàn)間

f=IX，IX是雙射的，由關(guān)系復(fù)合性質(zhì)3得，f是入射的和g是滿射的。同理由

f

g=IY，得g是入射的和f是滿射的。所以f和g都可逆。⑵顯然f-1和g具有相同的定義域和陪域。⑶證明它們的對應(yīng)規(guī)律相同。任取yY，f-1(y)=f-1

IY(y)

=f-1

(f

g)

(y)

=(f-1

f)

g

(y)

=(

IX

g)

(y)=g(y)

所以f-1=g1/5/202418順便說明：f-1=g的兩個(gè)條件必須同時(shí)滿足，缺一不可。例如X

Y。。。。12ab。cf。。12Xg。。12X。。12XIX此例只滿足g

f=IX

,但f與g都非雙射，不可逆。4.定理5-3.4,令f:X

Y,g:Y

X是兩個(gè)雙射函數(shù),則

(g

f)-1=f-1

g-1此定理與關(guān)系的復(fù)合求逆(R

S)C=SC

RC

類似，作業(yè)P156(1),(3)c)，(5)1/5/202419*5-4集合的特征函數(shù)與模糊子集一.集合的特征函數(shù)[定義]:令E是全集,A是E的子集,定義函數(shù)

ψA:E{0,1}對任何x∈E,有

1x∈AψA(x)=

0xA稱是ψA:E{0,1}子集A的特征函數(shù).1/5/202420下面以E={a,b,c}為例,看E的各個(gè)子集的特征函數(shù)。cab01abc01abc01abc01abc01abc01abc01abc011/5/2024212.性質(zhì)令A(yù),B是全集E的子集,1)A=Φx(ψA(x)=0)

2)A=Ex(ψA(x)=1)3)ABx(ψA(x)≤ψB(x))證明:任取x∈E,從下表看出ABx(ψA(x)≤ψB(x))

xAxBxAxBψA(x)ψB(x))

ψA(x)≤ψB(x))

FFT00TFTT01TTFF10FTTT11T1/5/2024224)A=Bx(ψA(x)=ψB(x))5)ABx(ψA(x)≤ψB(x))x(ψB(x)=1

ψA(x)=0)

6)ψA∩B(x)=ψA(x)ψB(x)xAxBxA∩BψA∩B(x)ψA(x)ψB(x))

FFF00×0=0

FTF00×1=0TFF01×0=0TTT11×1=11/5/2024237)Ψ~A(x)=1-ψA(x))x∈Ax∈~AψA(x)Ψ~A(x)1-ψA(x))TF101-1=0FT011-0=18).ψA∪B(x)=ψA(x)+ψB(x)-ψA∩B(x)x∈Ax∈BψA∩B(x)xA∪BψA∪B(x)ψA(x)+ψB(x))-ψA∩B(x)

FF0F00＋0－0＝0FT0T10＋1－0＝1TF0T11＋0－0＝1TT1T11＋1－1＝11/5/2024249)ψA-B(x)=ψA(x)-ψA∩B(x)證明:任取x∈EψA-B(x)=ψA∩~B(x)=ψA(x)ψ~B(x)=ψA(x)(1-ψB(x))=ψA(x)-ψA(x)ψB(x)=ψA(x)-ψA∩B(x)應(yīng)用上述公式可以得到一些集合公式。例如證明吸收律：A∪(A∩B)=A證明:任取x∈A,ψA∪(A∩B)(x)=ψA(x)+ψA∩B(x)-ψA∩(A∩B)(x)=ψA(x)+ψA∩B(x)-ψA∩B(x)=ψA(x)1/5/202425二.模糊子集[定義]

注意:1/5/202426定義說明1/5/202427例子.令E={,,,,}

表示E中“圓形”的模糊子集。表示E中“方形”的模糊子集。它們的隸屬函數(shù)如下:abcdea1a0.4b0.8b0.3c0.3c1d0.2d0.2e0e01/5/202428模糊子集的表示方法1)序偶的集合表示

2)用Zaden記號表示3)用有序n元組表示1/5/202429

4)用函數(shù)表達(dá)式或曲線表示例如,以年齡為論域,E={0,1,2,3,…200},Zaden給出了“年老---”“年青---”兩個(gè)模糊子集的隸屬函數(shù)表示為:502511/5/202430模糊集合的運(yùn)算1/5/2024315-6集合的基數(shù)一.自然數(shù)1.集合A的后繼集合A+A是個(gè)集合，A的后繼集合A+

為：

A+=A∪{A}例如:A:A+:Φ=00+=Φ∪{Φ}={Φ}=1={0}{Φ}=11+={Φ}∪{{Φ}}={Φ,{Φ}}=2={0,1}{Φ,{Φ}}=22+={Φ,{Φ}}∪{{Φ,{Φ}}}={Φ,{Φ},{Φ,{Φ}}}=3={0,1,2}…...…...1/5/2024322.自然數(shù)集合N的定義(Peano公理)

1).0∈N這里0=Φ2).n∈N,則n+∈N,這里n+=n∪{n}

3).不存在

n∈N,使得n+=00是最小的自然數(shù)

4).若n+=m+,則n=m后繼數(shù)的唯一性

5).如果S

N，且

⑴0∈S；

⑵n∈S,則n+∈S

則S=N。從此定義得n={0,1,2,3,…,n-1},所以有：0∈1∈2∈3∈…...0

123……自然數(shù)的這個(gè)定義，解釋了許多數(shù)學(xué)問題，是一個(gè)很準(zhǔn)確的抽象。因?yàn)?,1,2,3,..本身就是個(gè)抽象的概念。1/5/202433二.集合的等勢比較兩個(gè)集合的“大小”有兩種方法：數(shù)集合中元素的個(gè)數(shù)。這只使用于有限集合?？磧蓚€(gè)集合的元素間是否有一一對應(yīng)的關(guān)系(雙射)。這種方法既適用于有限集合，也適用無限集合。［定義］：A是B集合，如果存在雙射f:AB，

則稱A與B等勢。記作A~B。例如下面集合間是等勢的。

N={0,1,2,3,4,…...}A={0,2,4,6,8,…...}f:NA，f(x)=2xB={1,3,5,7,9,…...}g:NB，g(x)=2x+11/5/202434

集合間的等勢關(guān)系“~”是個(gè)等價(jià)關(guān)系

令S是個(gè)集合族(即“所有集合構(gòu)成的集合”)，在S上的等勢關(guān)系~，滿足：⑴自反性：因?yàn)槿魏渭螦有雙射IA:AA,∴A~A⑵對稱性：任何集合A,B，若A~B，有雙射f:AB,

又有雙射f-1

:BA，所以B~A。

⑶傳遞性：任何集合A,B,C，若A~B，且B~C，則有雙射f:AB,和雙射g:BC,由函數(shù)的復(fù)合得雙射：g○

f:AC，所以A~C。所以~是等價(jià)關(guān)系。按照等勢關(guān)系“~”對集合族S，進(jìn)行劃分，得到商集S/~，進(jìn)而得到基數(shù)類的概念。1/5/202435三.基數(shù)類和基數(shù)1.基數(shù)類［定義］

S是集合族，“~”是S上的等勢關(guān)系，相對~的等價(jià)類稱之為基數(shù)類。S={0,Φ，1,{1},{a},…，2,{0,1},{a,b},…，

3,{0,1,2},…，N,I,…，R,…}S/~={[0],[1],[2],[3],…,[N],[R],...}

任何集合A，必屬于且僅屬于一個(gè)等價(jià)類。如{a,b,0,1}[4],因?yàn)閧a,b,0,1}與4(即集合{0,1,2,3})等勢。偶數(shù)集合E={0,2,4,6,8,...}[N],因?yàn)镋~N。1/5/2024362.基數(shù)

[定義]給定集合A，A所屬于的基數(shù)類，稱之為A的基數(shù)，記作K[A]。

如A={1,2},A[2],K[A]=[2],簡記成

K[A]=2

如B={a,b,c},B[3],K[B]=[3],簡記成

K[B]=3采用這種簡單記法，使得對于有限集合A，K[A]=|A|。1/5/202437四.有限集合與無限集合

［定義］凡是和某個(gè)自然數(shù)n等勢的集合，都稱之為有限集合；否則是無限集合。

如A={a,b,c,d,e},A與5({0,1,2,3,4})等勢，故A是有限集。五.可數(shù)集合及其基數(shù)自然數(shù)集合N的基數(shù)

因?yàn)镹不可能與某個(gè)自然數(shù)n等勢。所以N的基數(shù)不能是有限數(shù)，就用一個(gè)“無限大”的數(shù)

0(讀:阿列夫零)表示,即K[N]=0

。1/5/202438可數(shù)集:與自然數(shù)集合N等勢的集合，稱之為可數(shù)集。

A={0,2,4,6,8,…...}f:NAf(n)=2nB={1,3,5,7,9,…...}g:NBg(n)=2n+1C={100,10,102,103,104,,…...}h:NCh(n)=10n

都是可數(shù)集合。至多可數(shù)集：有限集合和可數(shù)集統(tǒng)稱至多可數(shù)集。1/5/202439

整數(shù)集合I~N因?yàn)镮可以寫成：I={0,-1,1,-2,2,-3,3,-4,4,...}即可將I中元素從0開始按照箭頭指定次序排列：0123-1-2-3所以I是可數(shù)集?？蓴?shù)集的判定

定理5-6.1

集合A是可數(shù)集，充分且必要條件是可將A的元素寫成序列形式，即

A={a0,a1,a2,a3,...}1/5/202440有理數(shù)集合Q~N。因?yàn)槊總€(gè)有理數(shù)都可以寫成一個(gè)分?jǐn)?shù)形式如下：0/11/12/13/1-1/1-2/1-3/1-1/2-2/2-3/20/21/22/23/20/31/32/33/3-1/3-2/3-3/3-1/4-2/4-3/40/41/42/43/4.............................................可以從0/1開始按照箭頭指定次序排列Q中元素(如果某個(gè)在前面出現(xiàn)，就跳過去)，所以Q是可數(shù)集。另外I×I~N以及N×N~N如右圖所示。同理可證N×N~N011223-1-1-2-2-31/5/202441六.不可數(shù)集合及其基數(shù)1.實(shí)數(shù)軸上的(0,1)區(qū)間中的實(shí)數(shù)是不可數(shù)的。證明：假設(shè)(0,1)是可數(shù)的，則可以將它的元素寫成如下序列形式：{x1,x2,x3,...},其中

xi=0.ai1ai2ai3……i=1,2,3,…..即0＜xi＜1aik∈{0,1,2,3,4,5,6,7,8,9}k=1,2,3,4,…令x1=0.a11a12a13a14…...x2=0.a21a22a23a24…...………...

xn

=0.an1an2an3an4….....……..構(gòu)造一個(gè)數(shù)b=0.b1b2b3b4…bn……，其中

b1≠a11b2≠

a22b3≠a33…bn≠

ann...

于是

b≠x1,b≠x2,b≠x3...

b≠

xn…∴b(0,1)產(chǎn)生矛盾，所以(0,1)是不可數(shù)的。1/5/2024422.連續(xù)統(tǒng)基數(shù)

⑴

(0,1)區(qū)間的基數(shù)是一個(gè)比N的基數(shù)

0更大的無限大的數(shù),用(阿列夫)表示,即>0

。

⑵

整個(gè)實(shí)數(shù)集合R~(0,1)證明：構(gòu)造函數(shù)f:(0,1)

R

f(x)=tg(πx-π/2)

顯然f是雙射，所以R~(0,1)。

⑶實(shí)數(shù)軸上的任何一段連續(xù)區(qū)間(a,b)的基數(shù)都是，所以稱之為連續(xù)統(tǒng)基數(shù)。011/5/2024433.計(jì)算公式⑴K[A1]=K[A2]=...=K[An]=,則

K[A1∪A2∪...∪An]=

⑵K[A]=K[B]=,則K[A×B

]=

⑶K[A]=

K[B]=

0,(或K[B]=n),(B是多可數(shù)集)則K[A－B

]=

1/5/202444七.基數(shù)的比較

前邊講了基數(shù)相等與否的問題,下面討論諸如和0的大小問題