北京大学：《离散数学》系列课程之一《集合论与图论》第9讲 函数

第9讲函数 内容提要 秦函数,偏函数,全函数,真偏函数 单射满射,双射,计数问题 癱象原象 秦常数函数恒等函数,特征函数,单调函数, 自然映射 合成(复合)反函数单边逆(左逆,右逆) 构造双射(有穷集无穷集) 《集合论与图论》第9讲

《集合论与图论》第9讲 1 第9讲 函数 内容提要 函数,偏函数,全函数,真偏函数 单射,满射,双射,计数问题 象,原象 常数函数,恒等函数,特征函数,单调函数, 自然映射 合成(复合),反函数,单边逆(左逆,右逆) 构造双射(有穷集,无穷集)

图数( function)映射( mapping) 单值的二元关系称为函数或映射 单值:Yx∈domF,Wy; zoran, XFy∧xFz→>y=z 秦F()=yEF台Xy 单值 秦⑦是空函数 常用F,G,H,千g,h,表示函数 非 《集合论与图论》第9讲

《集合论与图论》第9讲 2 函数(function),映射(mapping) 单值的二元关系称为函数或映射 单值: ∀x∈domF, ∀y,z∈ranF, xFy ∧ xFz → y=z F(x)=y ⇔ ∈F ⇔ xFy ∅是空函数 常用F,G,H,…,f,g,h,…表示函数. x yz 非单值 单值

偏函数( partial function) 偏函数:domFB={F|FA→B} 《集合论与图论》第9讲

《集合论与图论》第9讲 3 偏函数(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={ab},B={12},求AB 解:|A=2B|=2A×B=4P(A×B)=24=16 ,f1={a,1>,f2={a2)} 5-{b,1>3,4={b,2> f5={,b,1265-{a1> a2>,b,12y={,} AB={6 0112;13415647.8 ↓.# 非函数:{21,8a,2},{b,1>,,,<b,12… 《集合论与图论》第9讲

《集合论与图论》第9讲 4 例1 例1: 设 A={a,b}, B={1,2}, 求A→B. 解: |A|=2,|B|=2,|A×B|=4,|P(A×B)|=24=16. f0=∅, f1={}, f2={}, f3={}, f4={}, f5={,}, f6={,}, f7={,},f8={,}. A→B = {f0 ,f1 ,f2 ,f3 ,f4 ,f 5,f6 ,f7 ,f8}. # 非函数: {,}, {,}, {,,},…

全函数 total function) 全函数:domF=A 全函数记作F:A→>B A到B的全体全函数记为BA或A→>B RA =A→>B={F|F:A>B} 《集合论与图论》第9讲

《集合论与图论》第9讲 5 全函数(total function) 全函数: domF=A 全函数记作 F:A→B A到B的全体全函数记为BA或A→B BA = A→B = { F | F:A→B }

关于BA的说明 +BA=A>B=FF: A>B1 F是A到B的全函数} BAl= BIA 当A=时,B={} 秦当A≠且B=时,B=A→B=, 但A→>B={} 《集合论与图论》第9讲

《集合论与图论》第9讲 6 关于BA的说明 BA = A→B = {F|F:A→B} = {F|F是A到B的全函数} |BA| = |B||A|. 当A=∅时, BA={∅} 当A≠∅且B=∅时, BA=A→B=∅, 但A→B={∅}.

真偏函数( proper partial function) 婚真偏函数: domFcA, 真偏函数记作F:A→B, 癱A到B的全体真偏函数记为A+B AB=FIF: A+>B) 《集合论与图论》第9讲

《集合论与图论》第9讲 7 真偏函数(proper partial function) 真偏函数: domF⊂A, 真偏函数记作F:A→B, A到B的全体真偏函数记为A→B A→B = { F | F:A→B }

例1(续) 例1(续):设A=aby.B=12求AB 解:f6=0,f1={3 f3={b,1f-{b2> 5-{a,1>,b,1>},f6-{a,1>,b,2> 千={a,2>,b,1={a2>,b,2 AB={6,f1,f2,f3,f# 说明:F∈A→B→F∈domF→B F∈A→>B→F∈domF>B 《集合论与图论》第9讲

《集合论与图论》第9讲 8 例1(续) 例1(续): 设 A={a,b}, B={1,2}, 求A→B. 解: f0=∅, f1={}, f2={}, f3={}, f4={}, f5={,}, f6={,}, f7={,},f8={,}. 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 偏函数A→B domFcA 全函数A→B 真偏函数A+B domF=A domFca 《集合论与图论》第9讲

《集合论与图论》第9讲 9 三者关系 A→B = A→B ∪ A→B 偏函数A→B domF⊆A 全函数A→B domF=A 真偏函数A→B domF⊂A

全函数性质 秦设F:A→B, 单射( njection)F是单根的 满射( ejection):ranF=B 秦双射( bijection)F既是单射又是满射,亦 称为一一对应( one-to-one mapping) 非单射 非满射 《集合论与图论》第9讲

《集合论与图论》第9讲 10 全函数性质 设 F:A→B, 单射(injection): F是单根的 满射(surjection): ranF=B 双射(bijection): F既是单射又是满射, 亦 称为一一对应(one-to-one mapping). 非单射 非满射