離散數(shù)學(xué)1集合論與圖論課件chapter

第9講函數(shù)2021/7/3《集合論與圖論》第9講1內(nèi)容提要函數(shù),偏函數(shù),全函數(shù),真偏函數(shù)單射,滿射,雙射,計數(shù)問題象,原象常數(shù)函數(shù),恒等函數(shù),特征函數(shù),單調(diào)函數(shù),自然映射合成(復(fù)合),反函數(shù),單邊逆(左逆,右逆)構(gòu)造雙射(有窮集,無窮集)函數(shù)(function),映射(mapping)單值的二元關(guān)系稱為函數(shù)或映射單值:"x?

domF,"y,z?

ranF,xFy xFz

fi

y=zF(x)=y

<x,y>?

F

xFy?

是空函數(shù)常用F,G,H,…,f,g,h,…表示函數(shù).xyz非單值2021/7/3《集合論與圖論》第9講2單值偏函數(shù)(partial

function)偏函數(shù):

domF?

AA到B的偏函數(shù):

domF?

A

ranF?B偏函數(shù)記作F:Afi

B,稱A為F的前域,A到B的全體偏函數(shù)記為Afi

BAfi

B

=

{

F

|

F:Afi

B

}2021/7/3《集合論與圖論》第9講3例1例1:設(shè)A={a,b},

B={1,2},

求Afi

B.解:|A|=2,|B|=2,|A·B|=4,|P(A·B)|=24=16.f0=?

,f1={<a,1>},

f2={<a,2>},f3={<b,1>},

f4={<b,2>},f5={<a,1>,<b,1>},

f6={<a,1>,<b,2>},f7={<a,2>,<b,1>},f8={<a,2>,<b,2>}.Afi

B

=

{f0,f1

,f2,f3

,f4

,f

5,f6

,f7,f8}.

#非函數(shù):{<a,1>,<a,2>},

{<b,1>,<b,2>},{<a,1>,<a,2>,<b,1>},…2021/7/3《集合論與圖論》第9講4全函數(shù)(total

function)全函數(shù):domF=A全函數(shù)記作F:Afi

BA到B的全體全函數(shù)記為BA或Afi

B BA

=Afi

B={F

|

F:Afi

B}2021/7/3《集合論與圖論》第9講5關(guān)于BA的說明BA

=

Afi

B

=

{F|F:Afi

B}={F|F是A到B的全函數(shù)}|BA|

=

|B||A|.當(dāng)A=?

時,BA={?

}當(dāng)A??

且B=?

時,BA=Afi

B=?

,但Afi

B={?

}.2021/7/3《集合論與圖論》第9講6真偏函數(shù)(proper

partial

function)真偏函數(shù):

domF

A,真偏函數(shù)記作F:Afi

B,A到B的全體真偏函數(shù)記為Afi

BAfi

B

=

{

F

|

F:Afi

B

}2021/7/3《集合論與圖論》第9講7例1(續(xù))例1(續(xù)):設(shè)A={a,b},B={1,2},求Afi

B.解:f0=?

,f1={<a,1>},f2={<a,2>},f3={<b,1>},

f4={<b,2>},f5={<a,1>,<b,1>},

f6={<a,1>,<b,2>},f7={<a,2>,<b,1>},f8={<a,2>,<b,2>}.Afi

B={f0

,f1

,f2

,f3

,f4}.

#說明:F?Afi

B

F?

domFfi

B F?Afi

B

F?

domFfi

B2021/7/3《集合論與圖論》第9講8三者關(guān)系A(chǔ)fi

B

=

Afi

B

¨

Afi

B偏函數(shù)Afi

BdomF?

A全函數(shù)Afi

BdomF=A真偏函數(shù)Afi

BdomF

A2021/7/3《集合論與圖論》第9講9全函數(shù)性質(zhì)設(shè)F:Afi

