第八章 函数 主讲：李春英 办公地点：软件大楼202 E-Mail：zqxylcy@163.com 第八章 函数 主讲：李春英 办公地点：软件大楼202 E-Mail：zqxylcy@163.com 离散数学资源：http://www.scholat.com/teamIndex.html?teamId=187

第八章 函数 主要内容 某些重要的函数 函数定义与相关概念 恒等函数、常函数、单调函数 函数定义 函数相等 从A到B的函数f:AB 函数的复合与反函数 函数的复合运算 函数的逆运算 主要内容 函数定义与相关概念 函数定义 函数相等 从A到B的函数f:AB BA 函数的类型 单射、满射、双射函数

第八章 函数 学习要求 重点掌握 一般掌握 了解 1 2 3 1 函数的概念； 1 单射、满射和双射函数的证明; 2 单射、满射和双射函数的概念； 3 函数的复合运算和逆运算。 2 1 单射、满射和双射函数的证明; 2 函数与关系的区别和联系。 3 函数与计算机输入-输出的关系。

8.1 函数的定义与性质 主要内容 函数定义与相关概念 函数定义 函数相等 从A到B的函数f:AB BA 函数的类型 单射、满射、双射函数的定义与实例 某些重要的函数

8.1 函数的定义与性质 函数是数学的一个基本概念。 函数的概念在日常生活和计算机科学中非常重要。 高等数学中连续函数的概念推广到对离散量的讨论（将函数看作是一种特殊的二元关系）。 函数的概念在日常生活和计算机科学中非常重要。 各种高级程序语言中使用了大量的函数。 实际上，计算机的任何输出都可看成是某些输入的函数。 5

8.1 函数定义 定义8.1 设 F 为二元关系, 若x∈domF 都存在唯一的 8.1 函数定义 定义8.1 设 F 为二元关系, 若x∈domF 都存在唯一的 y∈ranF 使 <x,y>∈ F成立, 则称关系F 为函数（或 映射、变换）。对于函数F, 如果有<x,y>∈ F, 则记作 y=F(x), 并称 y 为x在函数F下的值。 例1：F1={<x1,y1>,<x2,y2>,<x3,y2>} F1是函数 F2={<x1,y1>,<x1,y2>} F2不是函数 如果关系F具备（1）的情况，那么F就不是函数： （1） x ∈domF，在ranF 中有两个及两个以上的值。 6 6

例2：函数F(x)=(x21)/(x+1), G(x)=x1。 函数相等 定义8.2 设F, G 为函数, 则F=G  FG∧GF 。 如果两个函数F 和 G 相等, 一定满足下面两个条件： (1) domF=domG ； (2) x∈domF=domG 都有F(x)=G(x) 。 例2：函数F(x)=(x21)/(x+1), G(x)=x1。 函数F(x)、G(x)是否相等？ 不相等！ 因为 domF≠domG. 7

从A到B的函数 定义8.3 设A, B为集合, 如果 f 为函数, domf=A, ranfB, 则称 f 为从A到B的函数, 记作 f：A→B. 例4：设A={1,2,3,4},B={a,b,c,d}，试判断下列关系哪些是 从A到B的函数。如果是，请写出它的值域。 （1）f1={<1,a>,<2,a>,<3,d>,<4,c>}； f1是从A到B的函数。 ranf1={a,c,d} 。 （2）f2={<1,a>,<2,a>,<2,d>,<4,c>}； f2不是函数。 因为domf2={1,2,4}≠A且元素2有两个不同的值a和d。 （3）f3={<1,a>,<2,b>,<3,d>,<4,c>}； f3是从A到B的函数。 ranf3={a,b,c,d} 。 （4）f4={<2,b>,<3,d>,<4,c>}。 f4是函数，但不是从A到B的。因为domf4={2,3,4}≠A 。 8

从A到B的函数的结论 结 论 （1）<x,y>∈ F y=f(x)； 结 论 （1）<x,y>∈ F y=f(x)； （2）<x,y>∈ F ∧<x,z>∈ F y=z； （3）|F|=|A|； （4） F(x)表示一个变值， F代表一个集合， 因此F ≠ F(x)。 如果关系F具备下列两种情况之一，那么F就不是从A到B的函数： （1） x ∈A，在B 中没有值； （2） x ∈A，在B中有两个及两个以上的值。 9

