---
# System prepended metadata

title: 2020-03-13 Intro. & Math Background
tags: [圖論]

---

# 2020-03-13 Intro. & Math Background
###### tags: `圖論`
[TOC]


{%youtube WtyiVHoixpk%}

### Set Definition
* $$ S = \{ x\in A:condition(x) \} $$


* X  is  **proper  subset**  of  A (X是A的subset，但不等於A)
  $$ X \subsetneq A $$



*  **Partition** 定義:
    $$ A_i \cap A_j = \emptyset\ \ \forall i \neq j \ \ , \ \bigcup_i A_i =A$$


* **symetric difference** of A and B : **AΔB**
    * Note: A xor B $$ A \Delta B =(A \cup B) - (A \cap B) $$


![](https://i.imgur.com/5L8qqIN.png)




* k-tuple $$ A^k =  \{ (x_1,...,x_k): x_i \in A \} $$ 
  $$When A=\{0,1\},A^k \ is \ the \ set \ of \ binary \ k-tuples. $$


### Quantifiers & Proofs

* **Universal** quantifier ∀ (For all ...)
    $$ (\forall x \in S) P(x) $$



* **Existential** quantifier ∃ (For some ...)
    $$(\exists x \in S) P(x)$$
    
    * 英文對照參考  
![](https://i.imgur.com/R4ujXfG.png)

    
* **Negation** of quantified statements:
    - $$\neg[(\forall x \in S) P(x)] \ same \ as \ (\exists x \in S) (\neg P(x)) $$
    - $$\neg[(\exists x \in S) P(x)] \ same \ as \ (\forall x \in S) (\neg P(x)) $$


*  Note: Quantifier 的順序會影響語句   
    * ∀x ∃y P: 無論x是哪一種，都存在「相對應的y」，使P為真
    * ∃y ∀x P: 存在一個y，使得「任何x」都能使P為真

*  logical definition
![](https://i.imgur.com/a9Pj3oV.png)

    
* $$ P \Rightarrow Q \ is \ (\neg P) \lor Q$$    
    * Note： 真值表

        |         | P   | ¬P  |
        | :-----: |:--: |:--: |
        | **Q**   | 1   | 1   |
        | **¬Q**  | 0   | 1   |

* **Sufficient V.S. Necessary** 
>[color=#ff0000] 
>
>Sufficient:
>如果給定句子的真偽，要讓 Q 的 value 可以被評估的話
>至少 P 要是 true 
>(P 是 true 時，「足以」近一步判斷 Q 值 與句子的真偽)
> 
>Necessary:
>如果知道 P 是 true，那麼 Q 必須是 true，
>否則句子是 false
>
>[name=MathematiKai ] :+1: :100: :smile: :satisfied: :cry: :laughing: 
>


* **Contrapositive**: 證明右邊成立，左邊自然而然也就成立
    $$P \Rightarrow Q \ is \ \neg Q \Rightarrow \neg P$$


* **Contradiction**: 
  
  $$ \text{ Assume }Q\text{ is false. When } P\text{ is true, }Contradiction \text{(false) occurs}$$
 $$ P \Rightarrow \neg Q (\Rightarrow\! \Leftarrow), \text{ thus, } P \Rightarrow Q \text{ must be true.}$$

### Induction

![](https://i.imgur.com/Kt4TXYb.png)

### Function
![](https://i.imgur.com/JNBkUxu.png)
* **Injective**: one-to-one
    * if x is different, then y is different
* **Surjective**: onto
    * every y has at least 1 correspondent x
* **Bijective**: one-to-one & onto
    * one-to-one correspondent

### Equivalence Relation
![](https://i.imgur.com/MXQvQ2X.png)

### Pigeonhole Principle
#### Lemma: 
**kn objects is partintioned into n classes, 
then some classes receive more than k objects**