B,單射(injection):F是單根的滿射(surjection):ranF=B雙射(bijection):F既是單射又是滿射,亦稱為一一對應(yīng)(one-to-one

mapping).非單射非滿射2021/7/3《集合論與圖論》第9講10例22021/7/3《集合論與圖論》第9講11例2:

設(shè)A1={a,b},

B1={1,2,3},A2={a,b,c},

B2={1,2},A3={a,b,c},

B3={1,2,3},求A1fi

B1,A2fi

B2,A3fi

B3中的單射,滿射,雙射.例2(解(1))2021/7/3《集合論與圖論》第9講12例2:

(1)

A1={a,b},

B1={1,2,3},解:(1)A1fi

B1中無滿射,無雙射,單射6個:f1={<a,1>,<b,2>},f3={<a,2>,<b,1>},f5={<a,3>,<b,1>},f2={<a,1>,<b,3>},f4={<a,2>,<b,3>},f6={<a,3>,<b,2>}.例2(解(2))2021/7/3《集合論與圖論》第9講13例2:

(2)

A2={a,b,c},

B2={1,2},解:(2)A2fi

B2中無單射,無雙射,滿射6個:f1={<a,1>,<b,1>,<c,2>},f2={<a,1>,<b,2>,<c,1>},f3={<a,2>,<b,1>,<c,1>},f4={<a,1>,<b,2>,<c,2>},f5={<a,2>,<b,1>,<c,2>},f6={<a,2>,<b,2>,<c,1>}.例2(解(3))2021/7/3《集合論與圖論》第9講14例2:

(3)

A3={a,b,c},

B3={1,2,3},解:(3)A2fi

B2中雙射6個:f1={<a,1>,<b,2>,<c,3>},f2={<a,1>,<b,3>,<c,2>},f3={<a,2>,<b,1>,<c,3>},f4={<a,2>,<b,3>,<c,1>},f5={<a,3>,<b,1>,<c,2>},f6={<a,3>,<b,2>,<c,1>}.

#計數(shù)(counting)問題2021/7/3《集合論與圖論》第9講15設(shè)|A|=n,|B|=m,

問Afi

B中有多少單射,滿射,雙射?n<m時,Afi

B中無滿射,雙射,單射個數(shù)為m(m-1)…(m-n+1)n=m時,Afi

B中雙射個數(shù)為n!n>m時,Afi

B中無單射,雙射,滿射個數(shù)為.mm!

n

例32021/7/3《集合論與圖論》第9講16A,B是非空有窮集,討論下列函數(shù)的性質(zhì)f:Afi

B,

g:Afi

A·B,

"

a?

A,g(a)=<a,f(a)>f:A·Bfi

A,

"

<a,b>?

A·B,f(<a,b>)=af:A·Bfi

B·A,

"

<a,b>?

A·B,f(<a,b>)=<b,a>例3(解)2021/7/3《集合論與圖論》第9講17f:Afi

B,g:Afi

A·B,

"

a?

A,

g(a)=<a,f(a)>當(dāng)|B|>1時,g是單射,非滿射,非雙射當(dāng)|B|=1時,g是單射,滿射,雙射f:A·Bfi

A,

"

<a,b>?

A·B,f(<a,b>)=a當(dāng)|B|>1時,f非單射,是滿射,非雙射當(dāng)|B|=1時,f是單射,滿射,雙射f:A·Bfi

B·A,"

<a,b>?A·B,

f(<a,b>)=<b,a>f是單射,滿射,雙射象(image),原象(preimage)設(shè)f:Afi

B,A’?

A,

B’?BA’的象是f(A’)

=

{y|$x(x?

A’ f(x)=y)}?

Bf(A)

=

ranfB’的原象是f

-1(B’)=

{x|$y(y?

B’ f(x)=y)}?

Af(A’)A’

f

-1(B’)

B’2021/7/3《集合論與圖論》第9講18象,原象(舉例)2021/7/3《集合論與圖論》第9講19例:

