復(fù)旦大學(xué)計(jì)算機(jī)院趙一鳴離散數(shù)學(xué)中文課件

1、定理(二)：設(shè)S是自然數(shù)集N的非空子集，如果0S，且當(dāng)nSn+1S，則S=N。定理(三)：設(shè)S是自然數(shù)集N的非空子集，如果0S，且當(dāng)0,1,2,nSn+1S，則S=N。數(shù)學(xué)歸納法，有兩種形式：(1)第一數(shù)學(xué)歸納法要證一個(gè)結(jié)論對(duì)所有自然數(shù)都真，只須做兩件事：1)當(dāng)n=0時(shí)，結(jié)論成立。2)若當(dāng)n=k結(jié)論成立，則當(dāng)n=k+1結(jié)論也成立。1(2)第二數(shù)學(xué)歸納法要證一個(gè)結(jié)論對(duì)所有自然數(shù)都真，只須做兩件事：當(dāng)n=0時(shí)，結(jié)論成立。若當(dāng)nk結(jié)論成立，則當(dāng)n=k+1結(jié)論也成立定理(四)：設(shè)P(n)是一個(gè)與自然數(shù)n有關(guān)的結(jié)論。若對(duì)于自然數(shù)0，結(jié)論成立；并且當(dāng)對(duì)自然數(shù)k結(jié)論成立時(shí)，對(duì)于自然數(shù)k+1結(jié)論也成立，則該結(jié)

2、論對(duì)所有自然數(shù)都成立。2定理(五)：設(shè)P(n)是一個(gè)與自然數(shù)n有關(guān)的結(jié)論。若對(duì)于自然數(shù)0，結(jié)論成立；并且當(dāng)對(duì)自然數(shù)0,1,2,k結(jié)論成立時(shí)，對(duì)于自然數(shù)k+1結(jié)論也成立，則該結(jié)論對(duì)所有自然數(shù)都成立。3二、集合的遞歸定義定義4.1:集合A的遞歸(歸納)定義由三部分組成: (1)基礎(chǔ):設(shè)置某些對(duì)象是在所要定義的集合A中的 (2)歸納(遞歸):建立一種由集合A的現(xiàn)有元素產(chǎn)生A中新元素的方法。 (3)閉合：除了有限次應(yīng)用(1)和(2)產(chǎn)生集合A的元素外,A中再?zèng)]有其它元素。4例：設(shè)整數(shù)集Z是全集,非負(fù)偶整數(shù)集E+=x|x0,且x=2y,yZ,它可以遞歸定義如下:(1)(基礎(chǔ))0E+。(2)(歸納)如果n

3、E+,則n+2E+。(3)(閉合)除有限次應(yīng)用(1)和(2)產(chǎn)生的整數(shù)外,再?zèng)]有其它的整數(shù)在E+中。例：下面的歸納定義所給出的是怎樣的集合？ (1)(基礎(chǔ))3S。(2)(歸納)如果x,yS,則x+yS。(3)(閉合)除有限次應(yīng)用(1)和(2)產(chǎn)生的整數(shù)外,再?zèng)]有其它的整數(shù)在S中。 3的正整數(shù)倍全體。5設(shè)是一個(gè)有限非空字符集,稱為字母表。從中選取有限個(gè)字符組成的串稱為上的字符串或字。設(shè)x是上的一個(gè)字, x=a1a2an,其中ai,1in,n是正整數(shù),表示字的長度。長度為0的字稱為空串,記為。若x,y是上的兩個(gè)字,x=a1a2an, y=b1b2bm,其中ai,bj(1in, 1jm),則由x和y

4、毗連得到新的字記為xy。即:xy=a1a2an b1b2bm。6例:設(shè)是一個(gè)字母表, 上所有的有限非空字符串集合記為+,遞歸定義如下:(1)(基礎(chǔ))如果a,則a+。(2)(歸納)如果x+,且a,則ax+(ax表示字符a與字x毗連得到的新的字。(3)(閉合)除有限次應(yīng)用(1)和(2)產(chǎn)生+中的字外, +中再?zèng)]有其它字。集合+包含長度為1,2,3,的字,即+包含無限個(gè)字, 但每個(gè)字的字符個(gè)數(shù)是有限的。7例:設(shè)是一個(gè)字母表, 上所有的有限字符串集合記為*,*包含空串，即*=+,可遞歸定義如下:(1)(基礎(chǔ))*。(2)(歸納)如果x*,且a,則ax*。(3)(閉合)除有限次應(yīng)用(1)和(2)產(chǎn)生*中的

5、字外, *中再?zèng)]有其它字。例如,若=0,1, 則*=,0,1,00,01, 10,11,000,001,是有限二進(jìn)制序列的集合, 其中包含空序列。8算術(shù)表達(dá)式集合是包含整數(shù), 一元運(yùn)算符+,-, 以及二元運(yùn)算符+,-,* ,/的符號(hào)序列所組成的集合, (3+5)/4),(-5)+6)*3)9算術(shù)表達(dá)式集合的遞歸定義如下:(1)(基礎(chǔ))如果D=0,1,2,3,4,5,6,7,8,9和xD+ ,則x是算術(shù)表達(dá)式。其中D+是D上所有非空數(shù)字串的集合。(2)(歸納)如果x和y都是算術(shù)表達(dá)式, 則(+x)是算術(shù)表達(dá)式; (-x)是算術(shù)表達(dá)式;(x+y)是算術(shù)表達(dá)式; (x-y)是算術(shù)表達(dá)式;(x*y)是

