`
somefuture
  • 浏览: 1089064 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

数理逻辑之 数学归纳法

 
阅读更多

说道数学归纳法,大家并不陌生。

这一节先来回顾一下我们似曾相识的归纳法,然后用它解决一个问题。

 

先来回忆一个小故事:高斯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),又分别增加了一个左括号和右括号。所以Θ依然有相同的左括号和右括号。

得证。

 

这里的证明需要注意的是,不能和上一题证明一样直接某一个高度的结果。因为合式公式的语法子树高度一般不相等。

0
1
分享到:
评论

相关推荐

    数学归纳法讲座

    同时,它也启示了其他形式的归纳推理,例如现代归纳法,虽然它在逻辑上更为宽松,不具有数学归纳法的确定性,但依然在概率论和统计学中扮演着关键角色。 数学归纳法的研究和教学是数学教育的一个重要组成部分。通过...

    国家集训队论文 数学归纳法与解题之道

    ### 国家集训队论文 数学归纳法与解题之道 #### 引言 本文源自于中国国家集训队的论文,主要探讨了数学归纳法及其在算法设计中的应用。作者张昆玮通过深入浅出的方式,不仅阐述了数学归纳法的基本原理,还结合具体...

    数理逻辑,王兵山,国防科技大学

    数理逻辑是数学的一个分支,主要研究形式系统的结构、性质和推理规则。它结合了数学、哲学和计算机科学,是理论计算机科学、人工智能和逻辑编程的基础。国防科技大学的数理逻辑课程,对于考研和考博的学生来说,具有...

    离散数学课后答案 数理逻辑学习指导语习题解答

    根据提供的标题、描述以及部分上...综上所述,数理逻辑不仅是离散数学的重要组成部分,也是现代计算机科学不可或缺的理论基础之一。掌握好数理逻辑不仅能帮助我们更好地理解计算机工作的原理,还能提高解决问题的能力。

    面向计算机科学的数理逻辑习题答案

    3. **证明方法**:数理逻辑中常用的证明技巧包括直接证明、反证法、归纳法等。习题可能会要求学生利用这些方法来证明一些简单的定理或结论。 4. **模型论与证明论**:这两个领域涉及到数理逻辑的更深层次内容,比如...

    哈工大数理逻辑课后答案

    数理逻辑是计算机科学、数学和哲学等领域的重要基础学科,它研究推理的结构和形式,以及它们与真实世界的关系。哈工大的数理逻辑课程旨在深入理解这一领域,通过课后习题的解答,学生可以巩固理论知识,提高逻辑推理...

    数理逻辑答案

    数学归纳法是一种强有力的证明技巧,它分为归纳基础(基础步骤)和归纳假设(归纳步骤)两部分。通过这两个步骤,我们能够证明对于任意给定的自然数k,某个性质都成立。 最后,书中还提供了关于逻辑命题变换的练习...

    2020高中数学 2-3数学归纳法同步检测 新人教B版选修2-2.doc

    数学归纳法是一种证明数理逻辑中命题的有效方法,尤其在处理与自然数相关的序列或递归性质时显得尤为关键。它基于两个步骤:基础步骤和归纳步骤。基础步骤确保命题对于某个初始值(通常是1)成立,归纳步骤则是假设...

    哈工大数理逻辑2003-2004试卷+答案

    哈尔滨工业大学(哈工大)作为中国顶尖的理工科大学之一,其数理逻辑课程的教学质量和深度一直备受赞誉。 这份"哈工大数理逻辑2003-2004试卷+答案"资料包,包含两部分:数理逻辑2003-2004 B卷的答案和数理逻辑试题...

    高等数理逻辑2018

    高等数理逻辑是计算机科学和数学的一个重要分支,它研究逻辑推理系统、形式语言和证明理论,为计算机程序设计、人工智能、理论计算机科学等领域提供了坚实的理论基础。2018年的高等数理逻辑课程可能涵盖了以下核心...

    数理逻辑(讲义)

    此外,可数无限集的概念,如自然数集合N,以及数学归纳法,是数理逻辑中证明和构造的基础工具。 在数理逻辑中,函数也可以递归定义,这允许我们构造和理解复杂的功能关系。递归定义通常包含初始条件和递推步骤,是...

    离散数学数理逻辑部分

    6. **推理规则与证明方法**:在数理逻辑中,我们学习如何利用推理规则如归纳法、反证法、归谬法等进行证明。这些方法帮助我们从已知事实推导出新的结论,是逻辑思维和问题解决的关键工具。 7. **模型论**:模型论...

    版高考数学一轮复习 核心素养测评三十六 直接证明与间接证明、数学归纳法 理 北师大版 试题.doc

    这些知识点涵盖了高中数学一轮复习中的重要证明方法,包括直接证明、间接证明(反证法)以及数学归纳法的运用,对于理解数理逻辑和解决实际问题至关重要。在学习过程中,学生需要掌握这些方法的原理和步骤,并能灵活...

    2017_2018学年高中数学第六章推理与证明6.3数学归纳法1分层训练湘教版选修2_2

    总的来说,数学归纳法是高中数学中至关重要的一部分,它提供了一种系统化证明数理规律的方法,对于培养逻辑思维和解决问题的能力具有重要意义。理解和熟练掌握数学归纳法对于进一步学习高级数学概念至关重要。

    2021届高考数学一轮复习第一部分考点通关练第五章不等式推理与证明算法初步与复数考点测试39数学归纳法含解析新人教B版

    标题和描述中提到的知识点主要聚焦于高中数学的数学归纳法这一主题,这是在解决数理逻辑和证明问题时常用的一种方法。数学归纳法是一种用于证明对于所有自然数都成立的命题的有效工具。 数学归纳法的基本步骤包括两...

    2017_2018学年高中数学第六章推理与证明6.3数学归纳法2分层训练湘教版选修2_2

    标题和描述中提到的是高中数学课程中...通过这些例子,我们可以看到数学归纳法在证明等式、不等式、数列性质以及几何体性质等方面的重要作用,它是一种强大的逻辑工具,能够帮助我们理解并证明一系列数理问题的普遍性。

    数理逻辑基础习题解答

    这一关系的证明采用了数学归纳法,分为三个步骤进行论证: - **基本情况**:当命题词数量\(m=1\)时,显然没有连接词,即\(n=0\),满足上述关系。 - **递推情况**:假设对于所有小于等于\(k\)的命题词数量,上述关系...

    面向计算机科学的数理逻辑:系统建模与推理(英文版)

    - **数学归纳法**:为了验证逻辑系统的正确性,本书引入了数学归纳法这一强大的工具。 - **声效性**:这部分讨论了命题逻辑系统的声效性,即所有可证明的公式都是有效的。 - **完备性**:紧接着,书中探讨了命题逻辑...

    数理逻辑入门 A Friendly Introduction to Mathematical Logic

    归归纳是数学证明中常用的一种技巧,在本节中作者通过具体例子向读者展示了如何运用归纳法来证明某些命题的真实性。这部分内容对于培养读者的逻辑思维能力和推理技巧至关重要。 ##### 1.5 句子 句子是指不含自由...

Global site tag (gtag.js) - Google Analytics