离散数学1集合论与图论课件chapter

第9讲函数2021/7/3《集合论与图论》第9讲1内容提要函数,偏函数,全函数,真偏函数单射,满射,双射,计数问题象,原象常数函数,恒等函数,特征函数,单调函数,自然映射合成(复合),反函数,单边逆(左逆,右逆)构造双射(有穷集,无穷集)函数(function),映射(mapping)单值的二元关系称为函数或映射单值:"x˛

domF,"y,z˛

ranF,xFy xFz

fi

y=zF(x)=y

<x,y>˛

F

xFy˘

是空函数常用F,G,H,…,f,g,h,…表示函数.xyz非单值2021/7/3《集合论与图论》第9讲2单值偏函数(partial

function)偏函数:

domF˝

AA到B的偏函数:

domF˝

A

ranF˝B偏函数记作F:Afi

B,称A为F的前域,A到B的全体偏函数记为Afi

BAfi

B

=

{

F

|

F:Afi

B

}2021/7/3《集合论与图论》第9讲3例1例1:设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}.

#非函数:{<a,1>,<a,2>},

{<b,1>,<b,2>},{<a,1>,<a,2>,<b,1>},…2021/7/3《集合论与图论》第9讲4全函数(total

function)全函数:domF=A全函数记作F:Afi

BA到B的全体全函数记为BA或Afi

B BA

=Afi

B={F

|

F:Afi

B}2021/7/3《集合论与图论》第9讲5关于BA的说明BA

=

Afi

B

=

{F|F:Afi

B}={F|F是A到B的全函数}|BA|

=

|B||A|.当A=˘

时,BA={˘

}当A„˘

且B=˘

时,BA=Afi

B=˘

,但Afi

B={˘

}.2021/7/3《集合论与图论》第9讲6真偏函数(proper

partial

function)真偏函数:

domF

A,真偏函数记作F:Afi

B,A到B的全体真偏函数记为Afi

BAfi

B

=

{

F

|

F:Afi

B

}2021/7/3《集合论与图论》第9讲7例1(续)例1(续):设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三者关系Afi

B

=

Afi

B

¨

Afi

B偏函数Afi

BdomF˝

A全函数Afi

BdomF=A真偏函数Afi

BdomF

A2021/7/3《集合论与图论》第9讲9全函数性质设F:Afi

B,单射(injection):F是单根的满射(surjection):ranF=B双射(bijection):F既是单射又是满射,亦称为一一对应(one-to-one

mapping).非单射非满射2021/7/3《集合论与图论》第9讲10例22021/7/3《集合论与图论》第9讲11例2:

设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>}.

#计数(counting)问题2021/7/3《集合论与图论》第9讲15设|A|=n,|B|=m,

问Afi

B中有多少单射,满射,双射?n<m时,Afi

B中无满射,双射,单射个数为m(m-1)…(m-n+1)n=m时,Afi

B中双射个数为n!n>m时,Afi

B中无单射,双射,满射个数为.mm!

n

例32021/7/3《集合论与图论》第9讲16A,B是非空有穷集,讨论下列函数的性质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)>当|B|>1时,g是单射,非满射,非双射当|B|=1时,g是单射,满射,双射f:A·Bfi

A,

"

<a,b>˛

A·B,f(<a,b>)=a当|B|>1时,f非单射,是满射,非双射当|B|=1时,f是单射,满射,双射f:A·Bfi

B·A,"

<a,b>˛A·B,

f(<a,b>)=<b,a>f是单射,满射,双射象(image),原象(preimage)设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设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设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.

#特殊函数2021/7/3《集合论与图论》第9讲22常数函数:f:Afi

B,$b˛

B,"x˛A,

f(x)=b恒等函数:IA:Afi

A,IA(x)=x特征函数:

cA:Efi

{0,1},

cA(x)=1

x˛A单调函数:f:Afi

B,<A,£A>,<B,£B>偏序集单调增:

"

x,y˛

A, x£Ay

f(x)£Bf(y)单调减:

"

x,y˛

A, x£Ay

f(y)£Bf(x),严格单调:

把£换成<自然映射:f:Afi

A/R,f(x)=[x]R,R为A上等价关系自然映射(举例)例: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函数运算2021/7/3《集合论与图论》第9讲24合成(复合):性质,左(右)单位元,单调性反函数:存在条件(双射才有反函数)单边逆:左逆,右逆,存在条件函数合成(composite)定理3:

设g:Afi

B,

f:Bfi

C,则f○g:

Afi

C,

f○g(x)=f(g(x)).证明思路:f○g是函数(即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是函数,即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:设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:设g:Afi

B,f:Bfi

C,则若f○g为满射,则f是满射.若f○g为单射,则g是单射.若f○g为双射,

则g是单射,f是满射.

#g2021/7/3《集合论与图论》第9讲30gf定理6定理6:

设

f:Afi

B,

则

f=f○IA

=IB○f.

#A2021/7/3《集合论与图论》第9讲31ABBIAIBf定理7(单调性)2021/7/3《集合论与图论》第9讲32定理7:

设

f:Rfi

R,g:Rfi

R,且f,g按£是单调增的,

则f○g也是单调增的.证明: x£y

g(x)£g(y)

f(g(x))£f(g(y)).#反函数(inverse

function)2021/7/3《集合论与图论》第9讲33定理8:设A为集合,则A-1为函数

A为单根的.

#推论:设R为二元关系,则R为函数

R-1为单根的.

#定理9:设f:Afi

B,且为双射,则f-1

:Bfi

A,

且也为双射.

#反函数:若f:Afi

B为双射,则f-1

:Bfi

A称为f的反函数.构造双射及求反函数|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:构造N·Nfi

N

双射?2021/7/3《集合论与图论》第9讲35方法1:用自然数性质2021/7/3《集合论与图论》第9讲36"n˛N n„0,$a,b˛

N,b为奇数,使得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为奇数"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)对应的自然数为(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