离散数学函数的复合与反函数

离散数学函数的复合与反函数第一页，共二十四页，2022年，8月28日由于函数是一种特殊的二元关系，两个函数的复合本质上就是两个关系的合成，因此函数的合成方法与关系的合成方法是一致的。由图可知f和g合成后的函数称为复合函数，记为g∘f。且g∘f={<1,2>,<2,2>,<3,1>}。

例如:已知f是A到B的函数，g是B到C的函数，它们所确定的对应关系如图所示。f={<1,1>,<2,1>,

<3,4>}，

g={<1,2>,<2,2>,<3,2>,<

4,1>}，第二页，共二十四页，2022年，8月28日由于函数是一种特殊的二元关系同，两个函数的复合本质上就是两个关系的合成。例如设f是A到B的函数，g是B到C的函数，它对所确定的对应关系如图所示：如果将函数f看作是A到B的二元关系，g看作是B到C的二元关系，合成后的关系记为R，它是A到C的二元关系，记为R=f∘g，且R={(x,b),(y,b),(z,a)}.f={<x,1>,<y,1>,

<z,4>}，

g={<1,b>,<2,b>,<3,b>,<

4,a>}，第三页，共二十四页，2022年，8月28日一、复合函数的定义设f是A到B的函数，g是B到C的函数，f和g合成后的函数称为复合函数，记为g

∘

f。它是A到C的函数。当a∈A,b∈B,c∈C，且f(a)=b,f(b)=c时，g∘f(a)=c.注意：当f和g看作是二元关系时，合成后的关系记为f∘g，但当f和g看作是函数时f和g合成后的函数称为复合函数，记为g

∘

f。第四页，共二十四页，2022年，8月28日定理设F,G是函数,则F∘G也是函数,且满足

(1)dom(F∘G)={x|x∈domF

F(x)∈domG}

(2)x∈dom(F∘G)有F∘G(x)=F(G(x))

第五页，共二十四页，2022年，8月28日例：设集合A={x,y,z},B={a,b,c,d},C={1,2,3}

f是A到B的函数，g是B到C的函数，其中

f(x)=b,f(y)=c,f(z)=cg(a)=1,g(b)=2,g(c)=1,

g(d)=3求复合函数g∘f。解：由定义可知复合函数g∘f是A到C的函数。且g∘f(x)=g(f(x))=g(b)=2.g∘f(y)=g(f(y))=g(c)=1.g∘f(z)=g(f(z))=g(c)=1.推论1

设f：A→B,g：B→C,则f∘g：A→C,且

x∈A都有f∘g(x)=f(g(x)).

第六页，共二十四页，2022年，8月28日推论2

设F,G,H为函数,则(F∘G)∘H和F∘(G∘H)

都是函数,且(F∘G)∘H=F∘(G∘H)由于函数是一种特殊的二元关系，而二元关系的合成可以看作是一种运算，且这种运算满足结合律但不满足交换律。于是有：推论3

设F,G为函数,则F∘G和G∘F

都是函数,且F∘G≠G∘F

第七页，共二十四页，2022年，8月28日函数复合运算的性质定理设f：A→B,g：B→C.

(1)如果f和

g都是单射函数,则g∘f

：A→C也是单射的函数.

(2)如果f和

g都是满射函数,则g∘f

：A→C也是满射的函数.

(3)如果f和

g都是双射函数,则g∘f

：A→C也是双射的函数.

证(1)c∈C,由g：B→C的满射性,b∈B使得

g(b)=c.对这个b,由f：A→B的满射性，a∈A

使得f(a)=b.由合成定理有g∘f

(a)=g(f(a))=g(b)=c

从而证明了f∘g：A→C是满射的.第八页，共二十四页，2022年，8月28日二、函数的逆（反函数）对于二元关系R，只要交换所有的有序对，就能得到逆关系；但对于函数f,交换所有的有序对得到的逆关系到却不一定是函数，只有当f为双射函数时其逆关系才是函数。第九页，共二十四页，2022年，8月28日二、反函数(函数的逆)但对于函数f,交换f的所有有序对得到的逆关系f1是二元关系却不一定是函数。如：F={<a,b>,<c,b>}，F1={<b,a>,<b,c>}对于二元关系R，只要交换所有有序对的顺序，就能得其逆关系；第十页，共二十四页，2022年，8月28日反函数存在的条件但对于函数f,交换所有的有序对得到的逆关系到却不一定是函数，只有当f为双射函数时其逆关系才是函数。第十一页，共二十四页，2022年，8月28日反函数的定义及性质反函数的定义：对于双射函数f：A→B,称f1：B→A是它的反函数.定理设f：A→B是双射的,则f1：B→A也是双射的.反函数的性质：定理:设f：A→B是双射的,则

