寫在前面

最近一次聽到離散數學四個字還是在復試的時候，英語部分結束后第一個問題就是：“你本科是數學專業的哈，那你說說離散數學在計算機科學中的應用”
我：“我暫時只能想到在寫代碼的時候會涉及到命題邏輯的相關內容，整個函式的流程與各種條件判斷都有關聯，沒記錯的話應該是離散數學課本第一章的內容，其他的應用就不清楚了”，

然后今天看了下成績單：

大二下學期的課程，而且才68分，差不多是學過，也沒學過，下面的內容基于閔老師原文和大二那本沒丟的離散數學教材，

1.集合

1.1 定義

書中說，集合是不能精確定義的基本概念，集合的表示有2種方法，列元素法和謂詞表示法，
如： A = { 0 , ± 1 , ± 2 , ± 3 } A=\{0,±1,±2,±3\} A={0,±1,±2,±3} —列元素法
B = { x ∣ x ∈ Q ∧ x 2 ≤ 9 } B=\{x|x∈\textbf{Q}\wedge x2≤9\} B={x∣x∈Q∧x2≤9} —謂詞表示法
A,B其實是同一個集合的不同表示，

習題 1: { 0 , 1 , { 0 , 1 } , { 1 , 2 } } \{ 0 , 1 , \{ 0 , 1 \} , \{ 1 , 2 \}\} {0,1,{0,1},{1,2}} 有幾個元素? 機器學習中, 這類形式的集合有什么優點和缺點?

答：有4個元素，集合本身也可以作為集合的元素，(類似資料結構的廣義表？)
對機器學習的影響 (純猜測)：
1、優點：以集合作為元素時，容納了比同樣基數的另一個集合更多的資料，可以包含更多種類的資料，
2、缺點：預處理資料時可能會碰到麻煩，比如如果要先找資料的中位數、三分位數、平均數，那么作為元素的集合應該如何參與平均值的計算呢，集合作為在劃分訓練集和測驗集時或許也會有問題，

1.2 基數、笛卡爾積

集合 A \mathbf{A} A的基數，即其元素個數, 記為 ∣ A ∣ |\mathbf{A}| ∣A∣或 c a r d A cardA cardA.

習題2： ? \emptyset ? 的基數是多少? { ? } \{\emptyset\} {?} 呢?

答：不含任何元素的集合稱為空集， ? \emptyset ?的基數為0
{ ? } \{\empty\} {?}有一個空集元素，基數為1

笛卡爾積定義： A 1 × A 2 . . . A n = { ( x 1 , x 2 , . . . x n ) ∣ x 1 ∈ A 1 , . . . x n ∈ A n } A_1 \times A_2...A_n = \{(x_1,x_2,...x_n)|x_1\in A_1,...x_n\in A_n\} A1?×A2?...An?={(x1?,x2?,...xn?)∣x1?∈A1?,...xn?∈An?}
【二維數軸上的點(a,b)和(b,a)不一樣， x n x_n xn?應該對應 A n A_n An?】

書中定義：設集合 A , B A,B A,B, A A A中元素和 B B B中元素構成有序對，所有這樣的有序對組成的集合稱作 A A A和 B B B的笛卡爾積，記作 A × B A\times B A×B.
A × B = { ? x , y ? ∣ x ∈ A ∧ y ∈ B } A\times B = \{\langle x,y\rangle |x\in A\wedge y\in B\} A×B={?x,y?∣x∈A∧y∈B}.

笛卡爾積 可以完美地表示混合型別的資料. 任何實體都可以用這種元素描述, 但反過來, 并非所有的元素都對應于資料集中的一個實體.
資料集的表示方法：
1):矩陣表示法
當各個屬性都為實型值 [實數或浮點數]，資料集可表示為 D ∈ R m × n \mathbf{D}∈\mathbb{R}^{m×n} D∈Rm×n,表示每個實際資料集都是 n × m n×m n×m維空間的一個點而已，如果記 D = ( x 1 , x 2 , … , x n ) T \mathbf{D}=(x_1,x_2,…,x_n)^T D=(x1?,x2?,…,xn?)T,則 x i ∈ R m x_i∈\mathbb{R}^m xi?∈Rm.

