計算機(jī)數(shù)學(xué)基礎(chǔ)市公開課一等獎省賽課獲獎

計算機(jī)數(shù)學(xué)基礎(chǔ)集合代數(shù)關(guān)系與函數(shù)清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第1頁函數(shù)函數(shù)---單值二元關(guān)系設(shè)F為二元關(guān)系，假如 ?x∈domF，?!y∈ranF，使得xFy成立，則稱F為函數(shù)。假如<x,y>∈F，則記F(x)=y，并稱y是F函數(shù)值。?!==存在唯一清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第2頁函數(shù)設(shè)A、B是集合，假如函數(shù)f滿足以下條件：a)domf?Ab)ranf?B則稱f是從A到B偏函數(shù)，記為f：A+→B。其中A是f前域，B是陪域。清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第3頁函數(shù)設(shè)A、B是集合，假如函數(shù)f滿足以下條件：a)domf=Ab)ranf?B則稱是從A到B全函數(shù)，簡稱從A到B函數(shù)。記為f：A→B。清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第4頁函數(shù)顯然一個從A到B函數(shù)，是滿足以下性質(zhì)二元關(guān)系：(1)每個元素x∈A，都必須有一個y∈A與之成為二元關(guān)系中一個元素即函數(shù)定義域就是A本身，而不是A一個真子集。清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第5頁函數(shù)(2)任何一個x∈A，都只能有唯一一個y∈A與之成為二元關(guān)系中一個元素，即<x,y>∈f∧<x,z>∈f?y=z(3)假如任何一個y∈A，都只有唯一一個x∈A與之成為二元關(guān)系中一個元素，則函數(shù)稱為單根。清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第6頁函數(shù)對一個從A到B函數(shù)來說，其值域可能是B真子集。以下術(shù)語都是函數(shù)同義詞，在不一樣場所可交替使用：“變換”“映射”“對應(yīng)”“運算”清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第7頁函數(shù)將全部從A到B函數(shù)組成集合記為BABA={f|f：A→B}假如A、B分別為n、m元集合，則BA元素個數(shù)為mn。假如A、B最少有一個是φ，而從A到B函數(shù)存在，則φφ=Bφ={φ}不存在從A≠φ到φ函數(shù)。清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第8頁函數(shù)性質(zhì)設(shè)函數(shù)f：A→B，(1)若ranf=B，則稱f是滿射；(2)若對任意y?ranf，只存在唯一x使得f(x)=y，則稱f是單射，或一對一；(3)若f既是滿射，又是單射，則稱f是雙射，或一一對應(yīng)。清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第9頁函數(shù)性質(zhì)為使得從A到B函數(shù)含有某種性質(zhì)，A、B元素個數(shù)需要滿足一定條件。對于有限集合，我們有1)|A|≤|B|，從A到B才能存在單射函數(shù)2)|A|≥|B|，從A到B才能存在滿射函數(shù)3)|A|=|B|，從A到B才能存在雙射函數(shù)清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第10頁函數(shù)性質(zhì)其中1)也稱為鴿巢原理（抽屜標(biāo)準(zhǔn)），其通俗說法是假如m只鴿子（物體）放入n個鴿巢（盒子）里，且m>n則某個鴿巢（盒子）里一定有兩個或更多鴿子（物體）。清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第11頁函數(shù)性質(zhì)例某校某個班有49人，其中年紀(jì)最大是20歲，最小17歲，則其中必有兩個學(xué)生是同年同月生。清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第12頁常見函數(shù)常數(shù)函數(shù)：f：A→B，假如存在y∈B，使得全部x∈A都有f(x)=y，則f稱為常數(shù)（常值）函數(shù)恒等函數(shù)：A上恒等關(guān)系IA稱為恒等函數(shù)，它是雙射。清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第13頁常見函數(shù)單調(diào)增加函數(shù)：f：R→R稱為單調(diào)增加： 假如對于任意x1、x2，假如x1<x2， 則f(x1)≤

f(x2)嚴(yán)格單調(diào)增加 假如對于任意x1、x2，假如x1<x2， 則f(x1)<f(x2)清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第14頁常見函數(shù)單調(diào)遞減函數(shù)：f：R→R稱為單調(diào)遞減： 假如對于任意x1、x2，假如x1<x2， 則f(x1)≥

f(x2)；嚴(yán)格單調(diào)遞減： 假如對于任意x1、x2，假如x1<x2， 則f(x1)>f(x2)；清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第15頁函數(shù)合成函數(shù)是關(guān)系特例，所以函數(shù)也有合成概念。設(shè)f：X→Y和g：Y→Z是兩個函數(shù)，則合成關(guān)系f○

