离散数学-----函数

1、2020/9/3,1,第8章 函数,8.1 函数的定义 8.2 函数的性质 8.3 一些常用函数 8.4 函数的复合和反函数 8.5 集合的势,2020/9/3,2,8.1 函数的定义,定义8.1 设 f 为二元关系, 若 xdomf 都存在唯一的yranf 使 x f y 成立, 则称 f为函数. 对于函数f, 如果有 x f y, 则记作 yf(x), 并称 y 为 f 在 x 的值. 例如 f1, f2,2020/9/3,3,8.1 函数的定义,从A到B的函数 定义8.3 设A, B为集合, 如果 (1) f 为函数 (2) domf = A (3) ranf B, 则称 f 为从A到B

2、的函数, 记作 f : AB.,2020/9/3,4,8.1 函数的定义,例1： 设A 1,2,3,4，B a,b,c,判断如下A到B的二元关系中，哪些是A到B的函数？ f1, f2, f3, f4, ,2020/9/3,5,8.1 函数的定义,例2：判断下列关系中哪些能构成函数？ （1）f|x,yN, xy10 （2）f|x,yR, xy2 （3）f|x,yN, yx1,2020/9/3,6,8.1 函数的定义,例3： 设A 1, 2, 3, B a, b，则A到B共有多少个不同的函数？分别列出来。 解： f0=, , f1=, f2=, ,f3=, f4=, f5=, f6=, , f7=

3、,2020/9/3,7,8.1 函数的定义,3.B上A 定义8.4 所有从A到B的函数的集合记作BA，读作“B上A”即： BAf | f : AB,思考：设|A|=m,|B|=n,则|BA|=？,2020/9/3,8,8.1 函数的定义,解： 设：A=x1, x2, ,xm, B=y1, y2, ,yn, 则集合A到B的函数f形如： f， ， 对于每个所在的 位置都可用B中的任何一个元素代替，即有n种不同的取法，这样的组合共有nm个。 因此A到B共有nm个不同的函数,即： |BA|= |B|A| 。,2020/9/3,9,8.2 函数的性质,定义8.6 设 f : AB, （1）若ranf =

4、 B, 则称 f : AB是满射的. （2）若 yranf 都存在唯一的 xA使得 f(x)=y, 则称 f : AB是单射的.（3）若 f : AB既是满射又是单射的, 则称 f : AB是双射的。 注: (1) f 满射意味着：y B, 都存在 xA 使得 f(x)=y. (2) f 单射意味着：f(x1)=f(x2) x1=x2,2020/9/3,10,8.2 函数的性质,例：,2020/9/3,11,8.2 函数的性质,例8.4 判断下面函数是否为单射, 满射, 双射的, 为什么?（1）f : RR, f(x)= x2+2x1（2）f : Z+R, f(x)=lnx（3）f : RZ,

5、 f(x)=x（4）f : RR, f(x)=2x+1,2020/9/3,12,解 (1) f : RR, f(x)= x2+2x1 (2) f : Z+R, f(x)=lnx (3) f : RZ, f(x)= x (4) f : RR, f(x)=2x+1,8.2 函数的性质,在x=1取得极大值0. 既不是单射也不是满射的.,单调上升, 是单射的. 但不满射, ranf=ln1, ln2, .,是满射的, 但不是单射的, 例如 f(1.5)=f(1.2)=1.,是满射、单射、双射的, 因为它是单调函数并且ranf=R.,2020/9/3,13,8.3 一些常用函数,定义8.7 (1) 设f

6、：AB, 如果存在 cB 使得对所有的 xA 都有 f(x)=c, 则称 f : AB是常函数. (2) 称 A 上的恒等关系 IA为 A 上的恒等函数, 对所有的xA 都有 IA(x)=x.,2020/9/3,14,8.3 一些常用函数,(3) 设f : AB， 如果对任意的 x1, x2A, x1x2, 就有 f(x1) f(x2), 则称 f 为单调递增的； 如果对任意的 x1, x2A, x1x2, 就有 f(x1) f(x2), 则称 f 为严格单调递增的. 单调递减 严格单调递减,2020/9/3,15,8.3 一些常用函数,(4) 设 A 为集合, 对于任意的 A A, A 的特

7、征函数 A : A0,1 定义为,实例： 设A=a,b,c, A的每一个子集 A都对应于一个特征函数, 不同的子集对应于不同的特征函数. 如 = ,， a,b = ,.,2020/9/3,16,(5) 设 R 是 A 上的等价关系, 令g : AA/Rg(a) = a （aA）称 g 是从 A 到商集 A/R 的自然映射.,8.3 一些常用函数,2020/9/3,17,8.3 一些常用函数,例： 已知 A=1, 2, 3上的等价关系如下，确定A到相应商集的自然映射。 R1=,IA R2=,IA R3=,IA R4=EA R5=IA,2020/9/3,18,8.3 一些常用函数,注意： 给定集合