2):集合與向量混合法
D = { x 1 , x 2 , … , x n } \mathbf{D}=\{x_1,x_2,…,x_n\} D={x1?,x2?,…,xn?},其中 x i ∈ R m x_i∈\mathbb{R}^m xi?∈Rm

優缺點對比:
i) 集合與向量混合法中, 元素可以隨意交換順序, 這與現實資料的獨立性一致; 【矩陣表示法是有序的】
ii) 集合與向量混合法中, 不允許兩個元素相同, 這與現實情況不一致;
iii) 矩陣表示法可以支持矩陣的相乘, 易于表示加權等操作, 用于神經網路, 線性回歸時方便.

1.3 冪集

書上定義：設 A A A為集合，把 A A A的全部子集構成的集合稱作 A A A的冪集，可記作 2 A 2^A 2A或者 P ( A ) P(A) P(A) 【 2 A 2^A 2A的每個元素都是一個集合】
例： A = { 1 , 2 , 3 } A=\{1,2,3\} A={1,2,3},將 A A A子集分類：
0元子集： ? \empty ? 【空集是任何集合的子集】
1元子集： { 1 } , { 2 } , { 3 } \{1\},\{2\},\{3\} {1},{2},{3}
2元子集： { 1 , 2 } , { 1 , 3 } , { 2 , 3 } \{1,2\},\{1,3\},\{2,3\} {1,2},{1,3},{2,3}
3元子集： { 1 , 2 , 3 } \{1,2,3\} {1,2,3}
對于 n n n元集，子集總數為 C ( n , 0 ) + C ( n , 1 ) + … C ( n , n ) = 2 n C(n,0)+C(n,1)+…C(n,n)=2^n C(n,0)+C(n,1)+…C(n,n)=2n
即，例 A A A中， ∣ 2 A ∣ = 2 ∣ A ∣ = 2 3 = 8 |2^A|=2^{|A|}=2^3=8 ∣2A∣=2∣A∣=23=8

2 二元關系

關系的本質是集合，

集合滿足以下任一條件都可以稱作為一個關系，如 R = A × B R=A\times B R=A×B
1):集合非空，且它的元素都是有序對，
2):空集

老師博客中給出的Definition 3. Let A A A and B B B be two sets. Any R ? A × B \mathbf{R} \subseteq \mathbf{A} \times \mathbf{B} R?A×B is a binray relation. R R R集合是笛卡爾積 A × B A\times B A×B的子集，由笛卡爾積的定義，R集合必然滿足條件1

3 函式

定義域、值域
老師提出的10號坑：函式是否是關系呢?
函式是關系，但關系不一定是函式，因為函式需要自變數有唯一確定的因變數，
y = 1 ? x 2 y = \sqrt{1 - x^2} y=1?x2 ? 可以寫成集合 R 1 = { ? 0 , 1 ? , ? ? 1 , 0 ? , ? 1 , 0 ? } R_1=\{\langle0,1\rangle,\langle-1,0\rangle,\langle1,0\rangle\} R1?={?0,1?,??1,0?,?1,0?}, R = D × V R=D\times V R=D×V,每個 x i ∈ D x_i\in D xi?∈D都有唯一對應的 y i ∈ V y_i\in V yi?∈V所以是函式，
反之，單位圓 x 2 + y 2 = 1 x^2+y^2=1 x2+y2=1 ，可以舉反例 R 2 = { ? 0 , 1 ? , ? 0 , ? 1 ? . . . } R_2=\{\langle0,1\rangle,\langle0,-1\rangle...\} R2?={?0,1?,?0,?1?...},所以不是函式，

習題 5: 多標簽學習中, 輸出為一個向量，相應的學習器算不算函式呢?

答：算，標簽資訊 → \rarr →向量是一個關系，輸出的向量可以由自變數唯一確定，所以是個函式，

4 元組

從資料結構的角度, 元組就是抽象資料型別; 從面向程式設計的角度, 元組就是一個類，

