当前课程知识点：软件理论基础 > 第一章 基础知识 > 1.4 证明方法 > Video
欢迎同学们来到《软件理论基础》Mooc课堂
现在介绍第四节 证明方法
介绍这门课
一些常用的证明方法
包括演绎证明、数学归纳法
反证法、鸽巢原理
首先，演绎证明
演绎证明是前提到结论
什么是前提呢？
已知的命题
通过前题或者假设
由前提推导的命题称为结论
一个证明过程
是由命题推理，得到一些序列
其中的每一个命题，或者是已知的
或者由前面的证明得到的命题
演绎证明
明显的一个特征是：
“如果……，则……” 或者是“If、Then”
“如果”部分作为已知命题
“则”这部分作为结论
譬如，如果 x+y=1
则 x^2 - y^2 = x-y
这是前提
这是要证明的结论
怎么证明呢?
第一步，x^2 - y^2, 用因式分解
得到 (x+y)×(x-y)
作为已知结论
这是因式分解
另外，（x+y）= 1，是我们给的前提
通过 （1）和（2）
得到了 x^2 - y^2 = x - y
这是利用演绎证明得到的
演绎证明有一种：If and only if
也叫“当且仅当”
要证明“当且仅当”
就要证明下面这两个命题
第一是：If A 则 B
第二是：If B 则 A
例题
假设 R 和 S 都是集合
要证明 R 包含在 S 中
实际上要证明 R 中任何一个元素
一定属于 S
证明了这一点，则 R 包含在 S 中
如果证明 R = S
就要证明
第一：R 中任何一个元素
属于 S 的
第二：证明 S 中任何一个元素
也属于 R 的
如果这两个命题都证明了，R 就等于 S 了
第二个证明方法是数学归纳法
数学归纳法
是从有限到有限
或者有限到无限的证明方法
也就是找规律
归纳法包含：归纳基础、归纳假设
归纳推导三个步骤
假设命题 P1，P2，P3，……，等等
这命题序列
基础：P1 为真
假设：n，n 大于等于 1
Pn 为真
证明：要推导 P(n+1) 也为真
如果完成这证明
就得到结论：
任意的 i，pi 一定为真
数学归纳法另外一种形式
给定任意正整数 n
要证明 P(n) 成立
首先我们要证明在 0 时
P(0) 是成立的
然后，对任意的 k 小于 n
假设 P(k) 成立
要证明 P(n) 也成立
如果证明了这些
那对任意的 n，P(n) 是成立的
这两种归纳法是等价的
下面介绍数学归纳法的另一种
互归纳法
假设有性质P1、P2、……、Pm
要证明其中的一个，譬如 P1(n), 成立
考虑 P1、P2、……、Pm
它们联合起来的命题 H(n)
如果证明 H(n) 比证明 P(1) 容易些
很多情况下,是有这样的
单独证明P1，有时很难
直接证明 H(n) 可能简单
那我们就证明 H(n) 是成立的
证明了 H(n) 成立
说明P1、P2、……、Pm 都是成立的
当然就证明 P1 成立
在数学归纳法
还有一种：结构归纳法
结构归纳法
假设集合 S 上有结构 f
要证明 S 中任何一个元素 x
它满足性质 P
首先，证明 S 中存在元素 a
是满足性质 P 的
然后，假设 a1、a2、……、an 是 S 中的元素
都满足性质 P
要证明 a1、a2、……、an 在这个结构
得到的元素在 S 中
而且它也满足性质 P
这叫做结构归纳法
往往在结构是归纳定义时
它的结论用归纳法证明
例子
定义算术运算
算术运算用归纳定义
第一，基础
任意的数字或者字母，也就是变量
它们都是算术表示
接下来，归纳
如果 P 和 R 是算术表示式
则 P+R、P×R、（P）也是表示式
这定义就是一个归纳
这里每一个表示
依赖于前面的一些定义
例如，单个数 1、数 2
单个变量 x 、y
都是表示式
另外，1+x、(x+y)、2×(1+x)
根据定义，都是表示式
再看例子
S 是刚才给出的
算术表示式的集合
则每个算术表示式
根据刚才的定义
左括号和右括号
数目一定是相等的
要证明它
刚才的例题
给出的算术表示式，它有一个结构
这结构是归纳定义的
证明这个结论
就用结构归纳法
证明：空串
它的左括号、右括号个数等于 0
是相等的
假设 x，y 都是 S 中的元素
它们的左括号、右括号是相等的
根据刚才的结构
（x）加一对括号
它的左括号、右括号数目都是 m+1了
xy，这是连接运算
后面要介绍的
左括号、右括号
大家可以验证
都是为 m+n
根据刚才的结构
可以知道
S 中的任何一个算术表示式
它的左括号、右括号是相等的
再介绍一个证明方法，反证法
反证法，用到原命题与逆否命题是等价的
结论
假如 A 成立
则 B 成立，这是原命题
跟它等价的是
如果 B 不成立，则 A 一定不成立
这两个命题是等价的
有时候，证明原命题很困难
证明它的逆否命题往往简单一些
那就证明它的逆否命题
例子
要证明根号 2 是无理数
直接证明根号 2 是无理数
是很难的
可以否定这个结论
假设根号 2 是有理数
有理数可以表示为 n/m
n 和 m 是没有公因数的整数
下面证明这个结论不成立
假如根号 2 表示为 n/m
两边平方，就得 2m^2
等于 n^2
我们看
n^2 可以表示成 2m^2
说明 n 的平方是偶数
n 的平方是偶数，那 n 一定是偶数
因为奇数的平方不可能是偶数
所以，n =2k
n = 2k
n^2 = 4k^2
也就是 2m^2 = 4k^2
这两边同除 2
得到 m^2 = 2k^2
由此得到 m^2 是偶数了
也就是 m 是偶数
n 是偶数，m 也是偶数
说明 n 和 m 有一个公因子 2
跟开始假设 m 和 n
没有公因数矛盾
这个矛盾就证明了
开始假设“根号 2 是有理数”是不正确的
下面介绍另外一种证明方法
鸽巢原理
假设有 n+1 只鸽子
而巢穴或者笼子只有 n 个
鸽子都放进这些笼子里
可以看出，至少有一个笼子
放两只或者两只以上的鸽子
也可以用这叙述
如果有 n+1 个物体，放在 n 个盒子里
全部放进去
那至少有一个盒子要放
两个或者更多的物品
这个原理也叫抽屉原则
这个原理虽然简单
有时可以解决一些复杂的问题
看例子
假设有五个点
放在边长为2厘米的正方形中
则至少有一对点
它们的距离小于或等于根号 2
直接去证明，比较困难
通过鸽巢原理
怎样呢？
把这个正方形
分成四等份的正方形
因为是五个点
四个等份的正方形中
至少有两个点
落在同一个正方块里
这两个点，可以验算
对角线的距离小于或等于根号 2
那么，我们证明了
有两个点的距离不超过根号 2
通过鸽巢原理，就解决这个问题
这节内容介绍到这里
谢谢大家！
-1.1 概要
--第一节
-1.2 数学基础
--Video
-1.3 图
--Video
-1.4 证明方法
--Video
-1.5 语言基础
--Video
-1.6 语言运算
--Video
-习题--作业
-2.1 确定有限自动机的概念
--Video
-2.2 确定有限自动机的定义
--Video
-2.3 扩展转移函数
--Video
-2.4 正则语言
--Video
-2.5 DFA构造
--Video
-习题--作业
-3.1 非确定有限自动机的概念
--Video
-3.2 e转移
--Video
-3.3 非确定有限自动机的定义
--Video
-3.4 扩展转移函数
--Video
-3.5 等价性证明
--Video
-3.6 文本搜索
--Video
-习题--作业
-4.1 单一终结状态的NFA
--Video
-4.2 正则语言的运算性质
--Video
-4.3 正则表示和语言
--Video
-4.4 正则表示和正则语言
--Video
-4.5 正则语言的同态
--Video
-4.6 正则表示的代数定律
--Video
-习题--作业
-5.1 文法
--Video
-5.2 线性文法
--Video
-5.3 正则文法与正则语言
--Video
-5.4 自动机的积
--Video
-习题--作业
-6.1 基本问题
--Video
-6.2 泵引理
--Video
-6.3 非正则语言的判定 1
--Video
-6.4 非正则语言的判定 2
--Video
-6.5 DFA的优化 1
--Video
-6.6 DFA的优化 2
--Video
-习题--作业
-7.1 上下文无关文法
--Video
-7.2 规约和推导
--Video
-7.3 语法分析树
--Video
-7.4 规约、推导和语法分析树之间的关系
--Video
-7.5 上下文无关语言
--Video
-习题--作业
-8.1 CFG的应用
--Video
-8.2 CFG的转化
--Video
-8.3 文法二义性
--Video
-8.4 二义性的消除方法
--Video
-8.5 CFG的构造方法
--Video
-8.6 CFG的构造实例
--Video
-第八章 CFG的应用与文法的二义性--习题
-9.1 PDA介绍
--Video
-9.2 PDA的定义
--Video
-9.3 PDA的即时描述
--Video
-9.4 PDA的语言
--Video
-9.5 PDA与CFG的关系
--Video
-习题--作业
-10.1 确定下推自动机
--Video
-10.2 DPDA与其他语言的关系
--Video
-10.3 终态型DPDA和空栈型DPDA
--Video
-10.4 消除无用符号
--Video
-10.5 消除e产生式
--Video
-10.6 消除单一产生式
--Video
-10.7 CFG的化简与Chomsky范式
--Video
-习题--作业
-11.1 CFL的必要条件
--Video
-11.2 CFL的Pumping引理
--Video
-11.3 CFL的闭运算性质
--Video
-11.4 CFL的同态性质
--Video
-11.5 CFL的交运算
--Video
-11.6 CFL的判定性质
--Video
-习题--作业
-12.1 图灵机的介绍
--Video
-12.2 图灵机的定义
--Video
-12.3 图灵机的即时描述
--Video
-12.4 图灵机的计算
--Video
-12.5 图灵机的编程技术
--Video
-习题--作业
-13.1 Turing理论
--Video
-13.2 图灵机带的扩展
--Video
-13.3 图灵机移动的扩展
--Video
-13.4 受限图灵机
--Video
-13.5 图灵机与其他自动机
--Video
-习题--作业
-14.1 图灵机编码
--Video
-14.2 对角线语言与通用语言
--Video
-14.3 图灵机语言的性质
--Video
-14.4 判定问题和语言
--Video
-14.5 计算复杂性问题
--Video
-第十四章 不可判定问题--习题
-15.1 时间自动机
--Video
-15.2 Buchi自动机
--Video
-15.3 软件形式化验证
--Video
-15.4 模型检测方法
--Video
-15.5 M3C模型检测系统
--Video
-习题--作业
-期中考试
