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

《集合论与图论》第9讲 第9讲 函数 内容提要 函数,偏函数,全函数,真偏函数 单射,满射,双射,计数问题 象,原象 常数函数,恒等函数,特征函数,单调函数,自然映射 合成(复合),反函数,单边逆(左逆,右逆) 构造双射(有穷集,无穷集) 函数(function) 函数: F是函数 ? F是单值的二元关系 F单值: ?x?domF, ?y,z?ranF, xFy ? xFz ? y=z 函数亦称映射(mapping) F(x)=y ? x,y?F ? xFy ?是函数,称为空函数 常用F,G,H,…,f,g,h,…表示函数. 偏函数(partial function) 偏函数: domF?A A到B的偏函数: domF?A且ranF?B 偏函数记作 F:A?B, 称A为F的前域, A到B的全体偏函数记为A?B A?B = { F | F:A?B } 例1 例1: 设 A={a,b}, B={1,2}, 求A?B. 解: |A|=2,|B|=2,|A?B|=4,|P(A?B)|=24=16. f0=?, f1={a,1}, f2={a,2}, f3={b,1}, f4={b,2}, f5={a,1,b,1}, f6={a,1,b,2}, f7={a,2,b,1},f8={a,2,b,2}. A?B = {f0 ,f1 ,f2 ,f3 ,f4 ,f 5,f6 ,f7 ,f8}. # 非函数: {a,1,a,2}, {b,1,b,2}, {a,1,a,2,b,1},… 全函数(total function) 全函数: domF=A 全函数记作 F:A?B A到B的全体全函数记为BA或A?B BA = A?B = { F | F:A?B } 关于BA的说明 BA={ F | F:A?B }={ F | F是A到B全函数 } |BA| = |B||A|. 当A=?时, BA={?} 当A??且B=?时, BA=A?B=?, 但A?B={?}. 真偏函数(proper partial function) 真偏函数: domF?A, 真偏函数记作F:A?B, A到B的全体真偏函数记为A?B A?B = { F | F:A?B } 例1(续) 例1(续): 设 A={a,b}, B={1,2}, 求A?B. 解: f0=?, f1={a,1}, f2={a,2}, f3={b,1}, f4={b,2}, f5={a,1,b,1}, f6={a,1,b,2}, f7={a,2,b,1},f8={a,2,b,2}. A?B={f0 , f1 , f2 , f3 , f4}. # 说明: F?A?B ? F?domF?B F?A?B ? F?domF?B 三者关系 A?B = A?B ? A?B 全函数性质 设 F:A?B, 单射(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}, 求A1?B1,A2?B2,A3?B3中的单射,满射,双射. 例2(解(1)) 例2: (1) A1={a,b}, B1={1,2,3}, 解: (1) A1?B1中无满射,无双射,单射6个: f1={a,1,b,2}, f2={a,1,b,3}, f3={a,2,b,1}, f4={a,2,b,3}, f5={a,3,b,1}, f6={a,3,b,2}. 例2(解(2)) 例2: (2) A2={a,b,c}, B2={1,2}, 解: (2) A2?B2中无单射,无双射,满射6个: f1={a,1,b,1,c,2}, f2={a,1,b,2,c,1}, f3={a,2,b,1,c,1}, f4={a,1,b,2,c,2}, f5={a,2,b,1,c,2}, f6={a,2,b,2,c,1}. 例2(解(3)) 例2: (3) A3={a,b,c}, B3={1,2,3}, 解: (3) A2?B2中双射6个: f1={a,1,b,2,c,3}, f2={a,1,b,3,c,2}, f3={a,2,b,1,c,3}, f4={a,2,b,3,c,1}, f5={a