# Chapter2 - 基本結構 Basic Structure

## 集合 Sets
* 物件間沒有順序的組合，例 : $A = \{ 1,2,3,4 \} = \{ 1,3,2,4 \}$

* 描述集合的方式
* 寫出全部元素 : $A = \{ 1,2,3,4 \}$
* 集合建構符號 : $O = \{ x | x$ is an odd positive integer$\}$
* 文氏圖

* 符號介紹
| 符號 | 說明 | 例子 |
|:---:|:---:|:---|
| $\in$ | 屬於 | $x \in X$ 表示 $x$ 是 $X$ 的元素之一 |
| $\notin$ | 不屬於 | $x \notin X \equiv ¬(x \in X)$ 表示 $x$ 不是 $X$ 的元素之一 |
| $\subseteq$ | 子集 | $x \subseteq y$ 表示 $x$ 內的元素均在 $y$ 裡 |
| $\supseteq$ | 超集 | $y \supseteq x$ 表示 $y$ 內含 $x$ 的所有元素 |
| $\subset$ | 真子集 | $x \subset y$ 表示 $x$ 是 $y$ 的真子集 ( $x$ 是 $y$ 的子集，但 $x$ 不等於 $y$ ) |
| $\supset$ | 真超集 | $y \subset x$ 表示 $y$ 是 $x$ 的真超集 ( $y$ 是 $x$ 的超集，但 $x$ 不等於 $y$ ) |
varnothing
* 基數 cardinality : 集合的大小
* 例 : \|$\varnothing$\| = 0、\|{1,2,3}\| = 3、\|{{1,2,3},{a,b}}\| = **2**
* 有限集合 : $|S| \in N$
* 無限集合 : 集合的基數無限大，例 : $N$、$R$、$Z$

* 冪集合 the power set : $P(S) = \{ x | x \subseteq S \}$ (一個集合 $S$ 的所有子集合)
* 例 : $P(\{a,b\}) = \{ \varnothing , \{a\}, \{b\}, \{a,b\}\}$
* $P(S)$ 也可以寫成 $2^S$，因此在有限集合S中， $|P(S)| = 2^{|S|}$
* 易混淆情況 : $P(\varnothing)=\{\varnothing\}$ 、 $P(\{\varnothing\}) = \{\varnothing,\{\varnothing\}\}$

* 有序n項 ordered N-tuples
* 有序n項 : 元素的順序通常很重要，需要有一個不同的結構來表示，通常寫成 $(a_1,a_2,...,a_n)$
* 有序對 : 2元組(2-tuple)，例 : $(a,b)$

* 卡氏積 Cartesian products : $A \times B = \{(a,b)|a \in A ∧ b \in B \}$
* 例題 : 求 $A \times B$
>* $A = \{ 1,2 \}$
>* $B = \{ a,b,c \}$

$Ans:A \times B = \{ (1,a),(1,b),(1,c),(2,a),(2,b),(2,c) \}$
* $|A \times B| = |A||B|$
* **不滿足交換率**， $A \times B$ 不一定等於 $B \times A$

## 集合運算
| 名稱 | 符號 | 說明 | 圖示 |
|:---:|:---:|:---|:---:|
| 聯集 union | $\cup$ | 兩個集合內的所有元素 |  |
| 交集 intersection | $\cap$ | 兩個集合內的共同元素 |  |
| 互斥 disjoint | | A和B沒有交集( $A \cap B = \varnothing$ ) <hr> **排容原理 :** <br> $\|A \cup B\| = \|A\| + \|B\| - \|A \cap B\|$ <br> $\|A \cup B \cup C\| = \|A\| + \|B\| + \|C\| - \|A \cap B\| - \|A \cap C\| - \|B \cap C\| + \|A \cap B \cap C\|$ |  |
| 差集 difference | $-$ | A裡面沒有B的地方；B咬了A一口 <br> $A-B= \{ x \in A ∧ x \notin B \}$ |  |
| 補集合 complment | $\overline A$ | 除了A之外的所有元素 | |
| 互斥或 XOR | $\oplus$ | A和B中相同的元素去除，具有交換率 <br> $A \oplus B = (A \bigcup B) - (A \bigcap B)$ |  |

