离散数学及其应用-05 函数

5.1函数的定义和性质5.2函数的复合和反函数第五章函数在数学中,函数是一种特殊的关系,用于描述两个集合之间的一一对应关系。函数的概念在数学中有广泛的应用,包括计算、建模、优化等领域。在计算机科学中,函数不仅用于处理数据和执行计算,还用于编写程序中的函数调用和模块化设计。通过函数的概念,复杂问题可以被分解为更简单的子问题,提高了分析问题和解决问题的效率。5.1函数的定义和性质定义5.1.1

设X，Y为集合，如果f为X到Y的关系(f⊆X×Y)，且对每一x∈X，都有唯一的y∈Y，使<x，y>∈f，称f为X到Y的函数(functions)，记为f：X→Y。当X=X1×X2

×…×Xn

时，称f为n元函数。函数也称映射(mapping)。5.1.1函数的基本概念换言之，函数是特殊的关系，它满足：(1)函数的定义域是X，而不能是X的某个真子集。(2)若<x，y>∈f，<x，y′>∈f，则y＝y′(单值性)。由于函数的第二个特性，人们常把<x，y>∈f或xfy这两种关系表示形式，在f为函数时改为y=f(x)。这时称x为自变元，y为函数在x处的值；也称y为x的像点，x为y的源点。一个源点只能有唯一的像点，但不同的源点允许有共同的像点。注意，函数的上述表示形式不适用于一般关系。(因为一般关系不具有单值性。)5.1.1函数的基本概念【例5.1.1】设A={1,2,3,4},B={a,b,c,d},判断下列集合是否是A到B的函数。f1={<1,a>,<2,a>,<3,d>,<4,c>};f2={<1,a>,<2,a>,<2,a>,<4,c>};f3={<1,a>,<2,b>,<3,d>,<4,a>};f4={<1,a>,<3,d>,<4,c>}。解f1,f3是函数,f2,f4不是函数。5.1.1函数的基本概念

5.1函数的定义和性质定义5.1.2

设f:A→B，g:C→D，如果A=C，B＝D，且对每一x∈A，有f(x)＝g(x)，称函数f等于g，记为f=g。如果A⊆C，B＝D，且对每一x∈A，有f(x)＝g(x)，称函数f包含于g，记为f⊆g。5.1.2函数的类型和常用函数【例5.1.3】设A={a，b}，B={1，2，3}。由A→B能生成多少个不同的函数？由B→A能生成多少个不同的函数？解：设fi:A→B(i=1,2,…，9)，gi:B→A(i=1,2,…，8)。f1={<a，1>，<b，1>}g1={<1，a>，<2，a>，<3，a>}f2={<a，1>，<b，2>}g2={<1，a>，<2，a>，<3，b>}f3={<a，1>，<b，3>}g3={<1，a>，<2，b>，<3，a>}f4={<a，2>，<b，1>}g4={<1，a>，<2，b>，<3，b>}f5={<a，2>，<b，2>}g5={<1，b>，<2，a>，<3，a>}f6={<a，2>，<b，3>}g6={<1，a>，<2，a>，<3，b>}f7={<a，3>，<b，1>}g7={<1，b>，<2，a>，<3，b>}f8={<a，3>，<b，2>}g8={<1，b>，<2，b>，<3，b>}f9={<a，3>，<b，3>}

5.1.2函数的类型和常用函数定理5.1.1

设|A|=m，|B|=n，那么{f|f:A→B}的基数

为nm，即共有nm个A到B的函数。证明：设A={a1，a2，…，am}，B={b1，b2，…，bn}，那么每一个f:A→B由一张如下的表来规定:表中，bi1，bi2，…，bim为取自b1，b2，…，bn的允许元素重复的排列，这种排列总数为nm个。因此，上述形式的表恰有nm张，恰对应全部nm个A到B的函数。证毕5.1.2函数的类型和常用函数当A，B是有穷集合时，我们以BA记所有A到B的全体函数的集合：

BA={f|f:A→B}

