第四章：數學資料型態
本章介紹數學中用來組織資料的基本結構：集合、序列、函數和關係。這些概念是定義演算法和資料結構的基礎。
4.1 集合
集合 是不同對象的無序匯集。這些對象稱為集合的元素。
集合的表示方法有列舉法如 {1, 2, 3}，或構造法如 { x | P(x) }。
集合運算
- 聯集 (A ∪ B): 在 A 或 B 中的元素。
- 交集 (A ∩ B): 同時在 A 和 B 中的元素。
- 差集 (A - B): 在 A 中但不在 B 中的元素。
4.3 函數
函數 是將定義域中的每個元素恰好映射到對應域中一個元素的規則。
🧪 函數性質實驗室
點擊左邊的元素選擇定義域，再點擊右邊元素選擇對應域，建立映射關係。
目標：嘗試建立一個「雙射」。
定義域 (D)
1
2
3
對應域 (C)
a
b
c
是函數?
單射?
滿射?
雙射?
提示：
單射：定義域中不同的元素映射到不同的像。
滿射：對應域中每個元素都被映射到。
雙射：同時是單射和滿射。
4.4 二元關係
二元關係描述集合中元素之間的聯繫。我們可以用矩陣來表示關係，矩陣中的 1 表示關係存在，0 表示不存在。
🧪 關係矩陣實驗室
點擊矩陣中的格子來切換關係 (開/關)。觀察下方的性質如何變化。
自反?
對稱?
反對稱?
傳遞?
定義提示：
自反性：所有對角線格子都必須開啟。
對稱性：矩陣關於對角線對稱。
4.5 有限基數
如果兩個集合之間存在一個雙射，我們稱這兩個集合「等勢」，即它們的元素數量相同。
鴿巢原理 是一個直觀的計數定理：如果 n 個物體放入 m 個容器中，且 n > m，則至少有一個容器包含不止一個物體。
教材來源：Mathematics for Computer Science (Lehman, Leighton, Meyer)