尚未整理的舊資料

以下資料已過時, 尚未整理

比較有效率的學習態度

這不是講義啦, 只是我上課內容的摘要提示, 還是要看課本和作習題才是!
離散數學只需要國中數學為基礎幾乎用不到幾何/微積分, 是數學不好的同學一個重新出發的大好機會.
要記憶中英文的專有名詞.
腳踏實地: 不要背公式, 要勤於舉例. 每學一個名詞, 一定要會舉例及舉反例. 小考考題當中也會不斷出現舉例題.
要嚴格檢查型別.

邏輯術語

要認得並理解這些術語; 完全不必理會這一單元中的定理與公式
statement/proposition (命題), negation
conjunction ("且"), disjunction ("或")
universal quantifer, existential quantifier
predicate (述語)
converse (逆命題)
equivalent (等價)

淺談證明

簡單的證明, 可從定義著手, 寫出前提與結論, 只需要填中間. 例如 Euclidean Algorithm 的引理.
counterexample (反例)
proof by contradiction (歸謬證法) 例如「根號 2 是無理數」, 又如「R 為不可數」
mathematical induction (數學歸納法): 像推骨牌一樣, 有 basis step 與 induction step.
使用數學歸納法證明範例:
1. 2^n < n! for all n > 3
2. f(n) < (7/4)^n for all n where f(n) are the Fibonacci numbers.
3. cos(t) + cos(3t) ... + cos((2n-1)t) = sin(2nt)/(2 sin(t))
4. 2^n 乘 2^n 大的地板當中任意挖掉一格, 必然可以用 L 型的 "三格磁磚" 舖滿.

遞迴關係式

一個函數, 如果它的定義當中又出現它自己, 這樣的定義方式即稱為一個 recurrence relation (遞迴關係式).
一個 sequence (數列) 當然也是函數, 它是 domain (定義域) 在 N 的函數.
一個 recurrence relation 當然不能無窮地遞迴下去, 就好像一個遞迴的副程式必須要有停止遞迴的條件一樣, 一個 recurrence relation 必須要有 initial condition.
用遞迴關係式表達難以直接解決的問題之範例 (答案在本頁的原始碼當中):
1. 平面上 n 條直線, 最多可以把平面分割成多少塊區域? 空間中 n 個平面, 最多可以把空間分割成多少塊區域?
2. 一片 3 * (2n) 的地板, 要用許多相同的 1 * 2 磁磚舖滿, 有多少種舖法?
3. 連續擲銅板 n 次, 紀錄所得的序列 (正反反正...), 試問「正面不連續出現」的序列有多少種?
4. n 個石子排成一列, 從左邊開始將石子取走, 每次至少取 1 顆, 至多取 4 顆, 直到全部取完為止, 共有多少種不同的取法? ("第一次取 2 顆, 第二次取 1 顆, ... 最後取 3 顆" 算做一種取法.)
5. n 個人的帽子掛在牆上, 漆黑之中每人亂取一頂, 試問有多少種取法, 每個人都拿到別人的帽子? ("1 號拿到 6 號的, 2 號拿到 5 號的, ... n 號拿到 2 號的" 算做一種取法.)
6. 0 到 10^n-1 的所有十進位數字當中, 有多少個數字內有連續三個 7? (連續更多個也可以; 連續的三個 7 出現不只一次也可以)
7. n 個矩陣相乘, 依計算的先後順序括上小括弧 (只影響乘法發生的順序; 矩陣排列的順序則不改變), 共有多少種不同的括法? (因矩陣乘法滿足結合律 associativity, 故各種不同的括法算出來的答案相同.)
Linear homogeneous relation of degree k with constant coefficients: a(n) = r1 a(n-1) + r2 a(n-2) ... + rk a(n-k)
上述類型的遞迴關係式, 其一般式可以由公式求得.
1. 例一: a(n) = a(n-1) + 12 a(n-2), a(0) = -2, a(1) = 13, 求 a(n) 的通式.
  解: 寫出這個遞迴關係式的 characteristic equation (特徵多項式): x^2 = x + 12, 解出兩根 4 與 -3, 令 a(n) = c1*4^n + c2*(-3)^n, 以 n=0 與 n=1 代入, 解得 c1=1, c2=-3. 記得用 n=2, n=3 代入檢查一下.
