1.數理邏輯

2. 集合論

3. 代數系統

4. 圖論

集合論：集合–>關系–>函數

n元組的了解：有n個集合，從每個集合中抽取一個元素，組成一個n元組

笛卡爾積的了解：笛卡爾積是n個集合能構成的所有互不相等的n元組的集合

對于n元關系的了解：n元關系是n個集合的笛卡爾積的子集，這個子集是在笛卡爾積上加上限制條件構成的。就是在笛卡爾積中滿足同一關系式R的n元組構成的集合

2. 集合

【離散數學】2. 集合論2. 集合3. 關系4. 函數

2.1 基本概念

一個集合是能作為整體論述的事物的集體，用大寫字母表示

用謂詞描述集合的概念

2.1.1 集合的表示方法

列舉法：将集合中的元素枚舉

例 1 ：所有小于 5 的正整數 A = { 1 , 2 , 3 , 4 , 5 } 例 2 ： 1...50 的整數集 A = { 1 , 2 , . . . , 50 } 例 3 ：偶數集合 A = { . . . , − 4 , − 2 , 0 , 2 , 4 , . . . } \begin{aligned} &例1：所有小于5的正整數\\ &A=\{1,2,3,4,5\}\\\\ &例2：1...50的整數集\\ &A=\{1,2,...,50\}\\\\ &例3：偶數集合\\ &A=\{...,-4,-2,0,2,4,...\} \end{aligned} 例1：所有小于5的正整數A={1,2,3,4,5}例2：1...50的整數集A={1,2,...,50}例3：偶數集合A={...,−4,−2,0,2,4,...}
描述法：用謂詞描述出集合元素的公共特征

形如：S={a|P(a)}，表示 a ∈ S a\in S a∈S當且僅當P(a)為真

例：
1. 所有小于5的正整數
 
 A = { a ∣ a ∈ I ∧ 0 < a ∧ a < 5 } } A=\{a\mid a\in I∧0<a∧a<5\}\} A={a∣a∈I∧0<a∧a<5}}
2. 1…50的整數集

A = { a ∣ a ∈ I ∧ 1 ≤ a ≤ 50 } A=\{a\mid a\in I ∧1 \le a \le 50\} A={a∣a∈I∧1≤a≤50}

偶數集合

A = { x ∣ k ∈ I ∧ x = 2 k } A=\{x\mid k\in I∧x=2k\} A={x∣k∈I∧x=2k}
歸納定義法

見 2.3節
文氏圖

【離散數學】2. 集合論2. 集合3. 關系4. 函數

2.1.2 元素與集合的關系——從屬關系

元素(成員)：組成這個集合的元素或成員，用小寫字母表示

集合也可作為另一個集合的元素

元素屬于集合： a ∈ A a\in A a∈A
元素不屬于集合： a ∉ A a\notin A a∈/A

1. 與元素相關的集合概念

單元素集合：僅含有一個元素的集合

有限集合：含有有限個元素的集合

無限集合（無窮集）：不是有限集合的集合
集合的基：有限集合的元素個數，即為 |A|

A = { a , b } , 則 ∣ A ∣ = 2 , 又 ∣ { A } ∣ = 1 A=\{a,b\},則\mid A\mid=2,又\mid \{A\}\mid=1 A={a,b},則∣A∣=2,又∣{A}∣=1

記：

集合本身不能成為集合的元素，否則會導緻羅素悖論
n個元素的集合有 2 n 2^n 2n 個子集合

2. 集合中元素的特點

确定性：元素a是否在集合中出現是确定的，隻有出現或者不出現兩種情況
互異性：集合中的元素互異(彼此不同)
無序性：集合中的元素是無序的
任意性：集合中的元素可以是一個集合

2.1.2 集合間的關系

1. 相等

外延定理：兩個集合A和B相等(A=B)，當且僅當他們有相同的成員(A中每個元素是B的一個元素而B中的每個元素也是A的有一個元素)

A = B ⟺ ∀ x ( x ∈ A ↔ x ∈ B ) A = B ⟺ ∀ x ( x ∈ A → x ∈ B ) ∧ ∀ x ( x ∈ B → x ∈ A ) \begin{aligned} &A=B\iff \forall x(x \in A ↔x\in B)\\ &A=B\iff \forall x(x\in A \rightarrow x\in B)∧\forall x(x\in B \rightarrow x\in A) \end{aligned} A=B⟺∀x(x∈A↔x∈B)A=B⟺∀x(x∈A→x∈B)∧∀x(x∈B→x∈A)

列舉法中，元素的次序無關緊要
元素的重複出現無足輕重
集合的表示不是唯一的

2. 集合間的包含關系

A⊆B：設A和B是集合，如果A中的每一進制素是B的一個元素，則A是B的子集合，B是A的擴集

邏輯符号表示為：

A ⊆ B ⟺ ∀ x { x ∈ A → x ∈ B } A⊆B\iff \forall x\{x\in A\rightarrow x\in B\} A⊆B⟺∀x{x∈A→x∈B}

真子集：如果A⊆ B且A ≠ \neq = B，則A是B的真子集，記為 A⊂B（A真包含于B）

邏輯符号表示為：

A ⊂ V ⟺ ( A ⊆ B ) ∧ ( A ≠ B ) ⟺ ∀ x ( x ∈ A → x ∈ B ) ∧ ∃ x ( x ∈ B ∧ x ∉ A ) \begin{aligned} A⊂V&\iff (A⊆B)∧(A\neq B)\\ &\iff \forall x(x\in A\rightarrow x\in B)∧∃x(x\in B∧x\notin A) \end{aligned} A⊂V⟺(A⊆B)∧(A=B)⟺∀x(x∈A→x∈B)∧∃x(x∈B∧x∈/A)

對任一集合A，有A⊆U，U表示全集合

對任何集合A，恒有A⊆A
- 集合與其自身隻有包含關系，沒有從屬關系，即{A}可作為A的子集合，但A任何條件下不能作為集合A的元素
設A和B是集合，A=B當且僅當A⊆B和B⊆A
傳遞性：設A，B，C是集合，若A⊆B且B⊆C，則A⊆C
對于任何非空集合，都有兩個平凡子集，A集合本身和∅

空集：沒有任何元素的集合，記為∅

空集是任何集合的子集合，∅⊆A
空集是唯一的

2.2 集合上的運算

用給定的集合（運算對象）去指定一新的集合（運算結果）

2.2.1 并、交、差

1. 定義

設A和B是集合

A∪B：A和B的并

A ∪ B = { x ∣ A ∈ A ∨ x ∈ B } A∪B=\{x|A\in A∨x\in B\} A∪B={x∣A∈A∨x∈B}

A∩B：A和B的交

A ∩ B = { x ∣ x ∈ A ∧ x ∈ B } A∩B=\{x|x\in A ∧x \in B\} A∩B={x∣x∈A∧x∈B}

A-B：A和B的差

A − B = A ∩ B ‾ = { x ∣ x ∈ A ∧ x ∉ B } \begin{aligned} A-B &= A∩\overline{B}\\ &= \{x|x\in A∧x\notin B\} \end{aligned} A−B=A∩B={x∣x∈A∧x∈/B}

不相交：A∩B=∅，則A和B是不相交的。

C是集合族，若C中任意兩個不同元素不相交，則C是不相交集合的族

例：

C = { { 0 } , { 1 } , . . . } = { { i } ∣ i ∈ N } C=\{\{0\},\{1\},...\}=\{\{i\}\mid i\in N\} C={{0},{1},...}={{i}∣i∈N}

2. 定理

設A、B、C是集合

集合的交、并是可交換、可結合的，可配置設定的

A∪B = B∪A
A∩B = B∩A
C∪(A∪B) = (A∪B)∪C
A∩(B∩C) = (B∩C)∩A
A∪(B∩C) = (A∪B)∩(A∪C)
A∩(B∪C) = A∩B∪A∩C

其他運算性質

A∪A = A
A∩A = A
A∪∅ = A
A∩∅ = ∅
A-∅ = A
A-B ⊆ A
A⊆A∪B
A∩B⊆A
如果A⊆B且C⊆D，則 (A∪C)⊆(B∪D)
如果A⊆B且C⊆D，則 (A∩C)⊆(B∩D)
如果A⊆B，則 A∪B = B
如果A⊆B，則 A∩B = A

2.2.2 補運算

設U是論述域，A是U的子集

A的補 A ‾ \overline{A} A ： A ‾ = U − A = { x ∣ x ∈ U ∧ x ∉ A } \overline{A} = U-A = \{x\mid x\in U∧ x\notin A\} A=U−A={x∣x∈U∧x∈/A}

顯然：

A ∪ A ‾ = U A∪\overline{A}=U A∪A=U
A ∩ A ‾ = ∅ A∩\overline{A}=∅ A∩A=∅