f1∘f=IA,f∘f1=IB

对于双射函数f：A→A,有

f1∘f=f∘f1=IA

第十二页，共二十四页，2022年，8月28日函数复合与反函数的计算例：设R是实数集，且f,g,h是R到R的函数其中

f(x)=1+x,g(x)=1+x2,h(x)=1+x3,求f

∘

g,g

∘

f，(f∘g)∘h

和

f∘(g∘h).解：f∘g(x)=f(1+x2)=2+x2

g∘f(x)=g(1+x)=1+(1+x)2(f∘g)∘h(x)=(f∘g)∘(1+x3)=2+(1+x3)2f∘(g∘h)(x)=f(1+(1+x3)2)=2+(1+x3)2第十三页，共二十四页，2022年，8月28日思考：设f：R→R,g：R→R

求f

g,g

f.如果f和g存在反函数,求出它们的反函数.

f：R→R不是双射的,不存在反函数.g：R→R是双射的,它的反函数是g1：R→R,g1(x)=x2解：第十四页，共二十四页，2022年，8月28日思考：设a1,a2,…,an是任意的n个正整数，证明存在i和k(i0,k1)，使得ai+1+ai+2+……+ai+k

能被n整除。第十五页，共二十四页，2022年，8月28日三、鸽洞原理

如果某人营造了n个鸽洞，养了多于n只鸽子，则必有一个鸽洞有2只或2只以上的鸽子，这就是鸽洞原理。

用数学语言来描述这个原理，即：A，B是有限集合，f是A到B的函数，如果︱A︱﹥︱B︱，则A中至少有两个元素，其函数值相等。第十六页，共二十四页，2022年，8月28日一般的情况是：当鸽洞为n个，鸽子数大于n×m只时，必有一个鸽洞住有m+1只或多于m+1只鸽子。

例如，有3个鸽洞，13只鸽子，则必有一个鸽洞，住有5只或5只以上的鸽子。

更一般的情况是：

A，B是有限集合，f是A到B的函数，如果︱A︱﹥n×m

，︱B︱=n，则在A中至少有m+1个元素，其函数值相等。

第十七页，共二十四页，2022年，8月28日例：证明任意n+1个正整数，其中必有两个数之差被n整除。证明由于任意正整数被n除后，其余数只能是0，1，2……n-1，所以n+1个正整数中，必有两个数被n除后余数相同，因此这两个数之差必能被n整除。第十八页，共二十四页，2022年，8月28日例:某人步行驶10小时，共走45公里，已知他第一小时走了6公里，最后一小时只走了2公里，证明必有连续的两小时，在这两小时内至少走了10公里。证明:设第i小时走了ai公里，连续的两小时所走里程为a1+a2,a2+a3,…,a9+a10,共有9种；因为（a1+a2

）+（a2+a3

）+…

…+(a9+a10)=245-6-2=82,所以必有连续的两小时里所走里程大于等于10公里。第十九页，共二十四页，2022年，8月28日例:证明在1—100的正整数中，任取51个正整数，其中必存在两个数，一个数是另一个数的倍数。证明对于任意的偶数，使得：偶数=奇数2k.

构造以下50个集合：

A1={1，12，122，123，124，125，126}A3={3，32，322

，323

，324

，325}A5={5，52，522

，523

，524}A7={7，72，722

，723}A9={9，92，922

，923}A11={11，112，1122

，1123}A13={13，132，1322}

………….A49={49，492}A51={51}A53={53}

………..A99={99}第二十页，共二十四页，2022年，8月28日这50个集合中元素的总和共100个，恰好是1—100的所有正整数，且在含有2个或2个以上元素的集合A1，A3，A5，……,A49中，同一个集合中的任意两个正整数必是：一个数是另一个数的倍数。因此在1—100的正整数中任取51个数，其中至少有两个数属于同一个集合，所以这两个数中有一个数是另一个的倍数。第二十一页，共二十四页，2022年，8月28日

证明A1(小王)A2(小张)A3(小何)

A4(小周)A5(小杨)

A6(小刘)思考:试证在任意六个人中必有三人他们相互认识或相互不认识.第二十二页，共二十四页，2022年，8月28日例:在一个有6个点的完全图中，给每一条边涂色，可随意涂红色或白色。证明在这个完全图中，必存在一个三角形，其三条边的颜色相同。证明A1A1A2A3A2A3A4A5A4