推理与证明方法

1、5/6/202213 数学推理数学推理 Mathematical Reasoning 3.1 推理与证明方法推理与证明方法 Reasoning and Methods of Proof 3.2 数学归纳方法数学归纳方法 3.3 递推方法递推方法5/6/20222定理定理/Theorem: 一个真值为一个真值为T的命题语句。的命题语句。证明证明/Proof：用论证方式形成的一个命题语句序列说明：用论证方式形成的一个命题语句序列说明一个定理为一个定理为T。证明的构造证明的构造/形式：由两个部分组成形式：由两个部分组成 1、公理、假定或前提公理、假定或前提/axiom、postulate、hypot

2、heses 2、推理规则推理规则/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 结论结论/conclusion证明的基本工具：等值演算，真值表，范式，引用已知简单结论证明的基本工具：等值演算，真值表，范式

3、，引用已知简单结论下表是一些常用的简单结论下表是一些常用的简单结论5/6/20224Rule of Inference NameP P QAddition/析取附加式析取附加式P Q P Simplification/合取化简式合取化简式P、Q P Q Conjunction/并发式并发式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), 结论：结论： 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)（否定结论否定结论） 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进一步的思考进一步的思考 1、从等值演算到蕴涵演算、从等值演算到蕴涵演算 2、从命题公式的推理到谓词公式的推理、从命题公式的推理到谓词公式的推理 3、停机问题、停机问题/Halting

11、 Problem 5/6/202216练练 习习 pp.183 4、16、43、685/6/2022173 数学推理数学推理 Mathematical Reasoning 3.1 推理与证明方法推理与证明方法 3.2 数学归纳方法数学归纳方法 Mathematical Induction 3.3 递推方法递推方法5/6/202218The well-ordering property(良序定理良序定理）Every nonempty set of nonnegative integers has a least element (非空的非负整数集合必有最小元）非空的非负整数集合必有最小元）5/6

12、/202219数学归纳法数学归纳法用来证明与用来证明与整数有关整数有关的命题。的命题。数学归纳法的公式表示：数学归纳法的公式表示：P(1) m(m 1 P(m) P(m+1) n P(n) 1、归纳基础：、归纳基础： P(1) 2、归纳步骤：、归纳步骤： m (m 1 P(m) P(m+1)数学归纳的理论基础是数学归纳的理论基础是整数公理整数公理，如下所示：，如下所示：5/6/202220（1）0N；（2）对每一个）对每一个nN，唯一定义了一个自然数，唯一定义了一个自然数n，n 称为称为n的后邻；的后邻；（3）不同的自然数，其后邻也不同；）不同的自然数，其后邻也不同；（4）没有一个自然数的后邻

13、是）没有一个自然数的后邻是0；（5）如果有一个子集）如果有一个子集M N满足：满足： 0M； nM时必时必n M, 则则M = N自然数全体自然数全体N通过皮亚诺公理的五条公理组成。通过皮亚诺公理的五条公理组成。 这些公理缺一不可，其中性质（这些公理缺一不可，其中性质（5）称为归纳公理，并指出了自然数）称为归纳公理，并指出了自然数是满足公理（是满足公理（1）（4）的最小集合。）的最小集合。 5/6/202221数学归纳法的一般公式表示：数学归纳法的一般公式表示：P(k) m(m k P(m) P(m+1) n P(n) 1、归纳基础：、归纳基础： 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 数学归纳法的正确性可以用皮亚诺公理与良序数学归纳法的正确性可以用皮亚诺公理与良序定理来证明。定理来证明。5/6/202223第二数学归纳法：第二数学归纳法：P(n0) k ( k n0 P(n0) P(n0+1) P(k) P(k+1) n P(n) 1、归纳基础：、归纳基础： P(n0) 2、归纳步骤：、归纳步骤： k ( k n0 P(n0) P(n0+1) P(k) P(k+1) 5/6/202224证明：任意一个大于证明：任意一个大于1 的自然数或

15、为质数，或的自然数或为质数，或能表示为若干个质数的乘积。能表示为若干个质数的乘积。5/6/202225有限数学归纳法：对于有限数学归纳法：对于 n0 n nk 的的 P(n)有限数学归纳法的前推公式表示：有限数学归纳法的前推公式表示：P(n0) n(n0 n nk-1 P(n) P(n+1) n (n0 n nk P(n) 1、归纳基础：、归纳基础： 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的定义域：非负整数集的定义域：非负整数集 1、递归基础：、递归基础： f(0) 2、递归步骤：、递归步骤： f(n)=g(f(k), k05/6/202230菲波那契数菲波那契数/FibonacciF(0) = 0，F(1) = 1F(n) = F (n1) + F (n2)n1由上述公式，我们得到：由上述公式，我们得到：F (2) = 1，F (3) = 2，F (4) = 3，F (5) = 5，F (6)

17、 = 8，利用菲波那契数可以推算出兔子繁衍规律。利用菲波那契数可以推算出兔子繁衍规律。 5/6/202231Example 6（ PP. 205 ），）， f3=2 , f4=3 2, (归纳基础）归纳基础） fn-1 n-3, fn n-2(n3) (归纳假设）归纳假设） fn+1=fn-1+fn n-2+ n-3= n-3(1+ )= n-3 2 = n-1 (归纳证明）归纳证明）5/6/202232利用利用 Fibonacci数列研究数列研究Euclid算法的计算复杂性。算法的计算复杂性。 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, 假设假设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 整除的正整数集合。整除的正整数集合。 5/6/202234Well-formed formulae 1、命题公式的定义、命题公式的定义 2、谓词公式的定义、谓词公式的定义 3、数集上的、数集上的 +，-，*，/， 数学表达式的定义数学表达式的定义5/6/202235建立在递归函数上的算法称为递归算法，即要求解一建立在递归函数上的算法称为递归算法，即要求解一个有参数个有参数n的函数可以调用含有更小参数的同样的函数。的函数可以调用含有更小参数的同样的函数。任何一个递归算法都有一个迭代算法与之对应。递归任何一个递归算法都有一个迭代算法与之对应。递归算法要保存和计算一系列中间过步骤，而迭代算法只须算法要保存和计算一系列中间过步骤，而迭代算法只须保存最新结果，因此其计算量与存贮量都比递归算法好，保存最新结果，