函数与关系 例5：设A={a,b},B={1,2}，分别写出A到B的不同关系和不同函数。 解：因为|A|=2 ，|B|=2，所以|A×B|=|A|×|B|=4，即 A×B={<a,1>,<a,2>,<b,1>,<b,2>}， 此时从A到B的不同的关系有24=16个。 分别为：R0=Φ； R1={<a,1>}；R2={<a,2>}；R3={<b,1>}；R4={<b,2>}； R5={<a,1>,<a,2>}；R6={<a,1>,<b,1>}； R7={<a,1>,<b,2>}；R8={<a,2>,<b,1>}； R9={<a,2>,<b,2>}；R10={<b,1>,<b,2>}； R11={<a,1>,<a,2>,<b,1>}；R12={<a,1>,<a,2>,<b,2>}； R13={<a,1>,<b,1>,<b,2>}；R14={<a,2>,<b,1>,<b,2>}； R15={<a,1>,<a,2>,<b,1>,<b,2>}。 10

函数与关系的差别 函数是一种特殊的关系，它与一般关系比较具备如下差别： 个数差别：从A到B的不同的关系有2|A||B|个；但从A到B的不同的函数却仅有|B||A|个。 集合元素有序对的第一个元素存在差别：关系中有序对的第一个元素可以相同；函数中有序对的第一元素一定是互不相同的。 集合长度的差别：每一个函数的长度都为|A|个(|f|=|A|)，但关系的长度却为从0一直到|A|×|B|。 11

A到B的函数的集合 定义8.4 所有从A到B的函数的集合记作BA, 读作“B上A”。符号化表示为BA = { f | f：A→B } 。 |A|=m, |B|=n, 且m, n>0, |BA|=nm 例6： A={a,b,c},B={1,2}, 求BA. 解：BA={ f0, f1, … , f7}, 其中 f0 = {<a,1>,<b,1>,<c,1>} f2 = {<a,1>,<b,2>,<c,1>} f4 = {<a,2>,<b,1>,<c,1>} f6= {<a,2>,<b,2>,<c,1>} f1 = {<a,1>,<b,1>,<c,2>} f3 = {<a,1>,<b,2>,<c,2>} f5 = {<a,2>,<b,1>,<c,2>} f7 = {<a,2>,<b,2>,<c,2>}

函数的类型 定义8.6 设 f：A→B, (1) 若 ranf=B, 则称 f:A→B是满射的. (2) 若 y∈ranf 都存在唯一的 x∈A 使得 f(x)=y, 则称 f:A→B 是单射的. (3) 若 f:A→B 既是满射又是单射的, 则称 f:A→B是双射的. 例7 判断下面函数是否为单射, 满射, 双射的, 为什么? （1）f:Z+→R, f(x) = lnx。 f(x)是单调上升的, 是单射的. 但不是满射的。 ranf={ln1, ln2, …} R.

函数的类型 定义8.6 设 f：A→B, (1) 若 ranf=B, 则称 f:A→B是满射的. (2) 若 y∈ranf 都存在唯一的 x∈A 使得 f(x)=y, 则称 f:A→B 是单射的. (3) 若 f:A→B 既是满射又是单射的, 则称 f:A→B是双射的. 例7 判断下面函数是否为单射, 满射, 双射的, 为什么? (2) f:R→R, f(x)=2x+1。 是满射、单射、双射的。 因为它是单调函数并且ranf=R。

例8：确定下列函数的类型。 （1）设A={1,2,3,4,5},B={a,b,c,d}。f:A→B定义为： {<1,a>,<2,c>,<3,b>,<4,a>,<5,d>}； f是满射函数，因为domf=A，ranf=B 。 （2）设A={1,2,3},B={a,b,c,d}。f:A→B定义为： f={<1,a>,<2,c>,<3,b>}； f是单射函数，ranf B。 （3）设A={1,2,3},B={1,2,3}。f:A→B定义为 f={<1,2>,<2,3>,<3,1>}； f是双射函数，因为f既是单射函数，又是满射函数。

