---
# System prepended metadata

title: Chapter1 - 邏輯與證明 Logic & Proofs
tags: [離散數學]

---

# 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)$ 的命題
    * 建構式存在證明
    * 非建構式存在證明
* 唯一性證明 : 存在性與獨特性
