資源描述：
《定理（二）設(shè)S是自然數(shù)集N的非空子集,如果0S,且.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在PPT專區(qū)-天天文庫(kù)。
1、定理(二)：設(shè)S是自然數(shù)集N的非空子集，如果0?S，且當(dāng)n?S時(shí)，必有n+1?S，則S=N。定理(三)：設(shè)S是自然數(shù)集N的非空子集，如果0?S，且當(dāng)0,1,2,?n?S時(shí)，必有n+1?S，則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é)論也成立。(2)第二數(shù)學(xué)歸納法要證一個(gè)結(jié)論對(duì)所有自然數(shù)都真，只須做兩件事：①當(dāng)n=0時(shí)，結(jié)論成立。②若當(dāng)n?k結(jié)論成立，則當(dāng)n=k+1結(jié)論也成立定理(四)：設(shè)P(n)是一個(gè)
2、與自然數(shù)n有關(guān)的結(jié)論。若對(duì)于自然數(shù)0，結(jié)論成立；并且當(dāng)對(duì)自然數(shù)k結(jié)論成立時(shí)，對(duì)于自然數(shù)k+1結(jié)論也成立，則該結(jié)論對(duì)所有自然數(shù)都成立。定理(五)：設(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ù)都成立。二、集合的遞歸定義定義4.1:集合A的遞歸(歸納)定義由三部分組成:(1)基礎(chǔ):設(shè)置某些對(duì)象是在所要定義的集合A中的(2)歸納(遞歸):建立一種由集合A的現(xiàn)有元素產(chǎn)生A中新元素的方法。(3)閉合：除了有限次應(yīng)用(1)和
3、(2)產(chǎn)生集合A的元素外,A中再?zèng)]有其它元素。例：設(shè)整數(shù)集Z是全集,非負(fù)偶整數(shù)集E+={x
4、x≧0,且x=2y,y?Z},它可以遞歸定義如下:(1)(基礎(chǔ))0?E+。(2)(歸納)如果n?E+,則n+2?E+。(3)(閉合)除有限次應(yīng)用(1)和(2)產(chǎn)生的整數(shù)外,再?zèng)]有其它的整數(shù)在E+中。例：下面的歸納定義所給出的是怎樣的集合？(1)(基礎(chǔ))3?S。(2)(歸納)如果x,y?S,則x+y?S。(3)(閉合)除有限次應(yīng)用(1)和(2)產(chǎn)生的整數(shù)外,再?zèng)]有其它的整數(shù)在S中。3的正整數(shù)倍全體。設(shè)Σ是一個(gè)有限非空字符集,稱為字
5、母表。從Σ中選取有限個(gè)字符組成的串稱為Σ上的字符串或字。設(shè)x是Σ上的一個(gè)字,x=a1a2…an,其中ai?Σ,1≦i≦n,n是正整數(shù),表示字的長(zhǎng)度。長(zhǎng)度為0的字稱為空串,記為?。若x,y是Σ上的兩個(gè)字,x=a1a2…an,y=b1b2…bm,其中ai,bj?Σ(1≦i≦n,1≦j≦m),則由x和y毗連得到新的字記為xy。即:xy=a1a2…anb1b2…bm。例:設(shè)Σ是一個(gè)字母表,Σ上所有的有限非空字符串集合記為Σ+,遞歸定義如下:(1)(基礎(chǔ))如果a?Σ,則a?Σ+。(2)(歸納)如果x?Σ+,且a?Σ,則ax?Σ+
6、(ax表示字符a與字x毗連得到的新的字。(3)(閉合)除有限次應(yīng)用(1)和(2)產(chǎn)生Σ+中的字外,Σ+中再?zèng)]有其它字。集合Σ+包含長(zhǎng)度為1,2,3,…的字,即Σ+包含無(wú)限個(gè)字,但每個(gè)字的字符個(gè)數(shù)是有限的。例:設(shè)Σ是一個(gè)字母表,Σ上所有的有限字符串集合記為Σ*,Σ*包含空串，即Σ*=Σ+∪{?},可遞歸定義如下:(1)(基礎(chǔ))??Σ*。(2)(歸納)如果x?Σ*,且a?Σ,則ax?Σ*。(3)(閉合)除有限次應(yīng)用(1)和(2)產(chǎn)生Σ*中的字外,Σ*中再?zèng)]有其它字。例如,若Σ={0,1},則Σ*={?,0,1,00,01,
7、10,11,000,001…},是有限二進(jìn)制序列的集合,其中包含空序列。算術(shù)表達(dá)式集合是包含整數(shù),一元運(yùn)算符+,-,以及二元運(yùn)算符+,-,*,/的符號(hào)序列所組成的集合,((3+5)/4),(((-5)+6)*3)算術(shù)表達(dá)式集合的遞歸定義如下:(1)(基礎(chǔ))如果D={0,1,2,3,4,5,6,7,8,9}和x?D+,則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)是算術(shù)表
8、達(dá)式;(x/y)是算術(shù)表達(dá)式。(3)(閉合)一個(gè)符號(hào)序列是一個(gè)算術(shù)表達(dá)式當(dāng)且僅當(dāng)它能通過(guò)有限次應(yīng)用(1)和(2)而得到。后繼集合的概念:設(shè)A是任一給定集合,A∪{A}稱為A的后繼集合,簡(jiǎn)稱后繼,記為A+。定義4.2:設(shè)N為自然數(shù)集,它的遞歸定義如下:(1)(基礎(chǔ))??N。(2)(歸納)如果n?N,則n+?N(這里n+=n∪{n})。(3)(閉合)如果S?N,且S滿足(1)、(2)則S=N。自然數(shù)集的元素為:?,?+,(?+)+,((?+)+)+,…,即為:?,?∪{?},?∪{?}∪{?∪{?}}…可以簡(jiǎn)化為:?,{?
9、},{?,{?}},…用記號(hào):=給這些集合命名例如?命名為0,記為0:=?0:=?;1:=0+={?}={0};2:=1+={?,{?}}={0,1};3:=2+={?,{?},{?,{?}}}={0,1,2}…若已給出n,則n+1:=n+={0,1,2,…,n}定理4.1:(1)0不是任何自然數(shù)的后繼。(2)任何自然數(shù)的后繼是唯