结 论 设A，B为有限集合，f是从A到B的函数，则： f是单射的必要条件为|A|≤|B|； f是满射的必要条件为|B|≤|A|； 结 论 设A，B为有限集合，f是从A到B的函数，则： f是单射的必要条件为|A|≤|B|； f是满射的必要条件为|B|≤|A|； f是双射的必要条件为|A|＝|B|。 A B

函数类型证明方法 1. 证明 f:AB是满射的方法: 任取 yB, 找到 x (即给出x的表示)或者证明存在xA，使得f(x)=y。 f(x1)=f(x2)  …  x1=x2 推理前提 推理过程 推理结论 方法二 x1,x2A, x1x2  …  f(x1)f(x2) 3. 证明 f:AB不是满射的方法： 找到 yB, yranf 。 4. 证明 f:AB不是单射的方法：找到 x1,x2A, x1x2, 且 f(x1)=f(x2)。

某些重要函数 定义8.7 (1)设 f:A→B, 如果存在c∈B使得对所有的 x∈A都有 f(x)=c, 则称 f:A→B是常函数。 (2) 称 A上的恒等关系IA为A上的恒等函数, 对所有的x∈A都 有IA(x)=x。 (3) 设<A, ≼>, <B, ≼>为偏序集，f:A→B，如果对任意的 x1, x2∈A, x1≺x2, 就有 f(x1)≼ f(x2), 则称 f 为单调递增的；如 果对任意的x1, x2∈A, x1≺x2, 就有f(x1) ≺f(x2), 则称 f 为严 格单调递增的. 类似的也可以定义单调递减和严格单调递 减的函数。

8.2 函数的复合与反函数 主要内容 复合函数基本定理 函数的复合运算与函数性质 反函数的存在条件 反函数的性质

复合函数基本定理 定理8.1 设F, G是函数, 则FG也是函数, 且满足 (1) dom(FG)={x|x∈domF∧F(x)∈domG} (2) x∈dom(FG)有FG(x)=G(F(x)) 例10：设A={1,2,3,4,5},B={a,b,c,d},C={1,2,3,4,5}, 函数f:A→B， g:B→C定义如下： f={<1,a>,<2,a>,<3,d>,<4,c>,<5,b>}； g={<a,1>,<b,3>,<c,5>,<d,2>}。 求fog。 解 fog={<1,1>,<2,1>,<3,2>,<4,5>,<5,3>}

函数的复合不满足交换律，但满足结合律。 结合律请同学们自己验证！ 例11：设f:R→R,g:R→R,h:R→R，满足f(x)=2x, g(x)＝(x+1)2,h(x)＝x/2。计算： （1）fg，gf； （2）fh，hf。 解（1）fg(x)＝g(f(x))＝g(2x)＝(2x+1)2； gf(x)＝f(g(x))＝f((x+1)2)＝2(x+1)2； （2）fh(x)＝h(f(x))＝h(2x)＝x； hf(x)＝f(h(x))＝f(x/2)＝x； 　 函数的复合不满足交换律，但满足结合律。 结合律请同学们自己验证！

反函数 定义：设f:A→B的函数。如果 f-1＝{<y,x>|x∈A∧y∈B∧<x,y>∈f}是从B到A的函数，则称f-1：B→A为f：A→B的逆函数。 可以看出，一个函数的逆运算也是函数。即逆函数f-1存在当且仅当f是双射。 反函数存在的条件 (1) 任给函数F, 它的逆F 1不一定是函数, 只是一个二元关系. (2) 任给单射函数 f:A→B, 则f 1是函数, 且是从ranf 到A的双 射函数, 但不一定是从B到A的双射函数 (3) 对于双射函数 f:A→B, f 1:B→A是从B到A的双射函数.

例12：试求出下列函数的逆函数。 （1）设A={1,2,3},B={1,2,3}。f1:A→B定义为 f1={<1,2>,<2,3>,<3,1>}； f1-1={<2,1>,<3,2>,<1,3>} （2）f2={<0,1>,<1,1/2>,…,<n,1/(n+1)>,…} f2-1={<1,0>,<1/2,1>,…,<1/(n+1) , n>,…} （3）f3={<x,x+1>|x∈R}。 f3-1={<x+1,x>|x∈R}

