復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)與工程系吳永輝離散數(shù)學(xué)函數(shù)基礎(chǔ)知識(shí)市公開課獲獎(jiǎng)?wù)n件

1、第三章 函數(shù)3.1 函數(shù)基本概念3.2 逆函數(shù)與復(fù)合函數(shù)3.3 集合特性函數(shù)第1頁第1頁序言函數(shù)回顧中學(xué)期間所學(xué)函數(shù)函數(shù)特點(diǎn)：自變量和應(yīng)變量函數(shù)類型第2頁第2頁3.1 函數(shù)基本概念一 函數(shù)及其術(shù)語定義定義3.1（函數(shù)） 設(shè)A和B是兩個(gè)任意集合，f 是從A到B二元關(guān)系。若f 含有性質(zhì)：（1）f 定義域Dom f=A；（2）假如(a, b)，(a, b)f，則b=b。則稱關(guān)系f 是從A到B函數(shù)，記為f:AB，或AB。稱b為a象，a為b原象，記為b=f(a)。f 值域記為Rf。又稱f 為從A到B映射。第3頁第3頁3.1 函數(shù)基本概念函數(shù)：一個(gè)特殊關(guān)系 函數(shù)關(guān)系 函數(shù)關(guān)系 給出關(guān)系，依據(jù)函數(shù)定義鑒定是

2、否是函數(shù)。第4頁第4頁3.1 函數(shù)基本概念例：設(shè)A=1,2,3,4, B=a,b,c, 從A到B關(guān)系:R1=(1,a), (2,b), (3,c),R2=(1,a), (1,b), (2,b), (3,c), (4,c),R3=(1,a), (2,b), (3,b), (4,a)DR1=1,2,3A, 不是函數(shù)。DR2=1,2,3,4=A, 但(1,a),(1,b)R2, 故不是函數(shù)。R3是函數(shù)，滿足函數(shù)定義。第5頁第5頁例：設(shè)A=, a, a，定義f:AAP(A)下列：f(x, y)=x, x,y判斷下列各式是否成立：1) f(, )=2) f(, )=, 3) f(a, a)=a4) f(

3、a, a)=a, a, a西安交通大學(xué)1996年考研第6頁第6頁f(, )=, , =, =因此1)成立，2)不成立；f(a, a)=a, a, a因此3)不成立，4)成立；第7頁第7頁3.1 函數(shù)基本概念定義3.2 （象，原象） 設(shè)函數(shù)f：AB，XA，YB，定義：f(X)=f(a)|aX稱f(X)是在f 下X 象。f -1(Y)=aA| f(a)Y稱f -1(Y)是在f 下Y原象。第8頁第8頁例3.3 /*象，原象概念*/設(shè)A=1, 2, 3, B=a, b, c, d, g=(1, a), (2, c), (3, c)從A到B一個(gè)函數(shù)。S=1，T=1, 3，U=a，V=a, c。g(S)=

4、a，g(T)=a, cg-1(U)=1，g-1(V)=1, 2, 3第9頁第9頁3.1 函數(shù)基本概念二 滿射、內(nèi)射、雙射定義3.3（滿射、內(nèi)射、雙射）（1）設(shè)f：AB，若Rf=B，則稱f為滿射（到上）。（2）設(shè)f：AB，若a1, a2A， a1a2有f(a1)f(a2)，則稱f為內(nèi)射（一對(duì)一）。（3）設(shè)f：AB，若f是滿射且是內(nèi)射，則稱f為雙射（一一相應(yīng)）。第10頁第10頁例3.4 /* 判斷滿射、內(nèi)射、雙射 */設(shè)A=a, b, c, d, B=1, 2, 3, 4，f是從A到B函數(shù)。(1)f=(a, 1), (b, 2), (c, 3), (d, 2)(2)f=(a, 1), (b, 3)