* 定理
| 定理公式 | 定理名稱 |
|:---|:---|
| $A \cup \varnothing = A$ <br> $A \cap U = A$ | 同一律 |
| $A \cup U = U$ <br> $A \cap \varnothing = \varnothing$ | 支配律 |
| $A \cup A = A$ <br> $A \cap A = A$ | 冪等律 |
| $\overline {\overline A} = A$ | 補集律 |
| $A \cup B = B \cap A$ <br> $A \cap B = B \cup A$ | 交換律 |
| $A \cap (B \cap C) =(A \cap B) \cap C$ <br> $A \cup (B \cup C) =(A \cup B) \cup C$| 結合律 |
| $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ <br> $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$ | 分配律 |
| $\overline {A \cup B} = \overline A \cap \overline B$ <br> $\overline {A \cap B} = \overline A \cup \overline B$ | 笛摩根第律 |
| $A \cup (A \cap B) = A$ <br> $A \cap (A \cup B) = A$ | 吸收律 |
| $A \cup \overline A = U$ <br> $A \cap \overline A = \varnothing$ | 補律 |

* 證明集合恆等式
* 相互子集 : 分別證明 $E_1 \subseteq E_2$ 和 $E_2 \subseteq E_1$
* 使用集合建構符號及邏輯等價
* 成員表(*membership table*) : 真值表

* 任意交集 generalized intersection
* 用於n元交集，使用big arch符號，如 : $A_1 \cap A_2 ... \cap A_n = \bigcap^n_{i=1} A_i$
* 無限集合 : $\bigcap^∞_{i=1} A_i$

## 函數 Function
* 專有名詞
> 在 $A \rightarrow B$ 且 $f(a)=b \text{ (在 } a \in A \text{ 且 } b \in B \text{ 處)}$
* $A$ 是 $f$ 的定義域(domain)
* $B$ 是 $f$ 的對應域(codomain)
* $b$ 是 $a$ 在 $f$ 之下的映像(image)
* $a$ 是 $b$ 在 $f$ 之下的前像(pre-image)
* 值域(range)是 $A$ 的所有元素映像之集合 $\{ b | \exists a f(a)=b \}$

* 函數運算符號
* $(f_1 + f_2)(x) = f_1(x) + f_2(x)$
* $(f_1f_2)(x) = f_1(x)f_2(x)$

* 一對一函數 one-to-one function *(1-1)*
* 定義 : 在函數 $f$ 裡， $x$ 的值不同， $f(x)$的值也不同
* 別稱 : injection、injective function、**單射函數**
* 比較 :
|  |  | 
|:---:|:---:|:---:|
| 一對一函數 | **非**一對一函數 | **非**函數 |

* 映成函數 onto function
* 定義 : 對於某些函數，值域和對應域相等
* 別稱 : surjection、surjective function、**滿射函數**
* 比較 :
| | |  |  |  |
|:---:|:---:|:---:|:---:|:---:|
| **映成函數** | 是 | 否 | 是 | 否 |
| 一對一函數 | 否 | 否 | 是 | 是|

* 反函數 inverse function
* 一個一對一對應關係稱為可逆的(invertible)，因為我們可以定義這個函數的反函數 (當 $f(a) = b$ 時， $f^{-1}(b) = a$)
* 一個函數是不可逆的，若其不為一對一對應關係，因為此含數的反函數不存在
* 例題 : 令 $f$ 為由 $\{a, b, c\}$ 對應到 $\{1, 2, 3\}$ 的函數，定義為 $f(a) = 2$，$f(b) = 3$，而 $f(c) = 1$。 $f$是否為可逆的？若是，其反函數為何？

***Ans : 是，因為此函數是一對一對應關係，其反函數 $f^{-1}$ 定義為 : $f^{-1}(1) = c$ 、 $f^{-1}(2) = a$ 、 $f^{-1}(3) = b$***

* 函數的合成
> $g : A \rightarrow B ； f : B \rightarrow C$
* $(f。g) : A \rightarrow C$ 在 $(f。g)(a) = f(g(a))$ 處
* **注意** : $f。g \neq g。f$
* 例題 : 求 $f。g$ 和 $g。f$
> * $g(a) = b, g(b) = c, g(c) = a$
> * $f(a) = 3, f(b) = 2, f(c) = 1$

$Ans :$
* $f。g(a) = f(g(a)) = f(b) = 2$
* $f。g(b) = f(g(b)) = f(c) = 1$
* $f。g(c) = f(g(c)) = f(a) = 3$
* $g。f$ 未定義