g是f和g合成函數(shù)清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第16頁函數(shù)合成1)dom(f○

g) ={x|x∈domf∧f(x)∈domg} 因為i）dom(f○

g)?domf；Ii）ranf?domg，不然f○

g是空函數(shù)。清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第17頁函數(shù)合成2)?x∈dom(f○

g) 有f○

g(x)=g(f(x))。設(shè)f：X→Y和g：Y→Z則有f○

g：X→Z，且?x∈X，有f○

g(x)=g(f(x))；清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第18頁函數(shù)合成函數(shù)合成滿足結(jié)合律(f○

g)○

h=f○(g○

h)函數(shù)冪定義:i）(1)f0(x)=I(x) (2)fn+1(x)=f(fn(x))Ii）假如f2=f，則稱f是等冪函數(shù)。清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第19頁函數(shù)合成性質(zhì)設(shè)f：X→Y和g：Y→Z，(1)假如f、g是滿射(單射、雙射)函數(shù)，則f○

g是滿射(單射、雙射)函數(shù)(2a)假如f○

g是滿射函數(shù)，則g是滿射函數(shù)(2b)假如f○

g是單射函數(shù)，則f是單射函數(shù)清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第20頁函數(shù)合成性質(zhì)設(shè)f：X→Y和g：Y→Z，(2c)假如f○

g是雙射函數(shù)，則f是單射函數(shù)，g是滿射函數(shù)與恒等函數(shù)合成設(shè)f：X→Y，則

f=IX

○

f=f○IY清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第21頁逆關(guān)系與函數(shù)不能直接用逆關(guān)系來定義反函數(shù)。因為關(guān)系是函數(shù)，逆關(guān)系不一定是函數(shù)。1)逆關(guān)系F-1是函數(shù)?關(guān)系F是單根； 關(guān)系f是函數(shù)?逆關(guān)系f-1是單根；所以，逆關(guān)系F-1是函數(shù)，并沒有限定F是函數(shù)，而只是說明關(guān)系F是單根，所以假如F是函數(shù)，則F一定是單射函數(shù)。清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第22頁逆關(guān)系與函數(shù)2)假如f：X→Y是單射函數(shù)， 則逆關(guān)系f-1是函數(shù)， 且?x∈domF=X， 有f-1(f(x))=x， ?y∈ranf，有f(f-1(y))=y 注意f-1不一定是從Y到X函數(shù)。清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第23頁反函數(shù)假如函數(shù)f是雙射函數(shù)，則f逆關(guān)系是f反函數(shù)，記為f–1。假如函數(shù)f存在反函數(shù)f–1，則稱f是可逆(1)僅當(dāng)函數(shù)f是雙射，才定義反函數(shù)(2)f：X→Y，則f–1：Y→X，也是雙射(3)函數(shù)f：X→Y是雙射，則 反函數(shù)f–1：Y→X，也是雙射清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第24頁反函數(shù)(4)假如函數(shù)f：X→Y逆關(guān)系f–1是從Y到X函數(shù)，則f是雙射(5)假如函數(shù)f：X→Y，是可逆，則f○

f–1=IX，f–1○

f=IY(6)設(shè)函數(shù)f：X→Y，g：Y→X，g=f–1當(dāng)且僅當(dāng)f○

g=IX，g○

f=IY清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第25頁反函數(shù)左逆和右逆對于函數(shù)f：X→Y，假如存在g：Y→Z1)使得g○

f=IY，則稱g是f左逆2)使得f○

g=IX，則稱g是f右逆左逆和右逆可能沒有，也可能有多個清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第26頁反函數(shù)設(shè)函數(shù)f：X→Y，X≠φ，則f有一個右逆?f是單射；f有一個左逆?f是滿射；f有一個左逆且有一個右逆?f是雙射?左逆與右逆相等清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第27頁特殊函數(shù)特征函數(shù)：設(shè)全集為U，對于任意A?UA特征函數(shù)χA：A→{0,1}定義為清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第28頁函數(shù)表示為了描述特征函數(shù)性質(zhì)，首先要求以下函數(shù)表示方法設(shè)X是任意集合，Y?R，f和g都是從X到Y(jié)函數(shù)，則(1)f≤g表示 對于每個x∈X，都有f(x)≤g(x)(2)f+g表示 對于每個x∈X，都有(f+g)(x)=f(x)+g(x)清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第29頁函數(shù)表示(3)f–g表示 對于每個x∈X，都有(f–g)(x)=f(x)–g(x)(4)f×g表示 對于每個x∈X，都有(f×g)(x)=f(x)×g(x)0表示從U到{0,1}函數(shù){<x,0>|x∈A}1表示從U到{0,1}函數(shù){<x,1>|x∈A}清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第30頁特征函數(shù)特征函數(shù)特征1)χA=1–χ~A2)χA∩B=χA×χB3)χA∪B