5、, (c, 4), (d, 2)問f是滿射還是內(nèi)射？第11頁第11頁例：指出下列函數(shù)是否為滿射、內(nèi)射和雙射，并闡明理由。然后依據(jù)要求進(jìn)行計(jì)算，其中N為自然數(shù)集合。1）f:NNN，f(x, y)=x+y+1, 計(jì)算f(N1)。2） f:NNN，f(x)=(x, x+1)，計(jì)算f0, 1, 2。北京大學(xué)1993年考研第12頁第12頁解：1）由于0N，但是找不出這樣(x, y)NN，使得f(x, y)=0；因此f 不是滿射；由于f(1, 2)=f(2, 1)=1+2+1=4，因此f 不是內(nèi)射；f(N1)=x | xN且x2。第13頁第13頁解：2）由于(1, 1)NN，但找不出這樣xN，使得f(x)

6、=(1, 1)，因此f 不是滿射；對(duì)任意x, yN，f(x)=(x, x+1), f(y)=(y, y+1), 假如f(x)=f(y), 則(x, x+1)=(y, y+1), 即得x=y。因此f 是內(nèi)射。f0, 1, 2=(0, 1), (1, 2), (2, 3)第14頁第14頁例：設(shè)雙射f：AB，試結(jié)構(gòu)從P(A)到P(B)一個(gè)雙射，并證實(shí)之。武漢大學(xué)1997年考研第15頁第15頁解：結(jié)構(gòu)函數(shù)g: P(A)P(B), xP(A)，令g(x)=y，滿足ax，都有f(a)y，且對(duì)于by，f-1(b)x，即y為僅由x中各元素在f作用下象構(gòu)成集合。證實(shí)g: P(A)P(B)是雙射。第16頁第16頁

7、3.1 函數(shù)基本概念三、不同函數(shù)個(gè)數(shù)1 集合A到集合B能夠定義多少個(gè)不同函數(shù)?(1) 集合A到集合B二元關(guān)系個(gè)數(shù)/* 集合A到集合B二元關(guān)系是集合AB子集，因此應(yīng)考察AB有多少個(gè)不同子集，也就是考察AB冪集元素個(gè)數(shù)。*/因?yàn)閨AB|=|B|A|,故|P(AB)|=2|A|B|，因此集合A到集合B二元關(guān)系個(gè)數(shù)是2|A|B|第17頁第17頁3.1 函數(shù)基本概念(2) A上二元關(guān)系個(gè)數(shù)有多少個(gè)？設(shè)|A|=n，則A上二元關(guān)系個(gè)數(shù)有2n2A上有多少個(gè)自反關(guān)系？A=a1,a2, anAA=?用矩陣形式表示：第18頁第18頁3.1 函數(shù)基本概念自反關(guān)系一定包含(a1,a1), (a2,a2) , (an,a

8、n),余下共有n2-n個(gè)元素，可組成2n2 -n個(gè)不同關(guān)系。故不同自反關(guān)系有2n2 -n個(gè)。第19頁第19頁3.1 函數(shù)基本概念2. 集合A到集合B不同函數(shù)個(gè)數(shù)/*依據(jù)函數(shù)定義，AB子集不一定是A到B函數(shù)。*/設(shè)|A|=m,|B|=n, 因?yàn)閷?duì)A中m個(gè)元素任一個(gè)元素a，可在Bn個(gè)元素中任取一個(gè)元素作為a象, 因此A到B函數(shù)有nm個(gè)。第20頁第20頁3.1 函數(shù)基本概念3. 例：令X=x1, x2, , xm，Y=y1, y2, , yn ，問1）有多少不同由X到Y(jié) 關(guān)系？2）有多少不同由X到Y(jié) 函數(shù)？3）有多少不同由X到Y(jié) 內(nèi)射和雙射？中國(guó)科學(xué)院計(jì)算所1999年考研第21頁第21頁3.1 函數(shù)

9、基本概念1) 不同X到Y(jié)關(guān)系數(shù)|P(XY)|=2mn.2) nm.3) 在有限集中,只有n=m才存在X到Y(jié)雙射,且個(gè)數(shù)為m!,不然不存在雙射.若m=n,則內(nèi)射個(gè)數(shù)為m!,若mn,則內(nèi)射個(gè)數(shù)為0,若mn,從Y 中任取m 個(gè)元素有 種方法,此m 個(gè)元素與X 中m 個(gè)元素間有m! 種不同雙射,因此內(nèi)射個(gè)數(shù)為 .第22頁第22頁3.2 逆函數(shù)與復(fù)合函數(shù)一 逆函數(shù)定義3.4 (逆函數(shù)) 設(shè)f：AB是雙射，f逆關(guān)系稱為f逆函數(shù)，記為f-1：BA。 f(a)=b, f-1(b)=a第23頁第23頁定理3.1 設(shè)f：AB是雙射，則設(shè)f-1：BA也是雙射。證實(shí)辦法：依據(jù)雙射、滿射和內(nèi)射定義進(jìn)行證實(shí)：（1）證實(shí)滿

