浙江大学：《离散数学》课程教学资源（PPT课件讲稿）第三章 推理与证明方法（3.1）证明方法

推理与证明方法 3数学推理 Mathematical Reasoning 3.1推理与证明方法 Reasoning and methods of proof 32数学归纳方法 33递推方法 2/24/202111:15PM Deren Chen Zhejiang univ

推理与证明方法 2/24/2021 11:15 PM Deren Chen, Zhejiang Univ. 1 3 数学推理 Mathematical Reasoning 3.1 推理与证明方法 Reasoning and Methods of Proof 3.2 数学归纳方法 3.3 递推方法

一些基本概念 推理与证明方法 定理/ Theorem:一个真值为T的命题语句。 证明/ Proof:用论证方式形成的一个命题语句序列说明 个定理为T 证明的构造/形式:由两个部分组成 1、公理、假定或前提/ axiom、 postulate、 hypotheses 2、推理规则/ rule of inference 其它:引理/emma、推论/ corollary、猜想/ conjecture 2/24/202111:15PM Deren Chen Zhejiang univ 2

推理与证明方法 2/24/2021 11:15 PM Deren Chen, Zhejiang Univ. 2 定理/Theorem: 一个真值为T的命题语句。 证明/Proof：用论证方式形成的一个命题语句序列说明 一个定理为T。 证明的构造/形式：由两个部分组成 1、公理、假定或前提/axiom、postulate、hypotheses 2、推理规则/rule of inference 其它：引理/lemma、推论/corollary、猜想/conjecture 一些基本概念

Definition 1 推理与证明方法 蕴涵演算/ ogical implying operation 对于任意的公式P和Q,如果P→Q为,则称P 蕴涵Q,记为P→Q或P/:Q 蕴涵演算的推广表示: 2 Pn→Q 前提组/ hypotheses结论/ conclusion 2/24/202111:15PM Deren Chen Zhejiang univ 3

推理与证明方法 2/24/2021 11:15 PM Deren Chen, Zhejiang Univ. 3 Definition 1 蕴涵演算/logical implying operation 对于任意的公式P和Q，如果P → Q 为T，则称P 蕴涵Q， 记为P  Q 或P/Q 蕴涵演算的推广表示： P1、 P2 、 … 、Pn  Q 前提组/hypotheses 结论/conclusion

Table 1 推理与证明方法 Rule of Inference Name P→PVQ Addition/析取附加式 P∧Q→P Simplification/合取化简式 P、Q→P∧Q Conjunction/并发式 P、P→Q→Q Modus ponens,分离式 Q、P→Q→-P Modus tollens/拒取式 p、PVQ→Q Disjunctive syllogism析取三段式 P→Q、Q→R→P→R ypothetical syllogism假言三段式 2/24/202111:15PM Deren Chen Zhejiang univ

推理与证明方法 2/24/2021 11:15 PM Deren Chen, Zhejiang Univ. 4 Table 1 Rule of Inference Name P  P ∨Q Addition/析取附加式 P ∧Q  P Simplification/合取化简式 P、Q  P ∧Q Conjunction/并发式 P、 P → Q  Q Modus ponens/分离式 ¬ Q、 P → Q  ¬ P Modus tollens/拒取式 ¬ p、P ∨Q  Q Disjunctive syllogism/析取三段式 P → Q、 Q → R  P → R Hypothetical syllogism/假言三段式

EXAMPLE1 推理与证明方法 Hypotheses:PVQ,P→R,Q→S Conclusion:S∨R Proof: PVQ,P→R,Q→S→S∨R 2/24/202111:15PM Deren Chen Zhejiang univ

推理与证明方法 2/24/2021 11:15 PM Deren Chen, Zhejiang Univ. 5 EXAMPLE 1 Hypotheses: P ∨ Q, P → R, Q → S Conclusion: S ∨ R Proof: P ∨ Q, P → R, Q → S  S ∨ R

EXAMPLE2 推理与证明方法 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 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 th s afternoon Q: It is colder than yesterda R: We will go swimming S: We will take a canoe trip. T: We will be home by sunset 2/24/202111:15PM Deren Chen Zhejiang univ

推理与证明方法 2/24/2021 11:15 PM Deren Chen, Zhejiang Univ. 6 EXAMPLE 2 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 don’t 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

Table 2 推理与证明方法 Rule of inference Name vxP(x)→P(c) ifceU UI全称举例 P(c)for an arbitrary cEU=Vx P(x) UG/全称推广 彐xP(x)→P(c) for some ceU EI存在举例 P(c) for some c∈U→彐xP(x) EG存在推广 U: Universal l: Instantiation E: Existential g: generalization 2/24/202111:15PM Deren Chen Zhejiang univ

推理与证明方法 2/24/2021 11:15 PM Deren Chen, Zhejiang Univ. 7 Table 2. Rule of Inference Name x P(x)  P(c) if cU UI/全称举例 P(c) for an arbitrary cU  x P(x) UG/全称推广 x P(x)  P(c) for some cU EI/存在举例 P(c) for some cU  x P(x) EG/存在推广 U:Universal I:Instantiation E: Existential G: Generalization

EXAMPLE3 推理与证明方法 苏格拉底论证 人固有一死,苏格拉底是人,因此苏格拉底固有一死。 2/24/202111:15PM Deren Chen Zhejiang univ

推理与证明方法 2/24/2021 11:15 PM Deren Chen, Zhejiang Univ. 8 EXAMPLE 3 苏格拉底论证： 人固有一死，苏格拉底是人，因此苏格拉底固有一死

EXAMPLEA 推理与证明方法 Hypotheses:任何人如果他喜欢步行,则他就不喜欢乘 汽车;每个人喜欢乘汽车或者喜欢骑自行车;有的人不喜 欢骑自行车, Conclusion:因此有的人不喜欢步行。 2/24/202111:15PM Deren Chen Zhejiang univ

推理与证明方法 2/24/2021 11:15 PM Deren Chen, Zhejiang Univ. 9 EXAMPLE 4 Hypotheses: 任何人如果他喜欢步行，则他就不喜欢乘 汽车；每个人喜欢乘汽车或者喜欢骑自行车；有的人不喜 欢骑自行车， Conclusion: 因此有的人不喜欢步行

推理与证明方法 定理证明方法: 1、直接证明 direct proof:p→Q 2、间接证明/ indirect proo:p→Q分-Q→-P 3、空证明 acuous proof:p→Q其中P为F 4、平凡证明/ trivial proof:p→Q其中Q为T 2/24/202111:15PM Deren Chen Zhejiang univ

推理与证明方法 2/24/2021 11:15 PM Deren Chen, Zhejiang Univ. 10 定理证明方法： 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