则|BA|=|B||A|。特别地AA表示A上函数的全体。目前在计算机科学中，也用A→B替代BA。例4.8.3中，BA={f1，f2，…，f9}，|BA|=9，AB={g1，g2，…，g8}，|AB|=8。5.1.2函数的类型和常用函数该定理当X或Y中至少有一个集合是空集时，可分成下面两种情况：(1)当X＝φ时，X到Y的空关系为一函数，称为空函数，即YX=φφ={φ}。(2)当X≠φ且Y=φ时，X到Y的空关系不是一个函数，即YX=φX=φ。

5.1.2函数的类型和常用函数定义5.1.3

设f:X→Y，A⊆X，称f(A)为A的像(image)，定义为f(A)={y|∃

x(x∈A∧y=f(x))}显然，此时f为X到Y的函数，且f(φ)=φ

，f(X)=Ran(f)，此时f(X)称为函数的像，f({x})={f(x)}(x∈A)。在这里请注意区别函数值和像两个不同的概念。函数值f(x)∈Y，而像f(A)⊆Y。

5.1.2函数的类型和常用函数定理5.1.2

设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)证明：

(1)对任一y∈Y，有

y∈f(A∪B)

x(x∈A∪B∧y=f(x))

x((x∈A∧y=f(x))∨(x∈B∧y=f(x)))

x(x∈A∧y=f(x))∨∃x(x∈B∧y=f(x))

y∈f(A)∨y∈f(B)

y∈f(A)∪f(B)

因此f(A∪B)=f(A)∪f(B)。(2)、(3)的证明请读者完成。注意，(2)、(3)中的包含符号不能用等号代替。我们举例说明。证毕5.1.2函数的类型和常用函数【例5.1.4】设X={a，b，c，d}，Y={1，2，3，4，5}，f:X→Y，如图4.8.1所示。那么，图5.1.15.1.2函数的类型和常用函数f({a})={2}

f({b})={2}

f({a})∩f({b})={2}

f({a})-f({b})=φ

f({a}∩{b})=f(φ)=φ

f({a}-{b})=f({a})={2}

f({a}∩{b})⊂f({a})∩f({b})

f({a})-f({b})⊂f({a}-{b})注意:f(A)={f(x)|x∈A}的写法是不适当的，因为这意味着f(x)∈f(A)

x∈A，但它是与f(A)的定义不相符的，由f(x)∈f(A)并不能确定x∈A。

上例中f(b)=2∈f({a})，但b∉{a}。5.1.2函数的类型和常用函数定义5.1.4

给定函数f:X→Y，

(1)如果函数f

的值域Ranf=Y，则称f:X→Y为满射函数(surjection)，满射函数也称映上的函数。

(2)对于任意x1，x2∈X，若x1≠x2=>

f(x1)≠f(x2)，或者f(x1)=f(x2)=>x1=x2，则称f为单射函数(injection)，单射函数也称一对一的函数。5.1.2函数的类型和常用函数5.1.2函数的类型和常用函数图5-1-2单射、双射及满射函数之间的关系(3)f:X→Y。如果它既是映满的映射，又是一对一的映射，则称f为双射函数(bijection)，双射函数也称一一对应。由定义不难看出，如果f:X→Y是满射的，则对于任意的y∈Y，都存在x∈X，使得y=f(x);如果f:X→Y是单射的，则对于任意的y∈Ranf，都存在唯一的x∈X，使得y=f(x)。图4.8.2说明了这三类函数之间的关系。注意，既非单射又非满射的函数是大量存在的。5.1.2函数的类型和常用函数【例5.1.5】对于给定的f和集合A,请判断f的性质并求A在f下的像f(A)。(1)f:Z→Z,f(x)=3x,A={6}。(2)f:R→R,f(x)=x3+1,A={2,3}。(3)f:Z→N,f(x)=|x|,A={-1,2}。(4)f:R→R×R,f(x)=<x,x2>,A={1,3}。解(1)f是单射,f(A)=f({6})={18}。(2)f是双射,f(A)=f({2,3})={9,28}。(3)f是满射,f(A)=f({-1,2})={1,2}。(4)f是一般函数,f(A)=f({1,3})={<1,1>,<3,9>}。5.1.2函数的类型和常用函数定理5.1.3

