计算机问题求解-论题1-3常用证明方法及其逻辑正确性.pptx

计算机问题求解-论题1-3

常用证明方法及其逻辑正确性陶先平2019年10月22日

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

?你有没有怀疑过这个”therefore”的正确性？

Thereareinfinitelymanyprimenumbers.

WesetacontraryofourtheoremandusethisassumptiontostartThenwegetacontradictionthroughavalidargumentThenwegetthetheoremquickly

反证法的逻辑正确性必定来自于逻辑！??//注意以下推理中p和q的辖域其实，这两步之间的逻辑还挺复杂，更为本质！

反证法的逻辑正确性必定来自于逻辑！?问题1：在这个一般性的定理证明过程中，你现在能说清楚反证法的基本方法和它的逻辑正确性吗？

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

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

问题6：你能用学过的逻辑知识说明分情形证明法的正确性吗？证明p?q，如果恰有p?p1?p2?…?pn,则有：(p?q)?(p1?q)?(p2?q)?…?(pn?q)因此：p?p1?p2?…?pn成为关键所在，成为这种证明方法的“令人担心”的地方

存在性证明证明具有某种性质的对象的存在性?xp(x)基本方法：构造法：找到一个a，p(a)=T非构造法：归谬证明?x?p(x)=F讨论题：Chomp游戏，你该如何幸存？

Chomp游戏abcde

Chomp游戏可以先行必胜存在性证明方法的一种典范存在性证明的非构造法的一种典范证明思路：不可能平局：最多MN步骤必定出结果假设后手可以必胜：先手取走（m,n）,后手根据自己的必胜策略，取走（a,b）,然后按照拟定的后续步骤s1,s,2,…,sk获胜（剧情回退）先手取走(a,b),然后按照s1,s,2,…,sk获胜先手可以必胜

关于数学归纳法?问题7：对于这个说法，你有什么感想？你心目中印象最深刻的用数学归纳法证明的定理是什么？

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

数学归纳法的逻辑正确性会在哪儿被质疑？?

几个问题：1，良序性如果没有，数学归纳法会出什么问题？2，两个前提条件分别在哪里被使用？

两个范例用数学归纳法证明用4分和5分就可以组成12分及以上的每种邮资：奠基：3个4分硬币组成12分假设：k分邮资可以由4分和5分硬币组成归纳：k+1分如果k分邮资组合中含有4分硬币，用5分硬币替换，得到k+1分如果k分邮资组合中不含有4分硬币，？？？所有的马都是白马令p(n):任意n匹马都是同一种颜色奠基：p(1)成立假设：p(k)成立归纳：(p(k)-p(k+1))将k+1匹马分为两群：前k匹马同色（不失一般性，为白马），后k匹马同色，这两群马均同色，为白马K+1匹马均为白色，同色结论为真，证明结束问题出在哪里？

鸽笼原理示例观察：坐标是(a,b),(c,d)的点，其中点坐标为：因此：如果ac同奇偶，bd同奇偶，其中点是整数，是格点

看不见的鸽笼，看不见的鸽子自然数1,2,3,…,n2+1的任何一种排列中，必然含一个长度不小于n+1的严格递增链或严格递减链假设严格递增与递减序列最大长度均不大于n,建立n*n矩阵M如下：M[i,j]=k(k∈{1,2,…,n2+1})iff在所给的序列中以k开始的严格递增序列长度为i,以k开始的严格递减序列长度为ja,b,c,…,k,…,s1,2,3,…,n2+1的一种排列ij排列中的每个元素都一定会出现在矩阵M中，矩阵M最多有n2个位置=》必有两个元素在同一个位置假设有p,q都落入了M[i,j]中，分析p,q大小和p,q在排列中出现的位置，有若干情况pq;pq;p在q前;p在q后：无论何种情况，如pq;p在q前,从p的递增序列长度一定大于i。矛盾！

关于鸽笼原理的讨论为什么以下定理被命名为鸽笼原理？LetAandBbefinitesetsandletf:A-B.If|A||B|,then