補的唯一性：A和B是U的子集，則 B = A ‾ B=\overline{A} B=A 當且僅當 A∩B=∅ 和 A∪B=U

∅ ‾ = U \overline{∅} = U ∅=U
U ‾ = ∅ \overline{U}=∅ U=∅

A的補的補是A： A ‾ ‾ = A \overline{\overline{A}}=A A=A

德·摩根定律

A ∪ B ‾ = A ‾ ∩ B ‾ \overline{A∪B}=\overline{A}∩\overline{B} A∪B=A∩B
A ∩ B ‾ = A ‾ ∪ B ‾ \overline{A∩B}=\overline{A}∪\overline{B} A∩B=A∪B

包含關系的逆反定律：若 A ⊆ B A⊆B A⊆B ，則 B ‾ ⊆ A ‾ \overline{B}⊆\overline{A} B⊆A

2.2.3 并和交運算的擴充

設C是某論述域的搜集，C中的元素是集合

搜集：集合子集組成的族

C的成員的并，記為 U S ∈ C S = { x ∣ ∃ x ( S ∈ C ∧ x ∈ S ) } U_{S\in C}S = \{x\mid ∃x(S\in C∧x\in S)\} US∈CS={x∣∃x(S∈C∧x∈S)}

如果 x ∈ U S ∈ C x\in U_{S\in C} x∈US∈C ，那麼x至少是一個子集S的元素

若 C ≠ ∅ C\neq∅ C=∅ ，C的成員的交，記為 ∩ S ∈ C = { x ∣ ∀ x ( S ∈ C → x ∈ S ) } ∩_{S\in C}=\{x\mid \forall x(S\in C\rightarrow x\in S)\} ∩S∈C={x∣∀x(S∈C→x∈S)}

如果 x ∈ ∩ S ∈ C x\in ∩_{S\in C} x∈∩S∈C ,那麼x是每一個子集S的元素

加索引搜集：通過索引d 能唯一确定的一個集合，則稱 A d A_d Ad 為加索引搜集

C = { A d ∣ d ∈ D } C=\{A_d\mid d\in D\} C={Ad∣d∈D} 為加索引搜集，D為搜集的索引集合

例：

C = P { A 0 , A 1 , A 2 , . . . , A n } C=P\{A_0,A_1,A_2,...,A_n\} C=P{A0,A1,A2,...,An} , 則C的成員的并 U S ∈ C U_{S\in C} US∈C，記為

U i = 0 n A i 或 U 0 ≤ i ≤ n A i 或 A 0 U A 1 U . . . U A n U_{i=0}^nA_i\quad或\quad U_{0\le i\le n}A_i\quad或\quad A_0UA_1U...UA_n Ui=0nAi或U0≤i≤nAi或A0UA1U...UAn
設： [ 0 , a ) 表示集合 { x ∣ 0 ≤ x < a } [0,a)表示集合\{x\mid 0\le x < a\} [0,a)表示集合{x∣0≤x<a}

如果 S a = [ 0 , a ) , a ∈ R + , C = { S a ∣ a ∈ R + } S_a=[0,a),a\in R_+,C=\{S_a\mid a\in R_+\} Sa=[0,a),a∈R+,C={Sa∣a∈R+}，那麼

U s ∈ C S = [ 0 , ∞ ) , ∩ S ∈ C s = { 0 } U_{s\in C}S=[0,\infty),∩_{S\in C}s=\{0\} Us∈CS=[0,∞),∩S∈Cs={0}

如果 S a = [ 0 , a ) , a ∈ I + , C = { S a ∣ a ∈ I + } S_a=[0,a),a\in I_+,C=\{S_a\mid a\in I_+\} Sa=[0,a),a∈I+,C={Sa∣a∈I+} ,那麼

U i = 1 ∞ S i = [ 0 , 1 ) U [ 0 , 2 ) U . . . = [ 0 , ∞ ) ∩ i = 1 ∞ S i = [ 0 , 1 ) ∩ [ 0 , 2 ) ∩ . . . = [ 0 , 1 ) \begin{aligned} U_{i=1}^{\infty}S_i=[0,1)U[0,2)U...=[0,\infty)\\ ∩_{i=1}^{\infty}S_i=[0,1)∩[0,2)∩...=[0,1) \end{aligned} Ui=1∞Si=[0,1)U[0,2)U...=[0,∞)∩i=1∞Si=[0,1)∩[0,2)∩...=[0,1)

2.2.4 環和與環積

1.環和(對稱差)

環和(A⊕B)：

A ⊕ B = ( A − B ) U ( B − A ) = { x ∣ x ∈ A ∧ x ∉ B ∨ x ∈ B ∧ x ∉ A } \begin{aligned} A⊕B&=(A-B)U(B-A)\\ &=\{x\mid x\in A∧x\notin B∨x\in B∧x\notin A\} \end{aligned} A⊕B=(A−B)U(B−A)={x∣x∈A∧x∈/B∨x∈B∧x∈/A}

【離散數學】2. 集合論2. 集合3. 關系4. 函數

定理 A ⊕ B = ( A ∪ B ) − ( A ∩ B ) A\oplus B=(A\cup B)-(A\cap B) A⊕B=(A∪B)−(A∩B)

A ⊕ B = ( A − B ) U ( B − A ) = ( A ∩ B ‾ ) U ( B ∩ A ‾ ) = ( A U B ) ∩ ( A ‾ U B ‾ ) = ( A U B ) ∩ ( A ∩ B ‾ ) = ( A U B ) − ( A ∩ B ) \begin{aligned} A⊕B&=(A-B)U(B-A)\\ &=(A∩\overline{B})U(B∩\overline{A})\\ &=(AUB)∩(\overline{A}U\overline{B})\\ &=(AUB)∩(\overline{A∩B})\\\\ &=(AUB)-(A∩B) \end{aligned} A⊕B=(A−B)U(B−A)=(A∩B)U(B∩A)=(AUB)∩(AUB)=(AUB)∩(A∩B)=(AUB)−(A∩B)

推論：

A ‾ ⊕ B ‾ = A ⊕ B A ⊕ B = B ⊕ A A ⊕ A = ∅ ( A ⊕ B ) ⊕ C = A ⊕ ( B ⊕ C ) C ∩ ( A ⊕ B ) = C ∩ A ⊕ C ∩ B \begin{aligned} &\overline{A}⊕\overline{B}=A⊕B\\ &A⊕B=B⊕A\\ &A⊕A=∅\\ &(A⊕B)⊕C=A⊕(B⊕C)\\ &C∩(A⊕B)=C∩A⊕C∩B \end{aligned} A⊕B=A⊕BA⊕B=B⊕AA⊕A=∅(A⊕B)⊕C=A⊕(B⊕C)C∩(A⊕B)=C∩A⊕C∩B
交環和可配置設定，其餘不可配置設定

2. 環積

環積(A⊗B)：

A ⊗ B = A ⊕ B ‾ = ( A U B ) ∩ ( A ∩ B ‾ ) ‾ = A ∩ B U A ‾ ∩ B ‾ = { x ∣ x ∈ A ∧ x ∈ B ∨ x ∉ A ∧ x ∉ B } \begin{aligned} A⊗B&=\overline{A⊕B}\\\\ &=\overline{(AUB)∩(\overline{A∩B})}\\ &= A∩BU\overline{A}∩\overline{B}\\ &=\{x|x\in A∧x\in B∨x\notin A∧x\notin B\} \end{aligned} A⊗B=A⊕B=(AUB)∩(A∩B)=A∩BUA∩B={x∣x∈A∧x∈B∨x∈/A∧x∈/B}

【離散數學】2. 集合論2. 集合3. 關系4. 函數

定理：

A ‾ ⊗ B ‾ = A ⊗ B A ⊗ B = B ⊗ A A ⊗ A = U ( A ⊗ B ) ⊗ C = A ⊗ ( B ⊗ C ) C U ( A ⊗ B ) = ( C U A ) ⊗ ( C U B ) \begin{aligned} &\overline{A}⊗\overline{B}=A⊗B\\ &A⊗B=B⊗A\\ &A⊗A=U\\ &(A⊗B)⊗C=A⊗(B⊗C)\\ &CU(A⊗B)=(CUA)⊗(CUB) \end{aligned} A⊗B=A⊗BA⊗B=B⊗AA⊗A=U(A⊗B)⊗C=A⊗(B⊗C)CU(A⊗B)=(CUA)⊗(CUB)
并環積可配置設定，其餘不可配置設定

環積是環和的補

2.2.6 幂集合

集合A的幂集 ρ ( A ) \rho(A) ρ(A) 是A的所有子集的集合

ρ ( A ) = { B ∣ B ⊆ A } \rho(A)=\{B|B\subseteq A\} ρ(A)={B∣B⊆A}

如：