關于老師對樹的定義，我只看懂部分，我的理解如下：
首先定義樹 T = ( V , r , p ) , T=(\mathbf V,r,p), T=(V,r,p),其中集合 V \mathbf V V是節點集， r ∈ V r\in \mathbf V r∈V是根節點， r r r是 { v 1 , v 2 . , . . . , v n } \{v_1,v_2.,...,v_n\} {v1?,v2?.,...,vn?}中的任一個， p p p不是很明白，猜測是要滿足節點到節點的函式？？暫時抽象為節點到節點的邊，
條件a:節點 v v v不會回到 v v v，即 無環路
條件b:每個節點 v v v都有到根節點的唯一路徑

本來看到條件a的時候還有疑問：如果是這樣的圖，自己到自己有一條邊，在a條件k>1的情況，不就不滿足樹了嗎，然后看到條件b，那沒事了，

但是看了下教材，似乎可以這樣把條件縮減成一個：任意2個節點間存在唯一路徑，
試著寫一下： ? v 1 , v 2 ∈ V , ? 1 k > 0 , 使 p k ( v 1 ) = v 2 \forall v_1,v_2\in \mathbf V,\exist1k>0,使p^k(v_1)=v_2 ?v1?,v2?∈V,?1k>0,使pk(v1?)=v2?

習題 6: 元組只能表達物件的資料部分, 還是可以完整地表達 (既包括資料, 也包括方法/函式)? 用一個具體的程式來說明.

答：完整表達，用老師文中的例子說明，

public class Academy{
	private Staff stf[]; // 教職工集合
	private String presidentNum; // 院長工號
	private String partySecretaryNum; // 書記工號
	private Student std[]; // 學生集合
	private Laboratory lbr[]; // 實驗室集合
	
	//元組也包括方法\函式
	public boolean isStd(String stdNumber){
		//...
		//由學號判斷是否為本學院學生的方法
	}
}
// 教職工
public class Staff{
	private String name;
	private String sNumber; // 工號
	//...
}
// 學生
public class Student{
	private String stdNumber;
	//...
}
// 實驗室
public class Laboratory {
	private String lbrName;
	//...
}

習題 7: 定義二叉樹

T = ( V , r , p ) , V , r , p T=(\mathbf V,r,p),V,r,p T=(V,r,p),V,r,p和老師定義的樹的含義一樣，二叉樹的話應該加點條件
1：節點的度不大于2 ，我的理解是，除了根節點，有不超過3條邊(1入2出)，根不超過2條
1.1:非根節點：任意非根節點相鄰的節點都屬于一個V的子集合A，A的基數小于等于3
? v ∈ V \ { r } → A , p 1 ( v ) = w i , ? w i ∈ A ? V , ∣ A ∣ ≤ 3 \forall v\in \mathbf V\backslash \{r\}\rarr\mathbf A,p^1(v)=w_i,\forall w_i \in \mathbf A\subseteq\mathbf V,|\mathbf A|\leq3 ?v∈V\{r}→A,p1(v)=wi?,?wi?∈A?V,∣A∣≤3
1.2：根節點，根節點相鄰節點屬于一個V的子集合B，B基數小于等于2
p 1 ( r ) = w i , ? w i ∈ B ? V , ∣ B ∣ ≤ 2 p^1(r)=w_i,\forall w_i\in\mathbf B\subseteq\mathbf V,|\mathbf B|\leq2 p1(r)=wi?,?wi?∈B?V,∣B∣≤2
2：任意2個節點間存在唯一路徑，滿足樹的定義
? v 1 , v 2 ∈ V , ? 1 k > 0 , 使 p k ( v 1 ) = v 2 \forall v_1,v_2\in \mathbf V,\exist1k>0,使p^k(v_1)=v_2 ?v1?,v2?∈V,?1k>0,使pk(v1?)=v2?
3：左子樹右子樹有區別，是有序樹
不太會，函式自變數加一個？ f : V × D → V , D = { l e f t , r i g h t } f:\mathbf V\times D\rarr\mathbf V,D=\{left,right\} f:V×D→V,D={left,right}