2. 例二: a(n) = 21*a(n-1) - 147*a(n-2) + 343*a(n-3), a(0) = 5, a(1) = 11, a(2) = -35, 求 a(n) 的通式.
  解: 寫出這個遞迴關係式的 characteristic equation (特徵多項式): x^3 = 21*x^2 - 147*x + 343, 解出三重根 7, 令 a(n) = c1*7^n + c2*n*7^n + c3*n^2*7^n, 以 n=0, n=1, n=2 分別代入, 解得 c1=5, c2=-4, c3=4/7. 記得用 n=3 代入檢查一下.
注意: 待定常數的個數, 遞迴關係式的次數, 最起碼的邊界條件的個數, 一定相同. 即使有重根出現也一樣.
Linear relation of degree k with constant coefficients: 分別解出 homogeneous solution 與 particular solution...

Cartesian Product 與 Partition

ordered pair, ordered tuple. (與集合不同. 兩個 ordered tuples 要稱得上相等, 必須元素個數相同, 且對應位置的元素相同.)
Cartesian product: A1 x A2 x A3 ... x An = { (a1,a2,...an) | a1 is in A1, a2 is in A2, ... an is in An }
Cartesian product 的元素個數, 等於各集合元素個數的乘積.
例: (A x B) union (C x D) 與 (A union C) x (B union D) 有什麼關係?
例: 線段與線段的 Cartesian product? 線段與圓? 圓與圓?
A partition of a set A (亦稱為 a quotient set of A): A 的某些子集合所成的集合. 這些子集合的聯集必須是 A; 兩兩交集必須是空集合. (用口語說, 就是把所有元素分成好幾國, 每個元素都不可以有雙重國籍, 也不可以沒有國籍.)
一個 partition 內的每個元素 (它本身當然是一個集合) 叫做一個 block 或 cell.
一個集合可以有很多不同的 partitions.
例: 列舉出 A = {a,b,c,d} 所有的 partitions.
例: 若 |A| = 6, 試問要把 A 分割成 3 個互斥子集合, 有多少種分法?
例: 令 A = {a,b,c} x {1,2,3} 試舉一個 A 的 partition 的例子, 要滿足:
1. partition 內的每個 cell 的元素個數相同.
2. cell 的個數又與每個 cell 的元素個數相同.
3. 每個 cell 內所含的所有元素 (各是一個 ordered pair), 其第一個元素不可以完全相同.
Q: r 個元素的集合, 可以有多少種不同的 partitioning 方式? 提示: 先計算 S(r,n), 把 r 個不同的物品置入 n 個相同的盒子當中, 且每個盒子都要分到物品, 有多少種分法? 這些數字稱為 Stirling numbers of the second kind. 原題的答案即為 S(r,1) + S(r,2) ... + S(r,r). 答案在網頁的 source 當中.

Binary Relations 基本概念

例: 定義一個從 Z 到 Z 的 binary relation | 如下: a | b 表示 "a 這個整數整除 b 這個整數".
例: 定義一個從 M 到 H 的 binary relation F 如下: a F b 表示 "a 這個男子為 b 這個人的父親".
例: 定義一個從 AP 到 OS 的 binary relation R 如下: a R b 表示 "a 這個應用程式可以在 b 這個作業系統上執行".
例: 定義一個從 S 到 S 的 binary relation RA 如下: a RA b 表示 "a 這顆星球繞著 b 這顆星球轉".
例: 定義一個從 A 到 P 的 binary relation E 如下: a E b 表示 "a 這種動物喜歡吃 b 這種植物".
其他例子: <, <=, ..., "a 認識 b", "副程式 a 呼叫副程式 b", "a 是 b 的父親或母親", ...
上述各例中, 左邊的集合叫做這個 relation 的 domain (定義域); 右邊的集合叫做它的 range (值域).
表示一個 binary relation R 的方法:
1. (集合表示法) 列舉出所有滿足 a R b 的 (a,b)
2. (矩陣表示法) 把所有的 a 在左邊排成一行, 所有的 b 在上面排成一列, 在矩陣的每個位置上填入 1 或 0 (視 a R b 是否成立而決定填 1 或填 0).
3. (有向圖表示法, 常用於 domain = range 時) 把所有的元素一一畫出來 (成為一個個 vertex). 若 a R b 就從 a 畫一道箭頭 (稱為一個 edge) 指向 b.

