離散數(shù)學(函數(shù))PPT參考課件

1、函 數(shù),第 八 章,4.1 函數(shù)的概念,函數(shù)定義 函數(shù)與關系 函數(shù)相等 特殊函數(shù): 單射 滿射 雙射,8.1 函數(shù)的定義與性質,函數(shù)的定義,設 F 為二元關系, 若xdomF 都存在唯一的yranF 使 xFy 成立, 則稱 F 為函數(shù) 對于函數(shù)F, 如果有 xFy, 則記作 y=F(x), 并稱 y 為F 在 x 的值.,x 自變元 y 在F 作用下 x 的像,判斷下列關系哪個構成函數(shù),1,1,1,函數(shù)的定義,設F, G 為函數(shù), 則 F=G FGGF 如果兩個函數(shù)F 和 G 相等, 一定滿足下面兩個條件： (1) domF=domG (2) xdomF=domG 都有F(x)=G(x),函

2、數(shù)F(x)=(x21)/(x+1), G(x)=x1不相等, 因為,domFdomG.,函數(shù)的定義,設A, B為集合, 如果 f 為函數(shù), domf=A, ranfB, 則稱 f 為從A到B的函數(shù), 記作 f：AB.,函數(shù)的定義,在 f 中,A,domf,=,定義域,B,ranf,值域,(函數(shù)像的集合),例： 設 X =張三、李四、王五， Y =法國、美國、俄羅斯、英國 f = ,函數(shù)與關系,函數(shù)的定義域是A, 而不是A 的 某個真子集； 一個 x 只能對應于唯一的 y ； A B 的子集并不都能成為 A 到 B 的函數(shù)。,例,A=a,b,c, B=0,1 AB=, |P(AB)|=26, 但

3、只有 23 個子集定義為 X 到 Y 的函數(shù).,f0 = ,f1 = ,f2 = ,f7 = ,函數(shù)的定義,所有從A到B的函數(shù)的集合記作BA, 表示為 BA = f | f：AB |A|=m, |B|=n, 且m, n0, |BA|=nm A=, 則BA=B= A且B=, 則BA=A= ,函數(shù)的定義,設函數(shù) f：AB, A1A, B1B (1) A1在 f 下的像 f(A1) = f(x) | xA1 特別的, f(A)稱為函數(shù)的像 (2) B1在 f 下的完全原像 f 1(B1)=x|xAf(x)B1 注意： 函數(shù)值與像的區(qū)別：函數(shù)值 f(x)B, 像f(A1)B 一般說來 f 1(f(A1

4、)A1, 但是A1f 1(f(A1),例,例 設 f：NN, 且 令A=0,1, B=2, 那么有 f(A) = f 1(B) =, f( 0,1) = f(0), f(1)=0,2 f 1(2)=1,4,函數(shù)的定義,設 f：AB, (1) 若 ranf=B, 則稱 f:AB是滿射的 (2) 若 yranf 都存在唯一的 xA 使得 f(x)=y, 則稱 f:AB是單射的 (3) 若 f:AB 既是滿射又是單射的, 則稱 f:AB是雙射的,例,單 射,映射（函數(shù)）,雙(單、滿)射,滿射,例,判斷下面函數(shù)是否為單射, 滿射, 雙射的? (1) f:RR, f(x) = x2+2x1 (2) f:

5、Z+R, f(x) = lnx, Z+為正整數(shù)集 (3) f:RZ, f(x) = x (4) f:RR, f(x)=2x+1 (5) f:R+R+, f(x)=(x2+1)/x, 其中R+為正實數(shù)集.,定理,令 A 和 B 是有限集，若 A 和 B 的元素個數(shù)相同，即| A| = | B|，則 f: A B是單射的，當且僅當它是一個滿射。,此定理對無限集不一定成立。 例如：f: I I , f(x)=2x 整數(shù)映射到偶整數(shù)(單射、非滿射),例,對于給定的集合A和B構造雙射函數(shù) f:AB (1) A=P(1,2,3), B=0,11,2,3 (2) A=0,1, B=1/4,1/2 (3) A

6、=Z, B=N (4) , B=1,1,例,對于給定的集合A和B構造雙射函數(shù) f:AB (2) A=0,1, B=1/4,1/2,(1,1/2),f(x)=(x+1)/4,課堂練習,對于給定的集合A和B構造雙射函數(shù) f:AB A=-1, 1), B=2, 7),例,對于給定的集合A和B構造雙射函數(shù) f:AB (3) A=Z, B=N,(3) 將Z中元素以下列順序排列并與N中元素對應：Z： 011 2 23 3 N： 0 1 2 3 4 5 6 這種對應所表示的函數(shù)是：,函數(shù)的定義,(1)設 f:AB, 如果存在cB使得對所有的 xA都有 f(x)=c, 則稱 f:AB是常函數(shù). (2) 稱 A

