离散数学课堂PPT(左孝凌版).ppt

例如,设X={ a,b,c}, Y={0,1}, X×Y={ a,0, b,0 ,c，0 , a,1 ,b,1 , c，1 }， X×Y的子集有26个,其中只能23个是从X到Y的函数. f0={ a,0, b,0 ,c，0 } f1={ a,0, b,0 , c，1 } f2={ a,0, b,1 ,c，0 } f3 ={ a,0,b,1 , c，1 } f4 ={ a,1, b,0 ,c，0 } f5 ={ a,1, b,0 , c，1 } f6 ={ a,1,b,1 , c，0 } f7 ={ a,1 ,b,1 , c，1 } 设X和Y都为有限集,分别有m 和n个不同的元素,由于从X到Y任意一个函数的定义域是X,在这些函数中每一个有 m个序偶.另外任何元素x∈X,可以有Y的n个元素中的任何一个作为它的象,故共有nm个不同的函数.在上例中n=2,m=3 ,故有23个不同的函数.今后我们用符YX表示从X到Y的所有函数的集合.甚至当X和Y是无限集时,也用这个符号. 满射: 设函数f:X→Y, 如果ran f=Y,则称f是满射的(或到上映射). ran f=Y,即Y的每一个元素是X中一个或多个元素的象点. 设f:X→Y 是满射,即对任意y∈Y,必存在x∈X使得f(x)= y成立. 例如, 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是满射的. 入射: 设函数 f:X→Y, 若对于x1,x2∈X, x1≠x2都有f(x1)≠f(x2),则称f是X到Y入射(或单射、一对一映射)的。 即对于x1,x2∈X, 若有f(x1)＝f(x2)，则有x1＝x2 。 例函数f：N→N，f（x）＝2 x 是入射的，但不是满射的。 例函数f：Z→Z，f（x）＝x+1 是入射的，也是满射的。 双射：设函数f:X→Y,若f既是入射的又是满射的，则称f是双射的。 例如，上例的函数就是双射的。 例如，令[a,b]表示的闭区间， 即[a,b]＝{ x |a≤x≤b}， 令f：[0，1]→[a,b]，f（x）＝(b-a)x+a, 这个函数是双射的。 例 (a) (b) (c) 其中 (a),(c)是满射 , (b),(a)是入射, (c)是双射. 定理 4-1.1 令X和Y为有限集,若 |X|=|Y|, 则f:X→Y是入射的,当且仅当它是满射的. 证明a. 若f 是入射,则 |X|=| f(X)| ,因为| f(X)|=|Y|,从f的定义有f(X)?Y,而| f(X)|=|Y|,又因为|Y| 是有限的,故f(X)=Y, 因此f 是满射. b. 若f 是一个满射,根据满射定义f(X)=Y,于是|X|=|Y|= |f(X)|。因为|X|= |f(X)| 和|X|是有限的，故f是一个入射。 4－2 逆函数和复合函数 任意给定一个函数，它的逆不一定是函数，例如, 函数 f ＝{x1 ，y1, x2，y1, x3, y2} fc={y1, x1, y1, x2, y2, x3 }. 定理4－2.1设f:X→Y是双射函数，那么fc是Y→:X的双射函数。 证明 设f={ x,y | x∈X∧y∈Y∧f (x)=y} fc ={ y,x | x,y∈f } 因为f是满射的,故每一y∈Y 必存在x,y ∈ f , 因此必有y,x∈fc,即fc的前域为Y. 又因为f是入射, 对每一个y∈Y恰有一个x∈X, 使 x,y∈f, 因此仅有一个x∈X,使 y,x∈fc, 即y对应于唯一的x,故fc是函数. 又因ran fc =dom f =X,故fc 是满射, 又因为若y1≠y2有fc(y1)≠fc(y2), 因为fc(y1)=x1, fc(y2)= x2, 即x1=x2, 故f(x1)=f(x2) , 即y1=y2 得出矛盾,因此f是双射函数. 逆函数: 设f:X→Y是双射函数,称Y→X的双射函数fc为f的逆函数,记作f-1。 例如，设A＝{1，2，3}，B＝{ a,b,c}，f:A→B为 f ＝{1, a, 2, c, 3, b} 则f-1 ={ a,1, c,2