# Chapter1 - 邏輯與證明 Logic & Proofs

## 命題邏輯 Propositional Logic

1. $\overline p$ 或 $\lnot p$ : $\text{not } p$ (相反)
2. $p ∧ q$ : $p$ $\text{and}$ $q$ (兩者皆為真，結果為真)
3. $p ∨ q$ : $p$ $\text{or}$ $q$ (兩者皆為假，結果為假)
4. $p \rightarrow q$ : $\text{if}$ $p$ $\text{then}$ $q$，若 $p$ 則 $q$
5. $p ↔ q$ : $p$ $\text{ if and only if}$ $q$，$p$ 若且為若 $q$ (兩者皆為真，結果為真；兩者皆為假，結果為假)

| $p$ | $q$ | $p ∧ q$ | $p ∨ q$ | $p \rightarrow q$ | $p ↔ q$ |
|:---:|:---:|:---:|:---:|:---:|:---:|
| T | T | T | T | T | T |
| T | F | F | T | F | F |
| F | T | F | T | T | F |
| F | F | F | F | T | T |

$$運算層級 : \lnot > ∧ > ∨ > \rightarrow > ↔$$

## 命題等價 Propositional Equivalences
* 例題
> 你不能編輯受保護的維基百科條目，除非你是一個管理者
>* e : 你能編受保護的維基百科條目
>* a : 你是一個管理者

**使用真值表**找出結果後再帶入句子看是否合理
| e | a | e → a | a → e | e ↔ a |
|:---:|:---:|:---:|:---:|:---:|
| T | T | T | T | T |
| T | F | F | T(不合) | F |
| F | T | T(不合) | F | F |
| F | F | T | T | T |

$$\therefore Ans : e↔a$$

* 定理
| 定理公式 | 定理名稱 |
|:---:|:---:|
| p∧$T$≡p ； p∨$F$≡p | 同一律 |
| p∧$F$≡$F$ ； p∨$T$≡$T$ | 支配律 |
| p∨p≡p ； p∧p≡p | 冪等率 |
| ¬(¬p)≡p | 雙重否定律 |
| p∨q≡q∨p ； p∧q≡q∧p | 交換律 |
| (p∧q)∧r≡q∧(p∧r)<br>(p∨q)∨r≡q∨(p∨r) | 結合律 |
| (p∨(q∧r))≡(p∨q)∧(p∨r)<br>(p∧(q∨r))≡(p∧q)∨(p∧r) | 分配律 |
| **¬(p∧q)≡¬p∨¬q ； ¬(p∨q)≡¬p∧¬q** | **迪摩根定律 ※** |
| **p∨(p∧q)≡p ； p∧(p∨q)≡p** | **吸收律 ※** |
| p∨¬p≡$T$ & p∧¬p≡$F$ | 否定律 |

## 述詞與量詞 Predicates & Quantifiers
* 述詞 Predicates
* 因為命題邏輯無法表達自然語言或數學中語句的意義，因此有更強大的述詞邏輯(Predicate Logic)
> $x>3$ 在 $x$ 的值未確定前無法判定真假
* $x$ 為變數，是句子中的**主詞**；$>3$ 為主詞有的屬性，是句子的**述詞**
* 我們可以用 $P(x)$ 表 $x>3$，其中 $P$ 為述詞； $x$ 為變數

* 量詞 Quantifiers
* 當命題函數中所有變數都被賦值時，得到的語句變成一個含真值的命題

* 量化 Quantification
* 量化所表達的是，一個述詞在多大範圍的元素中為真

* 全稱量化(universal quantification) $\forall$ : $\forall x P(X)$ 所有的 $x$ 為真

* 存在量化(existential quantification) $\exists$ : $\exists x P(x)$ 部份的 $x$ 為真

| 量化種類 | 何時為真 | 何時為假 |
|:---:|:---:|:---:|
| $\forall x P(X)$ | 每一個 $x$ 都讓 $P(x)$為真 | 一個以上 $x$ 讓 P(x) 為假 |
| $\exists x P(x)$ | 一個以上 $x$ 讓 P(x) 為真 | 每一個 $x$ 都讓 $P(x)$為假 |

## 推論規則
* 為數學語句之真建構有效的論證(結論之真必須由先前的述句，亦即論證的前提而來)
* 例題
> * 如果你有正確的密碼，你就可以登入網路
> * 你有正確的密碼
---
$\therefore$ 你可以登入網路

