推理與證明方法

1、5/6/202213 數(shù)學(xué)推理數(shù)學(xué)推理 Mathematical Reasoning 3.1 推理與證明方法推理與證明方法 Reasoning and Methods of Proof 3.2 數(shù)學(xué)歸納方法數(shù)學(xué)歸納方法 3.3 遞推方法遞推方法5/6/20222定理定理/Theorem: 一個真值為一個真值為T的命題語句。的命題語句。證明證明/Proof：用論證方式形成的一個命題語句序列說明：用論證方式形成的一個命題語句序列說明一個定理為一個定理為T。證明的構(gòu)造證明的構(gòu)造/形式：由兩個部分組成形式：由兩個部分組成 1、公理、假定或前提公理、假定或前提/axiom、postulate、hypot

2、heses 2、推理規(guī)則推理規(guī)則/rule of inference其它：其它：引理引理/lemma、推論推論/corollary、猜想猜想/conjecture5/6/20223蘊涵演算蘊涵演算/logical implying operation 對于任意的公式對于任意的公式P和和Q，如果，如果P Q 為為T，則稱，則稱P蘊涵蘊涵Q， 記為記為P Q 或或P/Q蘊涵演算的推廣表示：蘊涵演算的推廣表示： P1、 P2 、 、Pn Q 前提組前提組/hypotheses 結(jié)論結(jié)論/conclusion證明的基本工具：等值演算，真值表，范式，引用已知簡單結(jié)論證明的基本工具：等值演算，真值表，范式

3、，引用已知簡單結(jié)論下表是一些常用的簡單結(jié)論下表是一些常用的簡單結(jié)論5/6/20224Rule of Inference NameP P QAddition/析取附加式析取附加式P Q P Simplification/合取化簡式合取化簡式P、Q P Q Conjunction/并發(fā)式并發(fā)式P、 P Q QModus ponens/分離式分離式 Q、 P Q PModus tollens/拒取式拒取式 p、P Q QDisjunctive syllogism/析取三段式析取三段式P Q、 Q R P R Hypothetical syllogism/假言三段式假言三段式5/6/20225Hypo

4、theses: (1) It is not sunny this afternoon and it is colder than yesterday. (2) We will go swimming only if it is sunny. (3) If we dont go swimming, then we will take a canoe trip. (4) If we take a canoe trip, then we will be home by sunset. Conclusion: We will be home by sunset. P: It is sunny this

5、 afternoon.Q: It is colder than yesterday.R: We will go swimming.S: We will take a canoe trip. T: We will be home by sunset. 5/6/20226The hypotheses become P Q ,R P, R S, and S T, The conclusion is Tn P Q (h) 7. S T (h)n P (s) 8.T nR P (h)n R (m)n R S (h)nS (m)5/6/20227Rule of InferenceName x P(x) P

6、(c) if c UUI/全稱舉例全稱舉例P(c) for an arbitrary c U x P(x) UG/全稱推廣全稱推廣 x P(x) P(c) for some c UEI/存在舉例存在舉例P(c) for some c U x P(x)EG/存在推廣存在推廣U:Universal I:InstantiationE: Existential G: Generalization5/6/20228蘇格拉底論證：蘇格拉底論證：人固有一死，蘇格拉底是人，因此蘇格拉底固有一死。人固有一死，蘇格拉底是人，因此蘇格拉底固有一死。P(x): x是人，是人，D(x):x是要死的，是要死的，S:蘇格拉