7、上的恒等關系IA為A上的恒等函數(shù), 對所有的xA都有IA(x)=x. (3) 設, 為偏序集，f:AB，如果對任意的 x1, x2A, x1x2, 就有 f(x1) f(x2), 則稱 f 為單調遞增的；如果對任意的x1, x2A, x1x2, 就有f(x1) f(x2), 則稱 f 為嚴格單調遞增的. 類似的也可以定義單調遞減和嚴格單調遞減的函數(shù).,函數(shù)的定義,(4) 設A為集合, 對于任意的AA, A的特征函數(shù) A :A0,1定義為 A(a)=1, aA A(a)=0, aAA (5) 設R是A上的等價關系, 令 g:AA/R g(a)=a, aA 稱 g 是從 A 到商集 A/R 的自然

8、映射,例,(1) 偏序集, , R為包含關系, 為一般的小于等于關系, 令 f:P(a,b)0,1, f()=f(a)=f(b)=0, f(a,b)=1, f 是,單調遞增的, 但不是嚴格單調遞增的,(2) A的每一個子集 A都對應于一個特征函數(shù), 不同的子集對應于不同的特征函數(shù). 例如A=a,b,c, 則有 a,b=,例,(3) 不同的等價關系確定不同的自然映射, 恒等關系確定的自然映射是雙射, 其他自然映射一般來說只是滿射.,A=1,2,3, R=,IA g: AA/R,g(1)=g(2)=1,2, g(3)=3,課堂練習,證明 f(AB) f(A) f(B),保序性：,A B f(A)

