AI 摘要

電腦科學數學：離散數學

筆記內容著重於電腦科學與人工智慧領域所使用的數學，依照概念、符號與公式整理重點脈絡，作為快速導讀、學習路線規劃與應用查找的直式索引。

集合論（Set Theory）

集合與元素（Set and Element）

元素屬於集合的基本關係：

$$x \in A$$

全集（Universal Set）

特定問題範疇內的所有元素所形成的集合。

$$U$$

空集合（Empty Set）

不包含任何元素的集合。

$$\emptyset$$

基數（Cardinality）

集合中元素的數量。

$$|A|$$

例如：

$$A=\{0,1\},\quad |A|=2$$

有限集合（Finite Set）

若集合的元素數量有限，則可表示為：

$$|A|=n,\quad n\in\mathbb{N}$$

集合建構式（Set-Builder Notation）

依據條件定義集合：

$$A=\{x\in\mathbb{R}\mid x>0\}$$

冪集（Power Set）

集合所有子集所形成的集合。

$$\mathcal{P}(A)$$

例如：

$$A=\{1,2\}$$ $$\mathcal{P}(A)=\{\emptyset,\{1\},\{2\},\{1,2\}\}$$

子集關係（Subset Relations）

子集（Subset）

$$A\subseteq B$$

表示 $A$ 的所有元素皆屬於 $B$。

真子集（Proper Subset）

$$A\subsetneq B$$

表示 $A$ 是 $B$ 的子集，且 $A\neq B$。

集合運算（Set Operations）

聯集（Union）

$$A\cup B=\{x\mid x\in A\text{ or }x\in B\}$$

交集（Intersection）

$$A\cap B=\{x\mid x\in A\text{ and }x\in B\}$$

差集（Set Difference）

$$A\setminus B=\{x\mid x\in A\text{ and }x\notin B\}$$

補集（Complement）

相對於全集 $U$ 的補集：

$$A^c=\{x\in U\mid x\notin A\}$$

笛卡兒積（Cartesian Product）

笛卡兒積描述集合之間的有序配對：

$$A\times B=\{(a,b)\mid a\in A,\;b\in B\}$$

由於配對具有順序，因此一般而言：

$$(a,b)\neq(b,a)$$

若 $A$ 與 $B$ 為有限集合，則：

$$|A\times B|=|A|\cdot|B|$$

多維擴展可表示為：

$$A_1\times\cdots\times A_k$$

關係（Relation）與函數（Function）皆可建立在笛卡兒積上：

$$R\subseteq A\times B$$ $$f\subseteq A\times B$$

函數與映射（Functions and Mappings）

函數定義（Function Definition）

函數是集合之間滿足單值性（Single-Valuedness）的對應關係：

$$f:A\to B$$

函數作用（Function Application）

若 $x\in A$，則函數將 $x$ 映射至 $B$ 中的某個元素：

$$x\in A,\quad f(x)\in B$$

指示函數（Indicator Function）

設 $A$ 為集合。指示函數將元素是否屬於 $A$ 表示為 $1$ 或 $0$：

$$\mathbf{1}_A(x)= \begin{cases} 1,&x\in A,\\ 0,&x\notin A. \end{cases}$$

排列組合（Combinatorics）

排列（Permutation）

排列考慮元素的順序。

不重複排列：

$$P_k^n=\frac{n!}{(n-k)!}$$

可重複排列：

$$n^k$$

組合（Combination）

組合不考慮元素的順序：

$$C_k^n=\frac{n!}{k!(n-k)!}$$