離散數(shù)學(xué)導(dǎo)論(盤) 教學(xué)課件 作者 王元元 張桂蕓 第六章演示文稿-大學(xué)課件-

*第三六

章消函解

原

數(shù)理第六章

函數(shù)函數(shù)及函數(shù)的合成特殊函數(shù)類函數(shù)的逆Δ

6.4

函數(shù)、謂詞、集合第六章

函

數(shù)函數(shù)及函數(shù)的合成函數(shù)的基本概念函數(shù)概念的拓廣函數(shù)的合成第六章

函

數(shù)特殊函數(shù)類單射的、滿射的和雙射的函數(shù)Δ

6.2.2

規(guī)范映射、單調(diào)映射和連續(xù)映射第六章

函

數(shù)函數(shù)及函數(shù)的合成函數(shù)的基本概念定義6.1設(shè)X，Y為集合，稱f為X到Y(jié)的函數(shù)（functions），記為

f：X→Y，如果

f

為X到

Y的關(guān)系（f

X

Y），且對每一

x

X，都有唯一的

y

Y，使

<x

,

y>

f

。當(dāng)X=X1

…

Xn時，稱

f

為n元函數(shù)。函數(shù)也稱映射（mapping）或變換(transformation）。第六章

函

數(shù)函數(shù)及函數(shù)的合成函數(shù)的基本概念定義6.2設(shè)

f:A→B，g:C→D，稱函數(shù)f等于g,

記為f

=

g，如果A

=

C，B＝D，且對每一x

A，f(x)＝g(x)稱函數(shù)

f

包含于

g，記為f

g，如果A

C，B＝D，且對每一x

A，f

(x)

＝

g

(x)

。第六章

函

數(shù)函數(shù)及函數(shù)的合成函數(shù)的基本概念√定理6.1設(shè)

X

=

m，

Y

=

n，那么{f

f:

X→Y}的基數(shù)為nm

。即共有nm個X到Y(jié)的函數(shù)。第六章

函

數(shù)函數(shù)及函數(shù)的合成函數(shù)的基本概念定義6.3設(shè)f:X→Y，AX，稱f’(A)為A的映像（image），定義為f’(A)={y

x(x A∧y=f(x))}顯然，f’為ρ(X)到ρ(Y)的函數(shù)，且f

’({f

(x)}

(x)

=

,

f

’(X)

=Ran(f)

,

f

’({x})

=A)第六章

函

數(shù)函數(shù)及函數(shù)的合成函數(shù)的基本概念√定理6.2設(shè)f:

X→Y，對任意A

X，B

X，（1）f

’(A∪B)

=

f

’(A)∪f

’(B)（2）f

’(A∩B)

f

’(A)∩f

’(B)（3）f

’(A)

-

f

’(B)

f

’(A

-

B)第六章

函

數(shù)定義6.4設(shè)

f

XY，稱f為X到Y(jié)的一個偏函數(shù)（partial

functions），如果f

滿足下列條件：對任意

x

X，y1，y2

Y，若<x

,

y1>

f，<x

,

y2>

f，則y1

=

y2

。6.1

函數(shù)及函數(shù)的合成6.1.2

函數(shù)概念的拓廣vv第六章

函

數(shù)6.1

函數(shù)及函數(shù)的合成6.12

函數(shù)概念的拓廣定義6.6設(shè)f為X到Y(jié)的偏函數(shù)，g為A到Y(jié)的偏函X，且對每一x A，f(x)=

g(x)數(shù)，A(即g

f

)，那么g

稱為f

在A上的限制（restriction），特記為f↑A

。第六章

函

數(shù)6.1

函數(shù)及函數(shù)的合成6.12

函數(shù)概念的拓廣定義6.5設(shè)

f

為A到Y(jié)的偏函數(shù)，g

為X到

Y的偏函數(shù)，

A

X，且對每一x

A，f(x)

=

g(x)

(即f

g)，,那么稱偏函數(shù)g為

f

的擴充（extention）。第六章

函

數(shù)6.1

函數(shù)及函數(shù)的合成6.1.3

函數(shù)的合成√定理6.3設(shè)f:X→Y，g:Y→Z，那么合成關(guān)系f○g為X到Z的函數(shù)。第六章函

數(shù)特殊函數(shù)類單射的、滿射的和雙射的函數(shù)定義6.7

設(shè)f：X→Y。（1）稱

f

為X到Y(jié)的單射函數(shù)，或單射（injection），

如對任意x1，x2 X

,

x1

x2

蘊涵

f(x1)

f(x2)。單射函數(shù)也稱—的函數(shù)。稱

f

為X到Y(jié)的滿射函數(shù)，或滿射（surjection），如對任意

y

Y，均有

x

X，使

y

=

f(x)。滿射函數(shù)也稱映上的函數(shù)。稱f為X到Y(jié)的雙射函數(shù)，或雙射（bejection），如果既是X到Y(jié)的單射，又是X到Y(jié)的滿射。雙射函數(shù)也稱一一對應(yīng)。第六章

函

數(shù)特殊函數(shù)類單射的、滿射的和雙射的函數(shù)定理6.4設(shè)f：X→Y，g：Y→Z，那么如果f和g是單射的，則g○f也是單射。如果f和g是滿射的，則g○f也是滿射的如果f和g是雙射的，則g○f也是雙射的第六章

函

數(shù)特殊函數(shù)類單射的、滿射的和雙射的函數(shù)定理6.5設(shè)f：X→Y，g：Y→Z，那么若g○f是單射，則f是單射。若g○f

是滿射，則g

是滿射。若g○f

是雙射，則f

是單射，g

是滿射。第六章

函

數(shù)特殊函數(shù)類單射的、滿射的和雙射的函數(shù)定義6.8設(shè)X為有限集，p：X→X為一雙射，那么稱p

為X上的置換（permutation）。當(dāng)

X

=

n時，稱p

為n次置換。第六章

函

數(shù)6.2Δ

6.2.2特殊函數(shù)類規(guī)范映射、單調(diào)映射和連續(xù)映射定義6.9設(shè)f：X→Y，稱關(guān)系ker(f)為函數(shù)f的核（kernel定義ker(f)={<x1,x2>

x1,x2

X,且f(x1)＝f(x2)}第六章

函

數(shù)6.2Δ

6.2.2特殊函數(shù)類規(guī)范映射、單調(diào)映射和連續(xù)映射√定理6.6設(shè)f：X→Y，那么ker(f)為X上的等價關(guān)系。于是有X的劃分X/ker(f)。第六章

函

數(shù)6.2Δ

6.2.2特殊函數(shù)類規(guī)范映射、單調(diào)映射和連續(xù)映射√定理6.7對任意函數(shù)f：X→Y，存在一個雙射h：X/ker(f)→Ran(f)。定理6.7中雙射h常稱為規(guī)范映射（canonical

mapping）。第六章

函

數(shù)6.2Δ

6.2.2特殊函數(shù)類規(guī)范映射、單調(diào)映射和連續(xù)映射√定理6.8√對任意函數(shù)f：X→Y，存在三個函數(shù)，g：X→X/ker(f)，h：X/ker(f)→Ran(f)，k：Ran(f)→Y，使g為滿射，h為雙射，k為單射，且f=k○h○g。第六章

函

數(shù)6.2Δ

6.2.2特殊函數(shù)類規(guī)范映射、單調(diào)映射和連續(xù)映射定義6.10設(shè)<X,

≤1>，<Y,

≤2>為有序集，稱函數(shù)f：X→

Y為X到Y(jié)的單調(diào)映射（monotonic

mapping），如果對任意x1，x2

X滿足x1≤1x2蘊涵f(x1)≤2f(x2)稱f為X到Y(jié)的嚴(yán)格單調(diào)映射（monotonicmapping）如果對任意x1，x2X，它滿足x1≤1x2

∧

x1

x2

蘊涵f(x1)≤2f(x2)

∧

f(x1)

f(第六章

函

數(shù)6.2Δ

6.2.2特殊函數(shù)類規(guī)范映射、單調(diào)映射和連續(xù)映射√定理6.9設(shè)<X,≤1>，<Y,≤2>為有序集，f：X→Y，g：Y→Z為單調(diào)映射，那么g○f為X到Z的單調(diào)映射。√定理6．10設(shè)<X,≤1>，<Y,≤2>為有序集，L

X為X中的≤1鏈，f：X→Y為單調(diào)映射，那么

f’(L)為Y中的≤2鏈。第六章

函

數(shù)6.2Δ

6.2.2特殊函數(shù)類規(guī)范映射、單調(diào)映射和連續(xù)映射定義6.11設(shè)<X,

≤1>，<Y,

≤2>為完備序集，稱f：X→Y為連續(xù)映射（continuous

mapping），如果對X中每一≤1鏈L，f

’(L)的上確界sup

f

’(L)存在且等于f(supL)(supL為L的上確界)。第六章

函

數(shù)6.2Δ

6.2.2特殊函數(shù)類規(guī)范映射、單調(diào)映射和連續(xù)映射√定理6.11設(shè)<X,≤1>，<Y,≤2>為完備序集。若f：X→Y為連續(xù)映射，那么f必為X到Y(jié)的單調(diào)映射。√定理6.12設(shè)<X,≤1>，<Y,≤2>為完備序集，f：X→Y為單調(diào)映射，若對每一鏈L

X，總有f(supL)≤2

sup

f’(L)那么f是一連續(xù)映像。第六章

函

數(shù)6.2Δ

6.2.2特殊函數(shù)類規(guī)范映射、單調(diào)映射和連續(xù)映射√定理6.13設(shè)<X,

≤1>，<Y,

≤2>，<Z

≤3>均為完備序集，f

:

X→Y,

g:

Y→Z都是連續(xù)映射，那么g○f：X→Z

也是連續(xù)映射。√定理6.14若f：X→Y為一雙射，那么f~為Y到X的函數(shù)，記為f

-1,f

-1：Y→X為一雙射。第六章

函

數(shù)6.3

函數(shù)的逆√定理6.15若f：X→Y是可逆的，那么（1）(f

-1)

-1=

f（2）f

-1○

f

=

EX,

f

○

f

-1

=

EY第六章

函

數(shù)6.3

函數(shù)的逆√定理6.16設(shè)f：X→Y，g：Y→Z都是可逆的，那么g○f也是可逆的，且(g○f)–1

=f

-1○g–1√定義6.12設(shè)f：X→Y，g：Y→X，稱g為f的左逆

函數(shù)（或左逆），如果g○f=Ex稱g為f的右逆函數(shù)（或右逆）第六章

函

數(shù)6.3

函數(shù)的逆√定理6.17√設(shè)f：X→Y。（1）f

有左逆當(dāng)且僅當(dāng)f為一單射。（2）f

有右逆當(dāng)且僅當(dāng)f為一滿射。第六章

函

數(shù)6.3

函數(shù)的逆√定理6.18設(shè)f：X→Y，那么下列三命題等價：（1）f

可逆，即f有逆函數(shù)f

-1。（2）存在函數(shù)g：Y→X，g既為f的左逆，又為f的右逆。（3）f

既有左逆，又有右逆。第六章

函

數(shù)6.3

函數(shù)的逆定義6.13設(shè)f：X→Y，Af

”(A)

=

{xY，定義f(x)

A}稱f”(A)為A的逆象（inverse

image）。第六章

函

數(shù)6.3

函數(shù)的逆√定理6.19設(shè)f：X→Y，那么（1）f

-1(Y)

=

f

-1(Ran(f))

=

XY，則f’(f-1(A))B

Y，則f

-1(A)

f

-1(B)A若A若A若AX，則A

f

-1

(f

’(A))第六章

函

數(shù)6.3

函數(shù)的逆√定理6.20設(shè)f：X→Y，那么X/ker(f)

=

{C

y(yY∧f

-1({y})

=

C)}第六章

函

數(shù)定義6.14設(shè)U為全集，那么U到{0,1}的函數(shù)統(tǒng)稱為特征函數(shù)（characteristic

functions）。設(shè)A為一集合（A

U），那么稱下列特征函數(shù)為集合A的特征函數(shù)：Δ

6.4函數(shù)、謂詞、集合第六章

函

數(shù)Δ

6.4

函數(shù)、謂詞、集合√定理6.21在U的全體子集（記為ρ(U)）與全體特征函數(shù)（記為{0,1}U）之間存在雙射Ψ:ρ(U)→{0,1}U

。第六章

函

數(shù)Δ

6.4函數(shù)、謂詞、集合√定理