德國一流大學教你數學家的思考工具,將問題化繁為簡!

2016-04-18 15:45

? 人氣

歸納原則

為了證明一堆有序物件當中的全部東西皆具有某種性質,可以先證明第一個東西有此項性質,然後再證明,若其中任意一個東西具有該性質,則下一個東西也有此性質。

[啟動LINE推播] 每日重大新聞通知

如果可以一件接著一件做,數學家就會一直做下去。─某面牆上的塗鴉智慧

推理法是一種邏輯推論,是從一般情況推導到特殊情況。歸納推理法和溯因推理法(逆推法)則是兩種非演繹推理法。下面這個具體的例子可以幫忙區別歸納、演繹及溯因推理法。

歸納推理法是從個別情況與結果來推導出規則。

情況:這些豆子是從這個布袋裡拿出來的。

結果:這些豆子是白色的。

規則:這個布袋裡的所有豆子都是白色的。

推就是要從世界上的模式和規律中,找出尚未觀察到的或是未知的事物。歸納的結果不一定非得是正確的,得出的僅是一個推論(這個布袋裡的所有豆子都是白色的),不一定要和前提一樣為真(從這個布袋中拿出來的豆子是白色的)。歸納推理僅是發現有可能的事實。我們隨時隨地會用到歸納推理。但是哲學家當中的懷疑論者反對歸納推理。一般來說,歸納推理法並未考慮所有的個別情況,因此某些未考慮到的情況有可能會與所做出的歸納互相矛盾。所以,歸納得出的結論在形式邏輯上並不被接受。

機率理論的邏輯

10% 的偷車賊是左撇子。所有的北極熊都是左撇子。因此如果您的車

被偷了,有10% 的機率是北極熊偷走的!!??─查普曼-可立(J. Chapman-Kelly)

除了日常生活上的實際運用之外,歸納推理還有一連串哲學考慮之下的上層結構。由哲學家古德曼(Nelson Goodman)首先提出,在此我們由龐士東(WilliamPoundstone)所改寫的一個例子,來看看使用歸納推理之後會發生什麼事情。有位珠寶商檢查一顆綠寶石。「又是一顆綠色的綠寶石。」他想。「這些年我看過不下上千顆綠寶石,每一顆都是綠的。」這位珠寶商因此得出一個假設:所有的綠寶石都是綠色的。這是個歸納推論,而且看似合理。

街上另外一邊也有一位同樣接觸過許多綠寶石的珠寶商。他是印第安巧克陶族(Choctau),只會說巧克陶語。從人類語言學的角度來看可以發現一件有趣的事,巧克陶語並不區分藍色和綠色,同一個詞可以同時用來表示兩種顏色。但在巧克陶語中,卻有okchamali(一種會發光的藍或綠)、okchakko(一種暗沉的藍或綠)之分。巧克陶族珠寶商說:「所有的綠寶石都是okchamali 的。」這也是一個歸納推論,同樣根據了他看過的上千顆綠寶石。

在同一條街上還有一位經驗同樣豐富,只會說一種稀有語言Gruebleen 的珠寶商。就如德語或巧克陶語,Gruebleen 這種語言也有自己對顏色的概念。Gruebleen 語沒有描述綠色的詞彙,但有一種被稱為grue 的特質(一個受到古德曼影響而產生的人造詞彙,由green 和blue 結合而成,另外還有bleen 這個詞)。所有具有grue 特質的東西,在2019 年12 月31 日午夜之前都是綠的,一過午夜就是藍的。而稱為bleen 的特質則是:在2019 年12 月31 日午夜之前是藍的,午夜之後變綠。如果要跟一個說Gruebleen 語的人,解釋我們所用的綠色一詞,可以跟他說:就是在2019 年12 月31 日午夜之前是grue,午夜之後是bleen 的那個東西。對於熟悉grue 和bleen 兩種概念、說Gruebleen 這種語言的人,「綠色」是一種聽起來十分人為的用語,他們對於這兩個顏色的定義,是以一個特定的時間點為參考點。也就是說,grue 在德語裡的解釋和綠色在Gruebleen 語裡的解釋是對稱的,所以我們沒有辦法說哪個語言在這方面更為基本。對那位說Gruebleen 語的珠寶商而言,目前所有的綠寶石全都是grue 的。

