第三離散數(shù)學(xué)

第三離散數(shù)學(xué)第一頁，共十八頁，2022年，8月28日①顯然g給B中每一元素定義了象，且象唯一。所以g·f=IA，即g是f的左逆函數(shù)。②說明象唯一性。設(shè)b∈B，g(b)=a1,g(b)=a2若b∈f(A)則f(a1)=f(a2)，由f是內(nèi)射，必有a1=a2所以g給b確定了唯一的象。若b∈B-f(A)則g(b)=a0所以a1=a2=a0，象也唯一因此，g:BA的函數(shù)。對(duì)a'∈A，記f(a')=b'∈B，有g(shù)·f(a')=g(f(a'))=g(b')=a'=IA(a')第二頁，共十八頁，2022年，8月28日⑵設(shè)f是滿函數(shù)，要證f有右逆函數(shù)，即構(gòu)造一個(gè)g:BA使f·g=IB，則g為f的右逆函數(shù)。所以f·g=IB，g是f的右逆函數(shù)。所以g:BA的函數(shù)對(duì)b'∈B,記a'=g(b')，則f·g(b')=f(g(b'))=f(a')=b'

=IB(b')證明：因?yàn)閒是AB的滿射，所以對(duì)b∈B，a∈A使得f(a)=b。構(gòu)造g，對(duì)b∈B＝f(A）定義g(b)=a，其中a是滿足f(a)=b的任意一個(gè)確定的a。這樣g給B中每一個(gè)元素定義了唯一的象。置換是一種特殊的雙射函數(shù)，只有有限集合A上的雙射，這一節(jié)很簡單，大家自己看書。第三頁，共十八頁，2022年，8月28日集合的特征函數(shù)：也就是給定集合U的子集A，A的特征函數(shù)定義為

eA：U{0，1}對(duì)任意的x∈U，有eA(x)=

即對(duì)全集U的每個(gè)元素x，當(dāng)x∈A時(shí)，eA(x)=1,否則為01當(dāng)x∈A

0當(dāng)xA第四頁，共十八頁，2022年，8月28日3.4數(shù)學(xué)歸納法及其應(yīng)用

數(shù)學(xué)歸納法在數(shù)學(xué)中是一個(gè)強(qiáng)有力的證明技巧。數(shù)學(xué)歸納法不僅是證明定理的一個(gè)重要工具，而且還為定義無窮集合提供了一種方法。這一節(jié)我們將介紹如何應(yīng)用數(shù)學(xué)歸納法。設(shè)p(n)是一個(gè)與自然數(shù)n有關(guān)的命題，我們說p(k)為真，即是說n=k，命題成立。為了證明一個(gè)命題p(n)對(duì)于所有n≥n0(n0≥1)的自然數(shù)都成立，只要證明兩件事。

⑴(歸納基礎(chǔ))當(dāng)n＝n0時(shí)，p(n0)真(可用任意方法證明）⑵(歸納步驟)若當(dāng)n=k時(shí)有p(k)為真，則當(dāng)n=k+1也真。

為此，一般先假設(shè)”n=k時(shí),p(k)為真”，這叫做歸納假設(shè)，再由此推出p(k+1)也真。這就是大家在中學(xué)就用過的數(shù)學(xué)歸納法。大家一般用它來證明等式或不等式。第五頁，共十八頁，2022年，8月28日例1.假設(shè)我們有3分和5分的兩種不同面值的郵票，我們要證明，8分和8分以上的郵費(fèi)都可以用這兩種面值的郵票組合而成。證明：對(duì)郵費(fèi)n進(jìn)行歸納證明。⒈n＝8時(shí)，可由一張3分和一張5分的郵票組合而成。則p(8)真。⒉設(shè)n＝k時(shí)，p(k)真，即我們可以用3分和5分的郵票恰好組成k分的郵費(fèi)。那么n＝k+1時(shí)：①若我們組成的k分郵費(fèi)中至少有一張5分的郵票，那么用2張三分的郵票去代替這張5分的郵票，我們就得到k+1分的郵費(fèi)。即p(k+1)真。②若k分的郵費(fèi)全用3分的郵票組成，因此用兩張5分的郵票去代替三張3分的郵票就得到k+1的郵費(fèi)。即p(k＋1)真。再由歸納原理知結(jié)論成立。第六頁，共十八頁，2022年，8月28日數(shù)學(xué)歸納法還有另一種形式，為了證明一個(gè)命題對(duì)于所有的自然數(shù)n都是真的，我們只要證明：⑴(歸納基礎(chǔ))當(dāng)n＝n0時(shí)，p(n0)真(可用任意方法證明）⑵若n0≤n＜k時(shí)，p(n)真，則n=k時(shí)，這個(gè)命題也真，即p(k)真。第七頁，共十八頁，2022年，8月28日例2.證明每一整數(shù)n≥2可以寫成素?cái)?shù)的乘積。證明：⑴(歸納基礎(chǔ))n=2時(shí)，因?yàn)?是素?cái)?shù)，所以結(jié)論成立。⑵(歸納步驟)對(duì)于任意的n∈N且n＞2