8、 A 和 A 上的等价关系 R, 就可以确定一个自然映射 g : AA/R. 不同的等价关系确定不同的自然映射, 恒等关系所确定的自然映射是双射, 而其他的自然映射一般来说只是满射.,2020/9/3,19,8.4 函数的复合和反函数,例:,gf=,2020/9/3,20,8.4 函数的复合和反函数,定理8.1 设f, g是函数, 则fg也是函数, 且满足 (1) dom(fg)= x | xdomf f(x)domg (2) xdom(fg) 有 fg(x) = g(f(x),2020/9/3,21,8.4 函数的复合和反函数,推论1 设f, g, h为函数, 则(fg)h 和 f(gh)都

9、是函数, 且 (fg)h = f(gh) 推论2 设f : AB, g : BC, 则 fg : AC, 且xA都有 fg(x) = g(f(x).,2020/9/3,22,8.4 函数的复合和反函数,函数复合的性质 定理8.2 设 f : AB, g : BC. (1) 如果 f : AB, g : BC都是满射的, 则 fg : AC也是满射的. (2) 如果 f : AB, g : BC都是单射的, 则 fg : AC也是单射的. (3) 如果 f : AB, g : BC都是双射的, 则 fg : AC也是双射的.,2020/9/3,23,8.4 函数的复合和反函数,反函数的存在条件及

10、定义 定理8.4 设 f : AB是双射的, 则f1: BA也是双射的.,2020/9/3,24,8.5 集合的势,集合的势 集合的势是量度集合所含元素多少的量。 集合的势越大，所含的元素越多。,2020/9/3,25,8.5 集合的势,问题： 集合势的大小与函数的关系？ 解： 设A，B为任意集合,如果存在函数f:A B,满足： f是满射的，则 |A|B|； f是单射的，则 |A|B|； A .B f为双射的，则 |A|B|。 AB f是单射的，且不存在A到B的双射，则|A|B|。 A .B,2020/9/3,26,8.5 集合的势,例如: |N|R| 定义f:N R，f(x)=x，显然f为单

11、射函数，所以|N|R|。 定理8.6 设A，B，C是任意集合， (1) AA (2) 若AB，则BA (3) 若AB，BC，则AC。,2020/9/3,27,8.5 集合的势,如何证明AB？ 构造从A到B的双射函数 1.有穷集之间的双射函数的构造 例1： A=P(1,2,3), B=0,11,2,3 解：A=,1,2,3,1,2,1,3,2,3,1,2,3. B= f0, f1, , f7 , 其中 f0=, f1=, f2=, f3=, f4=, f5=, f6=, f7=,.,2020/9/3,28,8.5 集合的势,令 f : AB, f()=f0 f(1)=f1 f(2)=f2 f(3

12、)=f3 f(1,2)=f4 f(1,3)=f5 f(2,3)=f6 f(1,2,3)=f7 故： AB,2020/9/3,29,8.5 集合的势,2.实数区间之间构造双射 构造方法：直线方程 例2： A=0,1 ， B=1/4,1/2 构造双射 f : AB,解：令 f : 0,11/4,1/2 f(x)=(x+1)/4,2020/9/3,30,8.5 集合的势,例：(0,1) R 证明：构造(0,1)到R的双射函数。 f: (0,1) （-/2, /2),f(x)= (x- 1/2)，显然f为双射 g: (-/2, /2) R,g(x)= tgx ，显然g为双射 于是fg : (0,1)

13、(/2, /2) , fg (x)=g(f(x)= tg(x- 1/2) ，也是双射函数 故： (0,1) R,2020/9/3,31,8.5 集合的势,3.A与N之间构造双射 方法： 将A中元素排成有序图形，然后从第一个元素开始按照次序与自然数对应.,2020/9/3,32,8.5 集合的势,例1：ZN 解：构造函数f : ZN 将Z中元素以下列顺序排列并与N中元素对应：Z：011 2233 N：0 1 2 3 4 5 6 这种对应所表示的函数是：,f是Z到N的双射函数。从而证明了ZN。,2020/9/3,33,8.5 集合的势,例2：NNE 解：构造函数f : N NE 将N中元素以下列顺

14、序排列并与NE中元素对应：,这种对应所表示的函数是：,f是N到NE的双射函数。从而证明了NNE。,2020/9/3,34,8.5 集合的势,一个结论： 从上例可以看出： 这说明： 无限集合能与它的真子集等势，这在有限集合中是不可能的。 这是无限集合与有限集合的本质区别之一。,2020/9/3,35,8.5 集合的势,例3： NNN 解：分析,2020/9/3,36,8.5 集合的势,例4：Q+N,2020/9/3,37,8.5 集合的势,2020/9/3,38,8.5 集合的势,定理8.7（Cantor定理） N与R不等势，且|N|R| 分析： 一方面： |N|R| f:N R，f(x)=x，显然f为单射函数，所以|N|R|。 另一方面 由于(0,1) R，故只需证明N与(0,1)不等势。,2020/9/3,39,8.5 集合的势,证明： N 与(0,1)不等势 设f:N (0,1)的任意函数