設 A = { 1 , 2 } , ρ ( A ) = { ∅ , { 1 } , { 2 } , { 1 , 2 } } 設A=\{1,2\},\rho(A)=\{∅,\{1\},\{2\},\{1,2\}\} 設A={1,2},ρ(A)={∅,{1},{2},{1,2}}

一個給定集合的幂集是唯一的
如果A是有限集，則 ρ ( A ) \rho(A) ρ(A) 的元素個數也是有限的，如 ∣ A ∣ = n \mid A\mid = n ∣A∣=n，則 ∣ ρ ( A ) ∣ = 2 n \mid \rho(A) \mid = 2^n ∣ρ(A)∣=2n

2.2.7 有限集運算的基數

容斥原理

設A、B是有限集合，其元素個數為 ∣ A ∣ , ∣ B ∣ \mid A \mid , \mid B \mid ∣A∣,∣B∣ ，則 ∣ A U B ∣ = ∣ A ∣ + ∣ B ∣ − ∣ A ∩ B ∣ \mid AUB \mid=\mid A\mid + \mid B \mid - \mid A∩B \mid ∣AUB∣=∣A∣+∣B∣−∣A∩B∣

加奇減偶

2.3 集合的笛卡爾積

2.3.1 序偶

兩個元素 a 1 , a 2 a_1,a_2 a1,a2 組成的序列記作 < a 1 , a 2 > <a_1,a_2> <a1,a2> ，稱為二重組或者序偶

a 1 , a 2 a_1,a_2 a1,a2 分别稱為第一和第二分量

二重組中元素的是有次序的

相等： < a , b > <a,b> <a,b>和 < c , d > <c,d> <c,d> 相等，當且僅當a=c且b=d

n重組， < a 1 , a 2 , . . . , a n > = < < a 1 , a 2 , . . . , a n − 1 > , a n > <a_1,a_2,...,a_n>=<<a_1,a_2,...,a_{n-1}>,a_n> <a1,a2,...,an>=<<a1,a2,...,an−1>,an>

n重組中，第一個分量為n-1重組

2.3.2 集合的叉積

集合A和B的叉積記為 A × B A\times B A×B ，表示兩集合元素的所有序偶集合，即 { < a , b > ∣ a ∈ A ∧ b ∈ B } \{ <a,b> \mid a\in A ∧b\in B\} {<a,b>∣a∈A∧b∈B}

集合 A 1 , A 2 , . . . , A n A_1,A_2,...,A_n A1,A2,...,An 的叉積記為 A 1 × A 2 × . . . × A n A_1 \times A_2 \times...\times A_n A1×A2×...×An 或 × i = 1 n A i \times_{i=1}^n A_i ×i=1nAi，表示n個集合元素的n重組，即 { < a 1 , a 2 , . . . , a n > ∣ a i ∈ A i ∧ 1 ≤ i ≤ n } \{ <a_1,a_2,...,a_n> \mid a_i \in A_i ∧ 1\le i \le n\} {<a1,a2,...,an>∣ai∈Ai∧1≤i≤n}

例：

設 A = { a , b } , B = { 1 , 2 , 3 } , C = { p , q } , D = { 0 } , E = ∅ 1. A × B = { < a , 1 > , < a , 2 > , < a , 3 > , , , } 2. A × B × C = { < a , 1 , p > , < a , 1 , q > , < a , 2 , p > , < a , 2 , q > , < a , 3 , p > , < a , 3 , q > , , , , , , } 3. C × D = { , < q , 0 > } 4. D × ( C 2 ) = D × { , , < q , p > , < q , q > } = { < 0 , > , < 0 , > , < 0 , < q , p > > , < 0 , < q , q > > } 5. A × E = ∅ \begin{aligned} &設A=\{a,b\},B=\{ 1,2,3 \},C=\{ p,q \},D=\{ 0\},E=∅\\ &1.\quad A\times B = \{ <a,1>,<a,2>,<a,3>,<b,1>,<b,2>,<b,3> \}\\ &2.\quad A\times B\times C=\{<a,1,p>,<a,1,q>,<a,2,p>,<a,2,q>,<a,3,p>,<a,3,q>,\\&<b,1,p>,<b,1,q>,<b,2,p>,<b,2,q>,<b,3,p>,<b,3,q>\}\\ &3.\quad C\times D=\{ <p,0>,<q,0> \}\\ &4.\quad D\times (C^2)=D\times \{<p,p>,<p,q>,<q,p>,<q,q> \}\\ &=\{ <0,<p,p>>,<0,<p,q>>,<0,<q,p>>,<0,<q,q>> \}\\ &5.\quad A\times E = ∅ \end{aligned} 設A={a,b},B={1,2,3},C={p,q},D={0},E=∅1.A×B={<a,1>,<a,2>,<a,3>,<b,1>,<b,2>,<b,3>}2.A×B×C={<a,1,p>,<a,1,q>,<a,2,p>,<a,2,q>,<a,3,p>,<a,3,q>,<b,1,p>,<b,1,q>,<b,2,p>,<b,2,q>,<b,3,p>,<b,3,q>}3.C×D={<p,0>,<q,0>}4.D×(C2)=D×{<p,p>,<p,q>,<q,p>,<q,q>}={<0,<p,p>>,<0,<p,q>>,<0,<q,p>>,<0,<q,q>>}5.A×E=∅

當A和B表示連續的實數集合，那麼 A × B A\times B A×B 能代表笛卡爾平面的點的集合

【離散數學】2. 集合論2. 集合3. 關系4. 函數

笛卡爾積無交換律無結合律

笛卡爾積的配置設定律

1. A × ( B ∪ C ) = ( A × B ) ∪ ( A × C ) 2. A × ( B ∩ C ) = ( A × B ) ∩ ( A × C ) 3. ( A ∪ B ) × C = ( A × B ) ∪ ( A × C ) 4. ( A ∩ B ) × C = ( A × B ) ∩ ( A × C ) \begin{aligned} &1. A\times (B∪C)=(A\times B)∪(A\times C)\\ &2. A\times(B∩C)=(A\times B)∩(A\times C)\\ &3. (A∪B) \times C = (A\times B)∪(A\times C)\\ &4. (A∩B) \times C = (A\times B)∩(A\times C) \end{aligned} 1.A×(B∪C)=(A×B)∪(A×C)2.A×(B∩C)=(A×B)∩(A×C)3.(A∪B)×C=(A×B)∪(A×C)4.(A∩B)×C=(A×B)∩(A×C)

笛卡爾積的計數

∣ A 1 × A 2 × . . . × A n ∣ = ∣ A 1 ∣ ⋅ ∣ A 2 ∣ ⋅ ⋅ ⋅ ∣ A n ∣ \begin{aligned} \mid A_1\times A_2 \times ... \times A_n \mid = \mid A_1 \mid · \mid A_2 \mid ··· \mid A_n \mid \end{aligned} ∣A1×A2×...×An∣=∣A1∣⋅∣A2∣⋅⋅⋅∣An∣

3. 關系

關系是集合，集合中的元素是有序n元組

3.1 基本概念

3.1.1 關系的基本概念

二進制關系： A × B A\times B A×B 的子集稱為A到B的一個二進制關系

A 2 = A × A A^2=A\times A A2=A×A 的子集稱為A上的二進制關系

n元關系： A 1 × A 2 × . . . × A n A_1 \times A_2 \times...\times A_n A1×A2×...×An 的子集稱為 A 1 × A 2 × . . . × A n A_1 \times A_2 \times...\times A_n A1×A2×...×An 上的一個n元關系

A n = A × A × . . . × A A^n=A\times A\times...\times A An=A×A×...×A 的子集稱為A上的n元關系

關系：二進制關系R中任一序偶 < x , y > <x,y> <x,y> 記作 < x , y > ∈ R <x,y>\in R <x,y>∈R 或 x R y xRy xRy

3.1.2 關系的個數

對于 A 1 × A 2 × . . . × A n A_1 \times A_2 \times...\times A_n A1×A2×...×An ，若每個集合 A i A_i Ai 都是有限的，其基數記為 ∣ A i ∣ = r i \mid A_i \mid=r_i ∣Ai∣=ri ，則笛卡爾積的基 ∣ A 1 × A 2 × . . . × A n ∣ = r 1 ⋅ r 2 ⋅ . . . r n \mid A_1 \times A_2 \times...\times A_n \mid=r_1·r_2·...r_n ∣A1×A2×...×An∣=r1⋅r2⋅...rn ，他的不同子集個數為 2 r 1 ⋅ r 2 ⋅ . . . r n 2^{r_1·r_2·...r_n} 2r1⋅r2⋅...rn ，是以 A 1 × A 2 × . . . × A n A_1 \times A_2 \times...\times A_n A1×A2×...×An 上的不同關系的個數為子集其子集個數 2 r 1 ⋅ r 2 ⋅ . . . r n 2^{r_1·r_2·...r_n} 2r1⋅r2⋅...rn

3.1.3 關系的相等