幾個常見名詞/符號: 以下假設 R 為一個從 A 到 B binary relation, 並以 A = {1,3,5}, B = {0,2,4,6}, "<" = { (1,2), (1,4), (1,6), (3,4), (3,6), (5,6) } 為例.

名詞/符號	set	digraph	範例
x R y	(x,y) in R	有一條 edge 從 x 指向 y	3 < 5
R(x), R-relative set of x	{ y in B \| (x,y) in R }	所有「被 x 指到」的 y.	"<"(3) = {4,6}
R(A1), R-relative set of A1	{ y in B \| (x,y) in R for some x in A1 }	所有「被 A1 內任何一個元素指到」的 y.	"<"({1,3}) = {2,4,6}
in-degree of y	\| { x in A \| (x,y) in R } \|	指向 y 的箭頭數.	in-degree(4) = 2
out-degree of x	\| { y in B \| (x,y) in R } \|	從 x 指出來的箭頭數.	out-degree(5) = 1
restriction of R to A1	R intersect (A1 x A1)	把 A1 以外的 vertices 及其上 edges 都拿掉.	(通常只用於 A = B 的場合)
complement of R	(A x B) \ R	把原有的 edge 去掉, 沒有的 edge 生出來.	{(1,0),(3,0),...(5,4)}
inverse of R	{ (y,x) \| (x,y) in R }	把所有的 edge 方向反過來.	{(2,1),(4,1),...(6,5)}

作業: 將上表加上一行 matrix 表示法的解釋.
Q: 令 A = B = { 1, 2, 3, 4, 5, 6 }, R 為 A 上的 "<" 這個 binary relation, x = 3, z = 4, A1 = {2,5}, 試以 set, matrix, digraph, 等三種表示法將上述各名詞表示出來.
Q: 從 Z 到 Z 的 binary relation "<", 它的 complement 是? 它的 inverse 是?
Q: 若 R 為一個從 A 到 B 的 binary relation, 且 x in A, 試問 R(x) 與 out-degree(x) 有何關係?
提醒: 當書本 (或考題) 說 "令 A x B 的一個子集合 R 表示 ... 這樣的一個 relation" 時, 請以集合表示法理解.
Q: 若 |A| = m, |B| = n, 則從 A 到 B 可以定義出多少個不同的 binary relations?

我們對什麼樣的 relations 有興趣? 若一個 binary relation R on A 內的所有元素都滿足 ... 特性, 則稱 R 為一個 ... relation.

特性	set	digraph
reflexive	(a,a) in R	每個 vertex 都指向自己.
irreflexive	(a,a) not in R	沒有一個 vertex 指向自己.
symmetric	(a,b) in R ==> (b,a) in R	有 edge 的地方一定都是雙向的.
asymmetric	(a,b) in R ==> (b,a) not in R	有 edge 的地方一定都是單向的 (而且沒有 vertex 指向自己).
antisymmetric	(a,b) in R and (b,a) in R ==> a=b	不同的兩個 vertices 之間最多只有一條 edge.
transitive	(a,b) in R and (b,c) in R ==> (a,c) in R	若 a 指向 b 且 b 指向 c, 則 a 指向 c

Q: 令 A 表 Gimp (一套類似 PhotoShop 的軟體, 喜歡畫圖的讀者一定要試試看!) 程式原始碼當中, 所有副程式所成的集合. 定義 C 為一個從 A 到 A 的 binary relation 如下: x C y 表示 x 的程式碼當中呼叫到 y. 試描述 A 的一個子集合 A1, 可以讓 restriction of C to A 為 reflexive.
partial order: reflexive, transitive, antisymmetric 的 binary relation. 例: a 整除 b; A 這個集合包含於 B 這個集合; ...
equivalence relation: reflexive, transitive, symmetric 的 binary relation. 例: a is congruent to b mod 7; a 與 b 這兩顆星球繞著同一顆星球轉; ...
equivalence relation (「同一國的關係」) 與 partition (「把所有元素分成那幾國」) 其實是同一觀念的不同表示法, 從一個可以產生出另外一個.
equivalence class of x 記為 [x], 其實就是先前定義的 R(x), 也就是「和 x 同一國的所有元素所成集合」.
Q: 以下各集合各滿足上述那些特性? R1 = {(a,a) | a is in A}, R2 = {(a,b) | a != b}, R3 = {(a,b) | a, b are in A}, R4 = {}

