數(shù)理邏輯-第三章-數(shù)學(xué)推理-數(shù)學(xué)歸納法

1、數(shù)理邏輯Mathematical Logic 第三章 數(shù)學(xué)推理Chapter 3 Mathematical Reasoning復(fù)習(xí)直接證明間接證明空證明平凡證明歸謬證明分情形證明qppqp為假q為真p(rr)(p1p2pn)q(p1q)(p2q)(pnq)特殊情形復(fù)習(xí)證明n個(gè)命題等價(jià)p1p2 pn (p1p2)(p2p3)(pnp1)xP(x)構(gòu)造性存在性證明非構(gòu)造性存在性證明如何證明xP(x)為假？復(fù)習(xí)新澤西的每個(gè)人都生活在距離海洋50英里之內(nèi)；新澤西的某個(gè)人從來沒見過海洋。因此，生活在距離海洋50英里之內(nèi)的某個(gè)人從來沒見過海洋。N(x):x是新澤西人；L(x):x生活在距離海洋50英里以內(nèi)

2、；S(x):x見過海洋。x(N(x)L(x);x(N(x)S(x)x(L(x)S(x)復(fù)習(xí)證明：若n是正整數(shù)，則n是偶數(shù)當(dāng)且僅當(dāng)7n+4是偶數(shù)p：n是偶數(shù)q：7n+4是偶數(shù)pq（直接證明）qp（間接證明）3.2 數(shù)學(xué)歸納法Mathematical Induction一、引言前n個(gè)正奇數(shù)之和的公式是什么？對(duì)n=1,2,3,4,5來說，前n個(gè)正奇數(shù)之和為：1=1，1+3=4，1+3+5=9，1+3+5+7=16，1+3+5+7+9=25猜測(cè)前n個(gè)正奇數(shù)之和是n2假如這個(gè)猜測(cè)是正確的，我們就需要一種方法來證明數(shù)學(xué)歸納法就是證明這種類型的斷言的極為重要的證明技術(shù)如何使用數(shù)學(xué)歸納法為什么它是有效的證明技

3、術(shù)注意：數(shù)學(xué)歸納法只能證明通過其它方式獲得的結(jié)果它不是發(fā)現(xiàn)公式或公理的工具一、引言二、良序性數(shù)學(xué)歸納法的有效性來源于如下關(guān)于整數(shù)集的基本公理：良序性每個(gè)非空的非負(fù)整數(shù)集都有最小元例：用良序性證明除法算法。若a是整數(shù)而且d是正整數(shù)，則存在唯一的整數(shù)q和r，滿足0rd和a=dq+r例：用良序性證明除法算法。設(shè)S是形如a-dq的非負(fù)整數(shù)的集合，其中q是整數(shù)這個(gè)集合非空，因?yàn)?dq可以任意大（取q是絕對(duì)值很大的負(fù)整數(shù)）根據(jù)良序性，S有最小元r=a-dq0。整數(shù)r非負(fù)，而且rd假設(shè)rd，那么令r1=a-d(q0+1)=a-dq0-d=r-d0二、良序性例：用良序性證明除法算法。那么r1是S中比r更小的非

4、負(fù)整數(shù)推出了矛盾所以，r0，并且rd因此，存在滿足0rd的整數(shù)r和q下一步還需要證明q和r是唯一的。二、良序性三、數(shù)學(xué)歸納法許多定理說：對(duì)所有正整數(shù)n來說P(n)為真1+2+3+n=n(n+1)/2n2nnP(n)數(shù)學(xué)歸納法證明對(duì)每個(gè)正整數(shù)n來說P(n)為真，包含如下兩個(gè)步驟：基礎(chǔ)步驟：P(1)為真歸納步驟：對(duì)每個(gè)正整數(shù)來說 P(n)P(n+1)為真對(duì)固定的正整數(shù)n來說，命題P(n)稱為歸納假設(shè)當(dāng)完成了如上兩個(gè)步驟時(shí)，就證明了對(duì)所有正整數(shù)n來說P(n)為真三、數(shù)學(xué)歸納法把這種證明技術(shù)表示成推理規(guī)則就是p(1)n(P(n)P(n+1) nP(n)證明對(duì)所有正整數(shù)來說P(n)為真首先證明P(1)為

5、真然后證明對(duì)每個(gè)正整數(shù)n來說都有P(n)P(n+1)為真假設(shè)P(n)為真，證明在此假設(shè)下P(n+1)也必然為真三、數(shù)學(xué)歸納法注意：不假定對(duì)所有正整數(shù)來說P(n)為真，只是證明了：若假定P(n)為真，則P(n+1)也為真因此，數(shù)學(xué)歸納法不屬于循環(huán)論證三、數(shù)學(xué)歸納法用數(shù)學(xué)歸納法證明定理時(shí)首先證明P(1)為真，然后知道P(2)為真，因?yàn)镻(1)蘊(yùn)含P(2)P(3)為真，因?yàn)镻(2)蘊(yùn)含P(3)以這樣的方式繼續(xù)下去，就可以看出對(duì)任意正整數(shù)k來說P(k)為真數(shù)學(xué)歸納法的形象解釋三、數(shù)學(xué)歸納法為什么數(shù)學(xué)歸納法是有效的？假定知道P(1)為真，而且對(duì)所有正整數(shù)n來說P(n)P(n+1)為真為了證明對(duì)所有正整數(shù)

6、來說P(n)為真，假定至少存在一個(gè)使P(n)為假的正整數(shù)那么使P(n)為假的正整數(shù)集合S非空根據(jù)良序性，S有一個(gè)最小元，把它表示為k三、數(shù)學(xué)歸納法為什么數(shù)學(xué)歸納法是有效的？可以知道k不是1，因?yàn)镻(1)為真因?yàn)閗是正的，并且大于1，所以k-1是一個(gè)正整數(shù)因?yàn)閗-1小于k，所以它不屬于S所以P(k-1)必然為真因?yàn)镻(k-1)P(k)為真，所以P(k)為真這與對(duì)k的選擇相矛盾三、數(shù)學(xué)歸納法四、數(shù)學(xué)歸納法的例子例：用數(shù)學(xué)歸納法證明：前n個(gè)正奇數(shù)之和是n2解：設(shè)P(n)表示命題：前n個(gè)正奇數(shù)之和是n2必須首先完成基礎(chǔ)步驟：P(1)為真然后必須完成歸納步驟：必須證明當(dāng)假定P(n)為真時(shí)P(n+1)為真

