# Definitions
###### tags: `圖論def`

### Set Definition

* 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_y A_i =A \forall$$

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


* 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)$$

* **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)) $$

* logical definition

* $$ 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:
>