現在請各位想像一下,我們同時在三位珠寶商面前擺上一顆綠寶石,並問他們這顆綠寶石在2020 年的顏色為何。三個人異口同聲說,他們在執業多年來的經驗裡從來沒有看過一顆綠寶石會變色。德國珠寶商預測,眼前的綠寶石在2020 年還是綠的。巧克陶族珠寶商說,它的顏色會是okchamali。而說Gruebleen語的珠寶商表示,這顆綠寶石在2020 年是grue 的。但等一下!在2020 年,grue意指藍色。三位珠寶商與綠寶石接觸的經驗同樣豐富,而且都使用了歸納推理,但說Gruebleen 語的珠寶商做出的預測,卻與說德語的珠寶商恰恰相反。這個自相矛盾絕對不能毫無意義地被忽視:2020 新年時,上述的預測至少有一個是錯的。

math03.jpg
(圖/julisaustria@flickr)

演繹推理是把規則應用到個別的情況,來推導出結果。

規則:這個布袋裡所有的豆子都是白色的。

情況:這些豆子是從這個布袋裡拿出來的。

結果:這些豆子是白色的。

演繹推理的結果不容爭辯,也可以說一定是正確的。從形式邏輯看來,演繹推理的結果為有效的結論。在數學上,也可以盡量使用演繹推理原則的結構。但是嚴格來說,演繹邏輯推理並未擴充已知知識的數量,它不過是把已經知道的事物換個方式來表達。

溯因推理是從規則和結果來推導出個別情況。

規則:這個布袋裡所有的豆子都是白色的。

結果:這些豆子是白色的。

情況:這些豆子是從這個布袋裡拿出來的。

根據規則和結果所得的結論雖然十分有可能正確,但不一定必為真。嚴格說來,這其實是非常粗略的邏輯,因為得出的結論十分不確定,如果正確,頂多也是碰巧,而且也沒有任何其他可以佐證的證據。和歸納推理相比,不僅是量的差別,也是質的差別。透過溯因推理得出的結論,是建立在間接證據的猜測,推理出一個觀察結果的最佳解釋。這個結論有可能為真,因而得悉潛在的真相。日常生活中我們經常做出如此的推論,像是想證明嫌犯有罪的警探,或是要根據特定症狀來做出初步診斷的醫生,這些事務的本質裡也都存在著溯因推理的結論。

將以上幾種推理法分門別類過後,現在要介紹的完全歸納法(數學歸納法)就是我們的下一個思考工具。數學歸納法的概念,最早是在1654 年由巴斯卡(Blaise Pascal)建立起來的。一種只需要兩個步驟就可以檢驗眾多、甚至是無限多個命題的基本原則。只要其中的命題可以排序、且任何一個命題與前一個命題之間存在著特定關係,歸納法可能就會適用。我們在思考時經常選擇採用歸納原則,譬如要證明一個關於所有自然數的命題是否成立。為了證明一個取決於n的命題A(n) 對任何一個自然數n 都成立,我們先將那些使得命題A(m) 為真的自然數m 所成的集合稱為M。然後我們必須考慮M 是所有自然數1、2、3、……的集合。一個可能的進行方法是分成兩個邏輯步驟:第一步先證明,A(1) 是真確的命題,而第二步是驗證,若對於任意自然數m,從A(m) 成立可推導出A(m + 1)也為真,那麼這個命題對於下一個自然數也成立。因為聽起來還是十分抽象,所以我想把這個基本結構具體解釋一下。

如果已知某個取決於n、而要證明對於所有n 皆成立的命題(例如20 + 21 +22 + … + 2n = 2n+1 − 1),首先可證明它對n = 1 為真(歸納起始點),再來,對任意自然數m,若從n = m 時命題會成立可以推導出n = m + 1 時命題也會成立(歸納步驟),那麼這個命題對所有的自然數n 皆成立。論證過程的兩個部分同樣重要。沒有歸納起始點的歸納步驟,以及沒有歸納步驟的歸納起始點,都是不完備的,無法證明所有自然數n 的情形。

透過爬樓梯的過程的比較,可以幫助我們更了解數學歸納法。成功的爬上樓梯包含兩個層面。第一必須知道如何爬上第一層階梯。其次必須找出一個從某一階爬到下一階的方法。一旦這兩關都會了,那麼便可以登上第一階,然後從第一階爬上第二階、從第二階爬到第三階等等,而可登上任何一階。如果在第一階就失敗,或是無法從第一階到下一階的話,整個過程就進行不了。

