南京大学：《计算机问题求解》课程教学资源（PPT课件讲稿）常用的证明方法

论题1-3 -常用的证明方法及其逻辑正确性 majun@nju.edu.cn 2017.10.19

论题1-3 - 常用的证明方法及其逻辑正确性 majun@nju.edu.cn 2017.10.19

主要内容 ·反证法及其逻辑正确性 ·分情形证明法及其逻辑正确性 ·数学归纳法及其逻辑正确性 ·鸽笼原理及其逻辑正确性

主要内容 • 反证法及其逻辑正确性 • 分情形证明法及其逻辑正确性 • 数学归纳法及其逻辑正确性 • 鸽笼原理及其逻辑正确性

主要内容 ·反证法及其逻辑正确性 ·分情形证明法及其逻辑正确性 ·数学归纳法及其逻辑正确性 ·鸽笼原理及其逻辑正确性

主要内容 • 反证法及其逻辑正确性 • 分情形证明法及其逻辑正确性 • 数学归纳法及其逻辑正确性 • 鸽笼原理及其逻辑正确性

V2 is not rational(Pythagoreans)? Proof. Suppose,to the contrary,that v2 is rational.Then there exist inte- gers p and q(with q nonzero)such that v2 =p/q.We may assume that p and g have no common factor,for if they did,we would sim- plify and begin again.Now,we have that v2q =p.Squaring both sides,we obtain 2g2 =p2.Thus p2 is even.Since p2 is even,we know from Problem 3.1 that p must be ever 你有没有怀疑过 some integer m.This means that 2q2= 这个”therefore" g2 =2m2.But this means that g2 is even. 的正确性？ lem 3.1 that q is even.So p and g have a common facto2,which is completely absurd,since we assumed they had no common factor Therefore our assumption that v2 is rational must be wrong and we have completed the proof of the theorem

2 is not rational (Pythagoreans)? 你有没有怀疑过 这个”therefore” 的正确性？

问题1： 你能用上堂课的描述方 式说明这个证明逻辑上 的合理性吗？

问题1：

反证法的逻辑正确性必定来自于逻辑！ ·令：A表示V2不是有理数；B(p,q)表示p和q互质 ·假定：7A为真 注意p,q值域， ·推理： 此处省略 (A,若干数学定理)→F ·A T→(A∧若干数学定理) ·3p3q ·p2=2q 其实，这两步之 (A∧若干数学定理)=F ·p是偶数，令p=2m 间的逻辑还挺复 A =F 4m2=2q 杂，更为本质！ ·2m2=g A=T q是偶数 ·B(p,q) ·B(p,q) ·B(p,q)AB(p,q) ·False ·A三T

反证法的逻辑正确性必定来自于逻辑！ • 令：𝐴表示 2不是有理数；𝐵(𝑝, 𝑞)表示p和q互质 • 假定：¬𝐴为真 • 推理： • ¬𝐴 • ∃𝑝∃𝑞 2 = 𝑝 𝑞 ∧ 𝐵 𝑝, 𝑞 • 𝑝 2 = 2𝑞 • 𝑝是偶数，令𝑝 = 2𝑚 • 4𝑚2 = 2𝑞 • 2𝑚2 = 𝑞 • 𝑞是偶数 • ¬𝐵 𝑝, 𝑞 • 𝐵 𝑝, 𝑞 • 𝐵 𝑝, 𝑞 ∧ ¬𝐵 𝑝, 𝑞 • 𝐹𝑎𝑙𝑠𝑒 • 𝐴 ≡ 𝑇 注意p,q 值域， 此处省略 其实，这两步之 间的逻辑还挺复 杂，更为本质！

反证法的逻辑正确性必定来自于逻辑！ ·定理证明： ·前提：一组命题公式A1,A2,,Ak ·结论：一个命题公式B 在这个一般性的定理证 ·如果是这样： 明过程中，你现在能说 ·前提：一组命题公式B,A1,A2,,Ak 清楚反证法的基本方法 ·结论：F 和它的逻辑正确性吗？ ·即：B,A1,A2,,Ak→F ·.(B∧A1∧A2A…AAk)=F ·又A1,A2,.,Ak为真 。B=F ·B=T ●

反证法的逻辑正确性必定来自于逻辑！ • 定理证明： • 前提：一组命题公式A1, A2, …, Ak • 结论：一个命题公式B • 如果是这样： • 前提：一组命题公式¬𝐵, 𝐴1,𝐴2, … , 𝐴𝑘 • 结论：𝐹 • 即：¬𝐵, 𝐴1, 𝐴2, … ,𝐴𝑘 ⇒ 𝐹 • ∴ ¬𝐵 ∧ 𝐴1 ∧ 𝐴2 ∧ ⋯ ∧ 𝐴𝑘 = 𝐹 • 又∵ 𝐴1, 𝐴2,… , 𝐴𝑘为真 • ∴ ¬𝐵 = 𝐹 • ∴ 𝐵 = 𝑇 在这个一般性的定理证 明过程中，你现在能说 清楚反证法的基本方法 和它的逻辑正确性吗？

问题2： ·反证法有时比直接证明法更好用。你能说说为什么吗？ ·如果需要你证明如下定理，你有什么想法？ ·前提：A1,A2,…,Am ·结论：B1或者B2或者.或者Bn

问题2: • 反证法有时比直接证明法更好用。你能说说为什么吗？ • 如果需要你证明如下定理，你有什么想法？ • 前提：A1,A2,…,Am • 结论：B1或者B2或者…或者Bn

主要内容 ·反证法及其逻辑正确性 ·分情形证明法及其逻辑正确性 ·数学归纳法及其逻辑正确性 ·鸽笼原理及其逻辑正确性

主要内容 • 反证法及其逻辑正确性 • 分情形证明法及其逻辑正确性 • 数学归纳法及其逻辑正确性 • 鸽笼原理及其逻辑正确性

Theorem 5.3. Let x and y be real numbers.Then xyl =Ixllyl. 问题3：这种证明方法 为什么被称为分情形 Proof. 证明法？ First,suppose that x 0 and y 0.Then xy 0 and we have Ixyl xy,lxl=x,and lyl y.Therefore, Ixyl xy lxllyl, and we have established the result in this case. Second,suppose that x0.Then xy 0 and we have lxyl =-(xy),Ixl =-x,and lyl =y.Therefore, 最“令人担心”的是 什么？ Ixy=-(xy)=(xy=Ixllyl ● we have now established the result for all four possible cases and we may conclude that xyl =xllyl for all real numbers x and y

问题3：这种证明方法 为什么被称为分情形 证明法？ 问题4：这种证明方法 最“令人担心”的是 什么？ 问题5：有的时候，我 们在证明时会用到 “不失一般性”这个 词，你理解这是什么 意思吗？