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）的串，才是集合的元素。