说道数学归纳法,大家并不陌生。
这一节先来回顾一下我们似曾相识的归纳法,然后用它解决一个问题。
先来回忆一个小故事:高斯8岁的时候快速计算连续自然数的和。
咦!你感觉无聊了没:竟然有是这个故事,小时候都不知道听多少遍了。
其实过去这么久了,很多小时候我们耳熟能详的名字,现在对他们及他们的事迹印象没那么深了。
比如罗盛教、高士奇、齐白石、李星华等,多年不说,这样小学课本里的名字就很难想起来了。
闲言少叙,书归正传。看看我讲的高斯故事和你记得一不一样。
话说高斯八岁的时候已经上小学了。一天他的数学老师在家里让老婆打了(什么原因不知道,历史也没记载),所以他到学校就拿小孩子出气。这非常不好嘛,如果按照《乡村教师》里写的有记忆遗传就不需要教师了。他一冲进教室就往黑板上写了一道题目:1加到100是多少?
小孩子嘛,也不知道啥意思,没学过小数也没学过四元数,以为是1+2+3+...+100是多少。其实老师也是这吗想的。他估计小孩子们做完这么复杂的题目心里肯定很难受,和他让老婆打了一样难受。写完后他就坐在教室门口发呆,想着他老婆打他的招式,下一次该怎么躲才能让她老婆打他老婆自己。
这个问题都还没完整的想出来呢,高斯就不知好歹的跑过去大声说“老师我做完了!”老师大吃一惊:尼玛这是要逆天吗?结果拿过来一看:靠,结果真对了!!
(我觉得这个故事很扯淡,导致我认为高斯这个故事是假的)
高斯怎么做的,大家都知道我就不说了。
通过这个故事我们要说数学归纳法:请用归纳法证明对于任意的自然数n,都满足1+2+3+4+···+n=n·(n+1)/2
数学归纳法是一个只针对自然数的法则,和自然数没关系的绝对不能使用归纳法。所以我们不能说:根据归纳法,因为猴子有男女,所以猩猩有男女。
归纳法包含两个过程:
证明自然数1满足这个属性; 假设自然数n满足这个属性,根据n的这个属性证明n+1也有这个属性。
这个有两点要注意:必须先证明1满足这个属性,而不能直接证明任意一个其他确定的自然数有这属性(虽然看起来是一样的,但是逻辑不严密);要证明n+1有这属性必须是在n的基础上,不能用其他方法证明,否则就不是归纳法了。
我们把假设n有这个属性称为“归纳假设”。
证明:
当n=1时,满足1 = 1· (1 + 1)/2; 假设n=k(k>1)时有1+2+...+k=k·(k+1)/2,我们证明n=k+1时有1+2+3+...+k+(k+1)=(k+1)·(k+1+1)/2。 1+2+3+...+k+(k+1) =k·(k+1)/2 + (k+1) =k·(k+1)/2 +2·(k+1)/2 =(k+1)·(k+1+1)/2。 得证。
前面我们学写过合式公式语法树的高度,我们证明一个和他相关的定理:每个命题逻辑合式公式都含有相同个数的左括号和右括号。
这是命题逻辑中一个重要的定理。
证明:
我们通过合式公式语法树的高度使用数学归纳法。
我们用M(n)表示“每个高度为n的合式公式都有相同的左括号和右括号”。我们需要假设对于任意的k,k<n,都有M (k)成立。以此来证明M(n)成立。不妨设公式Θ的高度为n。
当n=1时,合式公式是一个原子命题,它的左右括号都是0,成立!
当n>1时,合式公式语法树的根节点有四种可能:¬、→、∨、∧,假设根节点是→,其余三种情况同理可证。则公式Θ的形式是(Θ1→Θ2),Θ1,Θ2是另外两个合式公式。可以肯定的是Θ1和Θ2的语法树高度一定比n小。根据归纳假设,我们已经知道Θ1和Θ2都有相同的左括号和右括号。当把它们组成公式Θ时是(Θ1→Θ2),又分别增加了一个左括号和右括号。所以Θ依然有相同的左括号和右括号。
得证。
这里的证明需要注意的是,不能和上一题证明一样直接某一个高度的结果。因为合式公式的语法子树高度一般不相等。
相关推荐
综述了当前所有数学归纳法的形式表达。给出了数学归纳法的定义,例题,证明,参考文献。
数理逻辑答案,数理逻辑答案,数理逻辑答案,数理逻辑答案
面向计算机科学的数理逻辑课后习题答案_1-5章面向计算机科学的数理逻辑课后习题答案_1-5章面向计算机科学的数理逻辑课后习题答案_1-5章面向计算机科学的数理逻辑课后习题答案_1-5章面向计算机科学的数理逻辑课后习题...
离散数据结构英文版 的补充知识~ 里面有数理逻辑以及其他的东西哟
王浩.数理逻辑通俗讲话 王浩.数理逻辑通俗讲话
数理逻辑部分习题答案:内容包括命题逻辑、一阶逻辑、集合及其运算、等部分的定义、定理、习题与解答
中山大学知名教授的讲义。...帮你学习数理逻辑。。。中山大学知名教授的讲义。。。帮你学习数理逻辑。。。中山大学知名教授的讲义。。。帮你学习数理逻辑。。。中山大学知名教授的讲义。。。帮你学习数理逻辑。。。
这是去屈婉玲版离散数学三分册之一的:离散数学 第一分册:数理逻辑
哈工大数理逻辑的课后答案,帮助学习学妹完成作业哦,仅供参考。 哈工大数理逻辑的课后答案,帮助学习学妹完成作业哦,仅供参考。
数理逻辑简要版,图文并茂,容易理解
莫绍揆,数理逻辑初步,数理逻辑通俗教材,数理逻辑通俗教材。
数理逻辑基础 数理逻辑基础 数理逻辑基础
国防科技大学,数理逻辑,考研考博用,电商网站都没这本书了。
作者: 汪芳庭 出版社: 中国科学技术大学出版社 出版年: 1990年9月 页数: 273
北京大学数理逻辑讲义 2018版 数学科学学院林作铨老师班
王老师的经典之作,可以认真研读,尤其是关于独立性的证明,对数理逻辑的发展有清晰的解释
中大数理逻辑教案-不错的数理逻辑教案。。
清华出的 数理逻辑与集合论,计算机专业研究生基础课。这本很精简,不错。
本书系统地介绍了逻辑演算,模型论和证明与反驳等数理逻辑的基本内容。全书分为五章,选材时充分考虑了适应逻辑系统的特征和计算机科学的要求_第一章介绍了形式系统的定义,结构及基本概念。第二章介绍了命题逻辑...
北京大学离散数学教材 数理逻辑部分 王捍贫