9、f(B),AB A AB B,f(AB) f(A) f(AB) f(B),方法1：,f(AB) f(A) f(B),x A f(x) f(A),課堂練習,證明 f(AB) f(A) f(B),保序性：,x A f(x) f(A),對于y, y f(AB) ,則 x, x AB ,使得f(x) = y,方法2：, y f(A) f(B),即 x A x B ,使得f(x) = y, f(x) f(A) f(x) f(B),函數(shù)的定義,設f和g是定義域為自然數(shù)N上的函數(shù) f(n)=O(g(n). 若存在正數(shù)c和n0使得對一切nn0 有 0 f(n)cg(n) f(n) =(g(n). 若存在正數(shù)c

10、和n0使得對一切nn0有 0 cg(n) f(n) f(n) =o(g(n). 若對任意正數(shù)c存在n0使得對一切nn0有 0 f(n) cg(n) f(n) =(g(n). 若對任意正數(shù)c存在n0使得對一切nn0有 0 cg(n) f(n) f(n) =(g(n) f(n) =O(g(n) 且 f(n) =(g(n),函數(shù)的定義,函數(shù)的定義,1+2+ n n + n + n = n2 對于n 1 所以 1+2+ n =,例： 1+2+n,O(n2),又1+2+ n 1+1+1= n 對于n 1 所以 1+2+ n =,(n),綜上 1+2+ n = ?,函數(shù)的定義,1+2+n,=(n2),4.

11、2 逆函數(shù)和復合函數(shù),復合函數(shù) 反函數(shù),8.2 函數(shù)的復合與反函數(shù),關系與逆關系: R-1 R 函數(shù)與反函數(shù)。 可能出現(xiàn)的問題： 定義域 (dom(f -1) A) 函數(shù)值 (一對多),函數(shù)的復合,設F, G是函數(shù), 則FG也是函數(shù), 且滿足 (1) dom(FG)=x|xdomFF(x)domG (2) xdom(FG)有FG(x)=G(F(x),證 先證明FG是函數(shù). 因為F, G是關系, 所以FG也是關系. 若對某個xdom(FG)有xF Gy1和 xFGy2, 則 FGFG t1(FG)t2(FG) t1t2(t1=t2GG) （F為函數(shù)） y1=y2 （G為函數(shù)） 所以 FG 為函數(shù)

12、,函數(shù)的復合,f : X Y , g : W Z,F = , G = ,X = 1,2, Y = 3,4, W = 3,6, Z = 7, 9,F G = ,f = , g = ,f g = ,(1) dom(F G)=x|xdomFF(x)domG,函數(shù)的復合,推論 設 f:AB, g:BC, 則 fg:AC, 且xA都有 fg(x)=g(f(x),證 由上述定理知 fg是函數(shù), 且 dom(fg)=x|xdomff(x)domg =x|xAf(x)B=A ran(fg) rang C 因此 fg:AC, 且xA有 fg(x)=g(f(x),求,例,f g (1),= g(f(1),= g(

13、p) = b,函數(shù)的復合,定理 設f:AB, g:BC (1) 如果 f:AB, g:BC滿射, 則 fg:AC也滿射 (2) 如果 f:AB, g:BC單射, 則 fg:AC也單射 (3) 如果 f:AB, g:BC雙射, 則 fg:AC也雙射 定理 設 f:AB, 則 f = f IB = IAf,證 (1) 任取cC, 由g:BC的滿射性, bB使得 g(b)=c. 對于這個b, 由 f:AB的滿射性，aA使得 f(a)=b. 由合成定理有 fg(a) = g(f(a) = g(b) = c 從而證明了fg:AC是滿射的,函數(shù)的復合,定理 設f:AB, g:BC (2) 如果 f:AB,

14、 g:BC單射, 則 fg:AC也單射,證 (2) 假設存在x1, x2A使得 f g(x1)=f g(x2) 由合成定理有 g(f(x1)=g(f(x2) 因為g:BC是單射的, 故 f(x1)=f(x2). 又由于f:AB是單射的, 所以x1=x2. 從而證明f g:AC是單射的.,函數(shù)的復合,注意：定理逆命題不為真, 即如果f g:AC是單射(或滿射、雙射)的, 不一定有 f:AB 和 g:BC都是單射(或滿射、雙射)的.,多個函數(shù)可復合,復合函數(shù)性質,解: g o h = , f o (g o h ) = , , f o g = , , ( f o g) o h = , , ,逆關系,

15、已知：集合 A=1, 2, 3, B=a, b, c令函數(shù) f: A B f =,但函數(shù) f的逆關系：,f -1 =, , ,不是函數(shù),原函數(shù)值域ran(f ) = dom(f -1) B,原函數(shù)f (多對一),原因,反函數(shù),定理 設 f:AB是雙射的, 則f 1:BA也是雙射的.,證明思路： 先證明 f 1:BA，即f 1是函數(shù)且domf 1=B, ranf 1=A. 再證明f 1:BA的雙射性質.,反函數(shù),證 因為 f 是函數(shù), 所以 f 1是關系, 且 dom f 1 = ranf = B , ran f 1 = domf = A 對于任意的 xB = dom f 1, 假設有y1, y

16、2A使得 f 1f 1 成立, 則由逆的定義有 ff 根據(jù) f 的單射性可得y1=y2, 從而證明了f 1是函數(shù)，且是滿射的.,若存在x1, x2B使得f 1 (x1)= f 1 (x2)=y, 從而有 f 1f 1 ff x1=x2 對于雙射函數(shù)f:AB, 稱 f 1:BA是它的反函數(shù).,反函數(shù),定理 (1) 設 f:AB是雙射的, 則 f 1f = IB, f f 1 = IA (2) 對于雙射函數(shù) f:AA, 有 f 1 f = f f 1 = IA,例,求: f f -1 及f -1 f,解:,f,f -1,f -1 f,f f -1,=IA,=IB,例,定理 是一一,對應函數(shù),則,(

17、雙射),定理,均為一一對應函數(shù), 則,(雙射),定理,定理,分段函數(shù)的復合,4.4 基數(shù)的概念,自然數(shù)集合 等勢 有(無)限集合 基數(shù),8.3 雙射函數(shù)與集合的基數(shù),定義 給定 A的后繼集為,若 為 ,則,可寫成如下形式,自然數(shù)集合,可簡記為,若命名集合 為0,則,L,得到自然數(shù)集合,自然數(shù)集合,自然數(shù)集合,(n -1)+ =0,1,2,. . . n -1 = n,L,定義 給定兩個集合A 與 B, 當且僅當存在著從 A 到 B 的雙射函數(shù), 稱集合A 與B 是等勢的, 記為A B .,等勢,等勢,等勢,等勢,證明: 設集合族為S 對任意 A S ,A A . 若 A ,B S , A B

18、,則B A 若 A ,B ,C S,A B ,B C , 則 A C,定理 在集合族上等勢關系是一個等價關系.,(1) IA是從A到A的雙射 (2) 若 f:AB是雙射，則f 1:BA是從B到A的雙射. (3) 若 f:AB，g:BC是雙射，則fg:AC是從A到C的雙射,定義 若有一個從集合 0,1, , n-1 到A 的雙射函數(shù),則稱A 是有限(窮)的; 若A 不是有限(窮)的,則它是無限的.,有(無)限集合,有(無)限集合,集合A 有限 A 某個自然數(shù),基數(shù),定義 (1) 對于有限集合A, 稱與A等勢的那個惟一的自然數(shù)為A的基數(shù), 記作cardA (也可以記作|A|) cardA = n

19、A n,一個集合是有限的當且僅當它與某個自然數(shù)等勢；,|有限集合| = 元素個數(shù) |空集| = 0,等勢,等勢,例1: 試證集合 A = a, b, c, d 與 B = , , , 等勢,證明: 設 f : A B , f (a) = , f (b) = , f (c) = , f (d) = , 則 f 是 A B 的雙射函數(shù), 所以A B,等勢,等勢,例2: 試證自然數(shù)集合 N 與 集合 A = 2n | n N 等勢 .,證明: 設 f : N A , 且 f (n) = 2n, n = 0, 1, 2, , 則 f 是 N A 的雙射函數(shù), 所以 N A .,等勢,等勢,例3: 設

20、A = ( 0,1 ) = x | x R 0 x 1, 證明 A 與實數(shù)集合 R 等勢 .,等勢,f 是單射的. 對于任意的x1 和 x2 , x1 , x2 ( 0,1 ) (2x1 -1) , (2x2 -1 ) (- , ) 于是 tan(2x1 -1) = tan(2x2 -1) (2x1 -1) =(2x2 -1 ) x1 = x2 , 所以 f 是單射函數(shù) .,2,2,2,2,2,2,2,等勢,因此 A R .,因為f 單調，所以f 是入射的.,2,例4,則 f 是Z到N的雙射函數(shù). 從而證明了ZN.,ZN,例5,0,1(0,1). 其中(0,1)和0,1分別為實數(shù)開區(qū)間和閉區(qū)間

21、. 令 f : 0,1(0,1),例6,對任何a, bR, ab, 0,1a,b，雙射函數(shù) f:0,1a,b, f(x)=(ba)x+a 類似地可以證明, 對任何a, bR, ab, 有(0,1)(a,b).,定義 有限集、或者與自然數(shù)集合等勢的任意集合稱為可數(shù)集(可列集),無限可數(shù)集的基數(shù)用0表示.,可數(shù)集,可數(shù)集,可數(shù)集,可數(shù)集舉例,例 A = a, b, c, B = 1, 3, 5, , 2n+1, , C = 3, 12, 27, , 3(n+1)2, , 整數(shù)集Z , 有理數(shù)集Q .,定理 設A是集合, A為可數(shù)集的充要條件是可排列成A = a1 , a2 , . , an , .

22、 的形式.,可數(shù)集充要條件,一個集合是可數(shù)集當且僅當可以將它的所有元素逐個的排成一個序列,使得序列中每個元素都屬于這個集合,并且這個集合中的每個元素都在序列中的某個位置出現(xiàn)且僅出現(xiàn)一次.對于任何的可數(shù)集, 它的元素都可以排列成一個有序圖形. 換句話說, 都可以找到一個“數(shù)遍”集合中全體元素的順序.,可數(shù)集充要條件,例,NNN. NN中所有的元素排成有序圖形,例,NQ. 雙射函數(shù) f:NQ, 其中f(n)是n下方的有理數(shù).,-2/1,5,-1/1,4,-3/1,18,2/1,10,3/1,11,0/1,0,1/1,1,-2/2,-1/2,3,-3/2,17,2/2,3/2,12,0/2,1/2,

23、2,-2/3,6,-1/3,7,-3/3,2/3,9,3/3,0/3,1/3,8,-2/4,-1/4,15,-3/4,16,2/4,3/4,13,0/4,1/4,14,PLAY,例:可數(shù)個兩兩不相交的可數(shù)集的并是可數(shù)集.,可數(shù)集,可數(shù)集的性質： 可數(shù)集的任何子集都是可數(shù)集. 兩個可數(shù)集的并是可數(shù)集. 兩個可數(shù)集的笛卡兒積是可數(shù)集. 可數(shù)個可數(shù)集的笛卡兒積仍是可數(shù)集.,證明 是可數(shù)集,是可數(shù)的.,令,是雙射的,故 是可數(shù)集.,例: Q是可數(shù)集.,定理:Q可數(shù)集,有關勢的結果,等勢結果 N Z Q NN 任何實數(shù)區(qū)間都與實數(shù)集合R等勢,不等勢的結果: 定理 (康托定理) (1) N R； (2)

24、對任意集合A都有AP(A) 證明思路： (1) 只需證明任何函數(shù) f:N0,1都不是滿射的. 任取函數(shù) f:N0,1, 列出 f 的所有函數(shù)值，然后構造一個0,1區(qū)間的小數(shù)b，使得b與所有的函數(shù)值都不相等.,證明,證 (1) 規(guī)定0,1中數(shù)的表示. 對任意的x0,1, 令 x = 0. x1 x2 , 0 xi 9 規(guī)定在 x 的表示式中不允許在某位后有無數(shù)個9的情況. 設 f: N0,1是任何函數(shù)，列出 f 的所有函數(shù)值： f(0) = 0.a1(1)a2(1) f(1) = 0.a1(2)a2(2) f(n1) = 0.a1(n)a2(n) 令 y 的表示式為0.b1b2, 并且滿足bi ai(i), i=1,2, 那么y0,1, 且y與上面列出的任何函數(shù)值都不相等. 這就推出yranf, 即 f 不是滿射的.,基數(shù),定義 (1) 對于有限集合A