证明方法.ppt

3 数学推理
Mathematical Reasoning
推理与证明方法
Reasoning and Methods of Proof
数学归纳方法
递推方法
11/11/2017
1
Deren Chen, Zhejiang Univ.
定理/Theorem: 一个真值为T的命题语句。
证明/Proof:用论证方式形成的一个命题语句序列说明一个定理为T。
证明的构造/形式:由两个部分组成
1、公理、假定或前提/axiom、postulate、hypotheses
2、推理规则/rule of inference
其它:引理/lemma、推论/corollary、猜想/conjecture
一些基本概念
11/11/2017
2
Deren Chen, Zhejiang Univ.
Definition 1
蕴涵演算/logical implying operation
对于任意的公式P和Q,如果P → Q 为T,则称P蕴涵Q, 记为P  Q 或P/Q
蕴涵演算的推广表示:
P1、 P2 、…、Pn  Q
前提组/hypotheses 结论/conclusion
11/11/2017
3
Deren Chen, Zhejiang Univ.
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/假言三段式
11/11/2017
4
Deren Chen, Zhejiang Univ.
EXAMPLE 1
Hypotheses: P ∨ Q, P → R, Q → S
Conclusion: S ∨ R
Proof:
P ∨ Q, P → R, Q → S  S ∨ R
11/11/2017
5
Deren Chen, Zhejiang Univ.
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.
11/11/2017
6
Deren Chen, Zhejiang Univ.
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
11/11/2017
7
Deren Chen, Zhejiang Univ.
EXAMPLE 3
苏格拉底论证:
人固有一死,苏格拉底是人,因此苏格拉底固有一死。
11/11/2017
8
Deren Chen, Zhejiang Univ.
EXAMPLE 4
Hypotheses: 任何人如果他喜欢步行,则他就不喜欢乘汽车;每个人喜欢乘汽车或者喜欢骑自行车;有的人不喜欢骑自行车,
Conclusion: 因此有的