* 一些重要的函數
* 底函數 the floor function ($\left \lfloor x \right \rfloor$) : 小於或等於 $x$ 的最大整數，例 : $\left \lfloor 0.5 \right \rfloor = 0$ 、 $\left \lfloor -0.5 \right \rfloor = -1$ 、$\left \lfloor 7 \right \rfloor = 7$
* 頂函數 the ceiling function ($\left \lceil x \right \rceil$) : 大於或等於 $x$ 的最小整數，例 : $\left \lceil 0.5 \right \rceil = 1$ 、 $\left \lceil -0.5 \right \rceil = 0$ 、$\left \lceil 7 \right \rceil = 7$
* 階層函數 the factorial function : $f(n) = n! = 1 \times 2 \times 3 \ldots \times n$ ，例 : $f(6) = 1 \times 2 \times 3 \times 4 \times 5 \times 6 = 720$

## 序列 Sequence
* 幾何數列 geometric progression
* $a$ : 首項 ； $r$ : 公比
* $a, ar, ar^2, \ldots , ar^n, \ldots$

* 算術數列 arithmetic progression
* $a$ : 首項 ； $d$ : 共差
* $a, a+d, a+2d, \dots , a+nd, \ldots$

* 推導序列規律技巧 :
* 利用前幾項是否能以加上某個固定量，或是加上與位置有關之量來求得接下去的項？
* 利用前幾項是否能以乘上某個固定量，來求得接下去的項？
* 能否以某種固定方式結合前幾項來得出下列之項？
* 序列之項是否會循環？

## 總和 Summations
$$
\sum^k_{i=j}a_i = a_j + a_{j+1} + ... + a_k
$$

* 巢狀總和 nested summations
* 有兩個總和符號
$$
\begin{align*}
& \sum^4_{i=1} \sum^3_{j=1} ij \notag \\
={ } & \sum^4_{i=1} i+2i+3i = \sum^4_{i=1} 6i \notag \\
={ } & 6 \times (1+2+3+4) = 6 \times 10 = 60
\end{align*}
$$

* 公式
$$
\begin{equation}
\sum^n_{j=0} ar^j = \begin{cases}
\frac{ar^{n+1}-a}{r-1}, & \text{if } r \neq 1 ; \\
(n+1)a, & \text{if } r = 1.
\end{cases}
\end{equation}
$$

## 集合的基數
* 定義 : 集合 A 和 B 具有相同的基數（記作 |A| = |B|），若且唯若存 A 和 B 為一對一對應關係（bijection，或稱雙射）。
* 可數集 countable : 一個集合元素的數量是有限的
* 不可數集 uncountable : 一個集合不是可數集
* 無限集合是可數集，若且唯若它能以序列形式列出集合中的元素
* 康托對角線論證法 Cantor diagonalization argument
* 例題 : 證明實數的集合是一個不可數集
$Ans :$ 設實數集合是可數集，則介於0與1間的實數可數的，將這些實數列出
$r_1 = 0.d_{11}d_{12}d_{13}d_{14} \ldots$
$r_2 = 0.d_{21}d_{22}d_{23}d_{24} \ldots$
$r_3 = 0.d_{31}d_{32}d_{33}d_{34} \ldots$
$r_4 = 0.d_{41}d_{42}d_{43}d_{44} \ldots$
$\vdots$
現在製造一個新實數 $r = 0.d_1d_2D_3d_4 \ldots$ ，其中若 $d_{ii} \neq 4$ 則 $d_i = 4$ ；若 $d_{ii} = 4$ 則 $d_i = 5$
這個數 $r$ 的所有小數位都是4與5，所以，$r$ 為實數且 $0 < r < 1$，然而 $r \neq r_1$，因為它們的第一個小數位不同，$r \neq r_2$，因為它們的第二個小數位不同，依此類推，$r \neq r_i$，$\forall i = 1, 2, 3, \ldots$。我們找出了一個介於0與1間的實數，但不在序列中。與原先之假設矛盾。所以實數集合是個不可數集合。

## 矩陣 Maxtrices
* 一個 $m \times n$ ( $m$ by $n$ )的矩陣，有 $m$ 行平的和 $n$ 行直的

