Proofs

Link

Proofs

1. Direct proof

根據定義，證明n是偶數，則n平方也是偶數。

根據定義，證明兩個有理數相加，也會為有理數。

功課，證明兩個完美數相乘也會是完美數

Perfect number 的定義

2. Proof by contraposition

• 反證

• 當覺得前件很複雜時，可以從後面看。用~q --> ~p 反推回來。

反證法，以~q --> ~p 出發，兩者邏輯等價

證明如果存在一個整數n，使3n + 2為奇數，則這個n應該是奇數。

證明n平方為奇數，則n為奇數

​3. Vacuous and Trivial

• 舉例 p --> q ， 唯一false唯 p = T, q = F, 只要能說p 永遠不會對，或是q永遠不會錯，則這論述永遠都是對的。

4. Proof by contradiction

證明根號2是無理數

• 矛盾證法

p --> q ≡ ~q --> ~p

前件不是已知的，假設結論是not，前件也是not。

• 與反證法的差異

p --> q vs ~q ^ p

假設結論錯了，但是前件還是對的話，那就互相矛盾了。

前件是已知的條件，

• 大意就是原本的假設及結論是對的，但是將結論反過來，還是同一個假設，這樣就彼此矛盾了。也就是說同一個假設不應該有兩個結果。

T --> F ≡ F

5. 數學歸納法

• 1 + 2 + 3 + ~~~~ n

• 三次方，

以上述兩個規則推導出二次方和四次方公式，並以歸納法證明

Example mistakes proofs

第四步，應該要多個條件(a-b) != 0，一個步驟錯所有就錯。a-b = 0的話，左數 a+b， 右式 b 可以是任意數，因為任何數乘上0都是0

Proof Cases(列舉法，窮舉法)

• 記得每一個都要證到

(p1 v p2 v ~~~~ v pn) --> q

~ (p1 v p2 ~~~ v pn) v q

≡ (~p1 ^ ~p2 ~~~ ^ ~pn) v q

≡ (~p1 v q) ^ (~p2 v q) ~~~~ ~(pn v q)

≡ (p1 --> q) ^ (p2 --> q) ~~~~~

列舉出x, y 證明無整數解。

上圖有問題，因為沒有列舉完，是錯誤的推論。少了 y = -1, y <= -2的列舉。有一個常用的數學名詞，WLOG不失一般性的原則，跟前面的證明一樣我懶的寫了。

x = 0 沒證，所以整個也錯了。再次提醒窮舉法每個都要證。

已知根號2為無理數，列舉根號2 的根號2次方如果為有理數，及如果為無理數。???????

other.. 格爾豐德-施奈德定理

Uniqueness Proofs

第二式，多假設了存在另一個s，導致這個結論(唯一的變數使其ar + b - 0)有第二個變數存在(~q)，最後得知s 與 r 相同(t)。 T --> F ≡ F

Open Problems and Conjectures

• 第一個是費馬小定理

Other

有些基本的定義稍微記一下。

• 偶數

• 奇數

• 有理數

在正常的思想中，通常我們假設一件事情(前件)，得到一個(結論)。都是以前件為真出發，結論才會為真。假設前件都會假，那也沒有必要去推論結論，假如結論都為對也沒必要去假設前件。

一個前件，也不可能讓兩個相反的結論同時發生(矛盾證法)。