推理与证明方法.ppt

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