设A，B是有穷集合，|A|=|B|，则f:A→B是单射的充分必要条件是f是满射。证明:先证必要性。设f是单射，则|A|=|f(A)|=|B|。因为f(A)B，而B是有穷集合，所以f(A)=B，故f是满射。再证充分性。设f是满射，则f(A)=B。于是|A|=|f(A)|=|B|。又因为A是有穷集合，所以f是单射。证毕注意:

对于无限集合，该定理不成立。如设f:Z→Z

，f(x)=2x，显然f是单射但不是满射。

5.1.2函数的类型和常用函数定义5.1.5

(1)设f:X→Y，如果存在c∈Y，使得对所有的x∈X都有f(x)=c，则称f:X→Y是常函数。(2)任意集合A上的恒等关系IA为一函数，常称为恒等函数，因为对任意x∈A都有IA(x)=x。(3)设<X，≼>，<Y，≼>为偏序集，f:X→Y，如果对任意的x1，x2∈X，x1≺

x2，就有f(x1)≺

f(x2)，则称f为单调递增的；如果对任意的x1，x2∈X，x1

x2，就有f(x1)≺f(x2)，则称f为严格单调递增的。5.1.2函数的类型和常用函数(4)设A为集合，对于任意的A′⊆A，A′的特征函数χA′：A→{0，1}定义为(5)设R是A上的等价关系，令

g:A→A/R

∀a∈A，g(a)=［a］，其中［a］是由a生成的等价类，则称g是从A到商集A/R的自然映射。我们都很熟悉实数集合R上的函数f:R→R，f(x)=x+1，它是单调递增的和严格单调递增的，但它只是上面定义中的单调函数的特例。而在上面的定义中，单调函数可以定义于一般的偏序集合上。5.1.2函数的类型和常用函数【例5.1.6】对于给定的f和集合A,请判断函数类型。(1)f1:R→R×R,f(x)=<x,x>。(2)f2:R→R×R,f(x)=<x,a>。解(1)f1是恒等函数。(2)f2是常函数。关于集合的特征函数:设A为集合,不难证明,A的每一个子集A'都对应于一个特征函数,不同的子集则对应于不同的特征函数。而自然映射g给定集合A和A上的等价关系R,就可以确定一个自然映射g:A→A/R。5.1.2函数的类型和常用函数【例5.1.7】设A={1,2,3},R={<1,2>,<2,1>}∪IA,求自然映射:g1:A→A/EA,g2:A→A/R。解g1(1)=g1(2)=g1(3)=g1(4)=Ag2(1)=g2(2)={1,2},g2(3)={3}注意到,A/EA={{1,2,3}}={A},A/R={{1,2},{3}},所以自然映射都是满射且只有等价关系取IA时是双射。5.1.2函数的类型和常用函数定义5.1.6设A为有限集，p：A→A为一单射函数，那么称p为A上的置换(permutations)。当|A|=n时，称p为n次置换。

置换常用一种特别的形式来表示。设A={a1，a2，…，an}，那么5.1.3置换函数表示一个A上的n次置换，它满足

p(aj)=aij

A上的恒等函数显然为一置换，称为幺置换，用i表示。

5.1.3置换函数定理5.2.1

设f:X→Y，g:Y→Z，那么合成关系f○

g为X到Z的函数。证明:首先证明Dom(f○

g)=X。对任一x∈X，有y∈Y，使<x，y>∈f；对这一y，有z∈Z，使得<y，z>∈g，因此<x，z>∈f○

g

。故x∈Dom(f○

g)。

Dom(f○g)=X得证。再证f○

g的单值性。设对任意x∈X有z1，z2，使<x，z1>∈f○

g，<x，z2>∈f○

g，那么有y1,y2，使<x,y1>∈f，<y1,z1>∈g，<x,y2>∈f，<y2,z2>∈g

