第第4 4章章 二元关系和函数二元关系和函数 Relation离散数学二元关系和函数 在高等数学中，函数是在实数集合上进行讨论的，在高等数学中，函数是在实数集合上进行讨论的，其定义域是连续的其定义域是连续的 本章把函数概念予以推广本章把函数概念予以推广 定义域为一般的集合，支持离散应用定义域为一般的集合，支持离散应用 把函数看作是一种特殊的关系：单值二元关系把函数看作是一种特殊的关系：单值二元关系4.6函函数数的的定定义义与与性性质质离散数学二元关系和函数函数定义函数定义定义定义 设设 F 为二元关系为二元关系, 若若 xdomF 都存在唯一的都存在唯一的yranF 使使 xFy 成立成立, 则称则称 F 为函数为函数. 对于函数对于函数F, 如果有如果有 xFy, 则记作则记作 y=F(x), 并称并称 y 为为 F 在在 x 的函数值的函数值. 例例1 F1=, F2=, F1是函数是函数, F2不是函数不是函数 4.6函函数数的的定定义义与与性性质质离散数学二元关系和函数函数与关系的区别函数与关系的区别从从A A到到B B的函数的函数f f与一般从与一般从A A到到B B的二元关系的二元关系R R有有如下区别：如下区别：A A的每一元素都必须是的每一元素都必须是f f的序偶的第一的序偶的第一坐标，即坐标，即dom(f)=Adom(f)=A；但；但dom(R)dom(R) R R若若f(x)=yf(x)=y，则函数则函数f f在在x x处的值是惟一处的值是惟一的，即的，即( (f(x)=y)f(x)=y) (f(x)=z)(f(x)=z)(y=z)(y=z)，；但；但(xRy)(xRy) (xRz)(xRz)得不到得不到y=zy=z4.6函函数数的的定定义义与与性性质质离散数学二元关系和函数例例1 1 设设A=1,2,3,4,5A=1,2,3,4,5，B=6,7,8,9,10B=6,7,8,9,10，分别，分别确定下列各式中的确定下列各式中的f f是否为由是否为由A A到到B B的函数。
的函数1)f=(1,8),(3,9),(4,10),(2,6),(5,9)(1)f=(1,8),(3,9),(4,10),(2,6),(5,9)(2)f=(1,9),(3,10),(2,6),(4,9)(2)f=(1,9),(3,10),(2,6),(4,9)(3)f=(1,7),(2,6),(4,5),(1,9),(5,10),(3,9)(3)f=(1,7),(2,6),(4,5),(1,9),(5,10),(3,9) 解解 （1 1）能构成函数，因为符合函数的定义条件）能构成函数，因为符合函数的定义条件 （2 2）不能构成函数，因为）不能构成函数，因为A A中的元素中的元素5 5没有像没有像，不满足像的存在性不满足像的存在性 （3 3）不能构成函数，因为）不能构成函数，因为A A中的元素中的元素1 1有两个有两个像像7 7和和9 9，不满足像的惟一性不满足像的惟一性 4.6函函数数的的定定义义与与性性质质离散数学二元关系和函数函数相等函数相等定义定义 设设F, G为函数为函数, 则则 F = G F GG F 一般使用下面两个条件一般使用下面两个条件： (1) domF = domG (2) xdomF = domG 都有都有 F(x) = G(x) 实例实例 函数函数 F(x)=(x2 1)/(x+1), G(x)=x 1不相等不相等, 因为因为 domF domG. 4.6函函数数的的定定义义与与性性质质离散数学二元关系和函数从从A A到到B B的函数的函数定义定义 设设A, B为集合为集合, 如果如果 f 为函数为函数 domf = A ranf B, 则称则称 f 为为从从A到到B的函数的函数, 记作记作 f：AB. 实例实例 f：NN, f(x)=2x 是从是从 N 到到 N 的函数的函数 g：NN, g(x)=2也是从也是从 N 到到 N 的函数的函数 4.6函函数数的的定定义义与与性性质质离散数学二元关系和函数B B上上A A定义定义 所有从所有从 A 到到 B 的函数的集合记作的函数的集合记作 BA, 读作读作“B上上A”，符号化表示为，符号化表示为 BA = f | f：AB 计数计数： |A|=m, |B|=n, 且且m, n0, |BA|=nm. A=, 则则 BA=B=. A且且B=, 则则 BA=A= .4.6函函数数的的定定义义与与性性质质离散数学二元关系和函数实例实例例例2 设设 A = 1, 2, 3, B = a, b, 求求BA. 解解 BA = f0, f1, , f7, 其中其中 f0=, f1=, f2=,，f3=, f4=,，f5=, f6=, f7=, 4.6函函数数的的定定义义与与性性质质离散数学二元关系和函数函数的像函数的像定义定义 设函数设函数 f：AB, A1 A. A1 在在 f 下的像下的像： f(A1) = f(x) | xA1 函数的像函数的像 f(A) = ranf 注意：注意： 函数值函数值 f(x)B, 而像而像 f(A1) B. 例例3 设设 f：NN, 且且 令令A=0,1, B=2, 那么有那么有 f(A) = f(0,1) = f(0), f(1) = 0, 2/ 2( )1xxf xxx若 为偶数若 为奇数4.6函函数数的的定定义义与与性性质质离散数学二元关系和函数函数的性质函数的性质定义定义 设设 f：AB,（1）若）若ranf = B, 则称则称 f：AB是是满射满射的的.（2）若）若任意任意x1， x2 A 而且不相等，都有而且不相等，都有f(x1)与与 f(x2)不相等不相等, 则称则称 f：AB是是单射单射的的.（3）若）若 f：AB既是满射又是单射的既是满射又是单射的, 则称则称 f： AB是是双射双射的的f 满射意味着：满射意味着： y B, 都存在都存在 x使得使得 f(x) = y. f 单射意味着：单射意味着：f(x1) = f(x2) x1= x2 4.6函函数数的的定定义义与与性性质质离散数学二元关系和函数注意：注意：由单射的定义可知，设由单射的定义可知，设X X和和Y Y是有限是有限集合，若存在单射函数集合，若存在单射函数f:XYf:XY，则则| |X|Y|X|Y|。
由满射的定义可知，设由满射的定义可知，设X X和和Y Y是有限是有限集合，若存在满射函数集合，若存在满射函数f:XYf:XY，则则| |X|Y|X|Y|由双射的定义可知，设由双射的定义可知，设X X和和Y Y是有限是有限集合，若存在双射函数集合，若存在双射函数f:XYf:XY，则则| |X|=|Y|X|=|Y|4.6函函数数的的定定义义与与性性质质离散数学二元关系和函数实例实例例例4 判断下面函数是否为单射判断下面函数是否为单射, 满射满射, 双射的双射的, 为什么为什么? (1) f：RR, f(x) = x2+2x 1 (2) f：Z+R, f(x) = lnx, Z+为正整数集为正整数集 (3) f：RZ, f(x) = x (4) f：RR, f(x) = 2x+1 (5) f：R+R+, f(x)=(x2+1)/x, 其中其中R+为正实数集为正实数集. 4.6函函数数的的定定义义与与性性质质离散数学二元关系和函数解解 (1) f：RR, f(x)= x2+2x 1 在在x=1取得极大值取得极大值0. 既不单射也不满射既不单射也不满射. (2) f：Z+R, f(x)=lnx 单调上升单调上升, 是单射是单射. 但不满射但不满射, ranf=ln1, ln2, . (3) f：RZ, f(x)= x 满射满射, 但不单射但不单射, 例如例如 f(1.5)=f(1.2)=1. (4) f：RR, f(x)=2x+1 满射、单射、双射满射、单射、双射, 因为它是单调的并且因为它是单调的并且ranf=R. (5) f：R+R+, f(x)=(x2+1)/x 有极小值有极小值f(1)=2. 该函数既不单射也不满射该函数既不单射也不满射. 实例（续）实例（续）4.6函函数数的的定定义义与与性性质质离散数学二元关系和函数构造从构造从A A到到B B的双射函数的双射函数有穷集之间的构造有穷集之间的构造例例5 A=P(1,2,3), B=0,11,2,3解解 A=,1,2,3,1,2,1,3,2,3,1,2,3. B= f0, f1, , f7 , 其中其中 f0=, f1=, f2=, f3=, f4=, f5=, f6=, f7=,.令令 f：AB, f()=f0, f(1)=f1, f(2)=f2, f(3)=f3, f(1,2)=f4, f(1,3)=f5, f(2,3)=f6, f(1,2,3)=f74.6函函数数的的定定义义与与性性质质离散数学二元关系和函数实数区间之间构造双射实数区间之间构造双射构造方法：直线方程构造方法：直线方程例例6 A=0,1 B=1/4,1/2构造双射构造双射 f :AB构造从构造从A A到到B B的双射函数（续）的双射函数（续）解解 令令 f：0,11/4,1/2 f(x)=(x+1)/4 4.6函函数数的的定定义义与与性性质质离散数学二元关系和函数构造从构造从A A到到B B的双射函数（续）的双射函数（续）A A 与自然数集合之间构造双射与自然数集合之间构造双射方法：将方法：将A中元素排成有序图形，然后从第一个元素开始中元素排成有序图形，然后从第一个元素开始 按照次序与自然数对应按照次序与自然数对应例例7 A=Z, B=N，构造双射，构造双射 f：AB将将Z中元素以下列顺序排列并与中元素以下列顺序排列并与N中元素对应：中元素对应：Z：0 11 22 33 N：0 1 2 3 4 5 6 则这种对应所表示的函数是则这种对应所表示的函数是：20Z,( )210 xfN f xxx：4.6函函数数的的定定义义与与性性质质离散数学二元关系和函数常函数、恒等函数、单调函数常函数、恒等函数、单调函数 1. 设设f：AB, 若存在若存在 cB 使得使得 xA 都有都有 f(x)=c, 则称则称 f：AB是是常函数常函数. 2. 称称 A 上的恒等关系上的恒等关系 IA为为 A 上的上的恒等函数恒等函数, 对所有对所有 的的 xA 都有都有 IA(x)=x. 3. 设设 f：RR，如果对任意的，如果对任意的 x1, x2R，x1x2, 就就 有有 f(x1) f(x2), 则称则称 f 为为单调递增单调递增的；如果对任意的；如果对任意 的的 x1, x2A, x1 x2, 就有就有 f(x1) f(x2), 则称则称 f 为为 严严 格单调递增格单调递增 的的. 类似可以定义类似可以定义单调递减单调递减 和和严格单调递减严格单调递减 的函数的函数.4.6函函数数的的定定义义与与性性质质离散数学二元关系和函数集合的特征函数集合的特征函数 设设 A 为集合为集合, A A, A 的的 特征函数特征函数 A：A0,1 定义为定义为 , 0, 1)(AAaAaaA 实例实例 集合：集合：X = A, B, C, D, E, F, G, H , 子集：子集：T = A, C, F, G, H T 的特征函数的特征函数 T ： x A B C D E F G H T(x) 1 0 1 0 0 1 1 1 4.6函函数数的的定定义义与与性性质质离散数学二元关系和函数5. 设设 R 是是 A 上的等价关系上的等价关系, 令令g：AA/Rg(a) = a, aA称称 g 是从是从 A 到商集到商集 A/R 的的自然映射自然映射. 自然映射自然映射 4.6函函数数的的定定义义与与性性质质离散数学二元关系和函数实例实例例例8 (1) A的每一个子集的每一个子集A都对应于一个特征函都对应于一个特征函数数, 不同的子集对应于不同的特征函数不同的子集对应于不同的特征函数. 例如例如 A=a, b, c, 则有则有 = , , ， a,b = , , (2) 给定集合给定集合 A， A 上不同的等价关系确定不同上不同的等价关系确定不同的自然映射的自然映射, 其中恒等关系确定的自然映射是其中恒等关系确定的自然映射是双射双射, 其他的自然映射一般来说是满射其他的自然映射一般来说是满射. 例如例如 A=1, 2, 3, R=,IA g(1) = g(2) = 1,2, g(3) = 34.6函函数数的的定定义义与与性性质质离散数学二元关系和函数函数复合的定理函数复合的定理定理定理 设设F, G是函数是函数, 则则F F G G也是函数也是函数, 且满足且满足 (1) dom( FG)= x | xdomG G(x)domF (2) xdom(F F G G) 有有FG(x) = F (G(x)推论推论1 设设F, G, H为函数为函数, 则则 (F G) H 和和 F (G H) 都是函数都是函数, 且且 (F G) H = F (G H)推论推论2 设设 f： BC, g： AB, 则则 f g：AC, 且且 xA 都有都有 f g(x) = f (g(x). 4.7函函数数复复合合和和反反函函数数离散数学二元关系和函数函数复合运算的性质函数复合运算的性质定理定理 设设g ：AB, f ：BC. (1) 如果如果f,g都是满射都是满射, 则则 fg：AC也是满射也是满射. (2) 如果如果 g, f 都是单射都是单射, 则则f f g:g:AC也是单射也是单射. (3) 如果如果 g, f 都是双射都是双射, 则则 f g：AC也是双射也是双射. 证证 (1) cC, 由由 f：BC 的满射性的满射性, bB 使得使得 f(b)=c. 对这个对这个b, 由由 g：AB 的满射性，的满射性， aA 使得使得 f(a)=b. 由合成定理由合成定理 f g(a)= f ( g(a)=f(b)=c 从而证明了从而证明了 f g：AC是满射的是满射的. 离散数学二元关系和函数函数复合运算的性质函数复合运算的性质 (2) 假设存在假设存在 x1, x2A使得使得 f g(x1) = f g(x x2 2) 由合成定理有由合成定理有 f (g(x1)= f (g(x2). 因为因为 f：BC是单射的是单射的, 故故 g(x1)=g(x2). 又由又由 于于 g：AB也是单射的也是单射的, 所以所以 x1=x2. 从而证从而证 明明 f g：AC是单射的是单射的. (3) 由由 (1) 和和 (2) 得证得证.定理定理 设设 f: AB，则，则 f = f IB = IA f 离散数学二元关系和函数定理定理 设设f:XYf:XY，g:YZg:YZ，那么那么（1 1）若）若gfgf是单射，则是单射，则f f是单射。
是单射2 2）若）若gfgf是满射，则是满射，则g g是满射3 3）若）若gfgf是双射，则是双射，则f f是单射，是单射，g g是满射函数复合运算的性质函数复合运算的性质离散数学二元关系和函数反函数存在的条件反函数存在的条件任给函数任给函数 F, 它的逆它的逆F 1不一定是函数不一定是函数, 是二元关系是二元关系.实例：实例：F=,， F 1=, 任给任给单射函数单射函数 f：AB, 则则 f 1是函数是函数, 且是从且是从 ranf 到到 A的双射函数的双射函数, 但不一定是从但不一定是从 B 到到 A 的双射函的双射函数数.实例：实例：f : N N, f(x) = 2x, f 1 : ranf N, f 1 (x) = x/2 离散数学二元关系和函数反函数反函数定理定理 设设 f：AB是双射的是双射的, 则则f 1：BA也是双射函数也是双射函数.证证 因为因为 f 是函数是函数, 所以所以 f 1 是关系是关系, 且且 dom f 1 = ranf = B , ran f 1 = domf = A, 对于任意的对于任意的 yB = dom f 1, 假设有假设有x1, x2A使得使得f 1f 1成立成立, 则由逆的定义有则由逆的定义有ff根据根据 f 的单射性可得的单射性可得 x1 = x2, 从而证明了从而证明了f 1是函数，且是是函数，且是满射的满射的. 下面证明下面证明 f 1 的单射性的单射性. 若存在若存在 y1, y2B 使得使得 f 1 (y1) = f 1 (y2) = x, 从而有从而有f 1f 1 ff y1 = y2 离散数学二元关系和函数反函数的定义及性质反函数的定义及性质对于双射函数对于双射函数f：AB, 称称 f 1：BA是它的是它的反反函数函数. 反函数的性质反函数的性质定理定理 设设 f：AB是双射的是双射的, 则则f 1f = IA, ff 1 = IB 对于双射函数对于双射函数 f：AA, 有有f 1f = ff 1 = IA 离散数学二元关系和函数定理定理 若若f:XYf:XY是可逆的，那么是可逆的，那么 （l l）(f(f-1-1) )-1-1=f=f （2 2）f f-1-1f=If=IX X，f ff f-1-1=I=IY Y定理定理3.93.9 设设X,Y,ZX,Y,Z是集合，如果是集合，如果f:XYf:XY，g:YZg:YZ都是可逆的，那么都是可逆的，那么g gf f也是可逆的也是可逆的，且，且( (g gf)f)-1-1=f=f-1-1g g-1-1 。
离散数学二元关系和函数函数复合与反函数的计算函数复合与反函数的计算例例 设设 f：RR, g：RR 求求 f g, g f. 如果如果 f 和和 g 存在反函数存在反函数, 求出它们的反函数求出它们的反函数. 23( )( )223xxf xg xxx解解 f：RR不是双射的不是双射的, 不存在反函数不存在反函数. g：RR是双射的是双射的, 它它的反函数是的反函数是 g 1：RR, g 1(x) = x 2 22:23(2)1( )( )0321fg RRgfRRxxxxfg xgf xxx离散数学二元关系和函数一、两个有限集如何比较多少一、两个有限集如何比较多少 设两个班级A 和B，要比较这两个班级的学生哪班多，哪班少，可采取两种方法方法1：报数报数后看谁的数目大，数目大的就表示这个班上学生人数多但这个方法对无限集却行不通方法2：配对将A 中的一个学生a1 和B 中的一个学生b1 配成一对，配好以后，不许他们再和别人配对了然后再把A 中的另一个学生a2 和B 中的一个学生b2 配成一对，同样，配好以后也不准他们再和其他人配对了这样一对一配下去，如果A中的人都配完了，而B还剩下一些人，则说B中的学生比A多；如果B 中的人都配完了，而A 剩下一些人，则说A中的学生比B多；如果A和B中的学生正好都能一对一地搭配起来，则说A和B的学生人数一样多。
这种“配对”的办法可以应用到无限集中去离散数学二元关系和函数定义一定义一 设设A A与与B B为集合，若存在从为集合，若存在从A A到到B B的双射的双射，则称，则称A A和和B B为等势，记为为等势，记为A AB B例例6.13 (-1,1)6.13 (-1,1)(-,+)(-,+)证明证明 因存在着双射因存在着双射 ，x(-1,1)x(-1,1)，所以，所以(-(-1,1)1,1)(-,+)(-,+) 等势关系具有如下性质等势关系具有如下性质 A AA A 若若A AB B，则，则B BA A 若若A AB B，B BC C，则，则A AC C 所以等势关系是等价关系所以等势关系是等价关系离散数学二元关系和函数定义二定义二 设设N Nn n=0,1,2,n-1=0,1,2,n-1，A A 为任一集合若为任一集合若A=A= 或或A A 与某个与某个N Nn n等势，则称等势，则称A A为有限集；否则称为有限集；否则称A A 为无限集为无限集定理一定理一 自然数集N为无限集 证明 任取nN，f 是从Nn 到N 的任意一个函数令k=1+maxf(0),f(1),f(n-1)，则kN但对每个xNn，都有f(x)k，因此f不是满射，从而f 不是双射。
由n和f的任意性得知N 是无限的离散数学二元关系和函数定义三定义三 （1 1）对于有限集合）对于有限集合A A，有唯一的，有唯一的NnNn与其等势与其等势，对应的，对应的n n称为称为A A的基数，记为的基数，记为|A|A|（2 2）自然数集）自然数集N N 的基数记为的基数记为 0 0（读作阿列夫零）读作阿列夫零）3 3）实数集）实数集R R 的基数记为的基数记为 （读作阿列夫）读作阿列夫） 由定义可知，有限集合的基数就是其所含元素的由定义可知，有限集合的基数就是其所含元素的个数两个有限集合等势当且仅当个数两个有限集合等势当且仅当A A和和B B 的元素个数的元素个数相同离散数学二元关系和函数定义四定义四 与自然数集N 等势的集合叫做可数集或可列集，其基数记为 0与自然数集N不等势的无限集叫做不可数集或不可列集下面介绍可数集的一些性质定理五定理五 集合A 为可数集的充要条件是A 的元素可以排列成无限序列的形式（即A=a0,a1,an,）定理二定理二 任一无限集必含有可数子集定理三定理三 任一无限集必与其某一真子集等势定理四定理四 可数集的任何无限子集是可数的定理五定理五 两个可数集的并集仍是可数集。