7、基礎(chǔ)步驟：P(1):前1個(gè)正奇數(shù)之和是12，這是真的，因?yàn)榈谝粋€(gè)正奇數(shù)是1例：用數(shù)學(xué)歸納法證明：前n個(gè)正奇數(shù)之和是n2歸納步驟：為了完成歸納步驟，必須證明對(duì)每個(gè)正整數(shù)n來說命題P(n)P(n+1)為真，為了證明這一點(diǎn)，假定對(duì)正整數(shù)n來說P(n)為真，即： 1+3+5+(2n-1)=n2必須證明假定P(n)為真，則P(n+1)為真四、數(shù)學(xué)歸納法的例子例：用數(shù)學(xué)歸納法證明：前n個(gè)正奇數(shù)之和是n2P(n+1)是命題 1+3+5+(2n-1)+(2n+1)=(n+1)2所以假定P(n)為真，得出 1+3+5+(2n-1)+(2n+1)=(1+3+5+(2n-1)+(2n+1)=n2+2n+1=(n+1

8、)2四、數(shù)學(xué)歸納法的例子例：用數(shù)學(xué)歸納法證明：前n個(gè)正奇數(shù)之和是n2這樣就證明了從P(n)得出P(n+1)在第二個(gè)等式中我們使用了歸納假設(shè)P(n)因?yàn)镻(1)為真，而且對(duì)所有正整數(shù)n來說P(n)P(n+1)為真，所以，由數(shù)學(xué)歸納法原理就證明了對(duì)所有正整數(shù)n來說P(n)為真四、數(shù)學(xué)歸納法的例子例：用數(shù)學(xué)歸納法證明：對(duì)所有正整數(shù)n來說不等式n2n解：設(shè)P(n)是命題“n2n”?；A(chǔ)步驟：P(1)為真，因?yàn)?21=2歸納步驟：假定對(duì)正整數(shù)n來說P(n)為真，即假定n2n，需要證明P(n+1)為真，即需要證明n+12(n+1)。四、數(shù)學(xué)歸納法的例子例：用數(shù)學(xué)歸納法證明：對(duì)所有正整數(shù)n來說不等式n2n解

