---
# System prepended metadata

title: Chapter2 - 基本結構 Basic Structure
tags: [離散數學]

---

# 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$ | 兩個集合內的所有元素 | ![未命名](https://hackmd.io/_uploads/B1q4Hoq2xx.png =200x) |
| 交集 intersection | $\cap$ | 兩個集合內的共同元素 | ![未命名](https://hackmd.io/_uploads/Hyzvric2eg.png =200x) |
| 互斥 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\|$ | ![未命名](https://hackmd.io/_uploads/r1zsUjqheg.png =200x) |
| 差集 difference | $-$ | A裡面沒有B的地方；B咬了A一口 <br> $A-B= \{ x \in A ∧ x \notin B \}$  | ![未命名](https://hackmd.io/_uploads/BJwh7j5hee.png =200x) |
| 補集合 complment | $\overline A$ | 除了A之外的所有元素 | ![未命名](https://hackmd.io/_uploads/By1dYs5neg.png =200x)|
| 互斥或 XOR | $\oplus$ | A和B中相同的元素去除，具有交換率 <br> $A \oplus B = (A \bigcup B) - (A \bigcap B)$ | ![未命名](https://hackmd.io/_uploads/H1ZgBs52gl.png =200x) |

* 定理
    | 定理公式 | 定理名稱 |
    |:---|:---|
    | $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、**單射函數**
    * 比較 :
        | ![one-to-one function](https://hackmd.io/_uploads/By1ugnLalx.png =200x) | ![not ont-to-one function](https://hackmd.io/_uploads/HyS7Dss6gg.png =200x) | ![not a function](https://hackmd.io/_uploads/Hk6YDjsTgl.png =200x)
        |:---:|:---:|:---:|
        | 一對一函數 | **非**一對一函數 | **非**函數 |
    
* 映成函數 onto function
    * 定義 : 對於某些函數，值域和對應域相等
    * 別稱 : surjection、surjective function、**滿射函數**
    * 比較 : 
        | |![onto but not 1-1](https://hackmd.io/_uploads/HyGRcnjpxe.png =200x) | ![not onto or 1-1](https://hackmd.io/_uploads/Bygxi2spex.png =200x) | ![onto and 1-1](https://hackmd.io/_uploads/rJcSFhjaxg.png =200x) | ![one-to-one function](https://hackmd.io/_uploads/By1ugnLalx.png =200x) |
        |:---:|:---:|:---:|:---:|:---:|
        | **映成函數** | 是 | 否 | 是 | 否 |
        | 一對一函數 | 否 | 否 | 是 | 是|

* 反函數 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次}$