| 推論規則 | 邏輯式 | 規則名稱 |
|:---|:---:|:---:|
| &emsp; $p$ <br> &emsp; $p \rightarrow q$ <hr> $\therefore q$ | $(p \wedge (p \rightarrow q)) \rightarrow q$ | 肯定前件 |
| &emsp; $\lnot q$ <br> &emsp; $p \rightarrow q$ <hr> $\therefore \lnot p$ | $(\lnot q \wedge (p \rightarrow q)) \rightarrow \lnot p$ | 否定後件 |
| &emsp; $p \rightarrow q$ <br> &emsp; $q \rightarrow r$ <hr> $\therefore p \rightarrow r$ | $((p \rightarrow q) \wedge (q \rightarrow r)) \rightarrow (p \rightarrow r)$ | 假言三段論證 |
| &emsp; $p \vee q$ <br> &emsp; $\lnot p$ <hr> $\therefore q$ | $((p \vee q) \wedge \lnot p) \rightarrow q$ | 選言三段論證 |
| &emsp; $p$ <hr> $\therefore p \vee q$ | $p \rightarrow (p \vee q)$ | 添加律 |
| &emsp; $p \wedge q$ <hr> $\therefore p$ | $(p \wedge q) \rightarrow p$ | 簡化律 |
| &emsp; $p$ <br> &emsp; $q$ <hr> $\therefore p \wedge q$ | $((p) \\wedge (q)) \rightarrow (p \wedge q)$ | 連言律 |
| &emsp; $p \vee q$ <br> &emsp; $\lnot p \vee r$ <hr> $\therefore q \vee r$ | $((p \vee q) \wedge (\lnot p \vee r)) \rightarrow (q \vee r)$ | 預解律 |

* 一個有效的論證可能導致錯誤的結果
* 例題
> 若 $\sqrt 2 > \frac {3}{2}$ 則 $(\sqrt 2)^2 > (\frac {3}{2})^2$ ，已知 $\sqrt 2 > \frac {3}{2}$ ，所以 $2 > \frac{9}{4}$

這句話是錯誤的
* 謬誤 : 推理看起來像是正當的推理規則，但它其實不是建立在必然為真的邏輯關係（永真式 / tautology）上，而是建立在某些偶然或特定情況下才成立的條件（contingency）上。
* 例題
> * 若你做完了課本上所有習題，則你學會了離散數學
> * 你學會了離散數學
> $\therefore$ 你做完了課本所有習題

這是謬誤，不合法的論證

* 量詞推論規則
| 推論規則 | 規則名稱 |
|:---|:---:|
| &emsp; $\forall xP(x)$ <hr> $\therefore P(c)$ | 全稱個例化 |
| &emsp; $P(c)$ for an arbitrary $c$ <hr> $\therefore \forall xP(x)$ | 全稱通則化 |
| &emsp; $\exists xP(x)$ <hr> $\therefore P(c)$ for some element $c$ | 存在個例化 |
| &emsp; $P(c)$ for some element $c$ <hr> $\therefore \exists xP(x)$ | 存在通則化 |

## 證明
* 名詞解釋
* 定理 Theorem : 一個句子被證明為真
* 證明 Proof : 建立於定理為真的有效論證
* 公理 Axiom : 假設是真實的論述
* 引理 Pemma : 一個較不重要的定理，可用於證明其他結果
* 系理 Corollary : 可從已證明的定理直接推出的定理
* 假說 Conjecture : 真值上未被論證的敘述

* 證明定理的方法
> 證明 $p \rightarrow q$ 的情況下
* 直接證明法 : 設 $p$ 為真，證明 $q$
> * 定義 : 一整數 $n$ 為奇數若且唯若 $n = 2k + 1$ ； $n 為偶數若且唯若 $n = 2k$。其中 $k$ 為某個整數。
> * 公理 : 每個整數不是奇數就是偶數
> * 定理 : 若 $n$ 是奇數，則 $n^2$ 是奇數
> * 證明 : 若 $n$ 是奇數，則 $n = 2k + 1$，因此 $n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$ ，所以 $n^2 的形式為 $2j + 1(j=2k^2+2k)$，因此 $n^2$ 也是奇數
* 反證法 : 設 $\overline q$ ，證明 $p$
> * 定理 : 若 $3n+ 2$ 是奇數，則 $n$ 是奇數(對所有整數 $n$)
> * 證明 :
假設結論為假，即設 $n$ 為偶數 ($n=2k$)
$$3n + 2 = 3 \times 2k + 2 = 6k + 2 = 2(3k+1)$$
由此可知， $3n+2$ 非奇數，證明 $\overline {(n是奇數)} \rightarrow \overline {(3n+2是奇數)}$ ，因此 ${(n是奇數)} \rightarrow {(3n+2是奇數)}$ 得證
* 空泛證明法 : 證明 $\overline p$
> * 定理 : 若 $n$ 是奇數也是偶數，則 $n^2=n+n$
> * 證明 : **$n$ 是奇數也是偶數**這句話一定為假，所以該定理正確
* 平庸證明法 : 證明 $q$
> * 定理 : 若 $n$ 是兩個整數的和，則 $n$ 不是奇數就是偶數
> * 證明 : 任何整數不是奇數就是偶數，因此無論前提是否真實，假說的結果都是正確的。
---
* 矛盾證明法 : 證明 $p$方法 。假設 $\overline p$，讓$p \rightarrow (q ∧ \overline q)$ 為真
* 等價證明法 : 證明 $p↔q$ ， 需先證明 $p \rightarrow q$ 和 $q \rightarrow p$ 為真

## 證明方法與策略
* 窮舉證明 : 有些定理可以藉由數量相當少的案例獲得證明
* 分案證明 : 必須涵蓋定理中**所有**可能情形
* 存在證明 : 形如 $\forall xP(x)$ 之命題，其中 $P$ 為述詞。證明形式為 $\exists xP(x)$ 的命題
* 建構式存在證明
* 非建構式存在證明
* 唯一性證明 : 存在性與獨特性