推理与证明方法PPT课件

1、2/3/2022 7:15 PM1 定理/Theorem: 一个真值为T的命题语句。 证明/Proof：用论证方式形成的一个命题语句序列说明一个定理为T。 证明的构造/形式：由两个部分组成 1、公理、假定或前提/axiom、postulate、hypotheses 2、推理规则/rule of inference 其它：引理/lemma、推论/corollary、猜想/conjecture一些基本概念第1页/共38页2/3/2022 7:15 PM2Definition 1 蕴涵演算/logical implying operation 对于任意的公式P和Q，如果P Q 为T，则称P蕴涵Q，

2、记为P Q 或P/Q 蕴涵演算的推广表示： P1、 P2 、 、Pn Q 前提组/hypotheses 结论/conclusion 证明的基本工具：等值演算，真值表，范式，引用已知简单结论 下表是一些常用的简单结论第2页/共38页2/3/2022 7:15 PM3Table 1 Rule of Inference NameP P QAddition/析取附加式析取附加式P Q P Simplification/合取化简式合取化简式P、Q P Q Conjunction/并发式并发式P、 P Q QModus ponens/分离式分离式 Q、 P Q PModus tollens/拒取式拒取式

3、p、P Q QDisjunctive syllogism/析取三段式析取三段式P Q、 Q R P R Hypothetical syllogism/假言三段式假言三段式第3页/共38页2/3/2022 7:15 PM4EXAMPLE 6 Hypotheses: (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 t

4、rip. (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 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. 第4页/共38页2/3/2022 7:15 PM5 The hypotheses become

5、P Q ,R P, R S, and S T, The conclusion is T1. P Q (h) 7. S T (h)2. P (s) 8.T 3.R P (h)4. R (m)5. R S (h)6.S (m)第5页/共38页2/3/2022 7:15 PM6Table 2. Rule of InferenceName x P(x) P(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)

6、EG/存在推广存在推广U:Universal I:InstantiationE: Existential G: Generalization第6页/共38页2/3/2022 7:15 PM7EXAMPLE 3 苏格拉底论证： 人固有一死，苏格拉底是人，因此苏格拉底固有一死。 P(x): x是人，D(x):x是要死的，S:苏格拉底。 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)第7页/共38页2/3/2022 7:15 PM8EXAMPLE 4 Hypotheses: 任何人如果他喜欢步

7、行，则他就不喜欢乘汽车；每个人喜欢乘汽车或者喜欢骑自行车；有的人不喜欢骑自行车， Conclusion: 因此有的人不喜欢步行。 W(x): 喜欢步行，B(x):x喜欢乘汽车，K(x)：x喜欢骑自行车；前提：x (W(x) B(x)， x (B(x) K(x) ), x ( K(x), 结论： x ( W(x)第8页/共38页2/3/2022 7:15 PM91. x ( K(x) (h) 7. W(c) B(c) (UI)2. K(c) (EI) 8. W(c)3. x (B(x) K(x) ) (h) 9. x ( W(x) (EG)4. B(c) K(c) (UI)5. B(c) 6.

8、x (W(x) B(x) (h)第9页/共38页2/3/2022 7:15 PM10Indirect proof, negate the conclusion Hypotheses: P Q, P R, Q S Conclusion: S R Proof: P Q, P R, Q S S R(1) (S R)（否定结论） 5. Q (3,4) 9. P Q (5,8)(2) S R （DM） 6. R (2) 10. (P Q) (9)(3) S （ 化简） 7. P R (h) 11. P Q (h)(4)Q S (h) 8. P (6,7) 12. F (11,12)第10页/共38页2/

9、3/2022 7:15 PM11 定理证明方法： 1、直接证明/direct proof: p Q 2、间接证明/indirect proof : p Q Q P 3、空证明/vacuous proof: p Q 其中 P为 F 4、平凡证明/trivial proof： p Q 其中 Q 为T第11页/共38页2/3/2022 7:15 PM12 5、反证明/proof of contradiction： P P S S 6、分例证明/proof of cases： P1 P2 Pn Q （P1 Q） （P2 Q） （Pn Q） 定理证明方法：第12页/共38页2/3/2022 7:15 P

10、M13 7、存在证明/existence proof： x P(x) constructive, nonconstructive 8、归纳证明/induction proof ： x P(x) 定理证明方法：（含有量词）第13页/共38页2/3/2022 7:15 PM14 进一步的思考 1、从等值演算到蕴涵演算 2、从命题公式的推理到谓词公式的推理 3、停机问题/Halting Problem 第14页/共38页2/3/2022 7:15 PM15 练 习 pp.183 4、16、43、68第15页/共38页2/3/2022 7:15 PM16 3 数学推理 Mathematical Rea

11、soning 3.1 推理与证明方法 3.2 数学归纳方法 Mathematical Induction 3.3 递推方法第16页/共38页2/3/2022 7:15 PM17The well-ordering property The well-ordering property(良序定理） Every nonempty set of nonnegative integers has a least element (非空的非负整数集合必有最小元）第17页/共38页2/3/2022 7:15 PM18 数学归纳法用来证明与整数有关的命题。 数学归纳法的公式表示： P(1) m(m 1 P(m

12、) P(m+1) n P(n) 1、归纳基础： P(1) 2、归纳步骤： m (m 1 P(m) P(m+1) 数学归纳的理论基础是整数公理，如下所示：Definition 1第18页/共38页2/3/2022 7:15 PM19皮亚诺公理 （1）0N； （2）对每一个nN，唯一定义了一个自然数n，n 称为n的后邻； （3）不同的自然数，其后邻也不同； （4）没有一个自然数的后邻是0； （5）如果有一个子集MN满足： 0M； nM时必n M, 则M = N 自然数全体N通过皮亚诺公理的五条公理组成。 这些公理缺一不可，其中性质（5）称为归纳公理，并指出了自然数是满足公理（1）（4）的最小集合。

13、 第19页/共38页2/3/2022 7:15 PM20 数学归纳法的一般公式表示： P(k) m(m k P(m) P(m+1) n P(n) 1、归纳基础： P(k) 2、归纳步骤： m (m k P(m) P(m+1)Definition 2第20页/共38页2/3/2022 7:15 PM21EXAMPLE 1 pp.191 example 5 1 + 2 + 22 + + 2n = 2n+1 - 1 数学归纳法的正确性可以用皮亚诺公理与良序定理来证明。第21页/共38页2/3/2022 7:15 PM22 第二数学归纳法： P(n0) k ( k n0 P(n0) P(n0+1) P

14、(k) P(k+1) n P(n) 1、归纳基础： P(n0) 2、归纳步骤： k ( k n0 P(n0) P(n0+1) P(k) P(k+1) Definition 3第22页/共38页2/3/2022 7:15 PM23EXAMPLE 2 证明：任意一个大于1 的自然数或为质数，或能表示为若干个质数的乘积。第23页/共38页2/3/2022 7:15 PM24 有限数学归纳法：对于 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

15、 n nk-1 P(n) P(n+1) Definition 4第24页/共38页2/3/2022 7:15 PM25EXAMPLE 3 pp. 195 Example 11，12，14第25页/共38页2/3/2022 7:15 PM26 3.3 递归方法 Recursive Definition第26页/共38页2/3/2022 7:15 PM27DEFINITION 1 定义1如果一个对象部分地由自己所组成，或者按它自己定义，则称为是递归的（Recursion）。 f的定义域：非负整数集 1、递归基础： f(0) 2、递归步骤： f(n)=g(f(k), k0Example 1第28页/

16、共38页2/3/2022 7:15 PM29 菲波那契数/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) = 8， 利用菲波那契数可以推算出兔子繁衍规律。 Example 2第29页/共38页2/3/2022 7:15 PM30 Example 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+

17、)= n-3 2 = n-1 (归纳证明）第30页/共38页2/3/2022 7:15 PM31 利用 Fibonacci数列研究Euclid算法的计算复杂性。 a=r0,b=r1 ri=ri+1qi+1+ri+2 (0 ri+2 ri+1, 0 In-2) 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 + 1第31页/共38页2/3/2022 7:15 PM

18、321、3 S2、X S Y S X + Y SS是能够被3 整除的正整数集合。Example 4 第32页/共38页2/3/2022 7:15 PM33Well-formed formulae 1、命题公式的定义 2、谓词公式的定义 3、数集上的 +，-，*，/， 数学表达式的定义Example 5第33页/共38页2/3/2022 7:15 PM34递归算法和迭代算法 建立在递归函数上的算法称为递归算法，即要求解一个有参数n的函数可以调用含有更小参数的同样的函数。 任何一个递归算法都有一个迭代算法与之对应。递归算法要保存和计算一系列中间过步骤，而迭代算法只须保存最新结果，因此其计算量与存贮量都比递归算法好，但是从