《函数及其运算》PPT课件.ppt

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