离散数学function.ppt

,离散数学,2,第四章 函数,4-1函数的概念 4-2逆函数和复合函数 4-4基数的概念 4-5可数集与不可数集 4-6基数的比较,3,第四章 函数,4-1函数的概念 4-2逆函数和复合函数 4-4基数的概念 4-5可数集与不可数集 4-6基数的比较,4,函数的概念,定义4-1.1 设X 和Y是任何两个集合。而 f 是X 到Y的一个关系，如果对于每一个xX ，有唯一的 yY，使得x,yf ，称关系 f 为函数，记作：f:XY 或 概念：自变量、映像、定义域和值域 注意： 1 函数与关系 2 函数亦称映射或变换。习惯用小写英文 f,g, 表示函数符。 3 在x,y f 中，f 的前域就是函数的定义域,记作dom f (或Df ) 显然由定义可知： Df=x xX (y)(yY y = f (x) =X,5,4 f 的值域记为 ran f (或Rf)， 即： Rf=yyY (x)(xX y = f (x) 。 问题：ran f=Y? 5 映像集：f(X)=ran f,6,实例,例1 设 X=1,5,p,张明，Y=2,q,7,9,G,f = 1,2 , 5,q , p,7, 张明, G 。求：Dom f和ran f 例2 判别下列关系中哪个能构成函数 1 f = x1,x2x1,x2 N ,且x1+x210。 2 f = y1,y2y1,y2 R,y22 = y1 。 3 f = x1,x2x1,x2 N ,x2为小于x1的素数个数 。,7,函数相等,定义4-1.2 (函数相等)设函数 f :AB, g :CD,若A=C,B=D且对一切 x A ,有 f (x) = g(x)，则称函数 f 和 g 相等。记为 f = g。 问题：函数相等的两个要素？ 问题：对于有限的集合X和Y，并且|X|=m，|Y|=n： 1 X到Y的关系有多少个？ 2 X到Y的函数有多少个？ 概念：符号YX 表示从 X 到 Y 的所有函数的集合，甚 至当 X 和 Y 是无限集时，也用这个符号。,8,满射函数,定义4-1.3 对于f :XY 的映射中，若ran f = Y，即Y 的每一个元素是 X 中一个或多个元素的像点，则称这个映射为满射(或到上映射)。 问题：如何说明或证明一个函数是满射的，请用谓词公式进行说明。 例1 A =a,b,c,d,B =1,2,3如果 f 为A 到 B 的函数,且f (a) = 1, f (b) = 1, f (c) = 3, f (d) = 2 ，则f 是A 到B 上的满射。,9,入射函数,定义4-1.4 从 X 到Y的映射,X中没有两个元素有相同的像，则称这个映射为入射(或一对一映射)。 问题：1 如何说明或证明一个函数是入射的，请用谓词公式进行说明。 2 建立在X和Y上的满射及双射函数个数与集合大小的关系。 例 函数f:a,b2,4,6, f (a) = 2, f (b) = 6 则 f 是入射，但不是满射。,10,双射函数,定义4-1.5 从 X 到 Y 的一个映射，若既是满射又是入射，则称这个映射是双射(或一一对应映射)。 例 函数 f:a,b1,2, f (a) = 1, f (b) = 2，则 f 为双射。 例 在下图中,(a),(c)是满射,(b),(c)是入射,(c)是双射, (d)非满射又非入射。,(a) (b) (c) (d),11,定理4-1.1 令 X和 Y 为有限集，若X和Y的元素个数相同，即|X| = |Y| ，则f :XY 是入射的，iff 它是一个满射。 证明： 注意：此定理仅在有限集的情况下才能成立，在无限集上不一定成立。如：f:II , f (x) = 2x,这里显然 f 是一个入射，而不是满射。,12,第四章 函数,4-1函数的概念 4-2逆函数和复合函数 4-4基数的概念 4-5可数集与不可数集 4-6基数的比较,13,逆函数,问题：给定一个关系 R ，颠倒 R 的所有序偶，得到逆关系Rc 。给定一个函数 f ，颠倒 f 的所有序偶，得到的逆关系 f c 是函数吗？如果不是，在什么情况下其是逆函数？,14,定理4-2.1 设f :XY 是一双射函数，则f c 是YX 的双射函数。 证明思路：分两步，（1）证f c 为函数；（2）证f c 为双射) 定义4-2.1 设f :XY 是一双射函数，称YX的双射函数f c为f 的逆函数，记作f -1 。,15,复合函数,定义4-2.2 设函数f : XY ,g: WZ ，若f (X) W ，则g f=|xXzZ(y)(yYy=f (x)z=g(y) 称g在函数f 的左边可复合。 注意： 1、关系的复合与函数复合在记法上的区别。 2、若ran f dom g 这个条件不成立，则定义g f 为空。 3、定理4-2.3两个函数的复合是一个函数。 4、定义4-2.2中，当W=Y是，则函数g f 称为复合函数，或称 g f 为g对 f 的左复合。 5、g f(x) = g(f(x) 。 6、由于函数的复合仍为函数，故可推广到有限个函数的复合。,16,例 f :RR, g:RR, h :RR, f(x)=x+2,g(x)=x-2,h(x)=3x 问题：函数的复合满足可结合性吗？ 定理4-2.3 令g f 是一个复合函数。 a)若g 和 f 是满射，则g f是满射的。 b)若g 和 f 是入射，则g f 是入射的。 c)若g 和 f 是双射，则g f 是双射的。 证明思路：利用满射、入射和双射的定义直接证明,17,常函数和恒等函数,定义4-2.3 函数 f :XY 叫做常函数，如果存在某个y0Y ， 对于每个xX都有 f (x) = y0，即f (X) =y0 。 定义4-2.4 如果IX =x,x|xX，则称函数IX:XX 为恒等函数。 定理4-2.4 设函数 f :XY ，则 f = f IX = IY f 。 证明思路：证明定义域相同，对应关系相同。 定理4-2.5 如果函数f :XY 有逆函数f -1:YX ， f-1 f = IX , f f1 = IY。,18,逆函数的逆函数与复合函数的逆函数,定理4-2.6 若f : XY 是双射函数，则( f 1)1 = f 。 定理4-2.7 若f :XY, g :YZ 均为双射，则(g f )-1 = f -1 g -1 。 证明： 因为f, g为双射，由定理4-2.3知g f 是双射。 由逆函数定义可知：f 1 =f c, g 1 =g c , (g f )-1= (g f )c。再由复合关系逆的性质知：( g f) c =f c gc。 所以 (g f )-1= (g f )c = f c g c= f -1 g -1 。,19,第四章 函数,4-1函数的概念 4-2逆函数和复合函数 4-4基数的概念 4-5可数集与不可数集 4-6基数的比较,20,集合的大小,有限集合的大小 无限集合的大小 问题：如何比较两个集合的大小？,21,G.Peano公理,定义4-4.1设A是任意集合，A的后继集定义为集合： A+ = AA。 (G.Peano公理)自然数N是如下集合： (1)0 N (其中0 = )。 (2)如果n N ，那么 n+ N ，(其中n = n+ n )。 (3)如果一个子集S N具有性质： a. 0 S ; b. 如果n S ，有n+ S ，则S = N 。,22,说明： 1 上述自然数定义称为归纳定义。 其中(1)为基础，(2)为归纳，(3)为极小性(指明了自然数系统 是满足公理(1)和(2)的最小集合)。 2 从N的定义可见，任意一个自然数可看作是一个集合的名。 问题：自然数系统是什么呢？,23,等势集合,定义4-4.2 给定两个集合P与Q，若对P中每个不同元素，与Q中每个元素可以分别两两成对，则说P的元素与Q的元素间存在着一一对应。 定义4-4.3 iff 集合A的元素与集合B的元素之间存在着一一对应，集合A与集合B称为是等势的(或称同浓的)，记作AB 。,24,实例,例1：N1=x|x=2*i, i N，证明N1N 例2：设R为实数集合，S =x|xR0x1。 证明： RS 。 证明：令f : RS ，f (x) =(arctg x/ )+1/2 。 显然 f : RS 是一个双射函数。故 RS 。,25,定理4-4.1 (等势的性质)在集合族上等势关系是一个等 价关系。 证明：设S为集合族。 1)对于AS，可作恒等函数 IA :AA, IA(x) = x。显然IA:AA 为一个双射函数。故AA 。即等势关系为自反关系。 2)对于 A,BS ，如果AB ，那么存在双射函数 f :AB 。由定理4-2.1可知 f -1:BA 存在，且为双射函数，故BA ，即等势关系为对称关系。 3)对于 A,B,CS ，如果AB,BC那么存在 f : AB, g : BC均为双射函数。由定理4-2.3可知 g f :AC 为双射函数， 故AC ，即等势关系为一个传递关系。 由(1)、(2)、(3)可知集合族上的等势关系是一个等价关系。 ,26,有限集合和无限集合,定义4-4.4 如果有一个从集合0，1，n-1到集合A的双射函数，则称集合A是有限的；如果集合A不是有限的，则它是无限的。 概念： Nn =0,1,2, ,n-1称为N的初始段，Nn 可用于证明集合N为有限集。故Nn 又作为一个“标准集合”。 定理4-4.2 自然数集N是无限的。 证明：,27,基数-无限集合的大小,定义4-4.5 所有与集合A等势的集合所组成的集合，叫做集合A的基数，记作 KA (或 、 |A| ) 说明： 1 、定义4-4.5是由G.弗雷格与B.A.W.罗素分别在1884年与1902年给 出的。但在ZFC系统中不能证明它构成一个集合。按照康托尔的原意，认为集合A的基数是量词抽象的结果，一次从A 的元素中抽去质的特性，另一次是抽去元素之间的次序关系。A 的基数是一切与A具有等势关系集的共同特征。故用或 |A| 中的两个杠表示二次抽象。 2、根据康托尔的原意，通常将基数定义描述为：度量集合大小的 量叫基数(或势)。如 KNn =n 。约定K = 0 。故有限集合的基 数为集合所含元素的个数。如果 A,B 为无限集合，并且AB ，则 有KA = KB 。,28,实例,证明区间0,1 与（0,1）基数相同。 证明：设 定义 f : 0,1 （0,1）, 显然 f 是0,1 到（0,1）上的双射函数。（如下图所示）。 ,29,第四章 函数,4-1函数的概念 4-2逆函数和复合函数 4-4基数的概念 4-5可数集与不可数集 4-6基数的比较,30,可数集,说明： N 是无限集，但是并非所有无限集都可以与 N 等势。故无限集合之间也是有大小的。 定义4-5.1 与自然数集合等势的任意集合称为可数的，可数集合的基数为 。即KN = 例：A =1,4,9,16, ,n2, ，B =1,8,27,64, ,n3, C =2,5,10,17, ,n2+1, ，D =1, 12 , 13 , , 1n , 均为可数集，且 KA = KB = K C = KD = 。,31,定理4-5.1 A为可数集的充分必要条件是A可以排列成A =a1,a2, .,an, 的形式。 证明：如果A=a1,a2, .,an, ，那么存在 f : AN 且f (an) = n-1 (n = 1,2, ) f 为双射函数。故 AN ，即 A 为可数集。 反之，如果 A 可数，那么 AN ，则存在双射函数 f : NA , 令 f (n) = an+1 (n = 0,1,2, ) 故 A=a1,a2, .,an, 。 说明：此定理可以作为A 是可数集的一个等价定义，也是证明 A 可数的一个实用方法。,32,定理4-5.2 任一无限集必含有可数子集。 证明： 定理4-5.3 任一无限集必与其某一个真子集等势。 证明：设 M 为无限集，由定理4-5.2可知A=a1,a2, .,an, , 且A M。设 M-A = B ，定义函数 f: MM-a1，且 f (x) = an+1( x = an , n = 1,2, ), f (x) = x(xB) 显然 M-a1M，且 f 为双射函数。,33,说明： 1、定理4-5.3中某一个真子集不是指所有真子集，如真子集为有限集，则有限集与无限集是不可能等势的。 2、可以证明 A 有限集是不满足定理4-5.3的（如何证明）。故有 A 无限集当且仅当与其某一个真子集等势，可以作为无限集的等价定义。,34,定理4-5.4 可数集的任何无限子集都是可数的。 证明：设 A 是可数集合，则 A=a1,a2, .,an, ,B A 为一无限子集，将 A 中的元素从 a1开始，向后检查，不断地删去不在 B 中的元素，则得到新的一列 ai1,ai2, ,ain, ,故B= ai1,ai2, ,ain, ，即 B 是可数的.,35,即 S = a11,a21,a11,a13,a22,a31,a41,a32, ，所以 S 是可数集。,定理4-5.5 可数个两两不相交的可数集合的并集，仍然是一可数集。 证明：（用排队的方法证明） 设可数个可数集分别表示为： S1 =a11,a12,a13, ,a1n, S2 =a21,a22,a23, ,a2n, S3 =a31,a32,a33, ,a3n, 令S =S1 S2 = ，对 S 的元素作如下排列：,36,说明： 1、定理4-5.5中 S 中的元素的排列方法是不唯一的。 2、利用定理4-5.4和定理4-5.5可以证明：可数个可数集的并是可数的。（如何证明）,37,定理4-5.6 ：NN是可数集。 证明： 令S1 =, , S2 = , , S3 = , , 则NN= 由定理4-5.5可知 NN是可数集。 说明：注意此种证明方法与教材上方法的差异,38,定理4-5.7 有理数集 Q 为可数集。（用排队法证明） 证明：一切有理数均呈n/m(n,mN,m0) 。现将所有n/m 按下列次序排列： （1）正分数按其分子、分母之和的大小顺序排列：从小到大。 （2）正分数的分子、分母之和相同者按分子大小顺序排列： 从大到小。 （3）将0放在首位，与正分数具有相同形式的负分数排于正分数之后。按照上述规则可得： 0,1/1,-1/1,2/1,-2/1,1/2,-1/2,3/1,-3/12/2,-2/2,1/3,-1/3, 故所有呈n/m 状的数所组成的集合为可数集，而 Q 为其无限子集，由定理4-5.4知 Q为可数集。,39,不可数的无限集,概念：连续统 并非所有的无限集均为可数集。选取（0,1）作为新的“标准集合”，记（0,1）的基数为 ，如果 A(0,1) ，那么KA = 。 也称作连续统的势。,40,定理4-5.8 实数集R是不可数的。（用反证法证明） 证明：,41,关于定理4-5.8的证明几点说明： 1、仅由 0,1 构成的无限序列集合是不可数的。 即 T=a0a1a2an|nN,an=0or1为不可数集。 2、将(1)推广由 0,1,2, ,9 构成的无限序列集合也是不可数集。 3、S =(x,y)|x.yR0x,y1 为不可数集。 (提示：构作f:S(0,1) 为双射函数 ) 4、证明：RRR = Rn 是不可数集。,42,第四章 函数,4-1函数的概念 4-2逆函数和复合函数 4-4基数的概念 4-5可数集与不可数集 4-6基数的比较,43,基数的比较,说明：通过构造双射函数证明集合等势需要高度的技巧性。 定义4-6.1 若从集合A到集合B存在一个入射，则称A的基数不大于B的基数，记作 KA KB 。若从A到B存在一个入射，但不存在双射，则称A的基数小于B的基数，记作KA KB 。,44,定理4-6.1