本章总结 （1）函数的概念。注意函数与关系的区别和联系； （2）单射、满射和双射函数的概念； （3）特殊函数的基本概念； （4）函数的复合运算，逆运算。

作 业 P160：第2题； P161：第6题 （1）、（5）、（8）； P162：第17题的前3个和最后1个，再求f-1 和g-1。

练习1 1．给定A, B 和 f, 判断是否构成函数 f:A→B. 如果是, 说明该 函数是否为单射、满射、双射的. 并根据要求进行计算. (4) A=B=R, f(x)=x3 (5) A=B=R+, f(x)=x/(x2+1). (6) A=B=R×R, f(<x,y>)=<x+y, xy>, 令 L={<x,y>|x,y∈R∧y=x+1}, 计算 f(L). (7) A=N×N, B=N, f(<x,y>)=|x2y2|. 计算f(N×{0}), f 1({0})

解答 (1) 能构成 f:A→B, f:A→B既不是单射也不是满射, 因为 f(3)=f(5)=9, 且7ranf. (2) 不构成 f:A→B, 因为 f 不是函数. <1,7>∈f 且<1,9>∈f, 与函 数定义矛盾 (3) 不构成 f:A→B, 因为dom f = {1,2,3,4} ≠ A (4) 能构成 f:A→B, 且 f:A→B是双射的 (5) 能构成 f:A→B, f:A→B既不是单射的也不是满射的. 因为该 函数在 x=1取极大值 f(1)=1/2. 函数不是单调的,且ranf≠R+. (6) 能构成 f:A→B, 且 f:A→B是双射的. f(L) = {<2x+1,1>|x∈R}=R×{1} (7) 能构成 f:A→B, f:A→B既不是单射的也不是满射的. 因为 f(<1,1>)=f(<2,2>)=0, 2ranf. f(N×{0}) = {n202|n∈N} = {n2|n∈N} f1({0}) = {<n,n>|n∈N 解

练习2 2.设 证明 f 既是满射的，也是单射的. 证 任取<u,v>RR，存在 使得 因此 f 是满射的 对于任意的 <x,y>, <u,v>RR, 有 因此 f 是单射的.

函数运算的应用 例8.3.4 假设f是的定义如下表。 即f(A)=D,f(B)=E,f(C)=S,…等等。 试找出给定密文“QAIQORSFDOOBUIPQKJBYAQ”对应的明文。 A B C D E F G H I J K L M S T N Y O P Q R U V W X Z

函数运算的应用 解由表8.3.1知，f-1如如下表所示。 将密文“QAIQORSFDOOBUIPQKJBYAQ”中的每一个字母在f-1中找出其对应的象就可得出对应的明文：“THETRUCKARRIVESGONIGHT”。 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

例8.3.5 设按顺序排列的13张红心纸牌， A2345678910JQK 经过1次洗牌后牌的顺序变为 38KA410QJ57629 再经两次同样方式的洗牌后牌的顺序是怎样的？

例8.3.5 解 对应结果见下表。 A 2 3 4 5 6 7 8 9 10 J Q K f fof fofof

实 例 例：设P是接受一个整数作为输入并产生一个整数作为输出 的计算机程序。令A=B=Z，则由P确定的关系fp定义如下 实 例 例：设P是接受一个整数作为输入并产生一个整数作为输出 的计算机程序。令A=B=Z，则由P确定的关系fp定义如下 ：如果<m,n>∈fp当且仅当输入m时，由程序P所产生的 输出是n。 请判断fp是否为一函数？ 2019/5/18

实 例 解 答 解答：显然，fp是一个函数。因为，任意一个特殊的输入对 应唯一的输出。 可用任意一个可能的输入集合A对应输出集合B而推广 实 例 解 答 解答：显然，fp是一个函数。因为，任意一个特殊的输入对 应唯一的输出。 可用任意一个可能的输入集合A对应输出集合B而推广 到一般情形的程序。 所以，通常把函数看做输入－输出的关系。 2019/5/18