來源：北京大學《離散數學》公開課
地址：https://www.bilibili.com/video/av18896337/?p=12
2.1 有序對和卡氏積
- 有序對<a,b>：有順序，類似于數組，可以用集合定義。
性質：有序對內元素對應相等
- 卡氏積A×B：所有元素一個來自A集合，另一個來自B集合的有序對
性質：不滿足交換律，不滿足結合律，對并和交滿足分配律，具有單調性（證明見北大教材p25）
2.2 二元關系
- A到B的二元關系定義：A×B的任一子集，即A×B冪集中的一個元素組成的集合（注意二元關系也是集合）
- A到B的二元關系的總個數：|P(A×B)|
- A上的特殊二元關系：空關系、恒等關系、全域關系、整除關系，大于小于關系，包含關系（只有包含關系定義在冪集P(A)上，見p26）
- 定義域、值域、域（由二元關系定義的集合）
- 關系的特殊情況：F是單根的、F是單值的（即F定義了一個函數）
- 二元關系的運算：
- 逆F^-1：將關系集合中所有的有序對反向
- 逆序合成FoG：有公共中間元素的有序對的集合
- 限制F↑A：x屬于A的關系集合
- 象F[A]：F↑A的值域，定義域為A的有序對集合對應的值域
- 合成運算定理1：合成運算結合律（重要）
- 合成運算定理2：A與B合成運算的逆=B逆與A逆的合成運算
2.3 關系的表示和關系的性質
- 關系矩陣（圖的矩陣表示）
- 關系圖
- 關系的性質
- 自反性：每個點都有環
- 反自反性：每個點都沒有環
- 對稱性：任意兩點間要么有兩條邊要么沒邊
- 反對稱性：任意兩點間都沒有兩條邊
- 傳遞性：可走捷徑（注意考慮有環的情況）
2.4 關系冪運算和關系閉包
（一）關系冪
- 關系R的n次冪：R與自己合成n次后得到的關系集合。也可以理解為G(R)中長度為n的路徑的起點和終點組成的有序對的集合
- 關系冪具有指數律：R^m * R^n = R^(m+n)，(R^m)^n=R^(mn)
（二）閉包
- R的閉包的定義：包含R，滿足給定性質，最小的有序對集合（包含于任意一個）
- 閉包的種類：
- 自反閉包：r(R)
- 對稱閉包：s(R)
- 傳遞閉包：t(R)
3. 閉包運算的性質
- 定理2.19：閉包運算有不動點
- 定理2.20：閉包運算有單調性（即較大的集合的閉包也較大）
- 定理2.21：閉包運算對自反閉包和對稱閉包的并有分配律，對傳遞閉包的并沒有分配率
4. 閉包的集合求法：
- 定理2.22：自反閉包=R U 恒等關系
- 定理2.23：對稱閉包=R U R的逆
- 定理2.24：傳遞閉包=R U R^2 U R^3 U.....（求傳遞閉包，就是把從此點可走到的點直接連起來）
5. 閉包的圖求法：
- 自反閉包：所有定點加環
- 對稱閉包：所有單向邊化為雙向邊
- 傳遞閉包：遍歷所有點，把從此點可達到的點直接與此點連起來
6. 閉包的矩陣求法：
- 自反閉包：主對角線全部改成1
- 對稱閉包：改為對稱矩陣
- 傳遞閉包：矩陣R 邏輯或 矩陣R^2 邏輯或 矩陣R^3........（邏輯或指：對所有運算式中的矩陣的每個對應位置上的元素進行或運算）
7. 定理2.25：求閉包后關系性質是否改變
- 自反性在求閉包后保持不變
- 對稱性在求閉包后保持不變
- 傳遞性在求對稱閉包后可能改變（反例：a->b具有傳遞性，但它的對稱閉包為a<->b，不具有傳遞性，因為a到a要兩步才能達到）
8. 定理2.26：閉包運算的交換律
- 求自反閉包和對稱閉包運算可交換
- 求自反閉包和傳遞閉包運算可交換
- 求對稱閉包和傳遞閉包運算不可交換，其中先求傳遞閉包再求對稱閉包得到的閉包較大
2.5 等價關系和劃分
- 等價關系
- 定義
等價關系R是自反，對稱，傳遞的二元關系
- 用等價關系分類
空關系（不是等價關系）、恒等關系（是等價關系，把每個元素自己分成一類）、全域關系（是等價關系，把所有元素分成一類）
2. 等價類
- R的等價類定義
所有與x有R關系的y的集合，記為[x]
- 等價類的一個例子
R為除以3后的同余關系（即x與y除以3的余數相等）
可證：除以n后的同余關系為等價關系（證：xRy等價于關系式x-y=k*n, 其中k為整數。由定義易證此關系式滿足自反性、對稱性，傳遞性）
現取dom={1,2,3,4,5}
那么有等價類：
[1]=[4]={1,4}（1,4是一個等價類，余數都是1）
[2]=[5]={2,5}（2,5是一個等價類，余數都是2）
[3]={3}（3是一個等價類，余數都是0）
在G(R)上可觀察到，1,4；2,5；3分別滿足全域關系（所有的點之間連通），即每個等價類內部具有全域關系
由此性質可知，得到關系的等價類后，就可以直接推導出所有的關系
- 等價類的性質（定理2.27）
- 非空（由于等價關系需滿足自反性，所以等價類中至少包含x自己）
- 若xRy，則[x]R=[y]R（因為等價關系R滿足對稱性和傳遞性。由對稱性：y與x有關，由傳遞性：y與x有關，x與其他元素有關，則y與所有與x有關的元素有關。反之，x與所有與y有關的元素有關，所以x與y的相關元素相同）
- 若x和y無關，則[x]R與[y]R不相交（反證法：若[x]R與[y]R有一個共同元素z，那么參考2的思路，由對稱性和傳遞性可得x和y必有關）
- 所有等價類的并為A（結論顯而易見，嚴格證明用集族的單調性，因為每個等價類都包含于A，所以所有等價類的并包含于A的并，即A自己）
可見：等價類是對A的一個劃分（A的每個元素都只在其中一個等價類中，且等價類的并為A）
而等價關系確定等價類的基礎。一切劃分從確定一個自反、對稱、傳遞的等價關系開始。
（ 插一句題外話：等價類讓我想起了麥肯錫咨詢里的一個原則：MECE：Mutually Exclusive Collectively Exhaustive（相互獨立、完全窮盡）。麥肯錫把這個原則視為咨詢的黃金法則，其實也就是離散數學中的劃分等價類。可見許多商業邏輯的原型都是數學。）
3. 商集
- 定義
A/R：A上R的等價類組成的集合（就是A用R劃分的結果）
- 例子（對應剛剛等價類中的那個例子）
{{1,4}，{2,5}，3}
- A上的等價關系有：
- IA 恒等關系
- E 全域關系
- Rij = IA U {<ai,aj>,<aj,ai>} （其中i不等于j，即所有點都有環，并且i和j結點有雙向邊。易證自反，對稱，傳遞）
空關系不是等價關系
- 對應的商集
- A/IA = {{a1},{a2},...{an}}
- A/E = {{a1,a2,...,an}}
- A/Rij = ai和aj為一類，其他元素各成一類
例子：求A={a,b,c}的等價關系（5種）和商集（5個）
4. 劃分（和商族等價）
- 定義：
A的一個劃分是A的一個包含于A冪集的集族，滿足：
集族中每個集合非空、集族中每個集合不相交，集族的并為A
- 定理2.28：
- R為A上的等價關系->A/R是A的劃分
- A是A的劃分->A的同塊關系（即劃分出的其中一個集合的關系）是A上的等價關系
- Stirling子集數
2.6 序關系
（一）偏序
- 偏序關系
- R自反、反對稱（反對稱指：若xRy且yRx，則x=y）、傳遞，則稱R為偏序關系
- xRy記作x≤y
2. 偏序集
一個帶有偏序關系≤的集合A即為偏序集，記作<A,≤>
3. 加細關系
劃分x包含于劃分y，則x是y的加細，xRy成立
4. 可比
x≤y或y≤x，則x和y可比
5. 覆蓋
x≤y且x!=y，則y覆蓋x
6. 哈斯圖
具有偏序關系的兩個結點相連接，其中若y覆蓋x，則y置于x上方
哈斯圖可用于繪制組織框架圖
7. 全序關系
偏序集A中任意元素之間都可比，則<A,≤>為全序集
等價于哈斯圖為直線
（二）擬序
- 擬序關系
R反自反、傳遞（蘊含了R是反對稱的）
2. 定理2.30
- 擬序關系有三歧性（要么x<y要么y<x要么x=y）
- (x<y v x = y) ∧ (y<x v x = y) -> x=y
以下4組概念可以類比高數中的最大值，最小值等（嚴格定義見p52）
3. 最大元，最小元
4. 極大元，極小元
5. 上界，下界
6. 上確界，下確界
7. 鏈，反鏈
偏序集中兩兩都可比，就是鏈，否則是反鏈
- 總結：
偏序是自反，傳遞，反對稱。實數上的小于等于是偏序關系
擬序是反自反，傳遞，反對稱。實數上的小于是偏序關系
3.1 函數
（一）函數的基本概念
- 函數F：F為一個二元關系，且F是單值的（單值：domF中每個x至多對應ranF中一個y）
- 偏函數：domF包含于A，ranF包含于B，即A中每個x在F上不一定有B中對應的y，嚴格定義見p58
- 真偏函數：在偏函數的基礎上，domF真包含于A，即A中一定有x在F上沒有有B中對應的y，嚴格定義見p58
- 全函數：A中每個x在F上一定有B上對應的y
（之后討論的都是全函數上的情況）
（二）函數的性質
- 單射：F是單根的
- 滿射：值域=B
- 雙射：x和y一一對應
- 象和原象
- 特征函數
- 單調函數（定義在任意的偏序關系上）
- 自然映射
f: A->A/R（映射到等價類上）
- 函數的合成
- 反函數
4.1 自然數的定義
- 封閉：F是函數，F(A)屬于A -> F是A上的一元運算
- 皮亞諾系統：<M,F,e> F:M->M
- F是單射
- e不屬于F的值域
- e屬于M
- M最小
- M在F下封閉
- 后繼運算：A+=A U {A}
- 歸納集D：集合D含有空集合，且對后繼運算封閉
- 自然數用集合定義：屬于每個歸納集的集合。從空集合出發，做有限次后繼運算的集合一定是自然數集（0對應空集合，1對應空集合的后繼，以此類推）
- 自然數集N：包含于每個歸納集的集合。N=歸納集D的廣義交
后繼函數：N->N
后繼函數是單射
- 定理4.1 自然數集是歸納集
- 定理4.2 <N,后繼函數,0>為皮亞諾系統
- 定理4.3 任何自然數的元素均為它的子集
- 定理4.4 m,n屬于自然數集，m的后繼屬于n的后繼 等價于 m屬于n
- 定理4.5 任何自然數都不是自己的元素
- 定理4.6 空集屬于除0以外的任何自然數
- 定理4.7 單歧性：m屬于n，m=n和n屬于m有且僅有一個成立
4.2 自然數的性質
- 傳遞集：A中的任何元素也是A的元素
- 自然數是傳遞集
- 定理4.10
A是傳遞集，等價于A的廣義并包含于A，等價于y屬于A，有y包含于A，等價于A包含于P(A)
- 定理4.11
A為傳遞集，等價于P(A)為傳遞集
- 定理4.12
A為傳遞集，等價于A后繼運算的廣義并為A
- 定理 4.13
每個自然數都是傳遞集
- 自然數集合N時傳遞集
- 自然數集上的二元運算
- 加法
- 乘法
5.1 集合的等勢
- 等勢：
A與B等勢：存在f，使A->B雙射
eg.整數集和自然數集是等勢的
- 康托定理：
任何的集合A和它的冪集P(A)之間都不能建立雙射
- 有窮集：
與某個自然數等勢的集合，不能與自己的真子集建立雙射的集合
- 無窮集
不能與自然數等勢的集合
5.2 基數
集合等勢則基數card相同
對自然數集N，cardN= N(阿列夫)
card A = Ni, 則card P(A) = Ni=1
)
