第3章 函数精选PPT.ppt

第3章 函数第1页，本讲稿共42页3.1 函数的概念v函数是一种多对一的二元关系，即该类关系中定义域的任何一元仅与值域中的某一元发生关系。函数 为集合 X 到集合 Y 的函数当且仅当：为 X 到 Y 的二元关系,记为 :X Y Dom()=X,Ran()Y(x)(y)(y)(xX y,yY xy xy y=y)第2页，本讲稿共42页3.1 函数的概念函数：XY 也称为映射。通常用(x)=y 表示 xy (或y=(x)此时 y=(x)也称 x 为自变量，y 为 x 在下的像，x 为 y 在 下的原像。对函数 :XY，AX，定义 A=y|(x)(xAy=(x)为 A 在 下的像。第3页，本讲稿共42页3.1 函数的概念例例 1=|x1,x2N 且 x1+x210 2=|y1,y2R 且 y22=y1 3=|z1,z2N,z2 为小于z1的素数个数 上述中，1，2 不是函数，3 是函数。第4页，本讲稿共42页3.1 函数的概念函数相等 设函数 f:AB,g:CD。若 A=C,B=D,且对所有 xA,有 f(x)=g(x)，则称 f 和 g 相等，记作 f=g。满射 设函数 f:XY,称 f 是一个满射,若 Ran(f)=Y。单射 设函数 f:XY,称 f 是一个入射(或单射)，若对任意 x1,x2X，有 x1 x2 f(x1)f(x2)。双射 设函数 f:XY，称 f 是一个双射，若 f 是满射又是入射。第5页，本讲稿共42页3.1 函数的概念v若干常用的函数：常函数、恒等函数、单调函数、严格单调函数、特征函数、自然映射。常函数 函数 f:XY 称为常函数 (y0)(y0YRan(f)=y0)恒等函数 函数 Idx：XY 称为X上的一个恒等函数 XY Idx(x)=xX=Y时，Idx 记为 Ix第6页，本讲稿共42页3.1 函数的概念单调函数 函数 f:RR(R为实数)称为 R 上的单调递增函数 (x)(y)(x,yRxy f(x)f(y)函数 f:RR(R为实数)称为 R 上的严格单调递增函数 (x)(y)(x,yRxy f(x)f(y)自然映射 设 R是 X 上的等价关系，令 f:XX/R，定义为 f x=xR，则 f 是函数（请证明之），并称之为从 X 到 X/R 的自然映射。第7页，本讲稿共42页定义 设有集合 A、B，BA=|为函数且 :A B (即 BA 是从 A 到 B 的所有函数的集合)定理 B=(只有函数符合要求)A A=(没有符合要求的函数)BA=B=A 若A=x0(即|A|=1)则 BA=|=，yB B C BA CA3.1 函数的概念第8页，本讲稿共42页选择公理 对任意的关系 R，总存在函数 ，使得 R 且 dom()=dom(R)。3.1 函数的概念第9页，本讲稿共42页3.2 逆函数v符合函数定义的关系的逆关系不一定能定义一个逆函数。定理 设 f:X Y 是一个双射函数，则其逆关系 f 1:Y X 也构成一个双射函数。证明 (1)f 1 符合函数的定义；(2)f 1 是满射；(3)f 1 是入射。第10页，本讲稿共42页3.2 逆函数逆函数 设 f:XY是一个双射函数，则其逆关系 f 1:YX 构成的双射函数称为其逆函数（或反函数），记为 f 1。例 A=1,2,3,B=a,b,c,f：AB f=,f 1=,为 f 的逆函数。定理 设 f:XY是一个双射函数，是关系的复合运算，则 f 1f=IY，f f 1=IX。定理 设双射函数 f:XY，则(f 1)1=f。第11页，本讲稿共42页3.3 复合函数函数复合 设函数 f:XY,g:WZ，且 Ran(f)W,令 gf=|xXzZ(y)(yYy=f(x)z=g(y)称 g 在 f 的左边复合。定理 上述 gf 是一个从 X 到 Z 的函数。证明 按照函数定义的3个要点逐一证明。(1)gf 是 X Z 的二元关系 (2)dom(gf)=X (3)设有 xX,z1,z2Z,且 z1=(gf)(x),z2=(gf)(x)容易证明 z1=z2第12页，本讲稿共42页3.3 复合函数vgf 的另外定义：设 g,f 分别如上所述，可定义 gf =fg定理 设 gf 是一个复合函数，则 若 g和f 是满射的，则gf 也是满射的。若 g和f 是入射的，则gf 也是入射的。若 g和f 是双射的，则gf 也是双射的。第13页，本讲稿共42页3.3 复合函数定理 设函数 f:XY，则 f=fIx=Iyf。定理 设双射函数 f:XY 存在逆函数 f 1:YX，则 f-1f=Ix，ff 1=Iy。定理 设双射函数 f:XY，g:YZ 则 (gf)1=f 1g1。第14页，本讲稿共42页3.4 特征函数特征函数 当 AB时，函数 A:B 0,1 定义为：称函数 A:B0,1 为集合A(关于B)的特征函数。定理 有集合B，二元关系 F：(B)0,1B 定义为：对 A(B)或 AB，F(A)=A，则 F是双射函数。证明 (1)是函数；(2)是入射；(3)是满射。1 若 xA0 若 xAA(x)=第15页，本讲稿共42页证明(1)F 是函数：按照函数定义逐一确认。(2)F 是入射。设 A1,A2(B)且 A1A2，则存在 xB，使得(xA1xA2)(xA2xA1)，从而有 故存在 xB，使得即3.4 特征函数第16页，本讲稿共42页(3)F 是满射。设有 g0,1B，即 g:B0,1构造 Ag=x|xB g(x)=1。显然 Ag(B)。由 F 定义：F(Ag)=fAg而对任意的 xB，fAg(x)=1 xAg g(x)=1所以 fAg=g，即 F(Ag)=g。即 Ag 就是 g 在 F 下的原像。因此F是满射3.4 特征函数第17页，本讲稿共42页3.5 递归关系与递归函数例 序列（5,8,11,14,17,）可由下列规则得到：1.第一个数为5；2.其他的数由其前一个数加上3得到。符号化表示成：1.a1=5;2.an=an1+3,n2第18页，本讲稿共42页3.5 递归关系与递归函数定义 在序列 a1,a2,an1,an,中，用 a1,a2,an1 中某些项来表示 an 的等式称为递归关系。v给定一个递归关系及其初始条件，可以定义一个序列。例 Fibonacci 序列：1,2,3,5,8,13,21,初始条件：f1=1,f2=2;递归关系：fn=fn1+fn2,n3第19页，本讲稿共42页3.5 递归关系与递归函数例 某人以1000个单位作资产投资，年收益率 8%。用Gn 表示他在第 n 年末的总资产。初始条件：G0=1000 递归关系：Gn=Gn1+Gn18%=Gn11.08讨论 有的递归关系可以推导出表示序列元素的显式公式。如上例：Gn=Gn11.08=Gn21.082 =G01.08n=10001.08n 第20页，本讲稿共42页3.5 递归关系与递归函数例 汉诺塔（Tower of Hanoi Puzzle,Lucas）。如图，A柱上从小到大套着 n 个圆盘，利用 B 柱将圆盘搬到 C 柱，要求：每次只能移动一个圆盘；只有处于最顶端的圆盘才能被移动；在操作过程中，不能将较大尺寸的圆盘放在较小尺寸的圆盘上面。A B C A B C第21页，本讲稿共42页3.5 递归关系与递归函数 归约为三个需要解决的子问题：第22页，本讲稿共42页3.5 递归关系与递归函数 即：1.将 A 柱上部的 n1 个圆盘搬到 B 柱；2.将 A 柱剩下的最大圆盘移到 C 柱；3.将 B 柱的 n1 个圆盘搬到 C 柱。设完成问题要求需要移动圆盘的次数为 Cn，则由上述讨论得到：Cn=Cn1+1+Cn1=2Cn1+1 初始条件：C1=1（只有一个圆盘时）讨论 可以归纳证明，Cn=2n1。当 n=64 时，Cn =（设移动1次圆盘需要1秒，约需 236年完成）第23页，本讲稿共42页3.6 集合的基数 等势 设集合 A，B，如果存在从 A 到 B 的双射函数，就称 A 和 B 是等势的，记做 A B。否则称 A 和 B 是不等势的。v注意与相似关系 符号的辨别。A B 有时也记作 A B 第24页，本讲稿共42页3.6 集合的基数 例 Z N。令 f:ZN2x 若 x02x1 若 x0(x)=则 f 是 ZN 的双射函数：Z：0 1 1 2 2 3 3 .N：0 1 2 3 4 5 6 .第25页，本讲稿共42页3.6 集合的基数 例 NN N。建立 NN 和 N之间的双射函数。(0,0)(1,0)(2,0)(3,0).(m+n,0)(0,m+n).(0,3)(0,2)(0,1)(m,n)第26页，本讲稿共42页3.6 集合的基数说明 NN 的元素是第一象限中（含坐标轴）整坐标的点，构造如图示的排序，从(0,0)开始，则点(m,n)的下标如下计算：斜线(0,m+n)(m+n,0)之前（不含）的点数为1+2+.+(m+n)斜线(0,m+n)(m+n,0)上(m,n)所在的点数为m+1下标（从0开始计算）：第27页，本讲稿共42页3.6 集合的基数例 N Q第28页，本讲稿共42页例(0,1)R3.6 集合的基数第29页，本讲稿共42页例 0,1 (0,1)3.6 集合的基数第30页，本讲稿共42页例 对任何 a,bR，ab，0,1 a,b3.6 集合的基数第31页，本讲稿共42页3.6 集合的基数例 对任意集合A，(A)0,1A（P.15 定理）定理 两个集合间的等势关系是等价关系。第32页，本讲稿共42页3.6 集合的基数 定理(Cantor)(1)集合 N 和集合 R 是不等势的。(2)任何集合 A 和其幂集(A)是不等势的。证明（略）优势 设集合 A，B，如果存在从 A 到 B 的单射函数，就称 B 优势于 A，记做 A B。若此时 A 和 B 不等势，则称 B 真优势于 A，记做 A B。例 N N，N R，N R，A (A)第33页，本讲稿共42页3.6 集合的基数定义 设集合 a，称集合 aa为 a 的后继,记作 a+。例 空集的后继 +=+=+=,+=+=,+,+第34页，本讲稿共42页3.6 集合的基数讨论 定义自然数 0=1=0+=0 2=1+=0,1 n=0,1,2,n-1 第35页，本讲稿共42页3.6 集合的基数定义 设集合A，如果有 (1)A；(2)a(aA a+A)则称集合A是一个归纳集。例,+,+,+,本身是归纳集。v从归纳集的定义可以看出，,+,+,.是所有归纳集的元素，于是可以将它们定义成自然数自然数。定义 自然数是属于每个归纳集的集合；自然数集 N=,+,+,+,是所有归纳集的交集。第36页，本讲稿共42页3.6 集合的基数有关自然数的一些性质 设 m,n 是自然数，则有 n n；若 mn，则 m 与 n 不等势；若 mn，则 mn；自然数的三歧性：mn，m n，nm 三者有且仅有一项成立；定义：m=n iff m n；mn iff mn。第37页，本讲稿共42页3.6 集合的基数 定义一个集合是有穷的当且仅当它与某个自然数等势。否则称为无穷集合。例都是无穷集。R 和 N 定理任何一个有穷集只与唯一的自然数等势。定义(1)的基 A 等势的那个唯一的自然数称为 A，与 A对有穷集 数，记作card(。ACardinal Number of A)自然数的基数记作(2)0，即 cardN=0(。a:lif)实数集(3)的基数记作 ，即cardR=。第38页，本讲稿共42页3.6 集合的基数定义 设有集合 A、B。(1)cardA=cardB iff A B；(2)cardA cardB iff A B；(3)cardAcardB iff cardA cardB cardA cardB。一些结果 vcardZ=cardQ=cardNN=cardN=0vcard(N)=carda,b=cand2N=cardR=v 0 第39页，本讲稿共42页3.6 集合的基数v对任意集合 A 有 A (A)，即有 cardA card(A)，故不存在最大的基数。v0,1,2,n,称为有穷基数；0 和 称为无穷基数。0 是最小的无穷基数。定义 设集合A，若 cardA 0，则称A为可数集。例 a,b,c不是可数R 都是可数集。N N，Q，Z，5，等势的集合都不是可数集。R 集。与第40页，本讲稿共42页3.6 集合的基数v关于可数集的一些结果（性质）可数集的任何子集都是可数集；两个可数集的并也是可数集；两个可数集的笛卡尔积也是可数集；可数个可数集的并也是可数集；无穷集A的幂集(A)不是可数集。第41页，本讲稿共42页3.6 集合的基数例为集合，B，A设 cardA=0，cardB=n，n 且N n。0 证明：cardB)=(A0 证，3由性质 也是可数集，故BAcard B A0。，不妨设有 B当 b的单射，B A A。建立Bf，B A:Af(a)=aAB)(A A可知 即card Acard，而B)(AcardA=0 故card B A0 因此cardB)=(A0 第42页，本讲稿共42页