衍生出來的 relations

complement of R: (A x A) \ R
inverse of R: R^-1 = { (b,a) | (a,b) is in R }
reflexisive closure of R: R union { (a,a) | a in A }
symmetric closure of R: R union R^-1
transitive closure of R: ...
所謂 "R 的 ... closure" 就是在 R 當中加入最少的元素對, 讓新的 relation 滿足 ... 特性.
Q: 若一個集合原本就已經是 reflexive, 則它的 reflexive closure 為? 若原本就已經是 symmetric, 則它的 symmetric closure 為?
Q: 「a 是 b 的手足」的 reflexive closure 是? 「a 是 b 的丈夫」的 symmetric closure 是? 「a 是 b 的父母」的 transitive closure 是? 「a 知道 b 的電話號碼」的 transitive closure 是? (答案在原始檔中)
composition of R and S: 若 R 為從 A 到 B 的 relation, S 為從 B 到 C 的 relation, 則定義 R 與 S 的 composition 為 { (a,c) | 存在 b 使得 (a,b) in R 且 (b,c) in S } 並記為 S o R
例:
1. 「a 這學期修 b 這門課」與「b 這門課在星期 c 這天有課」的 composition 為「a 這學期在星期 c 這天有課」.
2. 「a 這個出版社曾經出版過 b 這本書」與「b 這本書可以算是 c 這類的書」的 composition 為「a 這個出版社曾經出版過 c 這類的書」.
3. 「a 是 b 的兒子或女兒」與「b 是 c 的父親或母親」的 composition 為「a 是 c 的兄弟姊妹」
4. 「a 是 b 的父親或母親」與「b 是 c 的兒子或女兒」的 composition 為「a 是 c 的夫妻或自己」
從最後兩個例子可以看出: S o R 與 R o S 不一定相等. 事實上即使 S o R 存在, R o S 甚至未必存在.
符號: (S o R)(x) = S(R(a)) 與 a 有關係的所有 c 所成集合.
若 binary relation R 以矩陣方式表示為 M_R, S 以矩陣方式表示為 M_S, 則 S o R 如何以矩陣表示? 把一般矩陣乘法的定義當中的數字乘法改成 and, 把數字加法改成 or, 所得結果記為 M_R Q M_S 稱為 M_R 與 M_S 的 boolean product, 這個結果正好就是 S o R 的矩陣表示法. 想法: 只要存在有任何一個 b (多了也沒關係) 使得 a R b 且 b R c, 則稱 a (S o R) c.
Q: 給你兩個 relations R 與 S 用 digraphs 表示, 如何求出 S o R 的 digraph 表示法? 提示在本頁 source 某處.
transitive closure of R: 若 R 以矩陣表示為 M_R, 則 R 的 transitive closure 以矩陣表示為 M_R Q M_R² Q M_R³ ... (事實上若 A 內的元素個數為 n, 則上面的無窮 boolean product 只要算前面 n 項就夠了.)

Warshall's algorithm for computing Transitive Closure:

        for k=1,2,3...n
            列出可以到達 k 的 i 有那些 (第 k 列所有 1 出現的地方)
            列出從 k 可以到達的 i 有那些 (第 k 行所有 1 出現的地方)
            將所有的 (i,j) 填 1.
        end

到第 k 步為止, 所求得的結果並不是 M^k 也不是 M union M^2 union ... M^k 而是「若只准以 1,2,...k 為中繼站, 有那些地方可以相通?」

函數

