# Proofs

![](/files/-LZcciv0mx1nWC-fCl-u)

[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平方也是偶數。](/files/-LZegqp-sedKhiiqoa1X)

![根據定義，證明兩個有理數相加，也會為有理數。](/files/-LZei5cq4u-rfbSA2z6I)

![功課，證明兩個完美數相乘也會是完美數](/files/-LZeh-INQteHr_Gt0QaU)

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

#### 2. Proof by contraposition

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

![反證法，以\~q --> \~p 出發，兩者邏輯等價](/files/-LZehMQLa3ZJTRXJVUU8)

![證明如果存在一個整數n，使3n + 2為奇數，則這個n應該是奇數。](/files/-LZehxXPqBuD-FQNy-EZ)

![證明n平方為奇數，則n為奇數](/files/-LZeipcVH7GLM0YG3hU7)

####  ​3. Vacuous and Trivial

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

![](/files/-LZel-_tEXE0qUzOGW56)

![](/files/-LZelc9pXqfptFMfUzOO)

#### 4. Proof by contradiction

![證明根號2是無理數](/files/-LZxHBYB1YhkLo9obIcM)

* 矛盾證法

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

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

* 與反證法的差異

        p --> q vs \~q ^ p

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

        前件是已知的條件，

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

        T --> F ≡ F

![](/files/-LZxcF5i0zWnuDmdqk_h)

#### 5. 數學歸納法

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

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

## Example mistakes proofs

![](/files/-LZxJR5pRwkMOFZs3hCM)

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

![](/files/-LZxJYyySRdDessxIxUh)

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

* 記得每一個都要證到

![](/files/-LZxKq_1gD8lbM0-Qr67)

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

![](/files/-LZxNCi_GRy-8qYbOIVb)

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

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

![](/files/-LZxUVlesb6CGRCYv4zc)

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

![](/files/-LZxWO7Bukia_Bcc3V5V)

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

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

## Uniqueness Proofs

![](/files/-LZxXGGf91eONW4mVcHq)

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

## Open Problems and Conjectures

* 第一個是費馬小定理

![](/files/-LZxn7y6Sex9Spr1oKKA)

## Other

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

* 偶數
* 奇數
* 有理數

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

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mvdd188.gitbook.io/cs/san/proofs.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.