> For the complete documentation index, see [llms.txt](https://mvdd188.gitbook.io/cs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mvdd188.gitbook.io/cs/san/proofs.md).

# Proofs

![](https://692803005-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LZAnL0SzCN0zyF32Pbe%2F-LZcaN_sUmGfJ_AVnTzn%2F-LZcciv0mx1nWC-fCl-u%2F1551164876309.jpg?alt=media\&token=5f285805-1f02-4c75-8cae-9c82d92918a8)

[Link](https://divisbyzero.com/2008/09/22/what-is-the-difference-between-a-theorem-a-lemma-and-a-corollary/)

##  Proofs

#### 1. Direct proof

![根據定義，證明n是偶數，則n平方也是偶數。](https://692803005-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LZAnL0SzCN0zyF32Pbe%2F-LZeg2xM7-0VShasNFlY%2F-LZegqp-sedKhiiqoa1X%2F1551199482155.jpg?alt=media\&token=3da7f468-5531-45ac-bd81-04ade1323305)

![根據定義，證明兩個有理數相加，也會為有理數。](https://692803005-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LZAnL0SzCN0zyF32Pbe%2F-LZehCVJrEFS3xxoGqs7%2F-LZei5cq4u-rfbSA2z6I%2F1551199533822.jpg?alt=media\&token=328edfd2-4843-4dde-8f58-53f2b6c6b1ee)

![功課，證明兩個完美數相乘也會是完美數](https://692803005-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LZAnL0SzCN0zyF32Pbe%2F-LZeg2xM7-0VShasNFlY%2F-LZeh-INQteHr_Gt0QaU%2F1551199493733.jpg?alt=media\&token=be0ad28d-d507-4083-a6ce-72742021f5ef)

[Perfect number](https://en.wikipedia.org/wiki/Perfect_number) 的定義

#### 2. Proof by contraposition

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

![反證法，以\~q --> \~p 出發，兩者邏輯等價](https://692803005-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LZAnL0SzCN0zyF32Pbe%2F-LZehCVJrEFS3xxoGqs7%2F-LZehMQLa3ZJTRXJVUU8%2F1551199503789.jpg?alt=media\&token=3c48e2d1-7e79-435d-8f31-d6941aa0ecdc)

![證明如果存在一個整數n，使3n + 2為奇數，則這個n應該是奇數。](https://692803005-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LZAnL0SzCN0zyF32Pbe%2F-LZehCVJrEFS3xxoGqs7%2F-LZehxXPqBuD-FQNy-EZ%2F1551199521379.jpg?alt=media\&token=bfc688ec-dc97-43b7-898f-27d62b61f9c1)

![證明n平方為奇數，則n為奇數](https://692803005-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LZAnL0SzCN0zyF32Pbe%2F-LZehCVJrEFS3xxoGqs7%2F-LZeipcVH7GLM0YG3hU7%2F1551199545674.jpg?alt=media\&token=865c13ff-d48c-4678-9124-0764996ad265)

####  ​3. Vacuous and Trivial

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

![](https://692803005-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LZAnL0SzCN0zyF32Pbe%2F-LZekv9pBdCDs3LPnVys%2F-LZel-_tEXE0qUzOGW56%2F1551200649275.jpg?alt=media\&token=be375a92-b0cd-4f8a-865b-82c39350781f)

![](https://692803005-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LZAnL0SzCN0zyF32Pbe%2F-LZelZxWRjQ3iPvkq_0Q%2F-LZelc9pXqfptFMfUzOO%2F1551200821644.jpg?alt=media\&token=822e1e3d-086e-4450-846b-a95461227d1f)

#### 4. Proof by contradiction

![證明根號2是無理數](https://692803005-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LZAnL0SzCN0zyF32Pbe%2F-LZxH5w4ubyT8ENgxqUp%2F-LZxHBYB1YhkLo9obIcM%2F1551511326203.jpg?alt=media\&token=b4e25f1c-97a1-42c1-a0cf-24220687647f)

* 矛盾證法

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

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

* 與反證法的差異

        p --> q vs \~q ^ p

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

        前件是已知的條件，

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

        T --> F ≡ F

![](https://692803005-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LZAnL0SzCN0zyF32Pbe%2F-LZxbVN5m6waTPew80uM%2F-LZxcF5i0zWnuDmdqk_h%2F1551517134963.jpg?alt=media\&token=6f668c1b-1d7f-4036-b2f7-be8d9241136e)

#### 5. 數學歸納法

* 1 + 2 + 3 + \~\~\~\~ n
* 三次方，

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

## Example mistakes proofs

![](https://692803005-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LZAnL0SzCN0zyF32Pbe%2F-LZxH5w4ubyT8ENgxqUp%2F-LZxJR5pRwkMOFZs3hCM%2F1551511916883.jpg?alt=media\&token=aefee19c-d6ab-432d-93c4-cfe1896ce97c)

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

![](https://692803005-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LZAnL0SzCN0zyF32Pbe%2F-LZxH5w4ubyT8ENgxqUp%2F-LZxJYyySRdDessxIxUh%2F1551511942711.jpg?alt=media\&token=333b9681-c886-42bd-8af1-e17d95c1b101)

## Proof Cases(列舉法，窮舉法)

* 記得每一個都要證到

![](https://692803005-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LZAnL0SzCN0zyF32Pbe%2F-LZxH5w4ubyT8ENgxqUp%2F-LZxKq_1gD8lbM0-Qr67%2F1551512315782.jpg?alt=media\&token=b2ecb6b9-b102-43e4-a40a-1fca36690f54)

(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) \~\~\~\~\~

![](https://692803005-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LZAnL0SzCN0zyF32Pbe%2F-LZxN9FGlVxsoFgkRKiI%2F-LZxNCi_GRy-8qYbOIVb%2F1551512925081.jpg?alt=media\&token=11c0e9ff-6d8a-444a-a448-d79538b7f28e)

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

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

![](https://692803005-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LZAnL0SzCN0zyF32Pbe%2F-LZxUQFdboixJH5ODlvq%2F-LZxUVlesb6CGRCYv4zc%2F1551514824462.jpg?alt=media\&token=45f2ffb0-c9ab-466c-8a9d-05291a49584e)

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

![](https://692803005-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LZAnL0SzCN0zyF32Pbe%2F-LZxWIhmO8CnO0EIcI7x%2F-LZxWO7Bukia_Bcc3V5V%2F1551515294161.jpg?alt=media\&token=c77958e5-e946-43f3-bce8-6e7c46e3d35d)

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

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

## Uniqueness Proofs

![](https://692803005-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LZAnL0SzCN0zyF32Pbe%2F-LZxWr03cdNFULrpgSuY%2F-LZxXGGf91eONW4mVcHq%2F1551515471083.jpg?alt=media\&token=9d84aad0-1f7e-4265-bd74-fdef7a1c40f1)

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

## Open Problems and Conjectures

* 第一個是費馬小定理

![](https://692803005-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LZAnL0SzCN0zyF32Pbe%2F-LZxn46r3sTgx8cLq8rp%2F-LZxn7y6Sex9Spr1oKKA%2F1551519891846.jpg?alt=media\&token=7bdfb779-842d-43bc-8541-3b42f6e9922e)

## Other

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

* 偶數
* 奇數
* 有理數

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

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