第八章 形式语言与自动机ppt课件.ppt

4-1函数的概念定义4-,而f是A到B的二元关系,如果对于A中的每一个元素x,B中都存在惟一元素y,使得x,yf,则称关系f是A到B的函数或映射。记为f:A→B或AB假如x,yf,x称为自变元或像源,y称为在f作用下x的像或函数值。x,yf,常记为y=f(x),且记f(X)={f(x)|xX}。2020/9/301由函数的定义可以看出,函数是一种特殊的二元关系。若f是A到B的函数。它与一般二元关系的区别如下:①函数的定义中强调A中的每一个元素x有像,所以A=domf。这称为像的存在性。函数的定义域是A,而不是A的某个真子集。②函数的定义中还强调像y是惟一的,一个xA只能对应唯一的一个y,称做像的惟一性。像的惟一性可以描述为:设f(x1)=y1且f(x2)=y2。如果x1=x2,那么y1=y2。或者,如果y1≠y2,那么x1≠x2。2020/9/302【】设N为自然数集合,下列N上的二元关系是否为函数?f=x,2x|xNg=x,2|xN解:f和g都是从自然数集合N到自然数集合N的函数,常记为f:N→N,f(x)=2x和g:N→N,g(x)=2。2020/9/303定义设A和B是两个任意的集合,f:A→B,A1A,集合f(x)|xA1称为集合A1在f下的像,记为f(A1)。集合A在f下的像f(A)=f(x)|xA称为函数f的像。显然,函数f的像f(A)就是二元关系f的值域,即f(A)=ranfB。有时也记作Rf,即Rf={y|(x)(xA)∧(y=f(x))},集合B称为f的共域,ranf亦称为函数的像集合。【】设f:1,2,3→a,b,f=1,a,2,a,3,b,A1=1,2,试求A1在f下的像f(A1)和函数f的像f(A)。解:f(A1)=f(x)|xA1=f(1),f(2)=af(A)=f(x)|xA=f(1),f(2),f(3)=a,b2020/9/304定义4-:A→B,g:C→D,若A=C,B=D且xA和xC,有f(x)=g(x),则称函数f和g相等,记为f=g。例如,函数f:N→N,f(x)=x3函数g:1,2,3→N,g(x)=x3虽然函数f和g有相同的表达式x3,但是它们是两个不同的函数。如果把f和g看成二元关系,fN×N,用列举法表示为:0,0,1,1,2,8,3,27,4,64,…g1,2,3×N,用列举法表示为:0,0,1,1,2,8,3,27按二元关系相等的条件衡量,它们也是不等的。函数相等和二元关系相等是一致的。2020/9/305设A和B是两个任意集合,A×B任意子集是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:A→B是A到B的所有函数构成的集合,常记为BA。读作B上A。2020/9/306【】设A=1,2,3,B=a,b,求BA。解:由A到B的函数有以下8个:f0=1,a,2,a,3,af1=1,a,2,a,3,bf2=1,a,2,b,3,af3=1,a,2,b,3,bf4=1,b,2,a,3,af5=1,b,2,a,3,bf6=1,b,2,b,3,af7=1,b,2,b,3,bBA=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|。2020/9/307定义4-:A→B,若f的值域ranf=B,即B的每一个元素是A中一个或多个元素的象点,则称这个映射f为满射(或到上映射)。设f是A到B的函数,由定义不难看出,如果yB,都存在xA,使得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因为ranf=f(A)=1,2,3=B,所以f是满射。。:若A、B是有限集,f