數學家將歸納原則內化了,遠遠就能察覺這個方法是否能、從哪裡、該如何成功用來解決某個特定問題。

不懂數學的門外漢卻對這個方法保持著懷疑的態度。偶爾可以聽到他們反對數學歸納法的論點,例如有待證明的地方已被當成歸納步驟的前提。事實並非如此。在歸納步驟裡證明的是一個條件語句:若一個要被證明的命題在特定情況下是對的,則對下一個情況也是對的。但如果找不到這種情況,那麼前後情況之間的連結就沒有邏輯意義了。這是條件推論的中心思想之一。

然而條件推論也有它的陷阱。所以我們先來談談這種類型的推論及伴隨而來的陷阱。

許多人在條件推論上產生適應困難,這通常是發生在處理條件句時。一個條件句是由兩個敘述P 與Q 組成,兩者以「若⋯⋯則⋯⋯」的結構合成一句:若P,則Q。譬如:「如果有人做了一場旅行,那他一定有故事可講。」或是:「如果他們還沒死的話,那麼就會從此過著幸福快樂的生活。」

條件推論的有效變體在形式邏輯上稱為肯定前件(Modus ponens),具有以下結構:從蘊涵關係「若P 則Q」以及P 為真,可推得Q 也為真。因此,肯定前件是由前提(「某人去旅行」)推斷出結論(「他一定能講些東西」)。

這是簡單的條件推論形式,通常連學齡前兒童都能大致掌握。

第二種複雜許多的條件推論形式為否定後件(Modus tollens),具有以下結構:從蘊涵關係「若P 則Q」以及Q 的反面為真(非Q),可推斷出P 的反面為真(非P)。由此看來,否定後件是從否定的結論(「他沒有東西能講」)推理出否定的前提(「他沒去旅行」)。

儘管多數孩童都能掌握肯定前件這種推論形式,有些成年人在碰到否定後件這種推論形式時,卻出現問題,錯誤地應用在:從蘊涵關係「若P 則Q」以及Q為真,得出P 也為真。這是無效的結論,用剛才所舉的例子來看就會明白,不是每個有故事可講的人,之前都必定旅行過。其他的活動也能提供故事題材。

在此情況下其他可以想到的推論形式,即從蘊涵關係「若P 則Q」推導出「若非P 則非Q」,邏輯上來說也不成立。由剛剛的例子,就會是:「沒有旅行的人,就沒有東西好講」,而這是錯的。有些人雖然沒旅行,還是有話題可以講。

為了感受一般人在否定後件上遇到的困難,我們來看看華森(P. C. Wason)在1960 年代提出的選擇任務實驗。華森在受試者的面前放了四張卡片,每張卡片有一面是英文字母,另一面是數字。同時他告訴他們一項規則:「如果一張卡片有一面是母音,它的另一面必定是偶數。」受試者的任務就是要決定應該翻開四張卡片當中的哪幾張,來驗證這個規則。華森的四張卡片如下:

math01.jpg
華森的選擇任務實驗。(圖/漫遊者文化)

華森實驗受試者的作答整理如下:

作答           答案頻率

A 和4            46 %

A                  33 %

A、4 和7        7 %

A 和7             4 %

其他             10 %

如果我們將「卡片的一面是母音」這句話簡寫成P,把另一句「卡片的另一面是偶數」簡寫成Q,那麼便能將剛剛所提的規則寫成蘊涵關係「若P 則Q」。印著A 的卡片,代表的是屬於蘊涵關係的肯定前件(前提P 為真),而印著7的卡片則代表否定後件(結論Q 不正確)。為了驗證這項規則,必須檢查肯定前件和否定後件是否有效。因此我們必須將A 卡和7 卡翻面。至於剩下的D 卡和4 卡,代表的非P 和Q,不管它們另外一面印的是什麼,都不會影響規則的正確性。

華森選擇任務的實驗結果可以得出以下解釋:絕大多數的受試者都知道如何運用肯定前件,因為他們選擇翻開A 卡,但只有少數人正確運用否定後件。

