离散数学是计算机科学的基础理论，离散结构的基础知识和逻辑思维的形式化是信息技术类学生的基本功，离散数学的基本概念是理科专业学生进行信息类课程学习的重要基础。 本课程介绍计算机科学和信息技术理论基础的概念和思想方法，介绍数理逻辑、集合论、图论、抽象代数和形式语言与自动机等各部分的基本概念，介绍离散数学基本概念和空间信息技术之间的联系与结合，培养学生理解和掌握离散数学基本概念，采用形式化方法分析问题，并能自觉运用逻辑分析、结构层次分析和同构类比等思想方法解决问题的能力。
40-归纳原理
Loading...
来自 Peking University 的课程
离散数学概论 Discrete Mathematics Generality
155 个评分
从本节课中
集合论：集合代数
与讲师见面
陈斌副教授
北京大学
[音乐] 嗨，你好！欢迎回来，那么前面我们说了这个归纳
法，归纳法定义这个集合，而且我们顺便用归纳法
定义出自然数来了，你是不是觉得归纳法特别的强大
那么我们当然归纳法定义出来的集合，它是一个很好的一个集合
那么有了这个归纳定义之后，我们实际上可以用来做很多的事情 比如说这个归纳原理，那么假设一个集合A，它是通过归纳
定义所定义出来的集合，也就是它通过基础条款、 归纳条款以及
终极条款，然后规定出来的这么一个集合的话 那么，如果我想证明A当中所有的元素都具有某种性质P
所谓的具有性质P，也就是说，每一个元素放在这个
P的谓词里面，它访问都是为真，对吧，也就是说任意x 只要x属于A，它就必然蕴含着P(x),就P(x)也为真
那么如果想要证明这个，那么有归纳定义 所定义出来的集合就可以用归纳原理来做如下的证明
首先证明第一，证明归纳基础，就是针对这个归纳定义当中
的基础条款，我们来证明说基础条款当中所涉及的所有的这些初始
的元素，都使得这个P为真，每一个元素x。
，x₁他都会使 P为真，它就变成了命题了，P为真，这是归纳基础
然后归纳推理，也就是说我们要证明，想办法证明这个归纳条款，第二个条款，归纳条款是能够
保持这个性质P，那所谓的保持性质P呢，就是说
我先假设归纳条款当中已经确定的元素x 它是能够使得P(x)为真了
在这个假设的前提下，然后呢，证明用归纳条款当中的这个操作g
因为归纳条款总是从已知的元素 用一个映射然后变成一个新的元素，就是有一个规则生成器
新的元素，那么我们把这个生成的过程抽象成一个什么，抽象成一个操作
把这个操作叫一个名字，叫作g，那么它实际上就是一种函数了 它是一种函数，函数可以把x映射成另外一种别的东西
那么它生成的g(x)仍然具有性质P 也就是说P(g(x))为真，如果证明了这两个
有归纳基础，有归纳推理，那么我们就可以完成这个归纳
那么依据这个归纳原理，我们实际上可以去证明我们已经定义过的一些
用归纳定义的一些集合，它具有某种性质
我们曾经提到过，在数理逻辑里面这个命题公式也是用归纳定义来定义的，对吧
那么我们就试着说，看看命题公式里面它有一些什么性质，我可以用归纳原理来进行证明呢
那么我们来看看这个例子，命题公式当中的左括号的数量等于右括号的数量
当然，这个我们可能从来没有想过这会有什么问题 因为我们潜意识里头认为，括号嘛，它总是成对出现的
既然成对出现，那它肯定就会相等，对吧 当然，你这种话呢，并不严密
我们把它变成这个数学语言，变成符号，形式化的证明来看一看
我们用归纳原理来证明，因为命题公式本身它是由 归纳定义所对应的集合，所以呢，我们可以用归纳原理来证明它
那么我们假设这个有两个函数L和R
L[A]呢就返回左括号的数量，R[A]呢就返回公式A的右括号的数量
那么我们最终要证明任何一个公式A L[A]都等于R[A]，是吧，那先我们看这个归纳基础
在命题公式当中，它的这个基础条款是 命题常元、
命题变元，这些都是命题公式 那么我们发现命题常元和命题变元P、
Q、 R、 S这些东西，它本身不带任何的括号，所以呢 它的左括号等于0，右括号也等于0，那当然自然就会相等
那归纳基础我们成立了，第二个呢，就是归纳推理
归纳推理我们假设因为它是，我们回忆一下命题公式这个归纳定义 第二个这个递推规则就是说
假设A、 B是公式的话，那么A蕴含B
加括号也是公式，A加上一个否定连接词加括号也是公式 对吧，那么所以呢，我们从假设
A和B这两个，它既然已经是命题公式了，那么我们假设呢 它这个性质是成立的，也就是L[A]=R[A]
L[B]=R[B]，因为它是命题公式嘛 那好，我们来证明说，这个由A和B生成出来的这个新公式
它也符合这个左括号等于右括号的这个性质 那么我们先来看这个¬A加括号，那么¬A加括号的左边
它的左括号的数量是多少呢，它应该很明显 它是A的左括号的数量再加上1，因为它增加了一个左括号，对吧
那么L[A]既然等于R[A]，那么我们就可以写成等于R[A]加1
那么等于R[A]加1，那么R[A]加1又恰恰是这个R[(¬A)]
因为R[(¬A)]是A的这个右括号的数量再加上1
哎那么它们之间就相等，就架起这个相等的桥梁，所以我们证明的第一个
这也是意料之中的一件事情，那么第二个呢，我们看这个
蕴含，蕴含呢稍微复杂一点，因为它涉及到2个公式，那么我们也是从两头往中间来走
那么L[(A→B)]，那么它就等于A的左括号的数量加上B的左括号的数量再加上1
对吧，那么R呢，AB，A蕴含B，那么它也是
右括号的数量，A的右括号的数量加上B的右括号的数量再加1，因为多了一个右括号出来 然后呢，我们对比这2个式子
由归纳假设，归纳假设里头，L[A]=R[A],L[B]=R[B]
那么等量加等量，它还是等量，所以中间这个等号又终于
建立起这个桥梁，所以呢，L[(A→B)]它确实是等于R[(A→B)]的
是吧，那这样呢，我们就得出结论 对于一切的命题公式而言，左括号的数量就等于右括号的数量
这就是归纳原理所给我们带来的一个
强大的一个证明的工具，它可以证明用归纳定义所定义出来的集合
的每一个元素，不管是这个有限集合还是无穷的集合
它的每一个元素我不需要去挨个的去检验，它就能够具有某种性质P