設 R1 是 A 1 × A 2 × . . . × A n A_1\times A_2\times ...\times A_n A1×A2×...×An 上的n元關系，R2是 B 1 × B 2 × . . . × B m B_1\times B_2\times ...\times B_m B1×B2×...×Bm 上的m元關系

R1=R2：

n=m
對于一切i， A i = B i A_i=B_i Ai=Bi
R1和R2是相等的有序n元組集合

3.2 二進制關系

3.2.1 基本概念

集合X叫做關系R的前域，集合Y叫做關系R的陪域

R表示集合X到Y的二進制關系，有 < x , y > ∈ R <x,y>\in R <x,y>∈R 的所有x組成的集合D(R)稱為R的定義域

D ( R ) = { x ∣ ∃ y ( < x , y > ∈ R ) } D(R)=\{x\mid ∃y(<x,y>\in R) \} D(R)={x∣∃y(<x,y>∈R)}

由 < x , y > ∈ R <x,y>\in R <x,y>∈R 的所有y組成的集合R®稱為R的值域，即

R ( R ) = { y ∣ ∃ x ( < x , y > ∈ R ) } R(R)=\{y\mid ∃x(<x,y>\in R) \} R(R)={y∣∃x(<x,y>∈R)}

設R是 A 1 × A 2 × . . . × A n A_1 \times A_2 \times...\times A_n A1×A2×...×An 的子集，如果R=∅，則稱R為空關系，若R= A 1 × A 2 × . . . × A n A_1 \times A_2 \times...\times A_n A1×A2×...×An ，則稱R是全域關系

3.2.2 關系的表示

給定兩個有限集合， X = { x 1 , x 2 , . . . , x m } , Y = { y 1 , y 2 , . . . , y n } X=\{x_1,x_2,...,x_m \},Y=\{ y_1,y_2,...,y_n \} X={x1,x2,...,xm},Y={y1,y2,...,yn} ，R為從X到Y的一個二進制關系

關系的矩陣表示

對應于關系R有一個關系矩陣 M R = [ r i j ] m ∗ n M_R=[r_{ij}]_{m*n} MR=[rij]m∗n ，其中