設(shè)n＜k時(shí)，結(jié)論成立(即n＝2，3，...，k－1時(shí)，n能寫成素?cái)?shù)的乘積)n=k時(shí)：①若k是素?cái)?shù)，結(jié)論成立。②若k不是素?cái)?shù)，那么n＝k＝i·j，(2≤i，j＜k)于是根據(jù)歸納假設(shè)，i，j均能寫成素?cái)?shù)的乘積。即i=q1q2...qt，j=p1p2...pr，其中qm,pS均為素(m=1,2,...t;s=1,2,...r)∴n=q1q2....qtp1p2....pr，即n也能寫成素?cái)?shù)的乘積。因此，對(duì)任意的n∈N，n≥2，結(jié)論成立。第八頁，共十八頁，2022年，8月28日一個(gè)集合S的歸納定義由三部分組成：1.(基礎(chǔ)步)它指定某些事物屬于集合S。(即給集合以基本元素，使所定義集合非空)2.(歸納步)它指定由集合S的元素構(gòu)造新元素的一組規(guī)則。(即指出如何通過某些運(yùn)算，從S中的元素，求得集合的新元素)3.(極小性)由有限次的使用(1)、(2)而求得的那些元素組成。(即說明所定義的集合是滿足基礎(chǔ)和歸納步驟的最小集合)例3用歸納定義確定非負(fù)偶數(shù)集合S。解:(1)(基礎(chǔ)步)0∈S；(2)(歸納步)若n∈S，則n＋2∈S；(3)集合S是由有限次的使用步驟(1)和(2)而得到的那些元素組成。第九頁，共十八頁，2022年，8月28日先介紹幾個(gè)術(shù)語，然后再進(jìn)一步介紹歸納定義集合的例子。表示一個(gè)有限非空符號(hào)集，稱為一個(gè)字母表。由中的有限個(gè)符號(hào)組成的一個(gè)符號(hào)串，稱為上的一個(gè)字或一個(gè)串。設(shè)x是上的一個(gè)串，若x＝a1a2a3....an，n∈N且ai∈，1≤i≤n，那么x的長度為n。長度為0的串用∧(lambda)，稱為空串。若x,y是上的串，即x=a1a2...an,y=b1b2...bm,其中ai∈,bi∈，那么x與y的拼接，用xy表示，xy=a1a2...anb1b2...bm例4.設(shè)是一個(gè)字母表，﹢是上所有非空串的集合。用＊表示上所有串的集合，即＊={∧}∪﹢如若={a,b},那么﹢={a,b,aa,ab,ba,bb,aaa,aab,....}(2)(歸納步)若x∈﹢且a∈，那么ax∈﹢(1)(基礎(chǔ)步)若a∈，那么a∈﹢第十頁，共十八頁，2022年，8月28日例5Filonacci（菲波拉契）函數(shù)Fb:ZZ被定義為：Fb(0)=0Fb(1)=1Fb(n+1)=Fb(n-1)+Fb(n)(n=1,2,3,....)對(duì)于任何的n∈N(n≥2)，函數(shù)值Fb(n)可依據(jù)上式歸納到計(jì)算Fb(0)和Fb(1)，如求Fb(5)Fb(5)=Fb(3)+Fb(4)=Fb(1)+Fb(2)+Fb(2)+Fb(3)=Fb(1)+2Fb(2)+Fb(3)=Fb(1)+2Fb(2)+Fb(1)+Fb(2)=2Fb(1)+3Fb(2)=2+3(Fb(0)+Fb(1))=2+3=5第十一頁，共十八頁，2022年，8月28日3.5集合的基數(shù)(一)可數(shù)數(shù)集對(duì)于一個(gè)有限集合，我們這樣求基數(shù)，將集合的元素和自然數(shù)集的一個(gè)子集Nm的元素之間建立一個(gè)一一對(duì)應(yīng)的關(guān)系。例一個(gè)小組有若干個(gè)同學(xué)，我們依次點(diǎn)名這樣，這個(gè)小組的成員與N的子集N5＝{1,2,3,4,5}的元素之間有一個(gè)一一對(duì)應(yīng)的關(guān)系?！嗾f這個(gè)小組有5個(gè)同學(xué)。張華王小平曾梅余利李剛