何謂函數? 凡是滿足以下特性的 relation 都叫做函數: f 是一個從 A 到 B 的 binary relation, 且 A 的每個元素 a 都滿足 f(a) 恰有一個元素. (注意: 這裡的 f(a) 是 relation 的符號, 也就是 f-relative set of a). 亦即: 若一個 relation 的 domain 當中的每個元素的 out degree 都恰為 1, 則這個 relation 即是一個函數.
約定俗成的偷懶表示法: 若 f 為一個函數, 我們可以將 f(a) = {b} 簡單地寫成 f(a) = b 就好.
函數亦稱為 mapping (映射) 或 transformation (轉換). f(a)=b 當中的 a 稱為 argument (引數), b 稱為 image of a under f (a 在 f 作用下所得到的映象).
從 A 到 B 的 binary relation f, 若它恰好是一個 function, 我們經常用這樣的寫法來表示: f : A --> B
one-to-one function: 「不同的 a 必然映射到不同的 b」這類函數. 又叫做 injective function 或 injection (嵌射, 一山不容二虎). 亦即, 每個 b 的 in-degree 至多是 1.
onto function: 「每個 b 都是某個 a 的映象」這類函數. 又叫做 surjective function 或 surjection (蓋射, 每座山上都有老虎). 亦即, 每個 b 的 in-degree 至少是 1.
one-to-one correspondence between A and B: 既是 injective 又是 surjective 的函數. 又叫做 bijective function 或 bijection. 亦即, 每個 b 的 in-degree 恰為 1.
一般的函數 f, 它的 inverse relation f^-1 不一定滿足函數的定義; 但若 f 為 bijective, 則 f^-1 (它的 inverse relation) 不僅是一個 relation, 還會是一個 bijective function. f^-1 稱為 f 的 inverse fucntion (反函數); 我們說 f 是一個 invertible function (因為可以對它求反函數).
因為每個函數也都是一個 relation, 所以像 inverse 與 composition 這樣的觀念都被 "繼承" 下來了. 但要注意 f 的 inverse relation 一定存在; 但 f 的 inverse function 不一定存在.

Order Relations

一個從 A 到 A 的 binary relation R, 若滿足 reflexivity, transitivity, antisymmetry, 則稱為一個 partial order. (A, R) 稱為一個 partially ordered set, 或簡稱為 poset.
若 R 為一個 partial order, 則 R^-1 也是一個 partial order, 稱為 R 的 dual. 例如 "小於等於" 的 dual 是 "大於等於"; "包含於" 的 dual 是 "包含", "a 是 b 的因數" 的 dual 是 "a 是 b 的倍數",...
一個 poset (A, R) 當中的兩個元素 a 與 b, 如果 aRb 或 bRa 成立, 則稱 a 與 b 為 comparable. 若 (A, R) 當中的每一對元素都是 comparable, 則稱 R 為一個 linear order, 稱 A 為一個 linearly ordered set, 又稱為 chain.
Q: 請對上述每一名詞舉例.
定理: poset 的 digraph 表示法中, 只會有 loop, 不會有更長的 cycle 出現.
Hasse diagram: 簡化的 poset 表示法.
1. 把所有的 loop 省略不畫 (反正我們知道 poset 一定是 reflexive)
2. 把所有 "由 transitivity 可以推導出來的關係" 省略不畫. (反正我們知道 poset 一定是 transitive)
3. 將 diagram 擺設成所有的箭頭都往上指, (由上述定理知道這一定可以辦得到) 並把所有的箭頭省略不畫,
請練習把 poset 的 digraph 表示法與 Hasse diagram 互換.
假設 (A,R) 與 (B,S) 為兩個 posets. 一個從 A 到 B 的函數 f, 如果它是 one-to-one correspondence (bijection) 而且又滿足: a R b <==> f(a) S f(b), 則稱 f 為一個從 (A,R) 到 (B,S) 的 isomorphism (同構).
兩個 posets 之間, 如果可以找到 isomorphism, 則稱這它們為 isomomorphic posets.
例: 令 A = 2^{a,b,c}, R 為 A 上面的 "包含於" 關係; B = {1,2,3,5,6,10,15,30}, S 為 B 上面的 "整除" 關係. 則 (A,R) 與 (B,S) 同構. (事實上它們之間有好幾個 isomorphisms.)
isomorphism 的直覺解釋: 換湯不換葯; 換零件的標籤不換相對關係, 換零件的廠牌不換整體結構 (所以叫做同構).
自己與自己之間的 isomorphism 叫做 automorphism.
為何研究 isomorphism? 希望只要研究少數的 posets, 就可以把所有的定理搬到其他同構的 posets 上直接使用, 不必再證明一次.

Undirected Graph