10、射；（2）證實(shí)內(nèi)射。直接推導(dǎo)第24頁第24頁證實(shí)：由定義知：f-1是f逆函數(shù)。先證實(shí)f-1是滿射：設(shè)f=(a, b) | aA, bB, f(a)=b , f-1 =(b, a) | (a, b)f 。由于對(duì)于每一個(gè)aA，必有b使(a, b)f，從而對(duì)每一個(gè)aA使(b, a)f-1，即f-1(b)=a，因此f-1 : BA是滿射。再證實(shí)f-1是內(nèi)射：由于若f-1(b1)=a，f-1(b2)=a，則f(a)=b1，f(a)=b2。又f：AB是函數(shù)，便有b1=b2。因此f-1 : BA是內(nèi)射。第25頁第25頁定理3.2 設(shè)f：AB是雙射，則(f-1)-1=f。 證實(shí)兩個(gè)函數(shù)f和g相等辦法：對(duì)于定義

11、域A中任意元素a，證實(shí)f(a)=g(a)。第26頁第26頁3.2 逆函數(shù)與復(fù)合函數(shù)二 復(fù)合函數(shù)定義3.5（復(fù)合函數(shù)） 設(shè)g: AB, f: BC，定義復(fù)合函數(shù)f o g為：f o g =(a, c) | aA, cC，且存在bB，使b=g(a), c=f(b) ，稱f o g是從A到C復(fù)合函數(shù)，記為f o g : AC。 對(duì)aA, (f o g)(a)=f(g(a)。 先后順序第27頁第27頁3.2 逆函數(shù)與復(fù)合函數(shù)注意：這里采用復(fù)合函數(shù)習(xí)慣記法,目的是為了將變?cè)旁诤瘮?shù)記號(hào)右側(cè)，使(fg)(a)= f(g(a),因此用記號(hào)(fg)，而不用gf。例：A=1,2,3, f、g是集合A到A函數(shù)。g

12、=(1,2),(2,1),(3,3), f=(1,2),(2,3),(3,1)(fg)=(1,3),(2,2),(3,1)gf =(1,1),(2,3),(3,2)普通fggf第28頁第28頁定理：設(shè)函數(shù)g:AB,f:BC,則A到C復(fù)合關(guān)系gf是A到C函數(shù)。證實(shí)：先證實(shí)對(duì)A中任一元素,都有C中元素與之相應(yīng),然后證實(shí)對(duì)A中每個(gè)元素,都只相應(yīng)C中一個(gè)元素(1)對(duì)A中任一元素a,都有C中元素與之相應(yīng)對(duì)任意aA，由于g是A到B函數(shù)，因此存在bB，使得(a,b)g，又由于f是B到C函數(shù)，因此對(duì)于b，存在cC，使得(b,c) f，依據(jù)關(guān)系復(fù)合概念得(a,c)gf第29頁第29頁(2)對(duì)A中每個(gè)元素,都只相

13、應(yīng)C中一個(gè)元素即證實(shí)對(duì)A中元素a，若有x,yC，使得(a,x)gf，(a,y)gf，必有x=y。由于(a,x)gf，依據(jù)復(fù)合關(guān)系概念，存在b1B，使得(a,b1) g，(b1,x) f，同樣由于(a,y)gf，依據(jù)復(fù)合關(guān)系概念，存在b2B，使得(a,b2)g，(b2,y) f，現(xiàn)在有b1,b2B，而(a,b1)g，(a,b2)g，由于g是函數(shù)，因此b1=b2，現(xiàn)在是存在x,yC，(b1,x) f，(b1,y) f，而f也是函數(shù)，因此有x=y。因此gf是函數(shù)。第30頁第30頁3.2 逆函數(shù)與復(fù)合函數(shù)定理 3.3 設(shè)g: AB, f: BC, h: CD，則(h o f) o g= h o (f

14、o g)。證實(shí)：由我們前面證實(shí)定理能夠知道：(hf )g和h(fg)都是A到D函數(shù)。對(duì)任意aA，存在bB，使得g(a)=b, 又對(duì)于b，存在cC，使得f(b)=c, 對(duì)于c，存在dD，使得h(c)=d, 有(hf)g(a)=(hf)(g(a)=(hf)(b)= h(f(b)=h(c) =d，同樣我們有h(fg)(a)= h(fg(a)=h(f(g(a) =h(f(b)=h(c)=d，由a任意性得(hf )g=h(fg)第31頁第31頁3.2 逆函數(shù)與復(fù)合函數(shù)定理3.4 設(shè)g: AB, f: BC, f o g : AC，則(1) 若f和g是滿射，則f o g是滿射。(2) 若f和g是內(nèi)射，則f

15、 o g是內(nèi)射。(3) 若f和g是雙射，則f o g是雙射。第32頁第32頁證實(shí)：(1)要證實(shí)fg滿射，就是證實(shí)對(duì)C中每個(gè)元素都有A中元素與之相應(yīng)。對(duì)任意cC，由于f是滿射,因此存在bB，使得f(b)=c。又由于g是滿射，因此存在aA，使得g(a)=b，fg(a)= f(g(a)= f(b)=c,因此fg是滿射。第33頁第33頁(2)所謂內(nèi)射就是要證實(shí)當(dāng)ab時(shí)，fg(a) fg(b)對(duì)任意a,bA,若ab，則由于g是內(nèi)射,因此g(a) g(b)。又由于f是內(nèi)射,因此當(dāng)g(a) g(b)時(shí)，有f(g(a) f(g(b),即fg(a) fg(b)，因此fg是內(nèi)射。第34頁第34頁(3)由于f和g是

16、雙射,因此f和g當(dāng)然滿射,則由(1)知fg是滿射。f和g也是內(nèi)射，則由(2)可得fg內(nèi)射，因此fg是雙射。第35頁第35頁例：設(shè)f, g, h是I 到I 函數(shù)，f(x)=3x，g(x)=3x+1，h(x)=3x+2，I 是整數(shù)集，求函數(shù)復(fù)合fg, gh , fgh。依據(jù)復(fù)合函數(shù)定義: fg(x)=f(g(x)，上海大學(xué)1998年考研第36頁第36頁解：fg(x)=f(g(x)=3(3x+1)=9x+3gh(x)=g(h(x)=3(3x+2)+1=9x+7fgh(x)=f(g(h(x)=f(3(3x+2)+1)=3(3(3x+2)+1)=27x+21第37頁第37頁3.2 逆函數(shù)與復(fù)合函數(shù)三 恒

17、等函數(shù)定義3.6（恒等函數(shù)） 設(shè)f：AA，若對(duì)所有aA ，有f(a)=a，則稱f 為A上恒等函數(shù)，記為IA。第38頁第38頁定理3.5 設(shè)f：AB是任意一個(gè)函數(shù)，則IB o f=f o IA=f證實(shí)/*證實(shí)函數(shù)f和g相等:aA, f(a)=g(a)*/第39頁第39頁3.2 逆函數(shù)與復(fù)合函數(shù)定理3.6 若函數(shù)f：AB存在逆函數(shù)f -1，則f -1 o f= IA , f o f -1= IB 第40頁第40頁定理3.7設(shè)g: AB, f: BC都是雙射，則(f o g) -1= g -1of -1第41頁第41頁證實(shí)：由假設(shè)和定理3.4可知，f o g是雙射。又由定理3.1可知，g -1和f

18、-1是雙射。因此g-1of -1是雙射，并且(f o g) -1也是雙射。下面證實(shí)(f o g) -1= g -1of -1。對(duì)任意cC，且f-1(c)=b，g-1(b)=a于是(g -1of -1)(c)= g-1(f-1(c)= g-1(b)=a，(f o g) (a)=f(g(a)=f(b)=c.由上式知(f o g) -1(c)=a, 由于c任意性, 因此(f o g) -1= g -1of -1.第42頁第42頁定義：設(shè)函數(shù)f、g:AB,若對(duì)任意aA,有f(a)=g(a)，則稱函數(shù)f和g相等，記為f=g。例：在實(shí)數(shù)范圍內(nèi)，f(x)=x+1,g(x)= x(x+1)/x對(duì)x=0,f(0

19、)=1,而g在0處沒有定義。因此fg.因此兩個(gè)函數(shù)是否相等必須考察它們定義域是否相同。第43頁第43頁設(shè)f：AB是一個(gè)映射，記f -1是f 逆關(guān)系， f o g是f 、g復(fù)合關(guān)系。證實(shí)：1）當(dāng)且僅當(dāng)f -1 o f=IB時(shí)， f 是滿射。2）當(dāng)且僅當(dāng)f o f -1=IA時(shí)，f 是內(nèi)射。/*上海交通大學(xué)1999考研*/第44頁第44頁解：關(guān)系復(fù)合與函數(shù)復(fù)合聯(lián)系和區(qū)別第45頁第45頁3.3 集合特性函數(shù)1. 定義3.7（特性函數(shù)） 設(shè)U是全集，且AU，函數(shù)A: U 0, 1定義為：A(x)=1，若xA；A(x)=0，若xA。例3.5 設(shè)U是某大學(xué)全體學(xué)生構(gòu)成集合，A是女大學(xué)生集合，特性函數(shù)A值為

20、1相應(yīng)女大學(xué)生，0相應(yīng)于男大學(xué)生。第46頁第46頁2. 定理3.8設(shè)A和B是全集U子集，對(duì)于所有xU，下列各式成立：(1) A(x)=0 A=;(2) A(x)=1 A=U;(3) A(x)B(x) AB;(4) A(x)=B(x) A=B;第47頁第47頁(5) AB(x)= A(x) * B(x);(6) AB(x)= A(x)+B(x)-AB(x);第48頁第48頁證實(shí)： (5) 由于xAB即xA且xB，因此A(x)=1，B(x)=1，于是有AB(x)=A(x) * B(x)=1. 假如xAB，則AB(x)=0，于是A(x)=0或B(x)=0， AB(x)= A(x) * B(x)=0。

21、第49頁第49頁3. 利用集合特性函數(shù)證實(shí)集合恒等式例3.7第50頁第50頁例3.8證實(shí)A(BC)=(AB)(AC)證實(shí): A(BC)(x)=A(x) * BC(x)= A(x) * (B(x)+ C(x)- BC(x)= A(x) * B(x)+ A(x) * C(x)-A(x) * BC(x)= AB(x)+AC(x) -ABC(x)= AB(x)+AC(x) -(AB)(AC)(x)= (AB)(AC)(x)第51頁第51頁形式化證實(shí)1. 演繹證實(shí) 演繹證實(shí)包括命題序列，其正確性造成從某個(gè)初始命題（稱為前提或已知命題）得出“結(jié)論”命題。證實(shí)每一步都必須依據(jù)某條公認(rèn)邏輯原理，利用已知事實(shí)或

22、演繹證實(shí)中前面一些命題，或者利用這兩者組合。第52頁第52頁2. 定理形式1) “假如-則”方式: “假如H，則C?！?假如前提H對(duì)給定參數(shù)值為真，則結(jié)論C對(duì)同樣值為真。 其它形式: H蘊(yùn)涵C; H僅當(dāng)C; C當(dāng)H; 只要H為真，就得出C.第53頁第53頁2) 當(dāng)且僅當(dāng)命題: A當(dāng)且僅當(dāng)B, A iff B, A等價(jià)于B，A正好當(dāng)B兩個(gè)“假如-則”命題：假如A，則B；假如B，則A。第54頁第54頁命題命題：假如H，則C逆否命題：假如非C，則非H一個(gè)命題與其逆否命題同時(shí)為真或同時(shí)為假第55頁第55頁命題：假如H，則C逆命題：假如C，則H逆命題與原命題不等價(jià)第56頁第56頁第57頁第57頁習(xí)題解析

23、一、計(jì)算題1)設(shè)S=a, b, c，T=p, q， f: ST，問有多少函數(shù)f，其中有多少滿射。|S|=3, |T|=2, f: ST，共有函數(shù)為23=8個(gè)，其中滿射為2 =6個(gè)。第58頁第58頁2)下列哪些是函數(shù)，哪些是入射函數(shù)，哪些是滿射函數(shù)，假如是雙射，寫出它逆函數(shù)：A) f: Z N, f(x)=x2+1B) g: N Q, g(x)=1/xC) h: ZN Q, h(Z, n)=Z/(n+1)D) f: 1, 2, 3 p, q, r, f=(1, q), (2, r), (3, p) E) g: N N, g(x)=2xF) h: R2 R2, h(x, y)=(y+1, x+1)

24、 R2第59頁第59頁A) 函數(shù)B) 不是函數(shù)，在x=0無定義C) 函數(shù)，滿射D) 函數(shù)，雙射，f-1: p, q, r1, 2, 3, 這里f-1=(q, 1), (r, 2), (p, 3)E) 函數(shù)，內(nèi)射F) 函數(shù)，雙射, h-1: R2R2, 這里h-1(x, y)=(y-1, x-1).第60頁第60頁3)設(shè)g: AB, f: BC，定義復(fù)合函數(shù)f o g: AC，給出A, B和f, g；使得A) f o g: AC是滿射，但g不是滿射；A=1, 2, 3, 4, B=a, b, c, d, C=5, 6, 7, g=(1, a), (2, b), (3, c), (4, a), f

