[工学]SG09离散数学大全 集合与图论ppt课件

1、第9讲 函数内容提要函数,偏函数,全函数,真偏函数单射,满射,双射,计数问题象,原象常数函数,恒等函数,特征函数,单调函数,自然映射合成(复合),反函数,单边逆(左逆,右逆)构造双射(有穷集,无穷集)函数(function)函数: F是函数 F是单值的二元关系F单值: xdomF, y,zranF, xFy xFz y=z函数亦称映射(mapping)F(x)=y F xFy是函数,称为空函数常用F,G,H,f,g,h,表示函数.xyz非单值单值偏函数(partial function)偏函数: domFAA到B的偏函数: domFA且ranFB偏函数记作 F:AB, 称A为F的前域, A到B

2、的全体偏函数记为ABAB = F | F:AB 例1例1: 设 A=a,b, B=1,2, 求AB.解: |A|=2,|B|=2,|AB|=4,|P(AB)|=24=16. f0=, f1=, f2=, f3=, f4=, f5=, f6=, f7=,f8=,. AB = f0 ,f1 ,f2 ,f3 ,f4 ,f 5,f6 ,f7 ,f8. #非函数: , , ,全函数(total function)全函数: domF=A全函数记作 F:AB A到B的全体全函数记为BA或ABBA = AB = F | F:AB 关于BA的阐明BA= F | F:AB = F | F是A到B全函数 |BA|

3、= |B|A|.当A=时, BA=当A且B=时, BA=AB=, 但AB=. 真偏函数(proper partial function)真偏函数: domFA, 真偏函数记作F:AB, A到B的全体真偏函数记为ABAB = F | F:AB 例1(续)例1(续): 设 A=a,b, B=1,2, 求AB.解: f0=, f1=, f2=, f3=, f4=, f5=, f6=, f7=,f8=,. AB=f0 , f1 , f2 , f3 , f4. #阐明: FAB FdomFB FAB FdomFB三者关系AB = AB AB 偏函数AB domFA全函数AB domF=A真偏函数AB d

