《形式语言与自动机》由会员分享，可在线阅读，更多相关《形式语言与自动机（70页珍藏版）》请在金锄头文库上搜索。
1、第四章第四章 函数函数本章主要内容o函数的概念，逆函数和复合函数o特征函数与模糊子集o基数的概念，可数集与不可数集o基数的比较 学习要求o函数的定义与性质，函数定义，函数性质o函数运算，函数的逆，函数的合成o双射函数与集合的基数Date14-1 4-1 函数的概念函数的概念定义4-1.1 设A和B是两个任意集合，而f是A到B的二元关系， 如果对于A中的每一个元素x， B中都存在惟一元素y，使得 x,yf，则称关系f是A到B的函数或映射。记为 f：AB 或 A B 假如x,yf，x称为自变元或像源，y称为在 f 作用下x的像或 函数值。x,yf，常记为y=f(x)，且记f(X) = f(x) |
2、 xX 。Date2由函数的定义可以看出，函数是一种特殊的二元关系。若 f是A到B的函数。它与一般二元关系的区别如下：函数的定义中强调A中的每一个元素x有像，所以 A=dom f。 这称为像的存在性。函数的定义域是A，而不是A 的某个真子集。函数的定义中还强调像y是惟一的，一个x A只能对 应唯一的一个y，称做像的惟一性。像的惟一性可以描述为： 设f(x1)=y1且f(x2)=y2。如果x1=x2，那么y1=y2。或者，如果y1y2 ，那么x1x2。Date3【例4.1.1】设 N为自然数集合，下列N上的二元关系 是否为函数？f=x,2x | xN g=x,2 | xN 解：f和g都是从自然数
3、集合N到自然数集合N的函数 ，常记为f：NN，f(x)=2x和g：NN，g(x)=2。Date4定义 设A和B是两个任意的集合，f：AB，A1A， 集合f (x) |xA1称为集合A1在 f 下的像，记为f(A1)。 集合A在 f 下的像 f(A)= f(x) |xA称为函数f的像。显然， 函数 f 的像f(A)就是二元关系 f 的值域，即f(A)=ran f B。有 时也记作Rf，即Rf =y|(x)(xA) (y=f(x)，集合B称为f的 共域，ran f 亦称为函数的像集合。【例4.1.2】设f：1,2,3 a,b，f=1,a,2,a,3,b，A1=1,2， 试求A1在f下的像f(A1)
4、和函数f的像f(A)。解：f(A1)= f(x) |xA1=f(1), f(2)=af(A)= f(x) |xA=f(1), f(2), f(3)=a,bDate5定义4-1.2 设函数f：AB，g：CD，若A=C，B=D且 xA和xC ，有f(x)=g(x)，则称函数 f 和g相等，记为f =g 。例如，函数f：NN，f(x)= x3函数g：1,2,3 N，g(x)=x3虽然函数f和g有相同的表达式x3，但是它们是两个不同 的函数。如果把f和g看成二元关系，fNN，用列举法表示为：0,0,1,1,2,8,3,27, 4,64, g1,2,3 N，用列举法表示为：0,0,1,1,2,8,3,2
5、7按二元关系相等的条件衡量，它们也是不等的。函数相 等和二元关系相等是一致的。Date6设A和B是两个任意集合，AB任意子集是A到B的二元 关系，但不一定是A到B的函数。当A和B是有限集时，A到 B的二元关系共有2|A|B|个，A到B的函数有多少个呢？以下 研究这个问题。设A和B是两个任意的有限集合，分别由m个和n个不同 的元素，由于从A到B的任意一个函数的定义域是A ，在这 些函数中每一个恰有m个序偶。另外任何元素x A ，可以 有Y的n个元素中的任何一个作为他的像，故共有nm个不同 的函数。f |f：AB是A到B的所有函数构成的集合，常记为BA 。读作B上A。Date7【例4.1.3】设
6、A=1,2,3，B=a,b，求BA。解：由A到B的函数有以下8个： f0=1,a,2,a,3,af1=1,a,2,a,3,bf2=1,a,2,b,3,af3=1,a,2,b,3,bf4=1,b,2,a,3,af5=1,b,2,a,3,bf6=1,b,2,b,3,af7=1,b,2,b,3,bBA= f0, f1, f2, f3, f4, f5, f6, f7 A到B的函数共8个，8=23=|B|A|。当A和B都是有限集时，这个结论可以推广。一般地 说，若|A|=m，|B|=n，则|BA|=nm=|B|A|。 Date8定义4-1.3 设f：AB，若f的值域ran f =B，即B的每一个 元素是
7、A中一个或多个元素的象点，则称这个映射f为满射（ 或到上映射）。设f是A到B的函数，由定义不难看出，如果yB，都存 在xA，使得f(x)=y，则f是满射函数。例如，A=a,b,c,d，B=1,2,3，f是由A到B的函数， 定义为：f =a,1,b,1,c,3,d,2因为ran f=f(A)=1,2,3=B，所以f是满射。图4.1.1是f的示 意图。由图4.1.1可得出如下的结论：若A、B是有限集，f：AB 是满射，在f的示意图中，B中每 个元素至少是一个有向边的终点 且|A|B|Date9定义4-1.4 设f：AB，若yran f，存在惟一的xA ，使得f(x)=y，则称f为入射。 即A中没有
8、两个元素有相同 的象，则称这个映射为入射（或一对一映射）。设f是A到B的函数，由定义不难看出，如果对于x1A ，x2A，f(x1)=y1，f(x2)=y2。当y1=y2时，一定有x1=x2，则f是入射函数。当x1x2时，一定有y1y2，则f是入射函数。Date10【例4.1.4】设f：a,b2,4,6，定义 f =a,2,b,6函数f是否为入射？f是否为满射？解：因为f(a)=2，f(b)=6，所以f是入射。因为 f 的值 域ran f =2,62,4,6，所以f不是满射。图4.1.2是 f 的示 意图。由图4.1.2可得出如下的结论：若A、B是有限集， f：AB是入射，在 f 的 示意图中，
9、B中每个像 点是且仅是一条有向边 的终点且|A|B|Date11定义4-1.5 设f：AB，若f既是入射，又是满射，则 称f为双射。例如：A=1,2,3，B=a,b,c，f =1,a,2,c,3,b， f 是A到B的双射函数，图4.1.3是f的示意图。 Date12若A、B是有限集，f：AB是双射，则 f 一定是满射。 故B中每个元素至少是一个有向边的终点；f 也是单射，故 B中每个像点是且仅是一条有向边的终点。所以，在双射函 数的示意图中，B中每一个元素是且仅是一条有向边的终点 。若A、B是有限集，f：AB是双射，则 f 一定是满射， 所以|A|B|；f 也是入射，所以|A|B|。于是|A|
10、=|B|。Date13【例4.1.5】判断下列函数是否为入射、满射或双射。为什么？ f：RR，f(x)= - x2+2x-1，其中，R是实数集合 f：IR，f(x)=ln x，其中，I是正整数集合 f：RI，f(x)=x，其中，x是不大于x的最大整数 f：RR，f(x)= 2x+1 f：RR，f(x)= ，其中，R是正实数集合Date14解：f(x)=-x2+2x-1= -(x-1)2，f 是开口向下的抛物线 ，不是单调函数，所以不是入射。在 x =1处取得极大值0， 所以f 不是满射。 f 既不是入射也不是满射。 f 是单调增加函数。因此是入射，但不是满射，因为 ran f =ln 1，ln
11、 2，R f是满射，但不是入射，例如f(1.5)=1.5=1，而f(1.2) =1.2=1 f是单调增加函数且ran f =R，它既是入射，也是满射 ，因此它是双射。 f 不是入射也不是满射。当x0时，f(x)；而当 x时，f(x)。在x=1处函数f(x)取得极小值f(1) =2。 因此它既不是入射也不是满射。Date15定理4-1.1 令X和Y为有限集，若X和Y的元素个数相同， 即|X|=|Y|，则f：XY是入射的，当且仅当他是一个满射。 证明：a 若f是入射，则|X|=|f(X)|，因此|f(X)|=|Y|，从f 的定义我们 有f(X) Y，而|f(X) |=|Y|，又因为|Y|是有限的，
12、故f(X)=Y，因此f 是一个入射推出f是满射。b 若f是一个满射，根据满射的定义f(X) =Y，于是|X|=|Y|= |f(X) |。因为|X|= |f(X) |和|X|是有限的，故f是一个入射，因此f是 满射推出f是一个入射。 这个定理必须在有限集情况下才能成立，在无限集上不一定 有效，如f：II是f(X) =2x，在这种情况下整数映射到偶整数 ，显然这是一个入射，但不是满射。Date164-2 4-2 逆函数和复合函数逆函数和复合函数 定理4.2.1设 f：AB是双射函数，则 f 的逆关系f C是B A 的双射函数。证明：先证逆关系 f C是B到 A的函数。因为 f 是函数，所以 f C
13、是B到 A的二元关系。以下证 明B到 A的二元关系f C是B到 A的函数。yB，因为 f：AB是满射，所以，yB必有 xA ，使x,y f，由逆关系的定义得， y,x f C。设y1,x1 fC，y2,x2 fC，y1=y2，由逆关系的定 义知，x1,y1 f，x2,y2 f，因为f是入射，所以x1=x2 故 f C是B到 A的函数。 Date17再证 f C是满射。因为ran f C=dom f。又因为 f 是A到B的函数，所以dom f =A。于是ran f C=A。所以f C是B到 A的满射。最后证f C是入射。设y1,x1 f C，y2,x2 f C且x1=x2，由逆关系的定义有 x1
14、,y1 f，x2,y2 f，又因为f是函数，必有y1=y2。所以 f C是入射。这就证明了f C是双射函数。Date18定义4.2.1 设f：AB是双射函数，称BA 的双射函数f C 为 f 的逆函数，记为：f -1。例如，设A=1,2,3，B=a,b,c。f=1, a ,2, c ,3, b 显然，f是A到B的双射函数。f的逆关系f C=a,1,c,2,b,3 是B到A的双射函数，记为f -1，f 1是 f 的逆函数。又如 g=1, a ,2, a ,3,b也是A到B的函数，但g不 是满射，也不是入射，因而不是双射。逆关系gC=a,1,a, 2,b,3 不是B到 A的函数。Date19二元关系的复合关系定义为：设X，Y，Z是集合，R XY，SYZ，集合x,zxXzZ(y)(yYx,yRy,zS) 叫做R和S的复合关系。记为RS。即RS=x,zxXzZ(y)(yYx,yRy,zS) 将RS=x,zxXzZ(y)(yYx,yRy,zS) 记为SR，即SR=x,zxXzZ(y)(yYx,yRy,zS)前者叫做R和S的复合关系。为了与前者区别，后者叫做 二