=χA+χB–χA×χB4)χA–B

=χA–χA×χB清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第31頁特征函數(shù)特征函數(shù)特征5)?A(A?U→0≤χA≤1)6)χA=0?A=φ7)χA=1?A=U8)χA≤χB?A?B清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第32頁特征函數(shù)特征函數(shù)特征9)χA=χB?A=B10)χA×χB=χA

?A?B11)χA×χA=χA清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第33頁變換和置換函數(shù)非空集合A上函數(shù)，即一個從A到A函數(shù)稱為A一個變換。假如是雙射函數(shù)則稱為A一個一一變換。對應(yīng)A上恒等關(guān)系稱為恒等變換清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第34頁變換和置換函數(shù)按照函數(shù)合成概念，A上兩個變換是能夠合成，合成函數(shù)依然是從A到A函數(shù)，即依然是一個變換任何一個變換和恒等變換合成仍為原變換，即：f=IA○

f=f○IA清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第35頁變換和置換函數(shù)因為只有雙射函數(shù)才有反函數(shù)，所以只有一一變換才有反變換對于A上一一變換f，有f○

f–1=f–1

○

f=IA假如A是有限集，則A上一個一一變換稱為A一個置換。清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第36頁變換和置換函數(shù)假如A={a1,a2,.,an}則置換σ習(xí)慣記作這是有n個元素置換，稱為n元置換。共有n！個清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第37頁變換和置換函數(shù)以Sn表示這n！個n元置換集合例A={1,2,3}，則 S3={σ1,σ2,...,σ6)其中清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第38頁變換和置換函數(shù)σ1是恒等置換清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第39頁變換和置換函數(shù)能夠計算任何兩個置換合成，如普通合成運算不滿足交換律，通常清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第40頁變換和置換函數(shù)對于n個元素集合A中m個不一樣元素{b1,b2,...,bm}，假如n元置換σ定義為：這時稱σ為m次輪換。m=2時稱為對換。簡單表示成σ=(b1,b2,...,bm)清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第41頁變換和置換函數(shù)如上述等等。其中σ2，σ3，σ4是對換清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第42頁變換和置換函數(shù)輪換也能進(jìn)行合成運算。顯然一個對換與其自己合成為恒等置換即(bi,bj)○(bi,bj)=IA。清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第43頁變換和置換函數(shù)例A={1,2,3,4,5,6}，σ1=(4,1,3,5)，σ2=(5,6,3)清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第44頁變換和置換函數(shù)例A={1,2,3,4,5,6}，

σ1=(4,1,3,5)，σ2=(5,6,3)清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第45頁變換和置換函數(shù)普通情況下，輪換合成不滿足交換律，而且也不再是輪換。在什么情況下，輪換合成還是輪換呢？假如A中元素沒有同時出現(xiàn)在其上兩個輪換，這兩個輪換稱為是不交。如S6中輪換(1,2,4)和(3,5)是不交清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第46頁變換和置換函數(shù)兩個不交輪換合成運算滿足交換律任何一個置換，都能夠表示成一系列不交輪換合成，且表示式是唯一。任何一個輪換，都能夠表示成一系列對換合成，但表示式不是是唯一。清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第47頁變換和置換函數(shù)比如顯然兩個表示式是不一樣。清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第48頁集合基數(shù)對于有限集合基數(shù)，有包含排斥定理?，F(xiàn)在不局限于有限集?；鶖?shù)定義：集合A元素數(shù)，記為#A實際度量和比較集合大小根本方法是建立一一對應(yīng)關(guān)系這個方法可推廣到任意集合上。清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第49頁集合基數(shù)集合等勢概念A(yù)和B為集合假如存在雙射函數(shù)f：A→B則稱A和B等勢或等位記為A≈B；清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第50頁集合基數(shù)集合N×N與N等勢。存在雙射函數(shù)f:N×N→Nf(m,n)=[(m+n)2+3m+n]/2所以集合N×N≈N。清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第51頁集合基數(shù)雙射函數(shù)f:N×N→N以下列圖清華大學(xué)當(dāng)代遠(yuǎn)程教育*專升本課程第52頁集合基數(shù)自然數(shù)集合N與有理數(shù)集合Q等勢。函數(shù)f:N→Q，f(n)就是[n]旁邊有理數(shù)（見下列圖），因為f雙射性，N