否定後件之所以失敗,通常在於直接從結果來推斷原因,這當然站不住腳。結果的發生,頂多只會為原因增加說服力。會錯誤使用否定後件,可見人類傾向用非演繹式的推理。大體而言,我們可以將這種與生俱來的思考方式這麼總結:如果從我的假設P 可以預測出事件Q,又如果根據既有的知識程度,事件Q 的發生機率很低,那麼當事件Q 發生了,我的假設P 就變得更可信。換句話說,我們觀察到不尋常的事件Q。但如果P 為真,那麼Q 就是理所當然之事。由於如此,當Q 發生時,就有理由說P 也為真。因此,溯因推理的規則會導致假設P變得更具說服力。這是一種合理的論證,但不合乎邏輯。嚴格的從邏輯上看來,我們根本無法從「若P 則Q」和「Q 為真」推理出任何結果。這樣的推論不具邏輯說服力,而只是合理的推論。但溯因推理規則在日常生活和科學中仍舊十分重要,因而也用於人工智慧,來模擬正常人類的思考模式。溯因推理在許多科學領域中根本就是科學方法的典範:如果某個科學假說(或理論)P 做了一項預測Q,隨後Q 也真的發生了,這個科學理論便贏得支持。如果有許多個假說或理論競相解釋某個事實,那麼一個驗證理論的可能性便在於,先從這些假說推導出結果,然後做實驗,看看這些結果是否會發生,或說有哪些結果會發生。如果某個理論預測一個結果,而這個結果真的發生,此理論便獲得支持,但未受到證明。相反地,如果發生的事件與理論預測相牴觸,這個理論就會失去威信,甚至被瓦解。

就像這一章開頭提到的,我們還可以注意到,一般而言歸納推理是從特殊情形推到一般情況的推理形式。數學歸納法也是從特殊情況推至一般情形,但是在本質上並非歸納推理,而是演繹推理法。說得更精確些,數學歸納法的論證是經過演繹證明的:因為包含了所有的情況,所以這種歸納法(在數學上)是完備的。數學歸納法讓我們看到,如何從一個論點的成立,然後透過驗證唯一一個蘊涵關係,擴展到所有可能的情況。現在你也許可以看得更清楚,這種推理法的本質為何。

在前面描述的數學歸納法運用中,用自然數編號的命題會一個接一個地處理。當然也可以用別的方式處理所有的自然數;例如在歸納步驟時不是從n 推到n + 1,而是從n 推到2n,之後再將因此產生的缺口用倒推的方式補上,從命題對n 成立,來證明命題對n − 1 也成立。這就是所謂的正推-倒推-歸納法。如果只是為了證明某命題對於所有自然數1、2、⋯⋯、m 為真,在歸納步驟時也可以使用倒推的步驟,證明命題在從n 推到n − 1 時也成立(倒推歸納法),而歸納起始點,就會是證明當n = m 時命題成立。

我們現在把歸納原則使用在一個學校教的幾何範例上:

黑白畫家的經驗寶藏

K 先生只畫黑白作品,而且是後現代風格;不像普通的畫作,K 先生的畫只有直線,直線交錯產生的區塊他便畫上黑或白。K 先生的經驗是,不管畫了幾條直線,不管直線如何交錯,每一個(被直線分隔開的)區塊的顏色都不同,例如下圖中n = 4 條直線的圖案:

math02.jpg
黑白畫家的作品。(圖/漫遊者文化)

現在來想像一下有任意n 條直線和所形成的區塊,每條直線的「左邊」和「右邊」代表的是有意義的概念。

現在使用數學歸納法的風格,先看只有一條直線時的情況。一條直線將一個平面分成2 個區塊。顯然可以畫上不同的顏色。這不難。接下來我們假設被n 條直線分割的平面,其著色的區塊是符合我們的條件。現在加上一條直線G,位置隨便,只要不和之前的直線重疊即可。這條直線分開了一些已經著上顏色的區塊,而從新的直線的位置看來,分成左邊和右邊。我們現在把所有新直線G 左邊的區塊重新著上顏色。這個動作不僅影響了被G 所分隔的區塊,還有所有在G 左邊,但是不和G 相鄰的區塊。重新著色後G 右邊區塊的上色也符合規則,所以新區塊的著色也成立。這就是證明。

在第二個數學歸納法的例子裡,我們來看看二項式係數和2 的幕次之間看似純屬理論的關係。對於所有自然數n,下面的式子都成立:

