以下說明一些在講義中我們經常會用到,不過可能有些人不太熟悉的數學符號。在這裡我們只會說明符號的定義和舉例使用方法,不會深入探討各種運算的性質。本文只是整理常用到的符號,方便讀者在遇到看不懂的符號時可以快速查詢,可以不用一次把這裡的所有東西讀完並記住。
最常用的邏輯符號包含且(and)、或(or)、反(not),它們的符號分別是 $\land$、$\lor$ 和 $\neg$,就是等同於 C++ 裡 &&
、||
和 !
的意思。舉例來說:
(!(a > 3) && b < 6) || !(c + d > 10 || a + b == 123)
。注意到世人對 $\land$ 和 $\lor$ 的運算順序沒有什麼共識,所以同時出現時我們會加上括號來表示運算順序。以上都是「表示是或否的式子」也就是布林表達式。我們還會常常用到以下這些符號,$a$ 和 $b$ 都是布林表達式:
舉例來說:
一個集合(set)的意思是一堆不重複的東西,且這些東西沒有順序、可以沒有也可以有無限個,這裡的「東西」我們會稱為元素,可以是任何的數學物件,像是數字、數列等等。常見的數字集合有:
要表示一個集合的時候,我們通常會用一對大括號包起來,像是 $S=\{1,2,3\}$ 就是包含 $1,2,3$ 這三個數字的集合。$\varnothing$ 代表空的集合。$a \in S$ 代表 $a$ 是集合 $S$ 之中的一個元素,$a \notin S$ 則代表不是。比較巨大的集合我們也會用「滿足什麼樣條件的元素會在裡面」來表示,例如 $\{x \mid x < 10 \land x \in \mathbb{Z}\}$ 代表所有 $<10$ 的整數構成的集合(有時候 $x \in \mathbb{Z}$ 這類的條件會因為可以從前後文推測而被省略)、$\{x+5 \mid x \leq 3 \land x \in \mathbb{Z}^+\}$ 代表「由所有滿足 $x \leq 3$ 的正整數 $x$ 所得出的 $x+5$」所構成的集合,等同於 $\{6,7,8\}$,總之 $\mid$ 左邊的是在集合裡的元素們長什麼樣子,而裡面用到的變數必須滿足右邊的條件。
集合之間可以進行一些運算,得到一個新的集合,包含:
$\cup$、$\cap$ 的開口方向和對應意思的 $\lor$、$\land$ 是一樣的,非常好記。
也有用來表示集合與集合之間關係的符號:
有時候我們會規定一個宇集合(universal set),然後下文提到的集合全都是這個集合的子集。假設宇集合是 $U$,$\overline{A}$ 或 $A'$ 指的是 $A$ 的補集(complement),代表宇集裡所有不在 $A$ 之中的元素,例如 $U=\{1,2,3,4,5\}$、$A=\{1,2,3\}$,那 $\overline{A}$ 就是 $\{4,5\}$。
在表示一個區間的時候,我們常會使用區間記號。$[\ell,r]$ 代表 $\ell$ 到 $r$ 之間的數字構成的區間,包含 $\ell$ 和 $r$,$(\ell,r)$ 則代表不包含 $\ell,r$,也有混合版的 $[\ell,r)$ 和 $(\ell,r]$,中括號就代表包含,小括號則代表不包含。包含端點的區間我們稱之為閉區間,不包含則稱為開區間。區間可能是指其中所有實數,也可能是只有整數,依據前後文而定。區間是一種集合,舉例來說,$[\ell,r)=\{x \mid \ell \leq x < r\}$,所以也會跟各種集合相關的符號搭配使用。
\[ \sum_{k=a}^b f(k) \]
這坨東西的意思是對於 $k=a,a+1,\dots,b$,把 $f(k)$ 全部加起來,用程式碼來理解的話大概就是
int ans = 0;
for(int k = a; k <= b; k++){
ans += f(k);
}
像是 $\sum_{k=1}^3 k = 1+2+3$、$\sum_{k=1}^3 2k = 2+4+6$ 等等。有時候也會寫成
\[ \sum_{k \in S} f(k) \]
代表拿集合 $S$ 中所有的元素 $k$,將 $f(k)$ 加總起來。
有一個類似的符號是
\[ \prod_{k=a}^b f(k) \]
是類似的意思,只不過是把加換成乘。
要把一個實數變成整數的時候,我們會使用高斯記號,包含下高斯 $\lfloor x \rfloor$ 和上高斯 $\lceil x \rceil$,意思分別是「$\leq x$ 的最大整數」和「$\geq x$ 的最小整數」,白話一點說就是往下或往上找最靠近的整數,也就是向下取整和向上取整。舉個例子,$\lfloor 1.5 \rfloor = 1$、$\lceil \pi \rceil = 4$、$\lfloor -1.618 \rfloor = -2$。
注意到 C++ 之中的整數除法是「向零取整」,也就是在答案是正數時向下取整、答案是負數時向上取整,至於模運算 a % b
的結果其實是 a - a / b * b
,因此在 a / b
是負數時,a % b
的結果會是負的。我們在數學式子之中表示模運算時,會寫成 $a \bmod b$,不過一般來說我們會假設結果是 $\geq 0$ 的,也就是 $a \bmod b = a - \left\lfloor\frac{a}{b}\right\rfloor b$,要特別注意這和直接在 C++ 裡寫出 a % b
的結果是不同的。模運算的另一種寫法是 $a \equiv b \pmod{m}$,代表 $a \bmod m = b \bmod m$。
在表示因數倍數關係的時候,我們會用 $a \mid b$,讀作「$a$ 整除 $b$」,代表 $a$ 是 $b$ 的因數、$b$ 是 $a$ 的倍數、$\frac{b}{a}$ 是整數。
$\gcd(a,b)$ 代表 $a,b$ 兩個整數的最大公因數(如果有負數的話是代表 $\lvert a \rvert,\lvert b \rvert$ 的最大公因數)、$\text{lcm}(a,b)$ 代表最小公倍數,等同於 $\frac{\lvert a \times b \rvert}{\gcd(a,b)}$。