數學證明(Mathematical Proofs)


窮舉法(exhaustion)

直接把所有可能性列出來。

例如要證明「北一女中的一年善班全部都是女生」,就依序證明一年善班的 1 號同學是女生、2 號同學是女生...一路到最後一號同學都是女生,這樣就可以知道「北一女中的一年善班全部都是女生」這個命題為真。

在數學上,假設要證明「(∀X)[(x<5)→(x²<25)],x∈N」,則 x 有下列四種可能:

  1. x=1 → (x²=1) → (x²<25) 為真
  2. x=2 → (x²=4) → (x²<25) 為真
  3. x=3 → (x²=9) → (x²<25) 為真
  4. x=4 → (x²=16) → (x²<25) 為真

將 x 每一種可能的情況都列出來並一一檢視,這就是「窮舉法」,但因為窮舉法只能用在有限的情形,在數學上的應用相對較為少見。


直接法(direct proof)

即「(P→Q)」,不另做假設,從公認事實直接推出結果,常用謂詞邏輯,如肯定前件全稱實例化等,上個段落的「窮舉法」也屬於直接法。

例如要證明「若 x 為偶數,則 x² 也是偶數」,可採用下列方式:

  1. 設 x=2k,k∈Z
  2. x²=(2k)²=4k²=2(2k²)
  3. 令 j=2k²,因 x²=2j,而 2j 必為偶數,因此 x² 為偶數

逆否命題法(contraposition)

當 (P→Q) 證明較為困難時,可改證「(Q'→P')」,根據「離散數學學習筆記(一)」的內容可知「(P→Q)↔(Q'→P')」。

以上述「若 x 為偶數,則 x² 也是偶數」為例,其實也能改證「若 x² 不是偶數,則 x 不是偶數」。

  1. 設 x=2k+1,k∈Z
  2. x²=(2k+1)²=(4k²+4k+1)=2(2k²+2k)+1
  3. 令 j=(k²+2k),因 (2j+1) 必不為偶數,因此 x² 不是偶數

反證法(contradiction)

跟「逆否證明法」不同,反證法是先假設一個命題成立,最後推出跟該假設矛盾的結果。

例如要證明「這家公司營運狀況不好」,則可以先假設「這家公司營業額很高」,但事實上卻是財政赤字,因為「財政赤字」與「營業額很高」這個假設矛盾,因此可說明「這家公司營運狀況不好」。

在數學上來說,常被用來證明「√2 為無理數」:

假設 √2 為有理數,則根據有理數的定義,√2=q/p,其中 p、q∈Z 且 p、q 互質

  1. 將 √2 平方得 2=q²/p²,因此 q²=2p²
  2. 根據「若 q² 為偶數,則 q 為偶數」,可設 q=2k,k∈Z
  3. 將第 2. 步所得 q²=2p² 的 q 代換為 2k,可得 (2k)²=2p²
  4. 將 (2k)²=2p² 展開後得 4k²=2p²,化簡得 2k²=p²
  5. 令 k²=j,j∈Z,則 p²=2j,由此可知 p² 為偶數
  6. 根據「若p²為偶數,則p為偶數」,可知 p 為偶數
  7. 因 p 為偶數,可設 p=2a,其中 a∈Z
  8. 綜合第 3. 步與第 8. 步結果,可知 p 與 q 兩者同為偶數,必有一公因數「2」,因此 p、q 不互質,與第 1. 步假設矛盾

看起來有些複雜,但核心概念就是先提出一個跟原命題概念相反的假設,經過一系列推理過程,得出與該假設矛盾之結果,則可說明欲證明的命題為真。


數學歸納法(mathematical induction)

相信對於所有在臺灣讀高中的人來說,「數學歸納法」這個名詞並不陌生,一般常以「骨牌效應」做類比。

在「骨牌效應」中,有這樣的概念:

  1. 第一張骨牌先倒下
  2. 若第二張開始的第 n 張骨牌倒下,則第 n+1 張骨牌必倒下

「數學歸納法」共有三步驟:

  1. 證明「n=1」時成立
  2. 假設「n=k」成立
  3. 將「n=k」代入推理出「n=k+1」的過程,若仍成立則原命題為真

例如要證明等差級數公式「1+2+...+n=[n(n+1)]/2」,可用數學歸納法證明如下:

  1. n=1 時,1=[1(1+1)/2],成立
  2. 設 n=k 時,1+2+...+k=[k(k+1)]/2] 成立
  3. 當 n=k+1 時,總和為 1+2+…+k+(k+1)
  4. 第 3. 步粗體部分以 [k(k+1)]/2] 代換,得 [k(k+1)]/2+(k+1)
  5. 將 [k(k+1)]/2+(k+1) 通分,得 [k(k+1)+2(k+1)]/2
  6. 展開分子,得 (k²+3k+2)/2
  7. 將分子因式分解,得 (k+1)(k+2)/2
  8. 將 (k+2) 改寫為 (k+1)+1,得 (k+1)[(k+1)+1]/2,得證

小結

  1. 窮舉法:列出所有可能狀況。
  2. 直接法:證明 (P→Q)。
  3. 逆否命題法:證明 (Q'→P'),多用於 (P→Q) 不易證明時。
  4. 反證法:提出與原命題相反的假設後,證明該假設矛盾,推得原命題為真。
  5. 數學歸納法:先假設 n=1 成立,再假設 n=k 成立,最後將 n=k 的假設代入 n=k+1 中,若 n=k+1 時成立,則原命題為真。
#離散數學 #數學證明







你可能感興趣的文章

Day04 git 知己知彼

Day04 git 知己知彼

[C#] 寄送含有會議的信件至outlook

[C#] 寄送含有會議的信件至outlook

JS-[promises語法糖]-用async await來實現多個promises

JS-[promises語法糖]-用async await來實現多個promises






留言討論