f:Nfi

N,

f(x)=2x.A’=N偶={0,2,4,6,…}={2k|k?

N},f(A’)={0,4,8,12,…}={4k|k?

N}B’={2+4k|k?

N}={2,6,10,14,…},f

-1(B’)={1+2k|k?

N}={1,3,5,7,…}=N奇#定理3.12021/7/3《集合論與圖論》第9講20設(shè)f:Cfi

D為單射,C為C的非空子集族.C1,C2?

C,則f(¨

C)

=

¨

{f(A)|A?

C}f(˙

C)

=

˙{f(A)|A?

C}f(C1-C2)

=

f(C1)-f(C2).證明:

利用定理2.9和f的單射性.

#定理3.22021/7/3《集合論與圖論》第9講21設(shè)f:Cfi

D,D1,D2?

D,D是D的非空子集族.則f

-1(¨

D)=

¨

{f

-1(D)|D?

D}f

-1(˙

D)=

˙

{f

-1(D)|D?

D}f

-1(D1-D2)=

f

-1(D1)-f-1(D2).證明:

利用定理2.9.

#特殊函數(shù)2021/7/3《集合論與圖論》第9講22常數(shù)函數(shù):f:Afi

B,$b?

B,"x?A,

f(x)=b恒等函數(shù):IA:Afi

A,IA(x)=x特征函數(shù):

cA:Efi

{0,1},

cA(x)=1

x?A單調(diào)函數(shù):f:Afi

B,<A,￡A>,<B,￡B>偏序集單調(diào)增:

"

x,y?

A, x￡Ay

f(x)￡Bf(y)單調(diào)減:

"

x,y?

A, x￡Ay

f(y)￡Bf(x),嚴(yán)格單調(diào):

把￡換成<自然映射:f:Afi

A/R,f(x)=[x]R,R為A上等價關(guān)系自然映射(舉例)例:A={a,b,c,d,e,f},A/R={{a,b},{c,d,e},{f}},[a]=[b]={a,b},

[c]=[d]=[e]={c,d,e},

[f]={f},F:Afi

A/R,

F(x)=[x].F(a)={a,b},

F(b)={a,b},

F(

c

)={c,d,e},F(d)={c,d,e},

F(e)={c,d,e},

F(f)={f}.

#b2021/7/3《集合論與圖論》第9講23a

cdef函數(shù)運算2021/7/3《集合論與圖論》第9講24合成(復(fù)合):性質(zhì),左(右)單位元,單調(diào)性反函數(shù):存在條件(雙射才有反函數(shù))單邊逆:左逆,右逆,存在條件函數(shù)合成(composite)定理3:

設(shè)g:Afi

B,

f:Bfi

C,則f○g:

Afi

C,

f○g(x)=f(g(x)).證明思路:f○g是函數(shù)(即f○g單值)dom

f○g

=

Aran

f○g

?

C,

f○g(x)=f(g(x))2021/7/3《集合論與圖論》第9講25定理3(證明)2021/7/3《集合論與圖論》第9講26證明:(1)f○g是函數(shù),即f○g是單值的."

x?dom(f○g),

若$z1,z2?

ran(f○g),則x(f○g)z1

x(f○g)z2$y1(y1?

B

xgy1

y1fz1)

$y2(y2?

B

xgy2

y2fz2)xgy2$y1$y2(y1?

B

y2?B

xgy1

y1fz1

y2fz2)$y(y?

B

y1=y2=y

y1fz1

y2fz2)z1=z2定理3(證明)2021/7/3《集合論與圖論》第9講27證明:(2)dom(f○g)=A.顯然dom(f○g)?

A,下證A?

dom(f○g),"

x,

x?A

$!y(y?

B

xgy)

$!y$!z(y?

B

z?C

xgy

yfz)

$!z(z?

C

x(f○g)z)

x?