r i j = { 1 , < x i , y j > ∈ R 0 , < x i , y j > ∉ R i = 1 , 2 , . . . , m , j = 1 , 2 , . . . n r_{ij} = \begin{cases} 1,&<x_i,y_j>\in R\\ 0,&<x_i,y_j>\notin R \end{cases} \quad i=1,2,...,m,j=1,2,...n rij={1,0,<xi,yj>∈R<xi,yj>∈/Ri=1,2,...,m,j=1,2,...n

如X={1,2,3,4}求 X 2 X^2 X2 上大于關系的關系矩陣

[ 0 , 0 , 0 , 0 1 , 0 , 0 , 0 1 , 1 , 0 , 0 1 , 1 , 1 , 0 ] \begin{bmatrix} 0,0,0,0\\ 1,0,0,0\\ 1,1,0,0\\ 1,1,1,0 \end{bmatrix}

0,0,0,01,0,0,01,1,0,01,1,1,0

關系的圖形表示

有向圖

約定

從X到Y的關系R是 X × Y X\times Y X×Y 的子集，即 R ⊆ X × Y R\subseteq X\times Y R⊆X×Y ，而 X × Y ⊆ ( X ∪ Y ) × ( X ∪ Y ) X\times Y \subseteq (X\cup Y)\times (X\cup Y) X×Y⊆(X∪Y)×(X∪Y)。若令 Z = X ∪ Y Z=X\cup Y Z=X∪Y ，則 R ⊆ Z × Z R\subseteq Z\times Z R⊆Z×Z ，是以隻需研究同一集合上的關系的性質

3.2.3 關系的性質

自反性

自反

設R是集合X上的二進制關系，如果對于X中的每個x都有xRx，則稱二進制關系R是自反的

R 在 X 上自反 ⟺ ( ∀ x ) ( x ∈ X → x R x ) R在X上自反 \iff (\forall x) (x\in X\rightarrow xRx) R在X上自反⟺(∀x)(x∈X→xRx)

表示方法上看

關系圖中，每個結點都有自回路
關系矩陣的主對角線上元素都是1,不同結點間關系随意

反自反

設R是集合X上的二進制關系，如果對于X中的每個x都有 x R̸ x x\not R x xRx ，則稱二進制關系R是反自反的

R 在 X 上反自反 ⟺ ( ∀ x ) ( x ∈ X → x R̸ x ) R在X上反自反\iff (\forall x)(x\in X\rightarrow x\not R x) R在X上反自反⟺(∀x)(x∈X→xRx)

表示方法上看

關系圖中的每個結點都沒有自回路
關系矩陣的主對角線上的每個元素都是0

既不是自反，也不是反自反

表示方法上看

關系圖中的部分結點都沒有自回路
關系矩陣的主對角線上的部分元素都是0

對稱性

設R是集合X上的二進制關系，如果對于X中的每個x,y，每當xRy就有yRx，則稱二進制關系R是對稱的

R 在 X 上對稱 ⟺ ( ∀ x ) ( ∀ y ) ( x ∈ X ∧ y ∈ X ∧ x R y → y R x ) R在X上對稱\iff (\forall x)(\forall y)(x\in X∧y\in X∧xRy\rightarrow yRx) R在X上對稱⟺(∀x)(∀y)(x∈X∧y∈X∧xRy→yRx)

表示方法上看

關系圖中任意兩個結點間，若有定向弧必然是成對出現的
關系矩陣關于主對角線對稱

反對稱性

設R施集合X上的二進制關系，如果對于X中的每個x,y，當且僅當xRy和yRx，必有x=y，則稱二進制關系R是反對稱的

R 在 X 上反對稱 ⟺ ( ∀ x ) ( ∀ y ) ( x ∈ X ∧ y ∈ Y ∧ x R y ∧ y R x → x = y ) R 在 X 上反對稱 ⟺ ( ∀ x ) ( ∀ y ) ( x ∈ X ∧ y ∈ Y ∧ x R y ∧ x ≠ y → x R̸ y ) \begin{aligned} &R在X上反對稱\iff (\forall x)(\forall y)(x\in X∧y\in Y∧xRy∧yRx\rightarrow x=y)\\ &R在X上反對稱\iff (\forall x)(\forall y)(x\in X∧y\in Y∧xRy∧x\neq y\rightarrow x\not Ry) \end{aligned} R在X上反對稱⟺(∀x)(∀y)(x∈X∧y∈Y∧xRy∧yRx→x=y)R在X上反對稱⟺(∀x)(∀y)(x∈X∧y∈Y∧xRy∧x=y→xRy)

即存在關系 < x , y > <x,y> <x,y> ，則一定不存在關系 < y , x > <y,x> <y,x>

表示方法上看

關系圖中任意兩個結點間的定向弧不能成對出現
關系矩陣中關于主對角線對稱的元素不能同時為1

既不是對稱，也不是反對稱

既是對稱，也是反對稱

關系矩陣中隻有主對角線上有元素

集合 A = 1 , 2 , 3 ， R = < 1 , 1 > , < 2 , 2 > , < 3 , 3 > A={1,2,3}，R={<1,1>,<2,2>,<3,3>} A=1,2,3，R=<1,1>,<2,2>,<3,3>

傳遞性

設R是集合X上的二進制關系，如果對于X中的每個x，y，z,每當xRy，yRz，就有xRz，則稱二進制關系R是傳遞的

R 在 X 上傳遞 ⟺ ( ∀ x ) ( ∀ y ) ( ∀ z ) ( x ∈ X ∧ y ∈ X ∧ z ∈ X ∧ x R y ∧ y R z → x R z ) R在X上傳遞\iff (\forall x)(\forall y)(\forall z)(x\in X∧y\in X∧z\in X∧xRy∧yRz \rightarrow xRz) R在X上傳遞⟺(∀x)(∀y)(∀z)(x∈X∧y∈X∧z∈X∧xRy∧yRz→xRz)

具有傳遞性的三個節點，任意兩個節點間都必有直接路徑(步長為1)

如集合 A = 1 , 2 , 3 , 4 A={1,2,3,4} A=1,2,3,4 ，關系 R = < 4 , 1 > , < 4 , 2 > , < 4 , 3 > , < 3 , 2 > , < 2 , 1 > R={<4,1>,<4,2>,<4,3>,<3,2>,<2,1>} R=<4,1>,<4,2>,<4,3>,<3,2>,<2,1> 是傳遞的

表示方法上看

關系圖，如果從a到b，b到c存在一條有向路徑，則從a到c之間存在一條弧

常見關系的性質

整數集合I上，關系 ≤ \le ≤ 是

自反的，反對稱的，傳遞的，但不是反自反的和對稱的
整數集合I上，關系 < 是

反自反的，反對稱的，傳遞的，但不是自反的和對稱的
任何集合上的相等關系是

自反的，對稱的，反對稱的，傳遞的，但不是反自反的
非空集合上的空關系是

反自反的，對稱的，反對稱的，傳遞的，但不是自反的
基數大于1的集合上的全域關系是

自反的，對稱的，傳遞的，但不是反自反的和反對稱的

從關系矩陣上看關系的性質

上三角或者下三角是滿的，則具有傳遞性

主對角線是滿的，則具有自反性，反之，不具有自反性

關系矩陣是對稱矩陣，則關系具有對稱性

3.2.4 二進制關系的運算

相等

Ix是X上的二進制關系，且滿足 I x = { < x , x > ∣ x ∈ X } Ix=\{ <x,x> \mid x\in X \} Ix={<x,x>∣x∈X} ，則稱Ix或Ex是X上的相等關系

關系的本質是集合，關系經過集合運算後仍是關系

若Z和S是集合X到集合Y的兩個關系，則Z、S的并、交、補、差仍是X到Y的關系

關系的閉包

基本概念

若原先X上的關系R并不具有自反性(對稱性，傳遞性)，若添加某些條件(增加元組)後形成新的關系 R ′ R' R′ 具有自反性(對稱性，傳遞性)。則稱 R ′ R' R′ 是R的自反(對稱，傳遞)閉包

設R是X上的二進制關系，如果另一個關系R’，滿足：

R’是自反的(對稱的，可傳遞的)

R ⊆ R ′ R\subseteq R' R⊆R′

對于任何自反的(對稱的，可傳遞的)關系R’，如果有 R ⊆ R ′ ′ R\subseteq R'' R⊆R′′，則有 R ′ ⊆ R ′ ′ R'\subseteq R'' R′⊆R′′

則稱R’是R的自反(對稱,可傳遞)閉包，記為 r ( R ) ( s ( R ) , t ( R ) ) r(R)(s(R),t(R)) r(R)(s(R),t(R))

具有自反性(對稱性，可傳遞性)的關系R，其自反(對稱，可傳遞)閉包為其本身

R是自反的，當且僅當 r ( R ) = R r(R)=R r(R)=R
R是對稱的，當且僅當 s ( R ) = R s(R)=R s(R)=R
R是可傳遞的，當且僅當 t ( R ) = R t(R)=R t(R)=R

閉包的等價運算

設R是X上的二進制關系，R的基為 ∣ R ∣ = n \mid R \mid = n ∣R∣=n 則

自反閉包 r ( R ) = R ∪ I x r(R)=R\cup Ix r(R)=R∪Ix
對稱閉包 s ( R ) = R ∪ R ~ s(R)=R\cup \widetilde{R} s(R)=R∪R
傳遞閉包 r ( R ) = ⋃ i = 1 n = R ∪ R 2 ∪ . . . ∪ R n r(R)=\bigcup_{i=1}^n=R\cup R^2 \cup ...\cup R^n r(R)=⋃i=1n=R∪R2∪...∪Rn

Floyd算法的數學依據

傳遞閉包的簡便算法：Warshall

按列周遊，将第j列為1的行分别與第j行相或，用所得結果替換原始行
将第j次的運算結果作為第j+1次的初始矩陣，直至周遊完，所得結果即為傳遞閉包的矩陣表示

【離散數學】2. 集合論2. 集合3. 關系4. 函數

整數集合上的閉包運算

自反閉包	對稱閉包	傳遞閉包
I上的小于關系<	≤ \le ≤	≠ \neq =	<
I上的小于等于關系 ≤ \le ≤	≤ \le ≤	U	≤ \le ≤
全域關系	U	U	U
I上的不等關系 ≠ \neq =	U	≠ \neq =	U

閉包的閉包

如果R是自反的，那麼 s ( R ) s(R) s(R) , t ( R ) t(R) t(R) 是自反的
如果R是對稱的，那麼 r ( R ) r(R) r(R) , t ( R ) t(R) t(R) 是對稱的
如果R是傳遞的，那麼 t ( R ) t(R) t(R) 是傳遞的

類似性質：有r的是相等，t開頭的大

r s ( R ) = s r ( R ) rs(R)=sr(R) rs(R)=sr(R)
r t ( R ) = t r ( R ) rt(R)=tr(R) rt(R)=tr(R)
s t ( R ) ⊆ t s ( R ) st(R)\subseteq ts(R) st(R)⊆ts(R)

【離散數學】2. 集合論2. 集合3. 關系4. 函數

合成

概念

兩個集合間的關系如果都能通過與第三個集合的集合傳遞，則這兩個集合關于第三個集合的關系可以合并稱為這兩個集合的關系。

設R為X到Y的關系，S為Y到Z的關系，則RS稱為X到Z的合成關系

R S = { < x , z > ∣ x ∈ X ∧ z ∈ Z ∧ ∃ y ( y ∈ Y ∧ < x , y > ∈ R ∧ < y , z > ∈ S ) } RS=\{<x,z> \mid x\in X∧z\in Z∧∃y(y\in Y∧<x,y>\in R∧<y,z>\in S) \} RS={<x,z>∣x∈X∧z∈Z∧∃y(y∈Y∧<x,y>∈R∧<y,z>∈S)}

·表示合成運算，合成關系RS也可記為R·S

如：

R1是關系"…是…兄弟"，R2是關系"…是…父親"，R1R2是關系"…是…叔伯"

R2R2是關系"…是…祖父"

合成關系具有次序性

從定義上看，合成關系是有向的，是以參與合成運算的兩個關系不能交換

性質

不可交換
可以結合：R1，R2，R3分别是從A到B，B到C，C到D的關系，那麼(R1R2)R3 = R1(R2R3)
并滿足配置設定律，交滿足配置設定不等式：

設R1是從A到B的關系，R2和R3是從B到C的關系，R4是從C到D的關系，那麼

R 1 ( R 2 ∪ R 3 ) = R 1 R 2 ∪ R 1 R 3 ( R 2 ∪ R 3 ) R 4 = R 2 R 4 ∪ R 3 R 4 R 1 ( R 2 ∩ R 3 ) ⊆ R 1 R 2 ∩ R 1 R 3 ( R 2 ∩ R 3 ) R 4 ⊆ R 2 R 4 ∩ R 3 R 4 \begin{aligned} R1(R2\cup R3)=R1R2\cup R1R3\\ (R2\cup R3)R4=R2R4\cup R3R4\\ R1(R2\cap R3)\subseteq R1R2\cap R1R3\\ (R2\cap R3)R4\subseteq R2R4\cap R3R4 \end{aligned} R1(R2∪R3)=R1R2∪R1R3(R2∪R3)R4=R2R4∪R3R4R1(R2∩R3)⊆R1R2∩R1R3(R2∩R3)R4⊆R2R4∩R3R4
- 交起來的範圍小于分開交，并起來的範圍大于分開并
設R是從X到Y 的二進制關系，Ix和Iy分别是X和Y上的相等關系，則IxR=RIy=R
合成關系的幂

R 0 = I x R m R n = R m ∗ n ( R m ) n = R m ∗ n R^0 = Ix\\ R^mR^n=R^{m*n}\\ (R^m)^n=R^{m*n} R0=IxRmRn=Rm∗n(Rm)n=Rm∗n
設 ∣ A ∣ = n \mid A \mid=n ∣A∣=n ,R是集合A上的一個關系，那麼存在i和j使得 R i = R j R^i=R^j Ri=Rj ，且 0 ≤ i < j ≤ 2 n 2 0\le i < j \le 2^{n^2} 0≤i<j≤2n2

合成關系的矩陣表示

【離散數學】2. 集合論2. 集合3. 關系4. 函數

合成運算在矩陣表示上是矩陣乘法

求逆

基本概念

設R為X到Y的二進制關系，如果将R中每個序偶的元素順序互換，得到的集合稱為R的逆關系，記作 R ~ \widetilde{R} R

R ~ = { < y , x > ∣ < x , y > ∈ R } \widetilde{R}=\{<y,x> \mid <x,y>\in R \} R

={<y,x>∣<x,y>∈R}

逆關系的表示方法

關系 R ~ \widetilde{R} R

的圖：關系R圖形中将其弧的箭頭方向反置

關系 R ~ \widetilde{R} R

的矩陣：是關系R矩陣 M R M_R MR 的轉置矩陣 M R T M_R^T MRT

性質

R ~ ~ = R \widetilde{\widetilde{R}} = R R

=R
交、并、差合成都可拆開

R 1 ∪ R 2 ~ = R 1 ~ ∪ R 2 ~ \widetilde{R_1\cup R_2}=\widetilde{R_1}\cup \widetilde{R_2} R1∪R2

=R1

∪R2

R 1 ∩ R 2 ~ = R 1 ~ ∩ R 2 ~ \widetilde{R_1\cap R_2}=\widetilde{R_1}\cap \widetilde{R_2} R1∩R2

=R1

∩R2

A − B ~ = A ~ − B ~ \widetilde{A-B} = \widetilde{A}-\widetilde{B} A−B

=A

−B

T ⋅ S ~ = S ~ ⋅ T ~ \widetilde{T·S}=\widetilde{S}·\widetilde{T} T⋅S

=S

⋅T
笛卡爾積的逆

A × B ~ = B × A \widetilde{A\times B}=B\times A A×B

=B×A

A × B A\times B A×B 的全域關系的逆為 B × A B\times A B×A
補集的逆等于逆的補集

R ‾ ~ = R ~ ‾ \widetilde{\overline{R}}=\overline{\widetilde{R}} R

=R

，其中 R ~ ‾ = A × B − R \overline{\widetilde{R}}=A\times B-R R

=A×B−R
R 1 ⊆ R 2 ⇒ R 1 ~ ⊆ R 2 ~ R1\subseteq R2\Rightarrow \widetilde{R1}\subseteq\widetilde{R2} R1⊆R2⇒R1

⊆R2
對稱關系的逆

設關系R是X上的二進制關系，則
- R是對稱的，當且僅當 R = R ~ R=\widetilde{R} R=R
- R是反對稱的，當且僅當 R ∩ R ~ R\cap \widetilde{R} R∩R
  
  是 Ix 的子集

3.3 次序關系

3.3.1 偏序關系

A是一個集合，A上的一個關系，滿足自反性、反對稱性、傳遞性，則稱R是A上的一個偏序關系，記為 ≤ \le ≤

序偶 < A , ≤ > <A,\le> <A,≤> 稱為偏序集

小于等于關系：是典型的偏序關系，矩陣上看是上三角

蓋住

蓋住：如果 x , y ∈ A , x ≤ y , x ≠ y x,y\in A,x \le y, x\neq y x,y∈A,x≤y,x=y 且沒有其他元素z使得 x ≤ z , z ≤ y x\le z,z\le y x≤z,z≤y ，則稱元素y蓋住元素x

從關系圖上了解，x,y之間隻有直接路徑

偏序關系是存在蓋住關系的，滿足蓋住關系一定不是偏序關系

覆寫不滿足傳遞性

求蓋住

給定集合A={1,2,3,4,6,12}，設R是A上的整除關系，即 R = { < x , y > ∣ x 整除 y } R=\{<x,y>|x整除y\} R={<x,y>∣x整除y} ，驗證R是A上的偏序關系，求COV A

1 , 2 , 3 , 4 , 6 , 12 [ 1 , 1 , 1 , 1 , 1 , 1 0 , 1 , 0 , 1 , 1 , 1 0 , 0 , 1 , 0 , 1 , 1 0 , 0 , 0 , 1 , 0 , 1 0 , 0 , 0 , 0 , 1 , 1 0 , 0 , 0 , 0 , 0 , 1 ] \begin{aligned} &\quad 1,2,3,4,6,12\\ &\begin{bmatrix} 1,1,1,1,1,1\\ 0,1,0,1,1,1\\ 0,0,1,0,1,1\\ 0,0,0,1,0,1\\ 0,0,0,0,1,1\\ 0,0,0,0,0,1 \end{bmatrix} \end{aligned} 1,2,3,4,6,12

1,1,1,1,1,10,1,0,1,1,10,0,1,0,1,10,0,0,1,0,10,0,0,0,1,10,0,0,0,0,1

故關系R滿足自反性，反對稱性，傳遞性

C O V A = < 1 , 2 > , < 1 , 3 > , < 2 , 4 > , < 2 , 6 > , < 3 , 6 > , < 4 , 12 > , < 6 , 12 > COV A={<1,2>,<1,3>,<2,4>,<2,6>,<3,6>,<4,12>,<6,12>} COVA=<1,2>,<1,3>,<2,4>,<2,6>,<3,6>,<4,12>,<6,12>

由于 < 1 , 6 > = < 1 , 3 > + < 3 , 6 > <1,6> = <1,3> + <3,6> <1,6>=<1,3>+<3,6> 故 < 1 , 6 > <1,6> <1,6> 不滿足蓋住關系，同理

< 1 , 4 > = < 1 , 2 > + < 2 , 4 > < 1 , 12 > = < 1 , 2 > + < 2 , 6 > < 2 , 12 > = < 2 , 4 > + < 4 , 12 > <1,4> = <1,2>+<2,4> <1,12>=<1,2>+<2,6> <2,12>=<2,4>+<4,12> <1,4>=<1,2>+<2,4><1,12>=<1,2>+<2,6><2,12>=<2,4>+<4,12>

< 3 , 12 > = < 1 , 6 > + < 6 , 12 > <3,12>=<1,6>+<6,12> <3,12>=<1,6>+<6,12>

哈斯圖

用于研究偏序關系的特性

小圓圈代表關系
如果 x ≤ y , 且 x ≠ y x\le y,且x\neq y x≤y,且x=y ，則将代表y的小圓圈畫在代表x的小圓圈上面
如果 < x , y > ∈ C O V A <x,y>\in COV A <x,y>∈COVA ，則在x與y之間用直線相連

如上述例,其哈斯圖為

【離散數學】2. 集合論2. 集合3. 關系4. 函數

極值

設偏序集 < A , ≤ > <A,\le> <A,≤> ，且B是A的子集，對于B中任一進制素b，如果B中沒有任何元素x，滿足 b ≠ x b\neq x b=x ，且

b ≤ x b\le x b≤x 則稱b為B的極大元素

b ≥ x b\ge x b≥x，則稱b是B的極小元素

在哈斯圖中，最上面一層為極大元素，最下面一層為極小元素

【離散數學】2. 集合論2. 集合3. 關系4. 函數

最值

設偏序集 < A , ≤ > <A,\le> <A,≤> ，且B是A的子集，若B中某一進制素b，對于B中每一進制素x,

滿足 x ≤ b x\le b x≤b，則稱b為 <B,\le> <B,≤> 的最大元素

滿足 x ≥ b x\ge b x≥b，則稱b為 <B,\le> <B,≤> 的最小元素

【離散數學】2. 集合論2. 集合3. 關系4. 函數

在哈斯圖中，同一層的且沒有直接路徑的，無法判斷偏序關系

界

設偏序集 < A , ≤ > <A,\le> <A,≤> ，且B是A的子集，若A中某一進制素a,對于B中任一進制素x，滿足

x ≤ a x\le a x≤a，則稱a是B的上界

a ≤ x a\le x a≤x，則稱a是B的下界

【離散數學】2. 集合論2. 集合3. 關系4. 函數

設偏序集 < A , ≤ > <A,\le> <A,≤> ，且B是A的子集

若a是B的任一上界，對于B的所有上界y，滿足 a ≤ y a\le y a≤y ，則稱a為B的最小上界(上确界)，記為 LUB B

若b是B的任一下界，對于B的所有下界z，滿足 z ≤ b z\le b z≤b，，則稱b為B的最大下界(下确界)，記為GLB B

【離散數學】2. 集合論2. 集合3. 關系4. 函數

極值與界的性質

B的最大(小)元素和極大(小)元素都必須是B的元素，而B的上(下)界和最小上界(最大下界)可以是B的元素，也可以是父集A中的元素
極大元素和上界可以存在，也可以不存在，且當他們存在時，可能不唯一

對非空有限偏序集，其極大元素和極小元素總是存在的
設偏序集 < A , ≤ > <A,\le> <A,≤> ，且B是A的子集

如果b是B的最大元素，則b是B的極大元素和最小上界

如果b是B的一個上界，且b在B中，則b是B的最大元素

3.3.2 拟序關系

如果集合A上的二進制關系R是反對稱性、反自反的和傳遞的，那麼R叫A上的拟序關系，記為 <

在集合A上，
- R是一拟序，那麼 r ( R ) = R ∪ I A r(R)=R\cup I_A r(R)=R∪IA 的偏序
- R是一偏序， R − I A R-I_A R−IA是一拟序
即拟序集合與逆序集合唯一差別就是相等關系

3.3.3 全序關系

鍊與反鍊

設偏序集 < A , ≤ > <A,\le> <A,≤> ，在A的子集中，如果每兩個元素都是有關系的，則稱這個子集是鍊。

沒有直接關系的通過傳遞性可建立間接關系

在A的一個子集中，如果每兩個元素都是無關的，則稱這個子集為反鍊

單元素子集，既是鍊又是反鍊

【離散數學】2. 集合論2. 集合3. 關系4. 函數

全序關系

設偏序集 < A , ≤ > <A,\le> <A,≤> ，如果A集合本身是一個鍊，則稱 < A , ≤ > <A,\le> <A,≤> 為全序集合或順序集合，此時二進制關系 ≤ \le ≤ 稱為全序關系或者順序關系

全序集合 < A , ≤ > <A,\le> <A,≤> 就是對于A中任意兩個元素x,y，或者有 x ≤ y x\le y x≤y 或者有 y ≤ x y\le x y≤x 成立

3.3.4 良序

任一偏序集合，如果他的任意非空子集都存在最小元素，稱這種偏序集為良序

定義在自然數集合N上的小于等于關系就是良序的。定義在整數集合I上的小于等于關系就不是良序的

每一個良序集合一定是全序關系
每一個有限的全序集合，一定是良序集合

3.4 等價關系

3.4.1 覆寫與劃分

覆寫：一個集合劃分成若幹個分塊，若分塊的全體構成集合A，則成為A的一個覆寫

劃分：如果A中每個元素屬于且僅屬于一個分塊，那麼這些分塊的全體構成的集合叫做A的一個劃分

集合描述：令A為給定非空集合，非空集合族 π = { A 1 , A 2 , . . . , A n } \pi =\{A1,A2,...,An\} π={A1,A2,...,An} ，其中 A i ⊆ A ， A i A_i\subseteq A ，Ai Ai⊆A，Ai 不為空集且 A 1 ∪ A 2 ∪ . . . ∪ A n = A A1\cup A2\cup...\cup An = A A1∪A2∪...∪An=A ，集合族 π \pi π 則成為集合A的覆寫

若 A i ∩ A j = ϕ Ai\cap Aj = \phi Ai∩Aj=ϕ ，且 ∅ ∉ π ∅\notin \pi ∅∈/π 則稱 π \pi π 為A的劃分

若是劃分，則一定是覆寫；若是覆寫，則不一定是劃分

秩的概念：劃分的元素Ai成為劃分 π \pi π 的塊，如果劃分是有限集合，則不同塊的個數成為劃分的秩；若劃分的是無限集合，則它的秩是無限的，劃分的秩就是劃分的大小

細分

對劃分的再次或多次劃分

設 π \pi π 和 π ′ \pi' π′ 是給定非空集合A的劃分，如果 π ′ \pi' π′ 的每一塊都包含在 π \pi π 的每一塊中，那麼說 π ′ \pi' π′ 細分 π \pi π

如果 π ′ \pi' π′ 細分 π \pi π ，且 π ′ ≠ π \pi'\neq \pi π′=π ，則稱 π ′ \pi' π′ 是 π \pi π 的真細分

3.4.2 等價關系

設R為定義在集合A上的一個關系，若R是自反、對稱和傳遞的，則稱R為等價關系

區分偏序關系：自反，反對稱，傳遞
拟序關系：反自反，反對稱，傳遞

如：

三角形集合上的三角形的相似關系

模m同餘是等價關系：設m是一正整數， a , b ∈ Z a,b\in Z a,b∈Z。若存在整數k，使 a-b=km,則稱a與b模m同餘，記為 a ≡ b ( m o d m ) a\equiv b(mod\quad m) a≡b(modm) 。

【離散數學】2. 集合論2. 集合3. 關系4. 函數

同姓，同年生

誘導等價關系

設R是A上的二進制關系，設R’=tsr®是R的自反對稱傳遞閉包，那麼

R’是A上的等價關系，稱為R誘導的等價關系

如果R’‘是一等價關系，且 R ⊆ R ′ ′ R\subseteq R'' R⊆R′′，那麼 R ′ ⊆ R ′ ′ R'\subseteq R'' R′⊆R′′ ，即 R’ （R的自反對稱傳遞閉包）是包含R的最小等價關系

等價類

集合A中與元素a滿足等價關系的元素組成的集合

設R為集合A上的等價關系，對任何 a ∈ A a\in A a∈A ，集合 [ a ] R = { x ∣ x ∈ A , a R x } [a]_R=\{x\mid x\in A,aRx \} [a]R={x∣x∈A,aRx} 表示A中與a滿足R等價關系的元素組成的集合。簡記為[a]，稱a為等價類[a]的表示元素

等價類性質

等價類 [ a ] R [a]_R [a]R 非空，因為 a ∈ [ a ] R a\in [a]_R a∈[a]R ——自反性決定
a的等價類是集合A中所有與a等價的元素構成的集合——自反性與傳遞性決定
若 < a , b > ∈ R <a,b>\in R <a,b>∈R ，則a與b的等價類相等，即 [ a ] R = [ b ] R [a]_R=[b]_R [a]R=[b]R ，有公共元素的兩個等價類必然相等

若 < a , b > ∉ R <a,b>\notin R <a,b>∈/R ，則a與b一定不屬于同一個等價類，即 [ a ] R ≠ [ b ] R ⟺ [ a ] R ∩ [ b ] R = ∅ [a]_R\neq [b]_R \iff [a]_R \cap [b]_R=∅ [a]R=[b]R⟺[a]R∩[b]R=∅
⋃ [ x ] R = A \bigcup[x]_R =A ⋃[x]R=A

等價類的秩

如果等價類個數有限，則R的不同等價類的個數稱為R的秩

【離散數學】2. 集合論2. 集合3. 關系4. 函數

則同餘模3關系的秩為3

商集

設給定集合A上的等價關系R，以A的全部等價類作為新集合的元素，即 A / R = { [ a ] R ∣ a ∈ A } A/R=\{[a]_R \mid a\in A\} A/R={[a]R∣a∈A} 稱作A的商集

【離散數學】2. 集合論2. 集合3. 關系4. 函數

商集劃分等價關系

集合A上的等價關系R，決定了A的一個劃分，該劃分就是商集A/R
已知 A 1 , A 2 , . . . A n A_1,A_2,...A_n A1,A2,...An 為A的任一劃分，令A上的關系R滿足 R = ⋃ i = 1 n ( A i × A i ) R=\bigcup_{i=1}^n(A_i\times A_i) R=⋃i=1n(Ai×Ai) ，則R為A上的等價關系

1. 集合A={a,b,c,d}上,等價關系 R = { < a , a > , < a , b > , , , < c , c > , < c , d > , < d , c > , < d , d > } R=\{<a,a>,<a,b>,<b,a>,<b,b>,<c,c>,<c,d>,<d,c>,<d,d>\} R={<a,a>,<a,b>,<b,a>,<b,b>,<c,c>,<c,d>,<d,c>,<d,d>} 則，由等價關系R确定A的一個劃分

等價類： [ a ] R = { a , b } = [ b ] R , [ c ] R = { c , d } = [ d ] R [a]_R=\{a,b\}=[b]_R,[c]_R=\{c,d\}=[d]_R [a]R={a,b}=[b]R,[c]R={c,d}=[d]R

商集： A / R = { { a , b } , { c , d } } A/R=\{\{a,b\},\{c,d\}\} A/R={{a,b},{c,d}}

2. 集合 A={a,b,c,d} 的一個劃分 { { a } , { c } , { b , d } } \{\{a\},\{c\},\{b,d\}\} {{a},{c},{b,d}} ，确定A上的一個等價關系

{ a } × { a } = { < a , a > } \{a\}\times \{a\}=\{<a,a>\} {a}×{a}={<a,a>} ， { c } × { c } = { < c , c > } \{c\}\times \{c\}=\{<c,c>\} {c}×{c}={<c,c>}， { b , d } × { b , d } = { , , < d , b > , < d , d > } \{b,d\}\times \{b,d\}=\{<b,b>,<b,d>,<d,b>,<d,d>\} {b,d}×{b,d}={<b,b>,<b,d>,<d,b>,<d,d>}

故等價關系 R = { < a , a > , < c , c > , , , < d , b > , < d , d > } R=\{<a,a>,<c,c>,<b,b>,<b,d>,<d,b>,<d,d>\} R={<a,a>,<c,c>,<b,b>,<b,d>,<d,b>,<d,d>}

集合A的一個劃分确定A的元素間的一個等價關系
設R1和R2為非空集合A上的等價關系，則R1=R2，當且僅當 A/R1 =A/R2（等價關系與劃分一一對應）

4. 函數

函數的本質是二進制關系

4.1 概念

4.1.1 函數概念

函數：X和Y是任意兩個集合，f是X到Y的一個關系，如果對于每個 x ∈ X x\in X x∈X，有唯一的 y ∈ Y y\in Y y∈Y ，使 < x , y > ∈ f <x,y>\in f <x,y>∈f

記為：

f : X → Y 或者 X → f Y f:X\rightarrow Y 或者 X\xrightarrow{f}Y f:X→Y或者Xf

f的前域為函數 y=f(x) 的定義域，記作D(f)=X，f的值域 R ( f ) ⊆ Y R(f)\subseteq Y R(f)⊆Y ，集合Y稱為f的陪域

自變量與因變量

如果有一進制組 < x , y > ∈ f <x,y>\in f <x,y>∈f ，則x稱為自變元，y稱為f作用下x的映像，記為

f ( X ) = { f ( x ) ∣ x ∈ X } f(X)=\{f(x)\mid x\in X \} f(X)={f(x)∣x∈X}

4.1.2 函數個數

設X和Y都是有限集合，分别有m和n個不同元素，每個函數的定義域都為X，則這些函數恰好有 m 個序偶，對于X中任一進制素x，Y中都有n個元素可以成為x的映像，故共有 n m n^m nm 個不同函數

用符号 Y X Y^X YX 表示從X到Y的所有函數的集合

4.1.3 函數的相等

設函數 f : A → B , g : C → D f:A\rightarrow B,g:C\rightarrow D f:A→B,g:C→D ，如果A=C，B=D，且對于所有的 x ∈ A , x ∈ C x\in A,x\in C x∈A,x∈C 有f(x)=g(x)，則稱函數f和g相等，記為f=g

定義域、值域、陪域相等，則函數相等

4.2 合成函數

設函數 g : X → Y , f : W → Z g:X\rightarrow Y,f:W\rightarrow Z g:X→Y,f:W→Z ，若 g ( X ) ⊆ W g(X)\subseteq W g(X)⊆W ，則

f ⋅ g = { < x , z > ∣ x ∈ X ∧ z ∈ Z ∧ ( ∃ y ) ( y ∈ Y ∧ y ∈ W ∧ y = g ( x ) ∧ z = f ( y ) ) } f·g=\{<x,z>\mid x\in X ∧ z\in Z∧(∃y)(y\in Y∧y\in W∧ y=g(x)∧ z=f(y)) \} f⋅g={<x,z>∣x∈X∧z∈Z∧(∃y)(y∈Y∧y∈W∧y=g(x)∧z=f(y))}

稱f在函數g左邊可複合

4.2.1 合成函數

當W=Y，f·g稱為合成函數，或 f·g為f對g的左複合

設 g : X → Y , f : Y → Z g:X\rightarrow Y,f:Y\rightarrow Z g:X→Y,f:Y→Z 是函數，合成函數f·g是從X到Z的函數，對一切 x ∈ X , ( f ⋅ g ) ( x ) = f ( g ( x ) ) x\in X,(f·g)(x)=f(g(x)) x∈X,(f⋅g)(x)=f(g(x))

合成函數的定義域

設 g : { 0 , 1 , 2 } → N g:\{0,1,2\}\rightarrow N g:{0,1,2}→N 定義為 g(x)=x+1， f : N → N f:N\rightarrow N f:N→N 定義為 f(x)=3x+2，

合成函數g·f是沒有定義的，因為g的陪域不是N，無法作為f的前域N。
合成函數f·g時有定義的，f的陪域N，可以作為g的前域

性質

參照合成關系的性質

對集合X， f : X → X f:X\rightarrow X f:X→X ，函數f能同自身合成任意次，f的n次合成定義為：

f 0 ( x ) = x f^0(x)=x f0(x)=x
f n + 1 ( x ) = f ( f n ( x ) ) , n ∈ N f^{n+1}(x)=f(f^n(x)),n\in N fn+1(x)=f(fn(x)),n∈N

4.3 特殊函數

4.3.1 滿射單射雙射概念

映射 f : X → Y 映射f:X\rightarrow Y 映射f:X→Y，如果f(X)=Y，即Y的每一個元素都是X中一個或多個元素的映像，則稱這個映像為滿射

映射 f : X → Y 為滿射 ⟺ ( ∀ y ) ( y ∈ Y → ( ∃ x ) ( x ∈ X ∧ f ( x ) = y ) ) 映射f:X\rightarrow Y為滿射 \iff (\forall y)(y\in Y\rightarrow (∃x)(x\in X∧ f(x)=y)) 映射f:X→Y為滿射⟺(∀y)(y∈Y→(∃x)(x∈X∧f(x)=y))

映射 f : X → Y 映射f:X\rightarrow Y 映射f:X→Y ，如果X中沒有兩個元素有相同的映像，則稱這個映射為單射

映射 f : X → Y 為單射 ⟺ ( ∀ x 1 ) ( ∀ x 2 ) ( x 1 ∈ X ∧ x 2 ∈ X ∧ x 1 ≠ x 2 → f ( x 1 ) ≠ f ( x 2 ) ) 映射 f : X → Y 為單射 ⟺ ( ∀ x 1 ) ( ∀ x 2 ) ( x 1 ∈ X ∧ x 2 ∈ X ∧ f ( x 1 ) = f ( x 2 ) → x 1 = x 2 ) \begin{aligned} 映射f:X\rightarrow Y 為單射\iff (\forall x1)(\forall x2)(x1\in X ∧ x2\in X ∧ x1\neq x2\rightarrow f(x1)\neq f(x2))\\\\ 映射f:X\rightarrow Y 為單射\iff (\forall x1)(\forall x2)(x1\in X ∧ x2\in X ∧ f(x1)=f(x2)\rightarrow x1=x2) \end{aligned} 映射f:X→Y為單射⟺(∀x1)(∀x2)(x1∈X∧x2∈X∧x1=x2→f(x1)=f(x2))映射f:X→Y為單射⟺(∀x1)(∀x2)(x1∈X∧x2∈X∧f(x1)=f(x2)→x1=x2)

雙射：從X到Y的一個映射，既是滿射又是單射，則稱這個映射是雙射的

【離散數學】2. 集合論2. 集合3. 關系4. 函數

合成函數射的性質

gf是一個合成函數

如果g和f是滿射的，則gf是滿射的
如果g和f是單射的，則gf是單射的
如果g和f是雙射的，則gf是雙射的

設gf是合成函數，左滿右單

若gf是滿射的，則g是滿射的
若gf是單射的，則f是單射的
若gf是雙射的，則g是滿射的，f是單射的

4.3.2 常函數

設函數 f : X → Y f:X\rightarrow Y f:X→Y ，如果存在某個 y 0 ∈ Y y_0\in Y y0∈Y ，對于每個 x ∈ X x\in X x∈X，都有 f ( x ) = y 0 f(x)=y_0 f(x)=y0，即 f ( X ) = y 0 f(X)={y_0} f(X)=y0 ，則稱這個函數為常函數

4.3.3 恒等函數

如果有函數為相等關系Ix（ I x = { < x , x > ∣ x ∈ X } Ix=\{<x,x>\mid x\in X \} Ix={<x,x>∣x∈X} ），則稱函數 I x : X → X Ix:X\rightarrow X Ix:X→X 為恒等函數

4.3.4 雙射函數

X上的雙射函數稱為X上的置換或排列

恒等函數是一個置換，稱為麼置換或恒等置換

置換次數：

當X時無限集時，X上的置換是無限次的
當 ∣ X ∣ = n \mid X \mid=n ∣X∣=n ，則X上的置換為n次

4.3.5 集合的特征函數

建立集合與函數之間的關系 ψ A : U → { 0 , 1 } \psi_A:U\rightarrow \{0,1\} ψA:U→{0,1}

若U表示全集，對于一個集合 A ⊆ U A\subseteq U A⊆U

ψ A ( x ) = { 1 , 如果 x ∈ A 0 , 如果 x ∉ A \psi_A(x)= \begin{cases} 1,如果x\in A\\ 0,如果x\notin A \end{cases} ψA(x)={1,如果x∈A0,如果x∈/A

則稱其為集合A的特征函數

設 U = { a , b , c , d } , A = { b , d } , 其特征函數為 ψ A ( a ) = 0 , ψ A ( b ) = 1 , ψ A ( c ) = 0 , ψ A ( d ) = 1 \begin{aligned} 設U=\{a,b,c,d\},A=\{b,d\},其特征函數為\\ \psi_A(a)=0,\psi_A(b)=1,\psi_A(c)=0,\psi_A(d)=1 \end{aligned} 設U={a,b,c,d},A={b,d},其特征函數為ψA(a)=0,ψA(b)=1,ψA(c)=0,ψA(d)=1

性質

【離散數學】2. 集合論2. 集合3. 關系4. 函數

4.4 逆函數

關系的逆: < x , y > ∈ R ⟺ < y , x > ∈ R ~ <x,y>\in R \iff <y,x>\in \widetilde{R} <x,y>∈R⟺<y,x>∈R

但是關系的逆未必是函數

原關系 f : X → Y f:X\rightarrow Y f:X→Y 是雙射函數，那麼f的逆關系 f ~ : Y → X \widetilde{f}:Y\rightarrow X f

:Y→X 是雙射函數。并稱雙射函數 f ~ \widetilde{f} f

是f的逆函數，記為 f − 1 f^{-1} f−1 ，稱函數f是可逆的

滿足一一對應

如果函數 f : X → Y f:X\rightarrow Y f:X→Y 可逆

f ⋅ f − 1 = I y 且 f ⋅ f − 1 = I x f·f^{-1}=Iy且f·f^{-1}=Ix f⋅f−1=Iy且f⋅f−1=Ix
( f − 1 ) − 1 = f (f^{-1})^{-1}=f (f−1)−1=f