Pages

2011年5月20日 星期五

[數學] Structural Induction

以下是我學習Structural Induction過程的一些想法:
Structural Induction是一種證明遞迴定義的方法。而許多遞迴定義根據我目前的學習,都是一個非常原始的初始條件,加上一個類似國中高中學過的若k成立則k+1也成立於這個遞迴定義中。

例如正整數定義就是:(1) 0是正整數。
                                        (2) 如果x屬於正整數,則x+1是正整數。
所以"structural"這個字我在這裡理解為:已架構觀點來做歸納法。這種"架構",就是上述所謂的"初始條件"加 "k成立則k+1成立" 之類的架構。
而且這種架構特別對"連續"的東西很容易去定義。譬如說整數,字串,樹等等。例如說電腦問使用者:"什麼是2的倍數?"
使用者可以回答:(1) 2是2的倍數。  (2)如果有一個數是2的倍數,那麼這個數乘以2也是2的倍數。
這樣電腦就知道:"喔!原來2,4,6,8…都是2的倍數。"
所以目前我覺得這種Structure應該沒有什麼困難的地方,只是一種表示法而已。
所以用Structural Induction來證明遞迴定義時,以我目前學習的結果,我會把遞迴定義看成:(1) A符合條件S  (2) 若B符合S,則跟B有關係的某個東西C也會符合S。
然後把這兩點證明出來,就等於使用Structural Induction完成證明。
以上是我的一些小想法。
                         by Uncle

沒有留言:

張貼留言