9、：對(duì)n2n兩邊加1，n+12n+1，又因?yàn)?2n，所以 n+12n+12n+2n=2n+1因此，在P(n)為真的假定的基礎(chǔ)上，已經(jīng)證明了P(n+1)為真。歸納步驟完畢。四、數(shù)學(xué)歸納法的例子例：用數(shù)學(xué)歸納法證明：每當(dāng)n是正整數(shù)時(shí)，n3-n就被3整除解：設(shè)P(n)是命題“n3-n被3整除”；基礎(chǔ)步驟：P(1)為真歸納步驟：假定P(n)為真: n3-n被3整除，必須證明P(n+1)為真 (n+1)3-(n+1)=(n3+3n2+3n+1)-(n+1) =(n3-n)+3(n2+n)四、數(shù)學(xué)歸納法的例子如何證明對(duì)n=k,k+1,k+2,來說P(n)為真，其中k是不等于1的整數(shù)？只需改變基礎(chǔ)步驟證明P(

10、k)為真例：用數(shù)學(xué)歸納法證明：對(duì)所有非負(fù)整數(shù)來說 1+2+22+2n=2n+1-1四、數(shù)學(xué)歸納法的例子解：設(shè)P(n)是命題：對(duì)非負(fù)整數(shù)n來說上述公式成立基礎(chǔ)步驟：P(0)為真，因?yàn)?0=1=21-1歸納步驟：假定P(n)為真，必須證明P(n+1)為真，即：1+2+22+2n+2n+1=2(n+1)+1-1=2n+2-1使用歸納假設(shè)P(n)，得出：1+2+22+2n+2n+1=2n+1-1+2n+1=2n+2-1歸納步驟完成，證畢。四、數(shù)學(xué)歸納法的例子在證明對(duì)n=k,k+1,k+2,來說P(n)為真時(shí)，k可以是負(fù)的、零或正的想象多米諾骨牌的比喻，現(xiàn)在首先撞到的是第k張骨牌（基礎(chǔ)步驟），當(dāng)每張骨牌

11、倒下時(shí)，它就撞到下一張骨牌（歸納步驟）。四、數(shù)學(xué)歸納法的例子例：幾何級(jí)數(shù)求和幾何級(jí)數(shù)是形如a,ar,ar2,arn,的序列，其中a和r是實(shí)數(shù)上例就是一種特殊情形，其中a=1和r=2用數(shù)學(xué)歸納法證明幾何級(jí)數(shù)有窮多項(xiàng)之和的下列公式：當(dāng)r1時(shí)四、數(shù)學(xué)歸納法的例子例：調(diào)和數(shù)不等式用數(shù)學(xué)歸納法證明：每當(dāng)n是非負(fù)整數(shù)時(shí)就有H2n1+n/2例8-例11（P186）四、數(shù)學(xué)歸納法的例子例：設(shè)n是正整數(shù)。證明：可以用L形狀的碎片來鋪滿去掉1個(gè)格子的任何2n2n棋盤，其中這些碎片一次覆蓋3個(gè)格子。解：設(shè)P(n)是命題：可以用L形狀的碎片來鋪滿去掉1個(gè)格子的任何2n2n棋盤四、數(shù)學(xué)歸納法的例子基礎(chǔ)步驟：命題P(1)

12、為真，因?yàn)榭梢杂?個(gè)L形狀的碎片來鋪滿去掉1個(gè)格子的任何22棋盤，如下圖：四、數(shù)學(xué)歸納法的例子歸納步驟：假定P(n)為真，必須證明在這個(gè)假定之下P(n+1)也必然為真為了證明這一點(diǎn)，我們考慮去掉1個(gè)格子的2n+12n+1棋盤，將這個(gè)棋盤分成4個(gè)2n2n棋盤，如下圖四、數(shù)學(xué)歸納法的例子根據(jù)歸納假設(shè)，可以用L形狀的碎片來覆蓋第4個(gè)2n2n棋盤現(xiàn)在去掉另外三個(gè)2n2n棋盤的一角上的格子，如下圖四、數(shù)學(xué)歸納法的例子根據(jù)歸納假設(shè)，可以用L形狀的碎片來覆蓋這3個(gè)2n2n棋盤另外可以用1個(gè)L形狀的碎片來鋪滿這3個(gè)臨時(shí)去掉的格子因此，可以用L形狀碎片來鋪滿整個(gè)去掉1個(gè)格子的2n+12n+1棋盤歸納步驟完成，證