dom(f○g).定理3(證明)2021/7/3《集合論與圖論》第9講28證明:(3)f○g(x)=f(g(x)).由(1)(2)知ran(f○g)?

C,"

x,x?

A

$!z(z?

C

z=f○g(x))$!z$!y(z?

C

y?B

y=g(x)

z=f(y))$!z(z?

C

z=f(g(x)))所以對任意x

?A,有,f○g(x)=f(g(x)).#定理4定理4:設(shè)g:Afi

B,f:Bfi

C,f○g:Afi

C,則f,g均為滿射,則f○g也是滿射.f,g均為單射,則f○g也是單射.f,g均為雙射,

則

f○g也是雙射.

#2021/7/3《集合論與圖論》第9講29定理5定理5:設(shè)g:Afi

B,f:Bfi

C,則若f○g為滿射,則f是滿射.若f○g為單射,則g是單射.若f○g為雙射,

則g是單射,f是滿射.

#g2021/7/3《集合論與圖論》第9講30gf定理6定理6:

設(shè)

f:Afi

B,

則

f=f○IA

=IB○f.

#A2021/7/3《集合論與圖論》第9講31ABBIAIBf定理7(單調(diào)性)2021/7/3《集合論與圖論》第9講32定理7:

設(shè)

f:Rfi

R,g:Rfi

R,且f,g按￡是單調(diào)增的,

則f○g也是單調(diào)增的.證明: x￡y

g(x)￡g(y)

f(g(x))￡f(g(y)).#反函數(shù)(inverse

function)2021/7/3《集合論與圖論》第9講33定理8:設(shè)A為集合,則A-1為函數(shù)

A為單根的.

#推論:設(shè)R為二元關(guān)系,則R為函數(shù)

R-1為單根的.

#定理9:設(shè)f:Afi

B,且為雙射,則f-1

:Bfi

A,

且也為雙射.

#反函數(shù):若f:Afi

B為雙射,則f-1

:Bfi

A稱為f的反函數(shù).構(gòu)造雙射及求反函數(shù)|A|=m,

|B|=n,Afi

B存在雙射

n=m|A|=￥,|B|=￥,B A,Afi

B可存在雙射,如 f:Nfi

N-{0,1,2},f(n)=n+30

1

2

3

4

5

6

7

80

1

2

3

4

5

6

7

8[0,1]fi

(0,1)

?

Rfi

(0,1)

?N·Nfi

N

?2021/7/3《集合論與圖論》第9講34例6:構(gòu)造N·Nfi

N

雙射?2021/7/3《集合論與圖論》第9講35方法1:用自然數(shù)性質(zhì)2021/7/3《集合論與圖論》第9講36"n?N n?0,$a,b?

N,b為奇數(shù),使得n=2ab例:1=20·1,2=21·1,3=20·3,…, 6=21·3,…,100=22·25,…令n=2ab-1,可以去掉n?0的條件令b=2j+1,b為奇數(shù)"n?

N,n=2i(2j+1)-1,i,j?

N,此表示唯一.方法1:f:N·Nfi

N2021/7/3《集合論與圖論》第9講37f:N·Nfi

N, f

-1:Nfi

N·N,

"

<i,j>?N·N,f(<i,j>)=2i(2j+1)-1,f

-1(n)=f

-1(2i(2j+1)-1)=<i,j>.例:f(<0,0>)=0,f(<0,1>)=2,f(<1,0>)=1,…f

-1(5)=<1,1>,

f

-1(101)=<1,25>,f-1(200)=<0,100>,…方法2:Cantor編碼—對角線法<m,n><m,0><m+n,0>1+2+3+…+(m+n)+(m+1)=(m+n)(m+n+1)/2+(m+1)對應(yīng)的自然數(shù)為(m+n)(m+n+1)/2+m2021/7/3《集合論與圖論》第9講38方法2:f:N·Nfi

Nf:N·Nfi

N, f

-1:Nfi

N·N,

"

<m,n>?N