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