函式是關系，關系是集合，那么這樣列舉表示函式應該沒問題？ { ? r 1 , l e f t , r 2 ? , ? r 1 , r i g h t , r 3 ? , ? r 3 , l e f t , r 4 ? } \{\langle r_1,left,r_2\rangle,\langle r_1,right,r_3\rangle,\langle r_3,left,r_4\rangle\} {?r1?,left,r2??,?r1?,right,r3??,?r3?,left,r4??}

習題7

T = ( V , r , D , f ) T=(\mathbf V,r,\mathbf D,f) T=(V,r,D,f)

V = { v 1 , v 2 , . . . , v n } \mathbf V=\{v_1,v_2,...,v_n\} V={v1?,v2?,...,vn?} 節點集
r ∈ V r\in\mathbf V r∈V 根節點
D = { d 1 , d 2 } D=\{d_1,d_2\} D={d1?,d2?} 左右子樹區分 d1=left d2=right
f : V × D → V \ { r } f:\mathbf V\times D\rarr\mathbf V\backslash \{r\} f:V×D→V\{r} 找子節點的函式

滿足：
a): ? v ∈ V , ? d ∈ D , ? k > 0 , f k ( v , d ) ≠ v \forall v\in \mathbf V,\forall d\in \mathbf D,\forall k>0,f^k(v,d)≠v ?v∈V,?d∈D,?k>0,fk(v,d)?=v 對任意節點執行k次找子節點的函式，不會找到自己，即無環路
a條件改進思路1:反函式
f f f應該滿足雙射條件，所以有 f ? 1 ： V \ { r } → V × D f^{-1}：\mathbf V\backslash\{r\}\rarr\mathbf V \times\mathbf D f?1：V\{r}→V×D
那么 ? v ∈ V \ { r } , ? k > 0 \forall v\in\mathbf V\backslash\{r\},\forall k>0 ?v∈V\{r},?k>0有 f ? 1 k ( v ) ≠ ( v , d 1 ) o r ( v , d 2 ) {f^{-1}}^k(v)≠(v,d_1)or(v,d_2) f?1k(v)?=(v,d1?)or(v,d2?)
即：任意非根節點執行f的反函式 (父節點+自己是左孩子or右孩子)k次，不會找到自己，即無環路
思路2:把 d d d的任意性由符號語言表達清楚，
? v ∈ V , ? k > 0 \forall v\in \mathbf V,\forall k>0 ?v∈V,?k>0有 f 1 ( f 1 ( f 1 ( . . . f 1 ( v , q 1 ) . . . , q k ? 2 ) q k ? 1 ) , q k ) ≠ v f^1(f^1(f^1(...f^1(v,q_1)...,q_{k-2})q_{k-1}),q_{k})≠v f1(f1(f1(...f1(v,q1?)...,qk?2?)qk?1?),qk?)?=v,其中 q i ∈ D q_i\in\mathbf D qi?∈D
對任意節點執行k次找子節點的函式，不會找到自己，中 q i q_i qi?隨便取左還是右，不限于單邊樹，說明無環路

b): ? v ∈ V , ? d ∈ D , ? 1 k > 0 , 使 f k ( r , d ) = v \forall v\in \mathbf V,\forall d\in \mathbf D,\exist 1k>0,使f^k(r,d)=v ?v∈V,?d∈D,?1k>0,使fk(r,d)=v 根節點到任意非根節點都有唯一路徑

上述兩點滿足樹的定義，且滿足二叉樹的有序性(左右子樹)
c):節點的度不大于2
任意節點的子節點都屬于一個V的子集合A，A的基數小于等于2
? v ∈ V , ? d ∈ D , f 1 ( v , d ) = w i , ? w i ∈ A ? V , ∣ A ∣ ≤ 2 \forall v\in \mathbf V,\forall d\in \mathbf D,f^1(v,d)=w_i,\forall w_i \in \mathbf A\subseteq\mathbf V,|\mathbf A|\leq2 ?v∈V,?d∈D,f1(v,d)=wi?,?wi?∈A?V,∣A∣≤2