13、畢。四、數(shù)學(xué)歸納法的例子五、數(shù)學(xué)歸納法的第二原理假定對(duì)k=1,2,n來說P(k)為真，證明在這個(gè)假定的基礎(chǔ)之上P(n+1)也必然為真（第二數(shù)學(xué)歸納法）證明對(duì)所有正整數(shù)n來說P(n)為真的兩個(gè)步驟：基礎(chǔ)步驟：證明P(1)為真歸納步驟：證明對(duì)每個(gè)正整數(shù)n來說，P(1)P(2)P(n)P(n+1)為真例：證明：若n是大于1的整數(shù)，則n可以寫成素?cái)?shù)之積解：設(shè)P(n)：n可以寫成素?cái)?shù)之積基礎(chǔ)步驟：P(2)為真，因?yàn)镻(2)可以寫成一個(gè)素?cái)?shù)之積，即它自身歸納步驟：假定對(duì)所有滿足kn的正整數(shù)k來說P(k)為真，要完成歸納步驟就必須證明在這個(gè)假定下P(n+1)為真五、數(shù)學(xué)歸納法的第二原理例：證明：若n是大于1

14、的整數(shù)，則n可以寫成素?cái)?shù)之積解：分兩種情況考慮：當(dāng)n+1是素?cái)?shù)時(shí)和當(dāng)n+1是合數(shù)時(shí)。若n+1是素?cái)?shù)，則P(n+1)為真；若n+1是合數(shù)，則可以將其表示成兩個(gè)整數(shù)a和b之積，其中a、b滿足2abn+1根據(jù)歸納假設(shè)，a和b可以寫成素?cái)?shù)之積五、數(shù)學(xué)歸納法的第二原理例：證明：若n是大于1的整數(shù)，則n可以寫成素?cái)?shù)之積解：因此，若n+1是合數(shù)，則它可以寫成素?cái)?shù)之積歸納步驟完成證畢。五、數(shù)學(xué)歸納法的第二原理例：證明：可以僅用4分和5分的郵票來組成等于或超過12分的每種郵票解：設(shè)P(n)是命題：可以用4分和5分的郵票來組成n分郵資第一數(shù)學(xué)歸納法基礎(chǔ)步驟：P(12)為真，因?yàn)榭梢杂?個(gè)4分郵票組成12分郵資五、

15、數(shù)學(xué)歸納法的第二原理例：證明：可以僅用4分和5分的郵票來組成等于或超過12分的每種郵票歸納步驟：假定P(n)為真，即：可以用4分和5分郵票組成n分郵資證明在該假定下，P(n+1)為真假設(shè)在組成n分郵資的時(shí)候用到了至少1個(gè)4分郵票，則可以用1個(gè)5分郵票代替它，就組成了n+1分郵資五、數(shù)學(xué)歸納法的第二原理例：證明：可以僅用4分和5分的郵票來組成等于或超過12分的每種郵票假設(shè)在組成n分郵資的時(shí)候沒有用到4分郵票，由于n12，所以至少用了3個(gè)5分郵票，所有用4個(gè)4分郵票替代3個(gè)5分郵票，就組成了n+1分郵資歸納步驟完成，證畢。五、數(shù)學(xué)歸納法的第二原理例：證明：可以僅用4分和5分的郵票來組成等于或超過12分的每種郵票第二數(shù)學(xué)歸納法基礎(chǔ)步驟：證明P(12)、P(13)、P(14)、P(15)都為真歸納步驟：假定對(duì)所有滿足12kn的正整數(shù)P(k)為真(n15)，為了證明P(n+1)成立，可以用組成n-3分郵資的郵票加上1個(gè)4分郵票。歸納步驟完成，證畢。五、數(shù)學(xué)歸納法的第二原理注意：為了證明對(duì)n=k,k+1,來說P(n)為真，其中k是整數(shù)首先證明P(