推理与证明方法
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,1
3 数学推理
Mathematical Reasoning
3.1 推理与证明方法
Reasoning and Methods of Proof
3.2 数学归纳方法
3.3 递推方法推理与证明方法
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,2
定理 /Theorem,一个真值为 T的命题语句。
证明 /Proof：用论证方式形成的一个命题语句序列说明一个定理为 T。
证明的构造 /形式：由两个部分组成
1,公理、假定或前提 /axiom,postulate,hypotheses
2,推理规则 /rule of inference
其它,引理 /lemma,推论 /corollary,猜想 /conjecture
一些基本概念推理与证明方法
7/31/2009 11:28 AM 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
推理与证明方法
7/31/2009 11:28 AM 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/假言三段式推理与证明方法
7/31/2009 11:28 AM 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
推理与证明方法
7/31/2009 11:28 AM 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.
推理与证明方法
7/31/2009 11:28 AM 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?Ux P(x) UG/全称推广
x P(x)? P(c) for some c?U EI/存在举例
P(c) for some c?Ux P(x) EG/存在推广
U:Universal I:Instantiation
E,Existential G,Generalization
推理与证明方法
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,8
EXAMPLE 3
苏格拉底论证：
人固有一死,苏格拉底是人,因此苏格拉底固有一死 。
推理与证明方法
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,9
EXAMPLE 4
Hypotheses,任何人如果他喜欢步行,则他就不喜欢乘汽车；每个人喜欢乘汽车或者喜欢骑自行车；有的人不喜欢骑自行车,
Conclusion,因此有的人不喜欢步行 。
推理与证明方法
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,10
定理证明方法：
1,直接证明 /direct proof,p → Q
2,间接证明 /indirect proof,p → QQ →?P
3,空证明 /vacuous proof,p → Q 其中 P为 F
4,平凡证明 /trivial proof,p → Q 其中 Q 为 T
推理与证明方法
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,11
定理证明方法：
5,反证明 /proof of contradiction：
P
P? S ∧? S
6,分例证明 /proof of cases：
P1∨ P2 … ∨ Pn → Q
（ P1→ Q） ∧ （ P2 → Q） … ∧ （ Pn→ Q）
推理与证明方法
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,12
定理证明方法：
7,存在证明 /existence proof：
x P(x)
constructive,nonconstructive
8,归纳证明 /induction proof,
x P(x)
推理与证明方法
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,13
小 结
1、推理应用中的六个规则
2、证明的八种不同方法推理与证明方法
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,14
进一步的思考
1、从等值演算到蕴涵演算
2、从命题公式的推理到谓词公式的推理
3、停机问题 /Halting Problem
推理与证明方法
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,15
练 习
pp.183 4,16,43,68
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,1
3 数学推理
Mathematical Reasoning
3.1 推理与证明方法
Reasoning and Methods of Proof
3.2 数学归纳方法
3.3 递推方法推理与证明方法
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,2
定理 /Theorem,一个真值为 T的命题语句。
证明 /Proof：用论证方式形成的一个命题语句序列说明一个定理为 T。
证明的构造 /形式：由两个部分组成
1,公理、假定或前提 /axiom,postulate,hypotheses
2,推理规则 /rule of inference
其它,引理 /lemma,推论 /corollary,猜想 /conjecture
一些基本概念推理与证明方法
7/31/2009 11:28 AM 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
推理与证明方法
7/31/2009 11:28 AM 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/假言三段式推理与证明方法
7/31/2009 11:28 AM 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
推理与证明方法
7/31/2009 11:28 AM 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.
推理与证明方法
7/31/2009 11:28 AM 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?Ux P(x) UG/全称推广
x P(x)? P(c) for some c?U EI/存在举例
P(c) for some c?Ux P(x) EG/存在推广
U:Universal I:Instantiation
E,Existential G,Generalization
推理与证明方法
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,8
EXAMPLE 3
苏格拉底论证：
人固有一死,苏格拉底是人,因此苏格拉底固有一死 。
推理与证明方法
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,9
EXAMPLE 4
Hypotheses,任何人如果他喜欢步行,则他就不喜欢乘汽车；每个人喜欢乘汽车或者喜欢骑自行车；有的人不喜欢骑自行车,
Conclusion,因此有的人不喜欢步行 。
推理与证明方法
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,10
定理证明方法：
1,直接证明 /direct proof,p → Q
2,间接证明 /indirect proof,p → QQ →?P
3,空证明 /vacuous proof,p → Q 其中 P为 F
4,平凡证明 /trivial proof,p → Q 其中 Q 为 T
推理与证明方法
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,11
定理证明方法：
5,反证明 /proof of contradiction：
P
P? S ∧? S
6,分例证明 /proof of cases：
P1∨ P2 … ∨ Pn → Q
（ P1→ Q） ∧ （ P2 → Q） … ∧ （ Pn→ Q）
推理与证明方法
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,12
定理证明方法：
7,存在证明 /existence proof：
x P(x)
constructive,nonconstructive
8,归纳证明 /induction proof,
x P(x)
推理与证明方法
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,13
小 结
1、推理应用中的六个规则
2、证明的八种不同方法推理与证明方法
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,14
进一步的思考
1、从等值演算到蕴涵演算
2、从命题公式的推理到谓词公式的推理
3、停机问题 /Halting Problem
推理与证明方法
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,15
练 习
pp.183 4,16,43,68
