- 1、本文档共7页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
05-函数-离散数学讲义-海南大学(共十一讲)
5函数Function
§5.1 函数
函数的定义
A到B上的函数,f : A→B,是A到B的一个关系,对每个a∈Dom(f), f(a)∈B, f(a)恰有一个元素,即f(a)唯一确定。
(a,b)∈f, afb,记做f(a)=b.
函数也叫映射mappings或变换transformations
a叫做f的argument,f(a)叫做函数的值value,也叫a的像。
例1. A={1,2,3,4}, B={a,b,c,d}, f={(1,a), (2,a), (3,d), (4,c)}
f是一个函数。
例2设P是一个程序,输入输出都是整数,(m, n)∈fP意为输入m时程序运行输出n。则fP是一个函数。
标识图是一个图每个顶点或每条边或两者都带有标记。例如一个图的顶点代表一个城市,边代表两个城市之间的距离。设V是顶点集,L是标记集,则f:V→L是一个函数。用E作边集,g:E→L,也是一个函数。
f:Z→Z,
f(a)= f是函数。
恒等函数1A(a)=a是函数。
函数的复合
设f:A→B,g:B→C,是函数,则g?f:A→C,是函数。
g?f(a)=g(f(a))
例6.设f,g都是整数函数,
f(a)=a+1, g(b)=2b.
则 g?f (a)=2(a +1) 是整数集到偶数集的函数。
f?g(a)=2a+1也是整数集到奇数集的函数。
特殊函数Special Type of Functions
处处有定义everywhere defined:Dom(f)=A,
满函数,到上onto:Ran(f)=B.
一对一函数one to one,
单值函数bijection:a≠b (f(a)≠f(b), 或f(a)=f(b) (a=b.
一一对应
one to one correspondence:处处有定义,满,一一函数。
例13.设是A上所有等价关系的集合,Π是A的所有划分的集合,
f:R→Π,
R是A上等价关系, A/Ri是A上划分,
则f(R)=A/R是R到Π的一一对应。
可逆函数Invertible Functions
f-1也是函数,就称f是可逆函数。
例14. A={1,2,3,4}, B={a,b,c,d}, f={(1,a), (2,a), (3,d), (4,c)}
f是一个函数。
f-1={(a,1), (a,2), (d,3), (c,4)}不是函数,f不可逆。
例15.f(a)=a+1,f:Z→Z,f是一一的,因此可逆。
例16.f(x)=x2,f:R→R,f不是一一的,因此不可逆。
定理2. 设f:A→B是一个函数:
(a)1B? f= f.
(b)f?1A= f.
设f:A→B是一一对应:
(c)f-1? f=1A.
(b) f? f-1=1B.
定理3.设f:A→B, 设g:B→A都是函数.
g?f=1A,则f 单,处处有定义,
g满。
g?f =1A,f?g=1B. 则f,g
都是一一对应,f-1=g, g-1=f.
f,g可逆,则g? f可逆,
(g? f)-1=f-1?g-1
例17.f:R→R是一个函数,
f(x)=2x3-1,则f是单值函数。
令g(y)=
(g?f)(x)= g(f(x)=x, g?f=1R.
(f?g)(y)= f(g(y)=y, f?g=1R
f,g都是可逆函数,f,g都是单值函数。
定理4. 设A,B都是有限集,|A|=|B|,
f:A→B是一个函数,处处有定义。
f一一(f满。
f满(f一一。
§5.2 计算机科学中的函数
特征函数
模函数
f(n)=n!
floor function f(x)=( x (
ceiling function f(x)=(x(
多项式函数,指数函数 对数函数
l(w) 字符串长度函数,
pow(B) 幂集函数,
t(M)=MT矩阵转置函数
GCD(a,b) 最大公因数
LCM(a,b) 最小公倍数
布尔函数Boolean function
取值真假的函数。∧,∨,(
哈希函数Hashing Function
§5.3 函数的递增性Growth of Functions
设f和g都是Z+上函数。
如果存在常数c和k,使|f(n)|≤c|g(n)|, 对所有n≥k成立,记作f=O(g).
f=O(g)意为f增长得不比g快。
f=1/2×n3+3n2+1
f=O(n3)
f=O(n4)
n3=O(f)
n4(O(f)
如果f=O(g),g(O(f),称f的阶低于g的阶。
f ,g的阶
您可能关注的文档
最近下载
- 仁爱英语八年级上册Unit2-Topic2-SectionC-教学设计.doc VIP
- 慢性粒细胞白血病治疗病例分享.pptx
- 《糖皮质激素类药物临床应用指导原则2023版》解读PPT课件.pptx VIP
- 《兽医临床诊疗技术》教学课件合集.pptx
- 山塘整治--塘坝除险整治技术指南.ppt
- 小学音乐四年级花城版《山》教学课件.ppt
- 巴黎奥运会潘展乐的飞鱼人生介绍PPT课件(图文).pptx
- 个人征信报告模板征信报告模板(2021简版带水印).docx
- 北师大版七年级上册数学 2.1 有理数 PPT课件.ppt
- 第4课 互联网创新发展 教学设计 2023—2024学年浙教版(2023)初中信息技术七年级上册.docx
文档评论(0)