一個 undirected graph G = (V,E) 包含兩部分: vertices 及 edges.
一個 edge 的表示法: 在無向圖中, 用 {u,v} 表示; 在有向圖中用 (u,v) 表示.
一個 vertex v 的 degree: 接在 v 上面的 edges 端點個數.
兩頭都落在同一個 vertex 上面的 edge, 叫做一個 loop. (這樣的 edge 對這個 vertex 的 degree 貢獻了 2 次.) 如果沒有特殊說明, 通常我們都假設所討論的 graph 當中沒有 loop.
degree 為 0 的 vertex 叫做一個 isolated vertex.
一個 edges 兩頭的 vertices 稱為 adjacent vertices.
一連串接在一起, 不重複經過同一 vertex 的 edges, 稱為一個 simple path.
起點和終點相同的 simple path, 稱為一個 simple cycle.
一個 graph G 當中, 如果任兩個 vertices 之間都可以找到 simple path, 則稱 G 為 connected; 否則稱 G 為 disconnected. 一個 graph 的每一小塊自成 connected 的部分, 稱為一個 connected component.
特殊的 graphs:
1. discrete graph: 沒有 edges, 每個 vertex 都是一個獨立的 connected component.
2. linear graph: ...
3. complete graph K_n: 任兩個 vertices 之間都有 edge (共 n(n-1)/2 個 edges).
4. bipartite graph: 一個 graph, 如果可以找到一種拆法, 把它所有的 vertices 分成兩國, 讓所有的 edges 都橫跨兩國, 而同一國內的 vertices 彼此之間都沒有 edges, 則稱此 graph 為 bipartite graph. 例: 表達「那幾個男生愛那幾個女生」的 graph.
5. complete bipartite graph K_m,n: 是一種特殊的 bipartite graph, 兩國各有 m, n 個 vertices, 且每一對分屬不同兩國的 vertices 之間, 都有 edge 相連. (共 mn 個 edges)
從 G = (V,E) 的 V 與 E 當中隨便取出來的子集合 V' 與 E' (當然 E' 內所有 edges 的端點必須落在 V' 之內) 所構成的圖 G' = (V',E') 稱為 G 的一個 subgraph.
若 G = (V,E), 且有一個集合 F 讓 (V,E union F) 成為 complete graph, 讓 (V, E intersect F) 成為 discrete graph, 則稱 (V,F) 為 complement of G.
若 G1 = (V1, E1), G2 = (V2, E2), 且 f 為一個從 V1 到 V2 的 one-to-one correspondence, 並且保留對應 vertices 之間的相鄰關係, 則稱 f 為一個從 G1 到 G2 的 isomorphism. 兩個 graphs 之間如果可以找到 isomorphism, 則稱它們為 isomorphic graphs.
自己到自己的 isomorphism 叫做 automorphism.

Planar Graphs

可以被 embed (嵌) 到平面上, 而所有 edges 互不交叉的圖, 叫做 planar graph.
Kuratowski' Theorem: 一個圖 G 為 non-planar graph <==> G 至少有一個 subgraph 與 K₅ 或 K_3,3 homeomorphic.
Euler's Formula: 凡是一個 planar graph, 它的 vertices, edges, regions 的個數之間必滿足下列等式: v-e+r=2
一個 planar graph 若它沒有 loop 且至少含一個 edge, 則必滿足 3r <= 2e 且 e <= 3v-6. 所以 r 屬於 O(v) 且 e 屬於 O(v).
若 G 為一個 planar graph, 則可由 G 定義出它的一個 dual graph (對偶圖) G^d 如下: 在 G 的每個 region r (含 infinite region) 內畫一個 G^d 的 vertex 叫它 r^d; 找出每對相鄰的 regions r1 與 r2 , 及它們之間的分界 edge e, 然後把 r1 與 r2 的 dual vertices r1^d 與 r2^d 用一條 G^d 的 edge 連起來, 命名為 e^d.
Dual graph 的例子: 地圖上的國家邊界, 它的 dual graph 代表國與國的相鄰關係.

本頁最新版網址: https://frdm.cyut.edu.tw/~ckhung/b/dm/misc.php; 您所看到的版本: February 14 2012 10:32:25.
作者: 朝陽科技大學資訊管理系洪朝貴
寶貝你我的地球, 請減少列印, 多用背面, 丟棄時做垃圾分類。
本文件以 Creative Commons Attribution-ShareAlike License 或以 Free Document License 方式公開授權大眾自由複製/修改/散佈。