6、算術(shù)表達(dá)式; (x/y)是算術(shù)表達(dá)式。 (3)(閉合)一個(gè)符號(hào)序列是一個(gè)算術(shù)表達(dá)式當(dāng)且僅當(dāng)它能通過有限次應(yīng)用(1)和(2)而得到。10后繼集合的概念: 設(shè)A是任一給定集合,AA稱為A的后繼集合, 簡稱后繼, 記為A+。定義4.2:設(shè)N為自然數(shù)集, 它的遞歸定義如下:(1)(基礎(chǔ))N。(2)(歸納)如果nN, 則n+N(這里n+=nn)。(3)(閉合)如果SN,且S滿足(1)、(2)則S=N。11自然數(shù)集的元素為: ,+,(+)+,(+)+)+,即為: ,可以簡化為: ,用記號(hào):=給這些集合命名例如命名為0,記為0:=0:=; 1:=0+=0; 2:=1+=,=0,1; 3:=2+=,=0,1,

7、2 若已給出n, 則n+1:=n+=0,1,2,n12定理4.1:(1)0不是任何自然數(shù)的后繼。(2)任何自然數(shù)的后繼是唯一的。(3)如果n+=m+,則n=m。貝安諾(Peano)公理(1)0N;(2)對(duì)每一個(gè)nN,恰存在一個(gè)n+N(稱n+為n的后繼);(3)不存在一個(gè)nN,使n+=0;(4)如果n+=m+, 則n=m;(5)如果SN,且0S;如果nS,有n+S, 則S=N。134.2 基數(shù)一、基數(shù)概念在棋盤的第一個(gè)方格內(nèi)放一粒米，以后每一小格內(nèi)都比前一小格加一倍，最后擺滿所有64格1+2+22+263=264-1約合140億升所有整數(shù)的個(gè)數(shù)，一條線上所有幾何點(diǎn)個(gè)數(shù)(即區(qū)間a,b上 個(gè)數(shù))14

8、比較一堆珠子和一堆銅幣哪個(gè)多，把珠子和銅幣逐個(gè)比較，最后看哪堆有多余，若同時(shí)沒有則兩者相同。定義4.3：設(shè)A,B是任意兩個(gè)集合,若存在一個(gè)雙射f:AB,則稱A和B對(duì)等(或等勢),記為 AB;或稱A和B的基數(shù)相同。A的基數(shù)記為|A|;A和B的基數(shù)相同記為|A|=|B|15二、無限集定義4.4：設(shè)A為一個(gè)集合, 若A為空集或與集合0,1,2,n-1的基數(shù)相同, 則稱A為有限集,且|A|=nN。若集合A不是有限集, 則稱A為無限集。定理4.2:自然數(shù)集N是無限集。沒有一個(gè)自然數(shù)能作為N的基數(shù),因此今后將記|N|為0,讀作阿列夫零。 16定理4.2:自然數(shù)集N是無限集。即證明N不是有限集.關(guān)鍵證明對(duì)任

9、何nN，不存在從0,1,2,n-1到N的雙射。證明：設(shè)n是N中任一元素，f是從0,1,2,n-1到N的任一函數(shù)，沒有一個(gè)自然數(shù)能作為N的基數(shù),因此今后我們將記|N|為0,讀作阿列夫零。 17例:設(shè)N與Z之間有如下一一對(duì)應(yīng):N: 0,1, 2,3, 4,5, 6,Z: 0,1,-1,2,-2,3,-3,即存在雙射f:NZ,使對(duì)nN,所以|Z|=0。18例:設(shè)E=0,2,4, 因?yàn)榇嬖趂: NE,對(duì)任何nN有f(n)=2n , 顯然f是NE的雙射。這里E是N的真子集,然而|E|=|N|=0。這一事實(shí)揭示了無限集的一個(gè)重要特征:即無限集可以與它的一個(gè)真子集對(duì)等。19定理4.3:無限集必與它的一個(gè)真子

10、集對(duì)等。證明：基本思路A是構(gòu)造一個(gè)真子集,然后證明兩者之間存在雙射推論:凡不能與自身的任一真子集對(duì)等的集合為有限集。凡能與自身的某一真子集對(duì)等的集合稱為無限集,否則稱為有限集。前面的例子和定理說明了這樣的事實(shí)：在無窮大的世界里，部分可能等于全部。那么是否無窮大數(shù)都是相等的？204.3 可列集與不可列集定義4.5：若存在從N到A的雙射, 則稱A為可列無限集, 簡稱可列集或可數(shù)集, |A|=0。定理(一)：設(shè)A是可列集, 若存在從A到B的雙射,則B也是可列集。目標(biāo)證明存在N到A的雙射.21定理(二)：集合A是可列集的充要條件是集合A中的元素可以排成一個(gè)無窮序列的形式:a0,a1,a2,a3,a4,。利用自然數(shù)有序性目標(biāo)證明存在N到A的雙射。定理4.4：任何無限集必含有一個(gè)可列子集。采用構(gòu)造方法,從無限集中構(gòu)造一個(gè)無窮序列22定理4.5：可列集的任何無限子集必為可列集。定理4.6：可列集中加入有限個(gè)元素(或刪去有限個(gè)元素), 仍為可列集。23作業(yè):P76 1,補(bǔ)充:證明定理(五)：設(shè)P(n)是一個(gè)與自