B(n, 1) + 2B(n, 2) + 3B(n, 3) + ⋯ + nB(n, n) = n2n-1 (18)

我們想要使用歸納原則來證明。

歸納起始點:

n = 1: B(1, 1) = 1!/(1! ⋅ 0!) = 1 = 1 ⋅ 20

歸納步驟:

我們先假設,當任意自然數n = k 時(18) 式成立,也就是

B(k, 1) + 2B(k, 2) + 3B(k, 3) + ⋯ + kB(k, k) = k2k-1

為了方便稱呼,我們將左式簡稱為S(k)。於是,

S(k + 1) = B(k + 1, 1) + 2B(k + 1, 2) + 3B(k + 1, 3) + ⋯ +

(k + 1)B(k + 1, k + 1)

基本的概念就在於使用到下面這個分解:

B(n, k) = B(n − 1, k) + B(n − 1, k − 1)

把等號左右兩邊分開計算,便可驗證上面的式子。我們再次看到富比尼原理發揮作用。根據二項式係數的定義,左式是指從n 個人中選出k 人(k 人小組)的方法數。右式的解釋為:選出任何一人P。B(n − 1, k) 是選出不含P 在內的k 人小組的方法數,而B(n − 1, k − 1) 則是包含P 在內的k 人小組的方法數。兩者之和便是從n 人中選出k 人小組的方法數。

在這一步的考慮之後,我們可以把剛才的式子重新寫成:

S(k + 1) = [B(k, 0) + B(k, 1)] + 2[B(k, 1) + B(k, 2)] + ⋯ + k[B(k, k – 1)

+ B(k, k)] + (k + 1)B(k, k)

= B(k, 0) + 3B(k, 1) + 5B(k, 2) + ⋯ + (2k + 1)B(k, k)

= [B(k, 0) + B(k, 1) + B(k, 2) + ⋯ + B(k, k)] + 2S(k)

= 2k + 2k ⋅ 2k–1

= (k + 1) ⋅ 2k

在倒數第二步,我們使用了101 頁的(10) 式來化簡中括號裡的式子。

這是個完整的證明。但我們在這個例子多停留一會兒。受到富比尼原理發揮用的鼓勵,我們決定替複雜得多的(18) 式尋找一個類似的論證:一個比數學

歸納法更有創意的另類證法。

為此我們先自問以下的問題:從n 人當中選出k 人小組,而k 人小組裡有一人是主席,可有多少種選法? k 人小組可以選第1 到第n 個成員,而k 人小組中的任何成員均可當主席。答案:選出k 人小組一共有B(n, k) 種選法,而對於每種選法,又有k 種選出主席的方法,根據乘法原理,就有kB(n, k) 種可能的選法。好啦,k可以從1任意變化到n。這就產生了kB(n, k)從1到n的加總。這也正是(18)式的左半邊。太好了。那該如何求出右半邊呢?十分簡單。我們可以換個方式計算,先從n 人中選出主席,這一共有n 種選法。然後再從剩下的n − 1 人中選出k 人小組的其他成員。從n − 1 人中,不是被選進k 人小組,就是被排除在外,所以對每個人來說都有兩種可能。對n − 1 人而言,根據乘法原理,就有2n-1 種可能。因此,同樣是根據乘法原理,總共會有n2n-1 種選法。十分漂亮的證法,也是公式(18) 的第二種證明方法。

還有一個同樣機智、在某方面看來甚至更漂亮的方式來證明(18) 式:透過S(n)/2n。這個比率用文字來敘述,意思為含有n 個元素的集合{1, 2, 3, ⋯, n} 的所有子集合的平均大小。這是因為,有k 個元素的子集合恰好有B(n, k) 個,而所有的子集合總共有2n 個。為什麼呢?因為對於n 個元素的每個元素來說,也永遠有兩種可能:屬於某個子集,或不屬於某個子集。

現在我們可以把任何一個子集跟其餘集配對。成對的集合一共含有n 個元素,平均每個集合有n/2 個元素。由於每對集合都有n/2 個元素,所以S(n)/2n = n/2正是(18) 式所說的內容。很特別吧!

本文經授權轉載自漫遊者文化《德國一流大學教你數學家的22個思考工具

關鍵字:
風傳媒歡迎各界分享發聲,來稿請寄至 opinion@storm.mg

本週最多人贊助文章