25、=(a, 5), (b, 6), (c, 7), (d, 7), 則 f o g: AC是滿射，但g不是滿射。第61頁第61頁B) f o g: AC是內(nèi)射，但f不是內(nèi)射；A=1, 2, 3, B=a, b, c, d, C=5, 6, 7, 8, g=(1, a), (2, b), (3, c), f=(a, 5), (b, 6), (c, 7), (d, 7), 則f o g: AC是內(nèi)射，但f不是內(nèi)射；第62頁第62頁C) f o g: AC是雙射；A=1, 2, 3, B=a, b, c, d, C=5, 6, 7, g=(1, a), (2, b), (3, c), f=(a, 5)

26、, (b, 6), (c, 7), (d, 7), 則f o g: AC是雙射；第63頁第63頁計(jì)算題總結(jié)在概念明確基礎(chǔ)上解題第64頁第64頁二、證實(shí)題1）設(shè)g: AB, f: BC，定義復(fù)合函數(shù)f o g: AC，已知f o g是內(nèi)射， g是滿射，證實(shí)f是內(nèi)射。證實(shí)：反證法。假設(shè)f不是內(nèi)射，即存在b1, b2B，b1b2, g(b1)=g(b2)=c。由于g是滿射，因此存在a1, a2A, a1a2, g(a1)= b1, g(a2)=b2. 則f o g(a1)=f o g(a2). 因此f o g不是內(nèi)射，造成矛盾。 第65頁第65頁2）設(shè)g: AB, f: BC，定義復(fù)合函數(shù)f o g