7、底。蘇格拉底。 x (P(x) D(x), P(S) D(S)1. x (P(x) D(x) (h) 3. P(S)2. P(s) D(s) (UG) 4. D(S)5/6/20229Hypotheses: 任何人如果他喜歡步行，則他就不喜歡乘任何人如果他喜歡步行，則他就不喜歡乘汽車；每個人喜歡乘汽車或者喜歡騎自行車；有的人不喜汽車；每個人喜歡乘汽車或者喜歡騎自行車；有的人不喜歡騎自行車，歡騎自行車，Conclusion: 因此有的人不喜歡步行。因此有的人不喜歡步行。W(x): 喜歡步行，喜歡步行，B(x):x喜歡乘汽車，喜歡乘汽車，K(x)：x喜歡騎自喜歡騎自行車；前提：行車；前提： x (

8、W(x) B(x)， x (B(x) K(x) ), x ( K(x), 結(jié)論：結(jié)論： x ( W(x)5/6/202210n x ( K(x) (h) 7. W(c) B(c) (UI)n K(c) (EI) 8. W(c)n x (B(x) K(x) ) (h) 9. x ( W(x) (EG)nB(c) K(c) (UI)nB(c) n x (W(x) B(x) (h)5/6/202211Hypotheses: P Q, P R, Q SConclusion: S RProof: P Q, P R, Q S S Rn (S R)（否定結(jié)論否定結(jié)論） 5. Q (3,4) 9. P Q (

9、5,8)n S R （DM） 6. R (2) 10. (P Q) (9)n S （ 化簡）化簡） 7. P R (h) 11. P Q (h)nQ S (h) 8. P (6,7) 12. F (11,12)5/6/202212定理證明方法：定理證明方法：1、直接證明、直接證明/direct proof: p Q 2、間接證明、間接證明/indirect proof : p Q Q P3、空證明、空證明/vacuous proof: p Q 其中其中 P為為 F4、平凡證明、平凡證明/trivial proof： p Q 其中其中 Q 為為T5/6/2022135、反證明、反證明/proof

10、 of contradiction： P P S S6、分例證明、分例證明/proof of cases： P1 P2 Pn Q （P1 Q） （P2 Q） （Pn Q） 5/6/2022147、存在證明、存在證明/existence proof： x P(x) constructive, nonconstructive8、歸納證明、歸納證明/induction proof ： x P(x) 5/6/202215進(jìn)一步的思考進(jìn)一步的思考 1、從等值演算到蘊涵演算、從等值演算到蘊涵演算 2、從命題公式的推理到謂詞公式的推理、從命題公式的推理到謂詞公式的推理 3、停機問題、停機問題/Halting

11、 Problem 5/6/202216練練 習(xí)習(xí) pp.183 4、16、43、685/6/2022173 數(shù)學(xué)推理數(shù)學(xué)推理 Mathematical Reasoning 3.1 推理與證明方法推理與證明方法 3.2 數(shù)學(xué)歸納方法數(shù)學(xué)歸納方法 Mathematical Induction 3.3 遞推方法遞推方法5/6/202218The well-ordering property(良序定理良序定理）Every nonempty set of nonnegative integers has a least element (非空的非負(fù)整數(shù)集合必有最小元）非空的非負(fù)整數(shù)集合必有最小元）5/6

12、/202219數(shù)學(xué)歸納法數(shù)學(xué)歸納法用來證明與用來證明與整數(shù)有關(guān)整數(shù)有關(guān)的命題。的命題。數(shù)學(xué)歸納法的公式表示：數(shù)學(xué)歸納法的公式表示：P(1) m(m 1 P(m) P(m+1) n P(n) 1、歸納基礎(chǔ)：、歸納基礎(chǔ)： P(1) 2、歸納步驟：、歸納步驟： m (m 1 P(m) P(m+1)數(shù)學(xué)歸納的理論基礎(chǔ)是數(shù)學(xué)歸納的理論基礎(chǔ)是整數(shù)公理整數(shù)公理，如下所示：，如下所示：5/6/202220（1）0N；（2）對每一個）對每一個nN，唯一定義了一個自然數(shù)，唯一定義了一個自然數(shù)n，n 稱為稱為n的后鄰；的后鄰；（3）不同的自然數(shù)，其后鄰也不同；）不同的自然數(shù)，其后鄰也不同；（4）沒有一個自然數(shù)的后鄰

13、是）沒有一個自然數(shù)的后鄰是0；（5）如果有一個子集）如果有一個子集M N滿足：滿足： 0M； nM時必時必n M, 則則M = N自然數(shù)全體自然數(shù)全體N通過皮亞諾公理的五條公理組成。通過皮亞諾公理的五條公理組成。 這些公理缺一不可，其中性質(zhì)（這些公理缺一不可，其中性質(zhì)（5）稱為歸納公理，并指出了自然數(shù)）稱為歸納公理，并指出了自然數(shù)是滿足公理（是滿足公理（1）（4）的最小集合。）的最小集合。 5/6/202221數(shù)學(xué)歸納法的一般公式表示：數(shù)學(xué)歸納法的一般公式表示：P(k) m(m k P(m) P(m+1) n P(n) 1、歸納基礎(chǔ)：、歸納基礎(chǔ)： P(k) 2、歸納步驟：、歸納步驟： m (m

14、 k P(m) P(m+1)5/6/202222pp.191 example 5 1 + 2 + 22 + + 2n = 2n+1 - 1 數(shù)學(xué)歸納法的正確性可以用皮亞諾公理與良序數(shù)學(xué)歸納法的正確性可以用皮亞諾公理與良序定理來證明。定理來證明。5/6/202223第二數(shù)學(xué)歸納法：第二數(shù)學(xué)歸納法：P(n0) k ( k n0 P(n0) P(n0+1) P(k) P(k+1) n P(n) 1、歸納基礎(chǔ)：、歸納基礎(chǔ)： P(n0) 2、歸納步驟：、歸納步驟： k ( k n0 P(n0) P(n0+1) P(k) P(k+1) 5/6/202224證明：任意一個大于證明：任意一個大于1 的自然數(shù)或

15、為質(zhì)數(shù)，或的自然數(shù)或為質(zhì)數(shù)，或能表示為若干個質(zhì)數(shù)的乘積。能表示為若干個質(zhì)數(shù)的乘積。5/6/202225有限數(shù)學(xué)歸納法：對于有限數(shù)學(xué)歸納法：對于 n0 n nk 的的 P(n)有限數(shù)學(xué)歸納法的前推公式表示：有限數(shù)學(xué)歸納法的前推公式表示：P(n0) n(n0 n nk-1 P(n) P(n+1) n (n0 n nk P(n) 1、歸納基礎(chǔ)：、歸納基礎(chǔ)： P(n0) 2、歸納步驟：、歸納步驟： n(n0 n nk-1 P(n) P(n+1) 5/6/202226pp. 195 Example 11，12，145/6/2022273.3 遞歸方法遞歸方法 Recursive Definition5/

16、6/202228定義定義1如果一個對象部分地由自己所組成，或者如果一個對象部分地由自己所組成，或者按它自己定義，則稱為是按它自己定義，則稱為是遞歸遞歸的（的（Recursion）。）。f的定義域：非負(fù)整數(shù)集的定義域：非負(fù)整數(shù)集 1、遞歸基礎(chǔ)：、遞歸基礎(chǔ)： f(0) 2、遞歸步驟：、遞歸步驟： f(n)=g(f(k), k05/6/202230菲波那契數(shù)菲波那契數(shù)/FibonacciF(0) = 0，F(xiàn)(1) = 1F(n) = F (n1) + F (n2)n1由上述公式，我們得到：由上述公式，我們得到：F (2) = 1，F(xiàn) (3) = 2，F(xiàn) (4) = 3，F(xiàn) (5) = 5，F(xiàn) (6)

17、 = 8，利用菲波那契數(shù)可以推算出兔子繁衍規(guī)律。利用菲波那契數(shù)可以推算出兔子繁衍規(guī)律。 5/6/202231Example 6（ PP. 205 ），）， f3=2 , f4=3 2, (歸納基礎(chǔ)）歸納基礎(chǔ)） fn-1 n-3, fn n-2(n3) (歸納假設(shè)）歸納假設(shè)） fn+1=fn-1+fn n-2+ n-3= n-3(1+ )= n-3 2 = n-1 (歸納證明）歸納證明）5/6/202232利用利用 Fibonacci數(shù)列研究數(shù)列研究Euclid算法的計算復(fù)雜性。算法的計算復(fù)雜性。 a=r0,b=r1 ri=ri+1qi+1+ri+2 (0 ri+2 ri+1, 0 In-2)

18、rn-1=rnqn rn1 = f2, rn-12 rn 2f2=f3, 假設(shè)假設(shè)ri+1 fn+1-i ， ri+2 fn-i ri ri+1+ri+2 fn+1-i+fn-i = fn+2-i (0 i n-1 , 10b(n-1) 10 (n-1)/5 hence,n5 10b + 15/6/2022331、3 S2、X S Y S X + Y SS是能夠被是能夠被3 整除的正整數(shù)集合。整除的正整數(shù)集合。 5/6/202234Well-formed formulae 1、命題公式的定義、命題公式的定義 2、謂詞公式的定義、謂詞公式的定義 3、數(shù)集上的、數(shù)集上的 +，-，*，/， 數(shù)學(xué)表達(dá)式的定義數(shù)學(xué)表達(dá)式的定義5/6/202235建立在遞歸函數(shù)上的算法稱為遞歸算法，即要求解一建立在遞歸函數(shù)上的算法稱為遞歸算法，即要求解一個有參數(shù)個有參數(shù)n的函數(shù)可以調(diào)用含有更小參數(shù)的同樣的函數(shù)。的函數(shù)可以調(diào)用含有更小參數(shù)的同樣的函數(shù)。任何一個遞歸算法都有一個迭代算法與之對應(yīng)。遞歸任何一個遞歸算法都有一個迭代算法與之對應(yīng)。遞歸算法要保存和計算一系列中間過步驟，而迭代算法只須算法要保存和計算一系列中間過步驟，而迭代算法只須保存最新結(jié)果，因此其計算量與存貯量都比遞歸算法好，保存最新結(jié)果，