推理与证明方法

《推理与证明方法》由会员分享，可在线阅读，更多相关《推理与证明方法（38页珍藏版）》请在金锄头文库上搜索。

1、推理与证明方法推理与证明方法3 数学推理Mathematical Reasoning 3.1 推理与证明方法Reasoning and Methods of Proof 3.2 数学归纳方法3.3 递推方法Date1推理与证明方法推理与证明方法定理/Theorem: 一个真值为T的命题语句。证明/Proof：用论证方式形成的一个命题语句序列说明一个定理为T。证明的构造/形式：由两个部分组成1、公理、假定或前提/axiom、postulate、hypotheses2、推理规则/rule of inference其它：引理/lemma、推论/corollary、猜想/conjecture一些基本概

2、念Date2推理与证明方法推理与证明方法Definition 1 蕴涵演算/logical implying operation对于任意的公式P和Q，如果P Q 为T，则称P蕴涵Q， 记为P Q 或P/Q蕴涵演算的推广表示：P1、 P2 、 、Pn Q 前提组/hypotheses 结论/conclusion证明的基本工具：等值演算，真值表，范式，引用已知简单结论下表是一些常用的简单结论Date3推理与证明方法推理与证明方法Table 1 Rule of Inference Name P P QAddition/析取附加式P Q P Simplification/合取化简式P、Q P Q Co

3、njunction/并发式P、 P Q QModus ponens/分离式 Q、 P Q PModus tollens/拒取式 p、P Q QDisjunctive syllogism/析取三 段式 P Q、 Q R P R Hypothetical syllogism/假言 三段式Date4推理与证明方法推理与证明方法EXAMPLE 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)

4、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 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、Date5推理与证明方法推理与证明方法The 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)Date6推理与证明方法推理与证明方法Table 2. Rule of InferenceName x P(x) P(c) if cUUI/全称举例P(c) for an arbitrary cU x P(x) UG/全称推 广 x P(x) P(c) for some cUEI/存在举例P(c) for

6、some cU x P(x)EG/存在推广U:Universal I:InstantiationE: Existential G: GeneralizationDate7推理与证明方法推理与证明方法EXAMPLE 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)Date8推理与证明方法推理与证明方法EXAMPLE 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)Date9推理与证明方法推理与证明方法nx ( K(x) (h) 7. W(c) B(c) (UI)n K(c) (EI) 8. W(c)nx (B(x) K(x) ) (h) 9. x ( W(x) (EG)nB(c) K(c) (UI)nB(c) nx (W(x) B(x) (h)Date10推理与证明

8、方法推理与证明方法Indirect proof, negate the conclusionHypotheses: 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 (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)Date11推理与证明方法推理与证明方法定理证明方法：1、直接证明/direct proof: p Q 2、间

9、接证明/indirect proof : p Q Q P3、空证明/vacuous proof: p Q 其中 P为 F4、平凡证明/trivial proof： p Q 其中 Q 为TDate12推理与证明方法推理与证明方法5、反证明/proof of contradiction：P P S S6、分例证明/proof of cases： P1 P2 Pn Q （P1 Q） （P2 Q） （Pn Q） 定理证明方法：Date13推理与证明方法推理与证明方法7、存在证明/existence proof： x P(x) constructive, nonconstructive8、归纳证明/in

10、duction proof ： x P(x) 定理证明方法：（含有量词）Date14推理与证明方法推理与证明方法进一步的思考1、从等值演算到蕴涵演算2、从命题公式的推理到谓词公式的推理 3、停机问题/Halting Problem Date15推理与证明方法推理与证明方法练 习pp.183 4、16、43、68Date16推理与证明方法推理与证明方法3 数学推理Mathematical Reasoning 3.1 推理与证明方法3.2 数学归纳方法Mathematical Induction3.3 递推方法Date17推理与证明方法推理与证明方法The well-ordering proper

11、tyThe well-ordering property(良序定理）Every nonempty set of nonnegative integers has a least element (非空的非负整数集合必有最小元）Date18推理与证明方法推理与证明方法数学归纳法用来证明与整数有关的命题。数学归纳法的公式表示：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)数学归纳的理论基础是整数公理，如下所示：Definition 1Date19推理与证明方法推理与证明方法皮亚诺公理（1）0N；（2）对每一个n

12、N，唯一定义了一个自然数n，n 称为n的后邻；（3）不同的自然数，其后邻也不同；（4）没有一个自然数的后邻是0；（5）如果有一个子集MN满足： 0M； nM时必n M, 则M = N自然数全体N通过皮亚诺公理的五条公理组成。这些公理缺一不可，其中性质（5）称为归纳公理，并指出了自然数是满足公理（1）（4）的最小集合。 Date20推理与证明方法推理与证明方法数学归纳法的一般公式表示：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 2Date21推理与证明方法推理与证明方法EXAMPLE

13、1 pp.191 example 51 + 2 + 22 + + 2n = 2n+1 - 1 数学归纳法的正确性可以用皮亚诺公理与良序定理来证明。Date22推理与证明方法推理与证明方法第二数学归纳法：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) Definition 3Date23推理与证明方法推理与证明方法EXAMPLE 2 证明：任意一个大于1 的自然数或为质数，或能表示为若干个质数的乘积。Date24推理与证明方法推理与证明方法有限数学归纳法：对于 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) Definition 4Date25推理与证明方法推理与证明方法EXAMPLE 3 pp. 195