27、: AC，已知f o g是滿射， f是內(nèi)射，證實(shí)g是滿射。證實(shí)：反證法。假設(shè)g不是滿射，則存在bB，不存在aA，使得g(a)=b。由于f是內(nèi)射，因此存在cC, 使得f(b)=c，并且不存在其它bB, 使得f(b)=c。由于f o g是滿射，因此存在aA，f o g(a)=c, 則存在g(a)B，使得f(g(a)=c。則造成矛盾。因此g是滿射。第66頁第66頁3）設(shè)f: XY, g: YX，定義復(fù)合函數(shù)f o g=IX, g o f=IY，證實(shí)f與g是雙射，并且g=f-1。證實(shí)由學(xué)生完畢。第67頁第67頁證實(shí)辦法（1）依據(jù)定義給出性質(zhì)進(jìn)行證實(shí)：證實(shí)函數(shù)是滿射、內(nèi)射和雙射，即證實(shí)滿足滿射、內(nèi)射和雙射要滿足條件；（2）證實(shí)兩個(gè)函數(shù)f與g相等對(duì)任意aA, 證實(shí)f(a)=g(a).第68頁第68頁3.21 設(shè)函數(shù)f: AB, 且X和Y是A子集。證實(shí)：（1）f(XY)=f(X)f(Y)基本法證實(shí)兩個(gè)集合相等：第69頁第69頁（2）f(XY)f(X)f(Y)基本法證實(shí)第70