* 矩陣排序
$$
A = [a_{i,j}] =
\begin{bmatrix}
a_{1,1} & a_{1,2} & a_{1,3} & \ldots & a_{1,n} \\
a_{2,1} & a_{2,2} & a_{2,3} & \ldots & a_{2,n} \\
a_{3,1} & a_{3,2} & a_{3,3} & \ldots & a_{3,n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{m,1} & a_{m,2} & a_{m,3} & \ldots & a_{m,n} \\
\end{bmatrix}
$$

* 單位矩陣 identity matrices
$$
I_n =
\begin{bmatrix}
\begin{Bmatrix}
1 & \text{ if } i = j \\
0 & \text{ if } i \neq j \\
\end{Bmatrix}
\end{bmatrix} =
\begin{bmatrix}
1 & 0 & \ldots & 0 \\
0 & 1 & \ldots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \ldots & 1 \\
\end{bmatrix}
$$

* 反矩陣 matrix inverses
* $A$ 的反矩陣為 $A^{-1}$
* 如果反矩陣存在，它是唯一的，且 $A^{-1}A = AA^{-1} = I_n$

* 矩陣的冪次 powers of matrices
* $A^0 = I_n$
* $A^p = \underbrace {AAAAA \ldots A}_{乘p次}$ ($p \neq 0$ 且 $A$ 是一個 $n \times n$ 的矩陣)
* 例題 :
$$
\begin{bmatrix}
2 & 1 \\
-1 & 0 \\
\end{bmatrix}^3 =
\begin{bmatrix}
2 & 1 \\
-1 & 0 \\
\end{bmatrix} \cdot
\begin{bmatrix}
2 & 1 \\
-1 & 0 \\
\end{bmatrix} \cdot
\begin{bmatrix}
2 & 1 \\
-1 & 0 \\
\end{bmatrix} =
\begin{bmatrix}
2 & 1 \\
-1 & 0 \\
\end{bmatrix} \cdot
\begin{bmatrix}
3 & 2 \\
-2 & -1 \\
\end{bmatrix} =
\begin{bmatrix}
4 & 3 \\
-3 & -2 \\
\end{bmatrix}
$$

* 轉置矩陣 matrix transposition
* $A$ 的轉置矩陣為 $A^t$ 或 $A^T$
* $A^t = B = [b_{ij}] = [a_{ji}]$
* 例題 :
$$
\begin{bmatrix}
2 & 1 & 3 \\
0 & -1 & -2 \\
\end{bmatrix}^t =
\begin{bmatrix}
2 & 0 \\
1 & -1 \\
3 & -2 \\
\end{bmatrix}
$$

* 對稱矩陣 symmetric matrices
* $A$ 是一個對稱矩陣若且唯若 $A = A^t$ ，即 $A_{ij} = A{ji}$

* 0-1 矩陣 zero-one matrices
* 矩陣內的所有元素非0即1 (代表 ***False*** 或 ***True*** )
* 公式 :
* $A \wedge B \equiv [a_{ij} \wedge b_{ij}] = [a_{ij}b{ij}]$
* $A \vee B \equiv [a_{ij} \vee b_{ij}]$
* 例題 : 求 $A \wedge B$ 和 $A \vee B$
> $$
A =
\begin{bmatrix}
1 & 0 & 1 \\
0 & 1 & 0 \\
\end{bmatrix} \text{ , } B =
\begin{bmatrix}
0 & 1 & 0 \\
1 & 1 & 0 \\
\end{bmatrix}
$$

$Ans :$
* $$
A \wedge B =
\begin{bmatrix}
0 & 0 & 0 \\
0 & 1 & 0 \\
\end{bmatrix}
$$
* $$
A \vee B =
\begin{bmatrix}
1 & 1 & 1 \\
1 & 1 & 0 \\
\end{bmatrix}
$$

* 布爾積 Boolean products
* 矩陣相乘後，若元素結果矩陣相乘後，若元素 ≧ 1 則為 1
* 符號 : $\odot$
* 例題 : 求 $A \odot B$
> $$
A =
\begin{bmatrix}
1 & 0 \\
0 & 1 \\
1 & 0 \\
\end{bmatrix} \text{ , } B =
\begin{bmatrix}
1 & 1 & 0 \\
0 & 1 & 1 \\
\end{bmatrix}
$$

$$
Ans :
\begin{bmatrix}
1 & 1 & 0 \\
0 & 1 & 1 \\
1 & 1 & 0 \\
\end{bmatrix}
$$
* 布爾積的冪次 : $A^{[k]} \equiv \underbrace{A \odot A \odot \ldots \odot A}_{乘k次}$