Name: Password: Sign in

本文在 署名-非商业性使用-相同方式共享 3.0 版权协议下发布, 转载请注明出自 kyleslight.net

[Lecture 7] 证明的方法与策略

(该节的证明方式将沿用上节的 非形式化证明

1 穷举与分情形证明

1.1 穷举证明

有些定理能够通过对少量例子进行测试来得到证明。

例如对于 「100 以内连续正整数是全幂数只有 89」这个命题,我们可以穷举出 100 以内的所有全幂数,例如我们找到了 「1,4,8,9,16,25,27,32,36,49,64,81,100」,那么通过观察这一系列数即可知道只有 89 满足要求,命题为真得证。

对于判断条件太多的情况我们可以借助计算机帮助判断,然而我们经常会遇到无法列举的情况,所以穷举证明对这类问题有局限。

1.2 分情形证明

分情形证明基于以下推理规则:

[(p1p2...pn)q][(p1q)(p2q)...(pnq)]

也即,所有分条件构成的析取式 p1p2...pn (假设 pp1p2...pn)的语句 pq 可由分别证明每个部分 piq 为真得到证明。

例如我们要证明 「n 为整数时 n2n」,可以分别讨论 n1n=0n1 三种情形,在每种情形下可由分条件为真推出结论为真,那么原命题为真。

1.3 不失一般性

可以预见到有些问题分情况讨论会产生非常多甚至无限种分条件,它们当中的绝大部分分条件的讨论过程非常相似,因而我们可以在证明完其中一个特殊的分条件后进行合理的一般化,这种一般化建立在其他分条件是该特殊条件的简单变换,即 不失一般性 ( WLOG ) ,就像下面这个例子:

证明: (x+y)r<xr+yr,其中 xy 为正实数,0<r<1

假设 x+y=1(此时是特殊情形),则 0<x,y<1,即有 x<xry<yr,所以 x+y=1 时:

(x+y)r=1=x+y<xr+yr

成立。

又考虑到当 x+y=t (此时是一般化情形),有 x/t+y/t=1,将 x/ty/t 替换掉特殊情境中的 xy,则有:

(1t)r(x+y)r=(xt+yt)r<(xt)r+(yt)r=(1t)r(xr+yr)

整理即有

(x+y)r<xr+yr

因而原命题成立

2 存在性证明

2.1 构造性的存在性证明

有时候我们需要证明类似于 xP(x) 这样的语句,我们可以直接举出在论域中能使 P(a) 为真的元素 a,这种存在性证明叫做 构造性的

例如要证明 「存在正整数可以用两种方式表示为立方数的和」,那么只要举出元素 1729,它满足 「1729=103+93=123+13」即可。

虽然这种证明方式过程很直接,但寻找到这样满足条件的论域中的元素有时候并没有人们想象的那么简单。

2.2 非构造性的存在性证明

不直接举出满足条件元素的证明方法即 非构造性 的,一种典型的方法是上节提到的 归谬法,即假设存在为假可推出一个矛盾式,那么原命题为真。当然还有其他的方式来完成非构造性存在性的证明,例如下面这个 Chomp 游戏 的例子:

Chomp 是两个人玩的游戏。游戏中所有的曲奇饼放在网格中,左上角的曲奇饼被毒化(不能吃)。两个玩家轮流每轮吃一块曲奇饼,要求该曲奇饼右边或下边的所有曲奇饼被吃掉。如果一方吃到毒化曲奇或者无曲奇饼可吃则另一方胜利。

enter image description here
Chomp

现在要证明,存在一种制胜策略能保证第一个玩家获胜。

以下是一种非构造性的存在性证明,假设第一个玩家为 P1,第二个玩家为 P2:

  1. 假设 P1 吃掉右下角的曲奇饼,那么存在两种可能:这是 P1 制胜策略的第一步;这是 P2 的制胜策略的第一步
  2. 如果是 步骤 1 中的后者,P1 采用 P2 制胜策略的第一步
  3. 循环这个制胜策略

由于步数的有限(例如 M×N 步),因而可以保证 P1 获胜

(值得注意的是,尽管我们使用非构造的方法证明了存在这样一种制胜策略,我们并没有找到它,事实上没人能够找到这样一种通用的方法)

3 证明策略

3.1 前推

一般情况下,如果一个语句是条件语句,那么我们将先尝试直接证明。当直接证明难以奏效的时候我们将采用间接证明与归谬法,虽然它们具体的推理策略不同,但它们都是根据构造一个永真式来达到 pq 的效果(这里的 pq 非实指),即从某个起点开始到达终点。这种推理策略叫做 前推

3.2 后推

然而有时候我们无法从正向思路上来找到从起点到终点的路径,例如我们要证明 q,我们无法找到从已知条件入手直接得到 p 导致无法开启下一步,这个时候我们需要考虑 后推,作为一种从结论入手的方式来启发我们寻找合适的 p,在知道 p 之后再顺向推理。

考虑下面这个问题:

假定 P1,P2 玩游戏,轮流从 15 个石头中每次取 1,2,3 块石头,取到最后一块石头赢得游戏。证明:无论 P2 怎么取,第一个开始游戏的 P1 能找到方法胜利。

直接顺向考虑是很难证明的,考虑从最后一步后推:

  1. 假设剩下 1,2,3 块石头,P1 能获胜,因而 P1 保证最后剩下 4 块石头给 P2 即可胜利
  2. 假设剩下 5,6,7 块石头,P1 能获胜(由第 1 步),因而 P1 保证最后剩下 8 块石头给 P2 即可胜利
  3. 假设剩下 9,10,11 块石头,同样的道理 P1 保证最后剩下 12 块石头给 P2 即可胜利
  4. P1 第一次取 3 块石头

只需要 P1 采取每次保证给 P2 留下 4k (在这个游戏中 k=1,2,3)块石头的策略就剩获得胜利,即先手必胜的策略存在,因而原命题为真


还存在很多关于 集合函数算法数论 的证明方法。当然,这些方法的说明将留给后续部分:)

Copyright (c) 2014-2016 Kyles Light.
Powered by Tornado.
鄂 ICP 备 15003296 号