12345第十二頁，共十八頁，2022年，8月28日定義3-10：如果從集合Nm到A存在一個(gè)雙射，則稱集合A是有限集，＃A＝m。＃Φ＝0，Φ也是有限集。不是有限集的集合稱為無限集有限集中最簡單的一種是可數(shù)集。定義3-11：如果從集合N到A存在一個(gè)雙射，則稱A是可數(shù)集。記＃A＝§?！啊臁弊x作“阿列夫零”。有限集和可數(shù)集總稱為可計(jì)數(shù)集。如果集合A是無限的但不是可數(shù)的，則稱A是不可數(shù)集。例1：Z(非負(fù)整數(shù))是可數(shù)集f:NZf(x)=x-1顯然f是雙射。第十三頁，共十八頁，2022年，8月28日命題1：一個(gè)集合是可數(shù)集合的充要條件是它可以排成一個(gè)無序列的形式。證明：設(shè)A是一可數(shù)集。于是A與N的元素間存在一一對(duì)應(yīng)關(guān)系。令A(yù)中與n對(duì)應(yīng)的元素為an＝f(n)(n=1,2,3...)則A的元素按此編號(hào)可以排列成無窮序列：a1，a2，a3，....設(shè)A的元素可以排成一個(gè)無窮序列的形式：a1,a2,a3,...顯然f是一雙射。所以，A可數(shù)。那么我們可以構(gòu)造f，f:NA，f(n)=an第十四頁，共十八頁，2022年，8月28日定理3-12：任一無限集A必包含一可數(shù)子集。定理3-16：可數(shù)集的無限子集仍是可數(shù)集。定理3-17：設(shè)集A可數(shù)，集B有限，且A∩B＝Φ，則A∪B可數(shù)。定理3-18：若A、B都是可數(shù)集，A∩B＝Φ，則A∪B可數(shù)。定理3-17：若A是可數(shù)集，B是可數(shù)集或有限集，則A∪B是可數(shù)集。定理3-21：可數(shù)個(gè)互不相交的可數(shù)集的并集仍是可數(shù)集。第十五頁，共十八頁，2022年，8月28日(二)不可數(shù)集不是所有的無限集都是可數(shù)的定理3-23：集合R1＝{x|0＜x＜1}是不可數(shù)集。定義3-12：如果有從R1(0,1)到集合A的雙射函數(shù)，那么＃A＝§1。例4：[0，1]的基數(shù)為§1。解：定義A＝{1/2,1/3,1/4,....,1/n,....}做f:(0,1)[0,1]f(1/2)=0f(1/3)=1f(1/n)=1/(n-2)f(x)=xx∈(0,1)-A顯然f是雙射所以，＃[0,1]=§1第十六頁，共十八頁，2022年，8月28日(三)基數(shù)的比較我們知道，如果A和B是有限集⑴如果存在一個(gè)從A到B的雙射，那么＃A＝＃B⑵如果存在一個(gè)從A到B的內(nèi)射，那么＃A≤＃B⑶如果存在一個(gè)從A到B的內(nèi)射，但不存在雙射，那么＃A＜＃B現(xiàn)在把函數(shù)和基數(shù)之間的這些關(guān)系推廣到任意集合。

定義3-13：設(shè)A和B是任意的集合⑴如果有一個(gè)從A到B的雙射，那么稱A和B有相同的基數(shù)(或稱等勢(shì))，記為A～B或＃A＝＃B。⑵如果有一個(gè)內(nèi)射f：A