《《函数及其运算》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《函数及其运算》PPT课件.ppt（30页珍藏版）》请在三一办公上搜索。
1、函数及其运算,离散数学：第7讲,上一讲内容的回顾,偏序关系与偏序集拟序哈斯图偏序集中的特殊元素极大元与极小元最大元与最小元上(下)界与上(下)确界全序良序,函数及其运算,函数的定义像与完全原像几种特殊的函数满射、单射(一对一的)、双射(一一对应的)集合的特征函数自然映射函数的复合反函数鸽巢原理,函数：一个你非常熟悉的名词,0,x,y,y=f(x),a,函数f 在a点的“值”,x2,x1,y2,y2,f 是定义在实数集上的函数b是对应于a的值一般要求对定义域中的每个元素有一个，也只有一个函数值与之对应区间x1,x2是定义域的子集区间y1,y2是对应于x1,x2的像,b,函数的推广：映射,从集合A
2、到B的函数 f:AB是一种特殊的二元关系，满足：f 在其定义域中的每个元素都有唯一的值注意：:AB表示定义域是A，但值域可能是B的真子集。若A,B皆非空有限集合，从A到B的不同的函数有|B|A|个。注意：空关系本身是一个从空集到任意集合S(包括空集)的函数，因为它满足：x,x!yS,像与完全原像,设:AB,AA,则(A)=y|y=(x)，xA称为A在下的像。值是对定义域中一个元素而言，像是对定义域的一个子集而言。设BB,则-1(B)=x|xA,(x)B称为B的完全原像定义域A的一个子集A1的像的完全原像包含A1，但未必相等。,几种特殊的函数,满射:AB是满射的：ran=B,iff.yB,xA,
3、使得(x)=y单射（一对一的）:AB是单射的：y ran,!xA,使得(x)=y iff.x1,x2A,若x1x2，则(x1)(x2)iff.x1,x2A,若(x1)=(x2)，则x1=x2。双射（一一对应的）满射+单射,几种特殊的函数：例子,:RR,(x)=-x2+2x-1:Z+R,(x)=ln x,单射:RZ,(x)=x,满射:RR,(x)=2x-1，双射:R+R+,(x)=(x2+1)/x注意：f(x)2,而对任意正实数x，f(x)=f(1/x):RRRR,()=,双射。注意：(|x,yR且y=x+1)=R-1:NNN,()=|x2-y2|注意：(N0)=n2|nN,而-1(0)=|nN
4、,集合的特征函数,设A为集合，对任意的AA,特征函数A：A0,1 定义为：A(x)=1 iff.xA。可以在A的幂集与A的所有特征函数的集合之间建立一一对应的函数。定义函数:(A)|是A的特征函数如下：对任意A(A),(A)=A显然是双射,自然映射,R是A上的任一等价关系，g:AA/R,对任意aA,g(a)=a,称G为自然映射。自然映射是满射。对任意的等价类x A/R,存在xA，使得g(x)=x,交集与并集的函数象,设函数f：AB，且X，Y是A的子集，则f(XY)=f(X)f(Y)f(XY)f(X)f(Y),A,B,X,Y,a1,a2,c,f,在f(X)f(Y)中，但不在f(XY)中,函数的复
5、合,关系的复合适用于函数，运算的结果当然是关系实际上：函数的复合仍然是函数定理：如果f:AB,g:BC,则f g:AC,且xA都有f g(x)=g(f(x),结合律,函数的复合即关系的复合关系的复合运算满足结合律所以：函数的复合满足结合律即：对任意函数f:AB,g:BC,h:CD,(f g)h=f(g h),复合运算保持 函数性质：满射,满射的复合是满射 定理：如果f:AB,g:BC均是满射，则f g:AC也是满射。证明要点：任给yC,根据g的满射性质，一定有tB,使得g(t)=y，而根据f的满射性质，一定有xA,使得f(x)=t,因此，f g(x)=y。,但是,若f g是满射，能推出f 和g
6、是满射吗？显然，g一定是满射。若存在tB,但对任意xA,f(x)t,(即：f不是满射！)只要g(B-t)=C,则f g仍然是满射。,f,g,A,B,C,复合运算保持 函数性质：单射,单射的复合是单射 定理：如果f:AB,g:BC均是单射，则f g:AC也是单射。证明要点：若不然，即存在x1,x2A,且x1x2，使得f g（x1)=f g(x2)，设 f(x1)=t1,f(x2)=t2，如果 t1=t2，与f是单射矛盾。如果 t1 t2，与g是单射矛盾。,但是,若f g是单射，能推出f 和g是单射吗？显然，f一定是单射。若存在t1,t2B,t1t2，但g(t1)=g(t2),(即：g不是单射！)
7、只要 t1或者t2 不在f值域内，则f g仍然可能是单射。,（左，右）单位元素,IA是集合A上的恒等函数：IA(x)=x(xA)对于f:AB，f=f IB=IA f证明要点：证明集合 f 等于集合f IB以及IA f注意：若f,则f 且 IB 若 f IB，则 f,且 IB，则t=y,所以 f IB，,反函数,函数的逆关系不一定是函数例子(设A=a,b,c,B=1,2,3)f=,是函数，但是f的逆关系,不是函数f:AB的逆关系f-1:BA如果(!)也是函数，则称为f 的反函数。例子f:NNN,f()=2i(2j+1)-1是双射，f-1(2i(2j+1)-1)=,反函数的存在性定理,f:AB存在
8、反函数当且仅当 f 是双射。证明要点：若f非单射，则有,f-1,且x1x2，而若f非满射，则在f-1下，至少有一个B中的元素在A中没有相应的值。均与“f-1:BA也是函数”矛盾。若f-1不是函数，或者有,f-1,且x1x2，则f不是单射，或者在f-1下，至少有一个B中的元素在A中没有相应的值，则f不是满射。均与“f是双射”矛盾。,复合运算下的逆元素,设f:AB,g:BA：若g f=IB,则称g是f的左逆：左逆存在当且仅当f是满射 假设f 不是满射，根据已知，对任何bB,f(g(b)=b,而g(b)A,因此f 是满射。构造 g:BA 如下：对任意bB，由于f 是满射，一定有aA,使得f(a)=b
9、,令g(b)=a。(若这样的a不止一个，则任取其中一个)，则对任意bB，gf(b)=f(g(b)=b,gf=IB若f g=IA,则称g是f的右逆：右逆存在当且仅当f是单射f 既有左逆又有右逆当且仅当f是双射，且左右逆相等,逆元和消去律,设f:AB,则f存在右逆 iff.对任意g,g:SA,gf=gf g=g g=g(f f右-1)=(gf)f右-1=(gf)f右-1=g(f f右-1)=g 只需证明f 一定是单射。假设存在x1,x2A,x1x2,但f(x1)=f(x2)。构造从S到A的函数g,g,任取s0S,让g(s0)=x1,g(s0)=x2,而对其它任意sS,让g(s)=g(s)。则gf=
10、gf，但 g=g，矛盾。设f:AB,则f存在左逆 iff.对任意g,g:BC,f g=f g g=g,多对一的函数与鸽巢原理,设D和R均为有限集合，|D|R|,则对任意从D到R的函数,存在x1,x2D,使得(x1)=(x2)。推广：对任意从D到R的函数,存在k个元素x1,x2,.xkD,使得(x1)=(x2)=.=(xk),其中k=|D|/|R|,。,下一个是什么颜色？,黑的？白的？下一个是.?,鸽巢原理简单的应用示例,n个人相互握手，两人之间最多握一次，但没有人一次也不握，则至少有两个人握手次数相同 鸽子：人，n个巢：可能的握手次数，正整数，最小值为1，最大值为n-1,共有n-1个鸽子数(n
11、)大于 巢数(n-1),隐藏的鸽子，看不见的巢,某棋手在连续77天中每天至少下一盘棋，但总共下棋不超过132盘。则不管任何排日程，一定有连续若干天正好共下21盘。用正整数序列a1,a2,.,a77 表示从第一天到相应每天结束时已经下的总盘数。则aj=ai+21表示从第i+1天到第j天恰好下了21盘。鸽子：序列a1,a2,.,a77,a1+21,a2+21,.,a77+21,共154只巢：序列中元素可能的取值：1,2,.,153(132+21),共153个注意序列中前半段和后半段分别均为单调递增(每天至少下一盘)，所以相等的两个值只能分布在前后两段中。,推广的鸽巢原理示例,任意6个人中，或者有3人相互认识，或者有3人相互两两均不认识,作业,P.164-3-57-920-2225-26,
