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

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

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

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

问题1：

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

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

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

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

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

问题6：你能用学过的逻辑知识说明分情形证明法的正确性吗？ 证明𝑝→𝑞，如果恰有𝑝≡ 𝑝 1 ∨ 𝑝 2 ∨…∨ 𝑝 𝑛 ,则有： 𝑝→𝑞 ≡ 𝑝 1 →𝑞 ∧ 𝑝 2 →𝑞 ∧…∧ 𝑝 𝑛 →𝑞 事实上： 𝑝 1 →𝑞 ∧ 𝑝 2 →𝑞 ∧…∧ 𝑝 𝑛 →𝑞 ≡ ¬ 𝑝 1 ∨𝑞 ∧ ¬ 𝑝 2 ∨𝑞 ∧…∧ ¬ 𝑝 𝑛 ∨𝑞 ≡ ¬ 𝑝 1 ∧¬ 𝑝 2 ∧…∧¬ 𝑝 𝑛 ∨𝑞 ≡¬ 𝑝 1 ∨ 𝑝 2 ∨…∨ 𝑝 𝑛 ∨𝑞 ≡¬𝑝∨𝑞 ≡𝑝→𝑞 因此： 𝑝≡ 𝑝 1 ∨ 𝑝 2 ∨…∨ 𝑝 𝑛 成为关键所在，成为这种证明方法的“令人担心”的地方

存在性证明 讨论题：Chomp游戏，你该如何幸存？ 证明具有某种性质的对象的存在性 基本方法： ∃𝑥𝑃(𝑥) 构造法：找到一个𝑎，𝑃(𝑎)=𝑇 非构造法：归谬证明（反证法）∀𝑥𝑃 𝑥 =𝐹 讨论题：Chomp游戏，你该如何幸存？

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

关于数学归纳法 问题7：对于这个说法，你有什么感想？你心目中印象最深刻的用数学归纳法证明的定理是什么？ 数学归纳法通常可以用于证明形如以下的命题： ∀𝑥𝑃(𝑥) 问题7：对于这个说法，你有什么感想？你心目中印象最深刻的用数学归纳法证明的定理是什么？

数学归纳法的逻辑基础是什么？ 其合理性来自证明对象的结构 自然数的结构： 一般来讲，我们用良序性来描述上述类似结构： 0(或者1)是自然数； 如果k是自然数，k的“后继”也是自然数； 自然数只能通过使用上述规则得到 一般来讲，我们用良序性来描述上述类似结构： 实数

数学归纳法的逻辑正确性会在哪儿被质疑？ 𝑃 1 ,∀𝑛 𝑛≥1∧𝑃 𝑛 →𝑃 𝑛+1 能否推理出∀𝑛𝑃(𝑛)? 𝑃 1 ,∀𝑛 𝑛≥1∧𝑃 𝑛 →𝑃 𝑛+1 能否推理出∀𝑛𝑃(𝑛)? 𝑃 1 ∧∀𝑛 𝑛≥1∧𝑃 𝑛 →𝑃 𝑛+1 →∀𝑛𝑃 𝑛 是否永真?

数学归纳法的逻辑正确性 反证法 几个问题： 1.良序性如果没有，数学归纳法会出什么问题？ 数学归纳法的否定是什么？

Example-1 用数学归纳法证明用4分和5分就可以组成12分及以上的每种邮资： 奠基：3个4分硬币组成12分 假设：k分邮资可以由4分和5分硬币组成 归纳： 如果k分邮资组合中含有4分硬币，用5分硬币替换； 如果k分邮资组合中不含有4分硬币，？？？ 同时用到了分情形证明

Example-2 问题出在哪里？ 所有的马都是白马 令p(n):任意n匹马都是同一种颜色 奠基：p(1)成立 假设：p(k)成立 归纳：(p(k)->p(k+1)) 将k+1匹马分为两群：前k匹马同色（不失一般性，为白马），后k匹马同 色，这两群马均同色，为白马 K+1匹马均为白色，同色 结论为真，证明结束 问题出在哪里？

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

关于鸽笼原理的讨论 "如果有五个鸽子笼，养鸽人养了6只鸽子， 那么当鸽子飞回笼中后，至少有一个笼子 中装有2只鸽子。" Let A and B be finite sets and let 𝑓:𝐴→𝐵. If |A|>|B|, then 𝑓 is not one to one function. If 𝐴 < 𝐵 , then 𝑓 is not onto. 鸽笼（巢）原理、抽屉原理、狄利克雷原 理

看不见的鸽笼，看不见的鸽子 自然数1,2,3,…, 𝑛 2 +1的任何一种排列中，必然含一个长度不小于n+1的严格 递增链或严格递减链 排列中的每个元素都一定会出现在矩阵M中，矩阵M最多有 𝑛 2 个位置 =>必有两个元素在同一个位置 假设有𝑝,𝑞都落入了𝑀[𝑖,𝑗]中，分析𝑝,𝑞大小和𝑝,𝑞在排列中出现的位置，若干情况 无论何种情况，如p<q; p在q前, 则从p的递增序列长度一定大于i。 p<q p>q p在q前 1 2 p在q后 3 4 矛盾！

Knowing Each Other or Not Problem: show that among any 6 persons, there are 3 who know each other, or there are 3 who don’t know any two others Pigeonhole1:those knowing A B C There must be at least 3 elements which fall into one of the two pigeonhole D A Pigeonhole2:those not knowing A

Knowing Each Other or Not Problem: show that among any 6 persons, there are 3 who know each other, or there are 3 who don’t know any two others Pigeonhole1:those knowing A B C There must be at least 3 elements which fall into one of the two pigeonhole D A Pigeonhole2:those not knowing A

Knowing Each Other or Not Problem: show that among any 6 persons, there are 3 who know each other, or there are 3 who don’t know any two others Pigeonhole1:those knowing A B C There must be at least 3 elements which fall into one of the two pigeonhole D A Pigeonhole2:those not knowing A

最后几个问题： 一个证明的正确性是由哪些方面保证的？ 一个正确的结论是由哪些方面保证的？ 证明方法在证明过程中起到了什么作用？

Open Topic-1: Chomp Game Chomp is a two-player strategy game played on a rectangular chocolate bar made up of smaller square blocks (cells). The players take it in turns to choose one block and "eat it" (remove from the board), together with those that are below it and to its right. The top left block is "poisoned" and the player who eats this loses. If #cell>=2, first player must have a strategy to win! https://en.wikipedia.org/wiki/Chomp

Open Topic-2 证明数学归纳法同良序公理是等价的