。由于f为函数，知y1=y2；又因g为函数，得知z1=z2。f○

g为X到Z的函数得证。证毕5.2.1函数的复合运算我们注意到，<x，z>∈f○

g是指有y使<x，y>∈f，<y，z>∈g，即y=f(x)，z=g(y)=g(f(x))，因而

f○

g(x)=g(f(x))这就是说，当f，g为函数时，它们的合成作用于自变量的次序刚好与合成的原始记号的顺序相反。我们约定，函数合成时，只有当两个函数中一个的定义域与另一个的值域相同时，它们的合成才有意义。5.2.1函数的复合运算【例5.2.1】设A={1,2,3},B={a,b,c}f:A→A,f={<1,2>,<2,3>,<3,2>}g:A→B,g={<1,a>,<2,c>,<3,b>}求fоg和gоf。解fоg={<1,c>,<2,b>,<3,c>}gоf无法计算,因为g的值域不是f的定义域的子集。5.2.1函数的复合运算【例5.2.2】设f,g均为实函数,f(x)=2x,g(x)=(x+1)2,求f

о

g,g

о

f,fоf,gоg。解fоg(x)=g(f(x))=(2x+1)2=4x2+4x+2gоf(x)=f(g(x))=2(x+1)2=2x2+4x+2fоf(x)=f(f(x))=4xgоg(x)=g(g(x))=((x+1)2+1)2=x4+4x3+8x2+8x+45.2.1函数的复合运算推论：函数的复合运算满足结合律，即f○(g○

h)=(f○

g)○

h。证明：因对任意x∈Dom(f)，有

f○(g○

h)(x)=(g○

h)(f(x))

=h(g(f(x))

=h((f○

g)(x))

=(f○

g)○

h(x)

证毕5.2.1函数的复合运算由于函数的合成满足结合律，n个函数f的合成可记为fn，常称为f的n次迭代。

显然

5.2.1函数的复合运算定理5.2.2

设f:X→Y，则

f○

Iy=Ix○

f=f

关于单射的、满射的和双射的函数有下列性质。5.2.1函数的复合运算定理5.2.3

设函数f：X→Y，g：Y→Z，那么

(1)如果f和g是单射的，则f○

g也是单射的。

(2)如果f和g是满射的，则f○

g也是满射的。

(3)如果f和g是双射的，则f○

g也是双射的。5.2.1函数的复合运算证明：

(1)设x1，x2∈X，x1≠x2，由于f为单射，故有

y1≠y2∈Y且y1=f(x1)≠y2=f(x2)

又因为g也是单射，所以有

z1≠z2∈Z且z1=g(y1)≠z2=g(y2)=>g(f(x1))≠g(f(x2))

即f○

g(x1)≠f○

g(x2)

f○

g是单射得证。5.2.1函数的复合运算(2)为证f○

g为满射，设z为Z中任一元素。由于g为满射，因而至少有一y∈Y使g(y)=z。对于这一y，由于f为满射，又必有x∈X使y=f(x)。于是我们找到x，使g(f(x))=z，即f○

g(x)=z。f○

g是满射得证。(3)由(1)、(2)立得。证毕5.2.1函数的复合运算定理5.2.4

设f：X→Y，g：Y→Z，那么

(1)如果f○

g是单射，则f是单射函数。

(2)如果f○

g是满射，则g是满射函数。

(3)如果f○

g是双射，则f是单射函数，g是满射函数。证明：(1)设f○

g是单射，而f并非单射。那么有x1，x2∈X，x1≠x2，使f(x1)=f(x2)，从而

f○

g(x1)=g(f(x1))=g(f(x2))=f○

g(x2)

与g○

f为单射矛盾。因此f为单射。(2)、(3)的证明留给读者。证毕5.2.1函数的复合运算【例5.2.3】设A={1,2,3},请写出A上的所有置换。解5.2.1函数的复合运算定理5.2.5

若f：X→Y为一双射，那么其逆关系f-1为Y到X的函数，称为f的反函数