大学离散数学《函数》专题课件

离散数学专题离散数学专题：函数定义·性质·复合·应用DATE2026年内容导览01函数基础集合论定义与基本概念02函数性质单射满射双射与基数03特殊函数复合反函数与典型类型04综合应用计算机科学中的函数章节01函数基础从集合出发理解函数函数是集合之间的特殊对应关系从集合定义函数设A、B为集合，从A到B的函数f是笛卡尔积A×B的子集判两条判定条件全域性对每个

a∈A，都存在

b∈B

使(a,b)∈f单值性若(a,b₁)∈f且(a,b₂)∈f，则

b₁=b₂记记法与映射记法f:A→B，f(a)=b映射函数又称映射，是离散数学最基本的概念之一定义域、陪域与值域区分函数三大构成要素，突出值域与陪域的包含关系定定义域符号dom(f)=A含义函数允许的输入全体输入陪陪域符号codom(f)=B含义函数输出所在的目标集合目标集合值值域符号ran(f)={f(a)|a∈A}含义实际取到的输出全体实际输出函数相等与函数图像函数相等：定义域相同，且对每个a都有

f(a)=g(a)注意与图像对应规则相同但定义域或陪域不同，视为不同函数。函数图像：G(f)={(a,f(a))|a∈A}，是A×B的子集。图像是函数的可视化表示，函数与其图像一一对应。关系与函数的区别对比项二元关系函数定义A×B的任意子集满足单值性的特殊关系单值性不要求必须满足全域性不要求必须满足一个输入可对应多个输出只能对应一个输出函数是满足单值性与全域性的特殊二元关系单值性全域性函数的两个必备性质单值性：一个输入只对应一个输出全域性：定义域内每个输入都有输出常见函数类型离散函数4类取整函数阶乘函数模运算函数特征函数连续函数3类多项式函数指数函数对数函数按性质分类3类单射满射双射按定义域分类2类有限集上的函数无限集上的函数函数概念的理解要点“常见误区：把值域直接等同于陪域；忽略定义域讨论对应规则”单值性函数的本质一个输入只对应唯一输出函数的本质定义域2项不可分割定义域是函数不可分割的组成部分前提条件不能脱离定义域谈论函数陪域与值域2项陪域陪域是目标范围值域值域是实际取值章节02函数性质分类讨论揭示本质单射满射双射刻画函数的对应特征单射函数及其判定又称

一对一函数，不同输入必给不同输出定义对任意a₁,a₂∈A，若

f(a₁)=f(a₂)，则

a₁=a₂等价表述若

a₁≠a₂，则

f(a₁)≠f(a₂)正例f:R→R，f(x)=2x+1

是单射反例f:R→R，f(x)=x²

不是单射，因

f(1)=f(-1)VSVS满射函数及其判定定义：对每个

b∈B，都存在

a∈A，使

f(a)=b等价表述：值域等于陪域，即ran(f)=B又称映上函数，陪域中每个元素都被取到正反例对照类型函数判定说明正例f:R→R，f(x)=x³✅

满射每个实数都有原像反例f:R→R，f(x)=x²❌

非满射负数取不到双射函数与一一对应一个函数若既单射又满射，则称为双射实例f:R→Rf(x)=2x+1

是双射意义2项等势基础工具双射是判断两个集合等势的基础工具个数相同有限集合间存在双射，当且仅当两集合元素个数相同三类性质的关系与判定双射=单射+满射，三者关系因集合规模而异有限集合若两集合元素个数相等，则单射、满射、双射三者等价无限集合三者不等价，需分别验证判定技巧一通过像集大小与陪域大小的比较判断满射判定技巧二通过方程

f(a)=b

解的存在性与唯一性判断VS有限集合上的函数计数函数总数随陪域增大快速攀升，单射函数增长更为迅猛鸽巢原理与基数比较鸽巢原理：n+1

个物品放入

n

个盒子，至少一个盒子装有两个物品函数联系不存在从

n+1元集到

n元集的单射推广形式k·n+1

个物品放入

n

个盒子，至少一个盒子装有

