1.3 证明和证明的方法

形式语言和有限自动机有很强的理论性，许多论断是以定理的形式给出的，而定理的正确性是需要进行证明的。

形式语言和有限自动机理论中定理的证明，大多使用反证法和归纳法进行。

1.3.1 反证法

反证法也称为归谬法。利用反证法证明一个命题时，一般步骤为：

1）假设该命题不成立。

2）进行一系列的推理。

3）如果在推理的过程中，出现了下列情况之一：

（1）得出的结论与已知条件矛盾；

（2）得出的结论与公理矛盾；

（3）得出的结论与已证过的定理矛盾；

（4）得出的结论与临时的假定矛盾；

（5）得出的结论自相矛盾。

4）由于上述矛盾的出现，可以断言“假设该命题不成立”的假定是不正确的。

5）肯定原来的命题是正确的。

例1.6 反证法例子。

利用反证法证明是无理数。

证明：假设不是无理数，那么是有理数；则可以记为 而且n和m是互质的，即n和m的最大公约数为1。

则

n2=2m2

所以，n是偶数。令n=2k，则

（2k）2=2m2

4k2=2m2

2k2=m2

所以，m是偶数。

n和m都是偶数，而n、m的最大公约数为1，矛盾。所以，假设不成立，是无理数。

思考：18是完全平方数吗？

1.3.2 归纳法

归纳法就是从特殊到一般的推理方法。

归纳法分为完全归纳法和不完全归纳法两种形式。

完全归纳法是根据一切情况的分析而做出的推理。由于必须考虑所有的情况，所以得出的结论是完全可靠的。

不完全归纳法是根据一部分情况做出的推理，因此它不能作为严格的证明方法。

在形式语言与有限自动机理论中，大量使用数学归纳法来证明某个命题。

数学归纳法可以使用“有限”步骤来解决“无限”的问题。

数学归纳法的原理为：

假定对于一切非负整数n，有一个命题M（n）：

（1）M（0）为真。

（2）设对于任意 k≥0，M（k）为真；若能够推出 M（k + 1）为真，则对一切 n≥0，M（n）为真。

因此，在使用数学归纳法证明某个关于非负整数n的命题P（n）时，只需要证明（1）、（2）两点即可。第（1）步称为归纳基础，第（2）步称为归纳步骤。第（2）步中“设对于任意的k≥0， M（k）为真”称为归纳假设。

在实际应用中，某些命题P（n）并非对n≥0都成立，而是对n≥N（N为大于0的某个自然数）成立，此时，也一样可以使用该归纳法。具体步骤为：

假定对于一切非负整数n，有一个命题M（n）：

（1）M（N）为真。

（2）设对于任意k≥N，M（k）为真；若能够推出M（k + 1）为真，则对一切n≥N，M（n）为真。

1.3.3 递归的定义与归纳证明

递归定义提供了集合的一种良好定义方式，使得集合中的元素的构造规律较为明显，同时给集合性质的归纳证明提供了良好的基础。

递归定义集合的步骤如下：

（1）基础：首先定义该集合中的最基本的元素。

（2）递归：若该集合的元素为x1,x2,x3,…，则使用某种运算、函数或组合方法对这些元素进行处理后所得的新元素也在该集合中。

（3）有限性：只有满足（1）和（2）的元素才包含在集合中。

归纳方法证明递归定义集合的性质的步骤如下：

（1）基础：证明该集合中的最基本元素具有性质P；而且使得该集合非空。

（2）归纳：证明若该集合的元素x1, x2, x3,…具有性质P，则使用某种运算、函数或组合方法对这些元素进行处理后所得的元素也具有性质P。

（3）根据归纳法原理，集合中的所有元素也具有性质P。

例1.7 Fibonacci数组成的集合的定义。

Fibonacci数组成的集合为{0,1,1,2,3,5,8,13,21,34,55,…}

按照下列步骤生成该集合中的所有元素：

（1）基础：0和1是该集合的最基本的两个元素；

（2）归纳：若m是第i个元素，n是第i+1个元素，则第i+2个元素为n+m，其中i≥1；

（3）只有满足（1）和（2）的数，才是集合的元素。

例1.8 括号匹配的串所构成的集合的定义。

该集合是指所有左括号和右括号相匹配的串的集合，例如（）、（（））、（）（）等都是该集合的元素；而）（、（（）等就不是该集合的元素。

按照下列步骤生成该集合中的所有元素：

（1）基础：（）是该集合的最基本的元素。

（2）归纳：若 A是该集合的元素，则（A）是该集合的元素；若 A和B是该集合的元素，则AB是该集合的元素；

（3）只有满足（1）和（2）的串，才是集合的元素。