4、omFA全函数性质设 F:AB, 单射(injection): F是单根的 满射(surjection): ranF=B双射(bijection): F既是单射又是满射, 亦称为一一对应(one-to-one mapping).非单射非满射例2例2: 设A1=a,b, B1=1,2,3, A2=a,b,c, B2=1,2, A3=a,b,c, B3=1,2,3, 求A1B1,A2B2,A3B3中的单射,满射,双射.例2(解(1)例2: (1) A1=a,b, B1=1,2,3, 解: (1) A1B1中无满射,无双射,单射6个: f1=, f2=, f3=, f4=, f5=, f6=,. 例

5、2(解(2)例2: (2) A2=a,b,c, B2=1,2, 解: (2) A2B2中无单射,无双射,满射6个: f1=, f2=, f3=, f4=, f5=, f6=,. 例2(解(3)例2: (3) A3=a,b,c, B3=1,2,3, 解: (3) A2B2中双射6个: f1=, f2=, f3=, f4=, f5=, f6=,. #计数(counting)问题设|A|=n, |B|=m, 问AB中有多少单射,满射,双射?nm时, AB中无单射,双射, 满射个数为.!mnm象(image), 原象(preimage)设 f:AB, AA, BB象: A的象是f(A) = y | x

6、( xA f(x)=y ) B f(A)=ranf原象: B的原象是 f -1(A) = x | y( yB f(x)=y ) AAf(A)f -1(B)B象,原象(举例)例: f:NN, f(x)=2x. A=N偶=0,2,4,6,=2k|kN, f(A)=0,4,8,12,=4k|kN B=2+4k|kN=2,6,10,14, f -1(B)=1+2k|kN =1,3,5,7,=N奇 #特殊函数常数函数: xA, f(x)=bB恒等函数: IA:AA, IA(x)=x特征函数: A:E0,1, A(x)=1xA单调函数: f:AB, ,偏序集, x,yA, xAy f(x)Bf(y)单调增

7、, 单调减, 严厉单调自然映射: R为A上等价关系, f:AA/R, f(x)=xR.自然映射(举例)例: A=a,b,c,d,e,f, A/R=a,b,c,d,e,f, a=b=a,b, c=d=e=c,d,e, f=f, F:AA/R, F(x)=x. F(a)=a,b, F(b)=a,b, F( c )=c,d,e, F(d)=c,d,e, F(e)=c,d,e, F(f)=f. #abcdef函数运算合成(复合): 性质, 左(右)单位元, 单调性反函数: 存在条件单边逆: 左逆, 右逆, 存在条件函数合成(composite)定理3: 设 g:AB, f:BC, 那么 fg: AC,

8、 fg(x)=f(g(x).证明: (1) fg是函数 (2) dom fg = A (3) ran fg C. #合成的性质定理4: 设 g:AB, f:BC, fg:AC,那么 (1) f,g均为满射, 那么 fg也是满射. (2) f,g均为单射, 那么 fg也是单射. (3) f,g均为双射, 那么 fg也是双射. #合成的性质(续)定理5: 设 g:AB, f:BC, 那么 (1) 假设fg为满射, 那么f是满射. (2) 假设fg为单射, 那么g是单射. (3) 假设fg为双射, 那么g是单射,f是满射. #ggf合成的左(右)单位元定理6: 设 f:AB, 那么 f=fIA =I

9、Bf. #AABBIAIBf合成的单调性定理7: 设 f:RR, g:RR, 且f,g按是单调增的, 那么fg也是单调增的. 证明: xy g(x)g(y) f(g(x)f(g(y). #反函数(inverse function)定理8: 设A为集合,那么A-1为函数 A为单根的. #推论: 设R为二元关系,那么R为函数 R-1为单根的. #定理9: 设 f:AB, 且为双射,那么f -1 :BA, 且也为双射. #反函数: 假设f:AB为双射, 那么f -1 :BA称为f的反函数.单边逆设f:AB, g:BA左逆: g是f的左逆 gf=IA,右逆: g是f的右逆 fg=IB,ABfgIAIB

10、单边逆(举例)BABgfABAgffg=IBgf=IA单边逆的存在条件定理10: 设 f:AB, 且A,那么 (1) f 存在左逆 f 是单射; (2) f 存在右逆 f 是满射; (3) f 存在左逆,右逆 f 是双射. #gf fg 构造双射及求反函数|A|=m, |B|=n, AB存在双射 n=m|A|=, |B|=, BA, AB存在双射, 如 f: NN-0,1,2, f(n)=n+30,1(0,1) ? R(0,1) ?NNN ?012345678012345678 NNN 双射 ?方法1: 用自然数性质 nNn0, ,N, 为奇数, 使得 n=2例: 1= 201, 2= 211

11、, 3= 203, 6=213,100=2225,令n=2-1,可以去掉n0的条件令=2j+1, 为奇数nN, n=2i(2j+1)-1, i,jN, 此表示独一.方法1: f:NNN f:NNN, f -1:NNN, NN, f()=2i(2j+1)-1, f -1(n)=f -1(2i(2j+1)-1)=.例: f()=0, f()=2, f()=1, f -1(5)=, f -1(101)=, f -1(200)=,方法2:Cantor编码对角线法1+2+3+(m+n)+(m+1)=(m+n)(m+n+1)/2+(m+1)对应的自然数为(m+n)(m+n+1)/2+m方法2: f:NNN

12、 f:NNN, f -1:NNN, NN, f()=(m+n)(m+n+1)/2+m, 求 f -1(r)=. r=(m+n)(m+n+1)/2+m=t(t+1)/2+m, t=m+n, 0mt, 求最大t, 使得rt(t+1)/2. t2+t-2r0, , m=r-t(t+1)/2, n=t-m.例: f -1(0)=, f -1(1)=, f -1(2)=, f -1(3)=, ) 181(21rt总结概念: 函数,偏函数,全函数,真偏函数性质: 单射, 满射, 双射, 计数问题术语: 象, 原象特殊函数: 常数,恒等,特征,单调,自然映射运算: 合成(复合), 反函数, 单边逆技巧: 构

13、造双射习题讲解(#4,#5)15. R: 反自反, 反对称, 传送 S: 对称 T: 对称 (严厉说, 应按|A|分情形讨论)16. |R|=11, 对称 |S|=5, 反对称习题讲解(#4,#5)17. 自反, 对称01231001011101111111习题讲解(#4,#5)22.利用 R传送 RRR R自反 IAR. 反例: , (RR=RR传送, 反例只能破坏自反性 )23. 利用 (RS)-1= S-1R-1, R对称 R-1=R.习题讲解(#4,#5)27. OK. 利用fldR1fldR2= R1R2=, R2R1=, R1iR2j=, R2iR1j=, i,jN+.习题讲解(#4,#5)28. (“mn应改为“mn, 否那么