k+1

个典型应用有限集合不能与其真子集建立双射章节03特殊函数运算与逆运算的视角复合与反函数拓展函数的表达力复合函数设f:A→B，g:B→C，复合函数g∘f:A→C，满足(g∘f)(a)=g(f(a))成立条件f的陪域必须包含于g的定义域复合顺序先作用f再作用g记法从右向左读复合结果(g∘f)(a)=g(f(a))实例推导取f(x)=x+1代入g得g(f(x))=2(x+1)展开得2x+2(g∘f)(x)=2(x+1)=2x+2复合函数的性质结合律(h∘g)∘f=h∘(g∘f)复合运算满足结合律不满足交换律g∘f≠f∘g一般情形下不满足交换律单射保持f与g均为单射，则g∘f为单射满射保持f与g均为满射，则g∘f为满射双射保持f与g均为双射，则g∘f为双射反函数只有当f是双射时，反函数才存在反函数核心要点3项定义设f:A→B为双射，则f⁻¹:B→A，f⁻¹(b)=a当且仅当f(a)=b基本性质f⁻¹∘f=id_A；f∘f⁻¹=id_B示例求f(x)=2x+1的反函数：由y=2x+1解得x=(y−1)/2，故

f⁻¹(x)=(x−1)/2反函数的性质与求解核心恒等式2项(f⁻¹)⁻¹=f反函数的反函数是自身(g∘f)⁻¹=f⁻¹∘g⁻¹复合的反函数，顺序恰好反转求解步骤与图像特征4项验证双射由y=f(x)解出x交换x与y图像特征反函数图像与原函数图像关于直线

y=x

对称恒等函数与常函数恒等函数定义id_A:A→A，id_A(a)=a，把每个元素映射到自身性质恒等函数是双射地位复合运算的单位元，满足f∘id=id∘f=f常函数定义f(a)=c，所有输入都映射到同一个固定值判定定义域含多个元素时，既非单射也非满射（除陪域为单点集）恒等函数是复合运算的单位元，在函数复合中扮演特殊角色。特征函数与取整函数取整函数在算法分析与数论证明中经常出现特征函数集合运算定义对子集S，χ_S(a)=1（当a∈S），否则为

0用途把集合交并补运算转化为算术运算，在组合计数中广泛使用下取整x表示不超过x的最大整数上取整x表示不小于x的最小整数章节04综合应用理论落地于计算实践函数是计算机科学的核心数学工具函数在算法分析中的应用将函数思想对接算法复杂度分析，用增长率比较衡量算法效率函数增长率比较是算法效率评估的核心方法T(n)描述输入规模为n时的执行步数时间复杂度用函数表示以函数刻画算法随规模变化的开销输入规模n决定步数多少n越大，执行步数随之变化常用增长函数5项常数对数线性平方指数大O记法借助函数比较增长速率以函数增长率刻画算法效率高低忽略常数因子聚焦增长趋势本身而非系数细节哈希函数与数据映射冲突需专门策略处理哈希函数：将键映射到存储表位置的函数理理想情况：单射映射单射每个键对应唯一存储位置对应键与位置一一对应实实际问题：冲突现象多对一多个键映射到同一位置冲突产生冲突哈希函数设计质量直接影响查找效率函数与密码学函数性质为密码体制的安全性提供数学保障对称加密加密函数为可逆双射密钥决定具体映射单向函数正向计算容易逆向求解困难公钥密码的基础应用实例RSA算法依赖模幂运算的不可逆性函数在数据管理中的应用函数思想贯穿数据管理的映射与检索数据结构字典与关联数组本质上是键到值的函数数据库索引把键映射到记录位置的函数加速检索查询操作可视为对数据集合的函数求值关系规范化依赖函数依赖概念的判定函数与计算模型λ演算与图灵机计算能力等价，是可计算性理论的基础模型函数式计算范式以函数组合与求值为核心组织程序函数组合求值λ演算刻画函数抽象与应用的严格形式系统函数抽象形式系统编程语言影响函数思想深刻影响现代编程语言的设计与实现语言设计实现