返回：0100 离散数学课程总目录 · 上一章：0101 集合论课程引言、预备知识与集合基本概念 · 下一章：0103 函数与集合论习题课

1、资料来源与学习目标

本章对应北大离散数学刘田老师“集合论与图论”第二章。Auto_Tutor 中整理到的资料包括：

资料 内容
2.1 有序对与卡氏积 有序对、有序 n 元组、笛卡尔积及其性质
2.2 二元关系 n 元关系、二元关系、特殊关系、定义域、值域、逆、合成、限制、象
2.3 关系的表示和关系的性质 关系矩阵、关系图、自反、反自反、对称、反对称、传递
2.4 关系的幂运算和闭包 关系幂、自反闭包、对称闭包、传递闭包、闭包求法
2.5 等价关系和划分 等价关系、等价类、商集、划分、加细、Stirling 子集数
2.6 序关系 偏序、全序、拟序、哈斯图、特殊元素、链、反链、良序
002 习题与答案 习题 2.6、2.7、2.11、2.12、2.16、2.17、2.22、2.27、2.29、35、39、47、50、52

本章的核心目标：把第一章的集合语言升级成“关系语言”。关系本质上是有序对的集合；后面的函数、图、等价分类、偏序结构都从这里长出来。

2、颜色标注

颜色 含义
粉色 必背、必会证明、后续章节反复使用
蓝色 核心术语和定义
橙色 易错点、边界条件
绿色 理解提示和后续连接

3、章节主线

模块 本章要会什么 后续连接
有序对与笛卡尔积 知道 <a,b> 和 {a,b} 不同，会展开 A×B 关系定义
二元关系 把关系看成 A×B 或 A×A 的子集 函数、图
关系表示 会在集合表达式、关系矩阵、关系图之间转换 图论、计算闭包
关系性质 会判定自反、反自反、对称、反对称、传递 等价关系、序关系
闭包 会求 r(R)、s(R)、t(R) 等价闭包、可达性
等价关系 会从等价关系得到等价类和商集，也会从划分得到等价关系 分类、同余
序关系 会区分偏序、全序、拟序、良序，能读哈斯图 数据结构、拓扑排序

4、有序对与笛卡尔积

4.1 有序对

有序对定义为：

1
<a,b> = {{a},{a,b}}

其中 a 是第一元素，b 是第二元素；<a,b> 也常写作 (a,b)。

核心定理：

1
<a,b>=<c,d> ⇔ a=c ∧ b=d

因此，只要 a≠b，就有 <a,b>≠<b,a>。

有序对强调位置，普通集合不强调位置。 {a,b}={b,a}，但通常 <a,b>≠<b,a>。

有序三元组和 n 元组递归定义：

1
2
<a,b,c> = <<a,b>,c>
<a1,a2,...,an> = <<a1,a2,...,a(n-1)>,an>

4.2 笛卡尔积

笛卡尔积定义为：

1
A×B = {<x,y>|x∈A ∧ y∈B}

常用性质：

性质 说明
非交换 通常 A×B≠B×A
非结合 通常 (A×B)×C≠A×(B×C)
空积条件 A×B=∅ ⇔ A=∅ ∨ B=∅
分配律 A×(B∪C)=(A×B)∪(A×C)
交分配 A×(B∩C)=(A×B)∩(A×C)
包含推出 A⊆C ∧ B⊆D ⇒ A×B⊆C×D

理解：笛卡尔积就是把两个集合中的元素按顺序配对。它给“关系”准备了所有可能的边。

5、二元关系

5.1 基本定义

概念 定义
n 元关系 元素全是有序 n 元组的集合
二元关系 元素全是有序对的集合
A 到 B 的关系 A×B 的任意子集
A 上的关系 A×A 的任意子集
中缀记号 <x,y>∈R ⇔ xRy

若 |A|=m，|B|=n，则：

1
2
A 到 B 的二元关系共有 2^(mn) 个
A 上的二元关系共有 2^(m^2) 个

5.2 特殊关系

设 A 为任意集合：

关系 定义
空关系 ∅
恒等关系 `I_A={<x,x>
全域关系 E_A=A×A

常见例子：

关系 说明
整除关系 D_A `{<x,y>
小于等于关系 LE_A `{<x,y>
包含关系 `{<x,y>
真包含关系 `{<x,y>

5.3 定义域、值域、逆、合成、限制、象

概念 公式
定义域 `dom R={x
值域 `ran R={y
域 fld R=dom R∪ran R
逆关系 `R^-1={<x,y>
合成 `F∘G={<x,y>
限制 `F↑A={<x,y>
象 `F[A]={y

关系合成的顺序最容易错。这里采用课件中的记法：F∘G 表示先走 G，再走 F。

常用结论：

1
2
(R1∘R2)∘R3 = R1∘(R2∘R3)
(F∘G)^-1 = G^-1∘F^-1

6、关系的表示与性质

6.1 三种表示

设 A={a1,a2,...,an}，R⊆A×A。

表示 说明
集合表达式 直接列出或描述有序对
关系矩阵 M(R) 若 <ai,aj>∈R，则第 i,j 项为 1，否则为 0
关系图 G(R) 顶点表示元素，若 <ai,aj>∈R，画从 ai 到 aj 的有向边

关系矩阵常用性质：

1
2
M(R^-1) = M(R)^T
M(R1∘R2) = M(R2) · M(R1)

这里的矩阵乘法是逻辑乘：加法用 ∨，乘法用 ∧。

6.2 五种关系性质

性质 定义 矩阵/图判定
自反 (∀x∈A)xRx 主对角线全为 1；每个顶点有环
反自反 (∀x∈A)¬xRx 主对角线全为 0；每个顶点无环
对称 xRy⇒yRx 矩阵对称；有边必有反向边
反对称 xRy∧yRx⇒x=y 非对角位置不能成对出现 1
传递 xRy∧yRz⇒xRz R∘R⊆R；有两步路径必有直达边

对称和反对称不是互为否定。 一个关系可以既对称又反对称，例如恒等关系；也可以二者都不是。

几个快速判定：

1
2
3
4
5
R 自反 ⇔ I_A⊆R
R 反自反 ⇔ I_A∩R=∅
R 对称 ⇔ R^-1=R
R 反对称 ⇔ R^-1∩R⊆I_A
R 传递 ⇔ R∘R⊆R

7、关系幂与闭包

7.1 关系幂

设 R⊆A×A：

1
2
R^0 = I_A
R^(n+1) = R^n∘R

常用公式：

1
2
R^m∘R^n = R^(m+n)
(R^m)^n = R^(mn)

7.2 三种闭包

闭包的思想是：在保留原关系 R 的基础上，补最少的边，让它具有指定性质。

闭包 目标性质 公式
自反闭包 自反 r(R)=R∪I_A
对称闭包 对称 s(R)=R∪R^-1
传递闭包 传递 t(R)=R∪R^2∪R^3∪...

闭包的基本判定：

1
2
3
R 自反 ⇔ r(R)=R
R 对称 ⇔ s(R)=R
R 传递 ⇔ t(R)=R

传递闭包对并不完全分配。一般只有 t(R1)∪t(R2)⊆t(R1∪R2)，不一定反向包含，因为两个关系合起来可能产生新的两步路径。

8、等价关系与划分

8.1 等价关系

设 A≠∅，R⊆A×A。若 R 同时满足：

1
自反 + 对称 + 传递

则 R 是 A 上的等价关系。

典型例子：

关系 是否等价 原因
“同年生” 是 自反、对称、传递
“同姓” 是 自反、对称、传递
“年龄不比 y 小” 否 不对称
“选修同门课程” 否 不一定传递
“体重比 y 重” 否 非自反、非对称

8.2 等价类与商集

等价类：

1
[x]_R = {y|y∈A∧xRy}

商集：

1
A/R = {[x]_R|x∈A}

等价类四条核心性质：

性质 说明
[x]_R≠∅ 自反性保证 x∈[x]_R
xRy⇒[x]_R=[y]_R 等价的元素在同一类
¬xRy⇒[x]_R∩[y]_R=∅ 不等价的类互不相交
`∪{[x]_R x∈A}=A`

8.3 划分

集合 A≠∅ 的划分是 A 的一族非空子集，满足：

  1. 每个块非空。
  2. 不同块互不相交。
  3. 所有块的并是 A。

等价关系和划分是一一对应的：等价关系产生商集划分；划分也能诱导“同块”这个等价关系。

9、序关系

9.1 偏序

设 A≠∅，R⊆A×A。若 R 同时满足：

1
自反 + 反对称 + 传递

则 R 是 A 上的偏序关系，常记作 ≼。<A,≼> 称为偏序集。

典型偏序：

偏序 例子
小于等于 <A,≤>
大于等于 <A,≥>
整除 `<A,
包含 <P(A),⊆>
划分加细 <π,≼加细>

9.2 可比、覆盖、哈斯图

概念 定义
可比 x≼y ∨ y≼x
严格小于 x≼y ∧ x≠y，记作 x≺y
覆盖 x≺y 且不存在 z 使 x≺z≺y
哈斯图 去掉自环和传递边，把覆盖关系画成从下到上的无向边

9.3 全序、拟序、良序

概念 条件
全序 偏序且任意两个元素可比
拟序 反自反且传递；可推出反对称
拟全序 拟序且满足三歧性：x≺y、x=y、y≺x 有且仅有一个成立
良序 拟全序，且任意非空子集都有最小元

9.4 特殊元素

设 <A,≼> 为偏序集，B⊆A。

概念 定义
最大元 y∈B 且 ∀x∈B(x≼y)
最小元 y∈B 且 ∀x∈B(y≼x)
极大元 y∈B 且不存在 B 中严格大于它的元素
极小元 y∈B 且不存在 B 中严格小于它的元素
上界 y∈A 且 ∀x∈B(x≼y)
下界 y∈A 且 ∀x∈B(y≼x)
上确界 上界集合中的最小元
下确界 下界集合中的最大元

最大元一定是极大元；极大元不一定是最大元。最大元要求和所有元素可比，极大元只要求没有比它更大的元素。

10、习题与答案

习题 2.6：笛卡尔积包含式

题目：设 A,B,C,D 为任意集合，证明：

1
2
(1) (A×C)∪(B×D) ⊆ (A∪B)×(C∪D)
(2) (A-B)×(C-D) ⊆ (A×C)-(B×D)

证明思路：

1
2
3
4
若 <x,y>∈(A×C)∪(B×D)
则 (x∈A∧y∈C) ∨ (x∈B∧y∈D)
推出 x∈A∪B 且 y∈C∪D
所以 <x,y>∈(A∪B)×(C∪D)

第二式：

1
2
3
4
若 <x,y>∈(A-B)×(C-D)
则 x∈A∧x∉B∧y∈C∧y∉D
推出 <x,y>∈A×C，且 <x,y>∉B×D
所以 <x,y>∈(A×C)-(B×D)

习题 2.7：笛卡尔积与差、对称差

题目：设 A,B,C 为任意集合，证明：

1
2
(1) (A-B)×C = (A×C)-(B×C)
(2) (A⊕B)×C = (A×C)⊕(B×C)

证明 (1)：

1
2
3
4
5
<x,y>∈(A-B)×C
⇔ x∈A-B ∧ y∈C
⇔ x∈A ∧ x∉B ∧ y∈C
⇔ <x,y>∈A×C ∧ <x,y>∉B×C
⇔ <x,y>∈(A×C)-(B×C)

(2) 可由 (1) 推出：

1
2
3
4
5
(A⊕B)×C
= ((A-B)∪(B-A))×C
= ((A-B)×C)∪((B-A)×C)
= ((A×C)-(B×C))∪((B×C)-(A×C))
= (A×C)⊕(B×C)

习题 2.12：关系的逆、合成、限制和象

题目：设：

1
R = {<∅,{∅,{∅}}>, <{∅},∅>, <∅,∅>}

答案：

1
R^-1 = {<{∅,{∅}},∅>, <∅,{∅}>, <∅,∅>}
1
R∘R = {<{∅},{∅,{∅}}>, <{∅},∅>, <∅,∅>, <∅,{∅,{∅}}>}

限制：

1
2
3
4
R↑∅ = ∅
R↑{∅} = {<∅,{∅,{∅}}>, <∅,∅>}
R↑{{∅}} = {<{∅},∅>}
R↑{∅,{∅}} = R

象：

1
2
3
4
R[∅] = ∅
R[{∅}] = {{∅,{∅}},∅}
R[{{∅}}] = {∅}
R[{∅,{∅}}] = {{∅,{∅}},∅}

定义域、值域、域：

1
2
3
dom R = {∅,{∅}}
ran R = {{∅,{∅}},∅}
fld R = {∅,{∅},{∅,{∅}}}

习题 2.16：列举关系并分析性质

题目：设 A={0,1,...,12}，R,S⊆A×A：

1
2
R={<x,y>|x,y∈A∧x+y=10}
S={<x,y>|x,y∈A∧x+3y=12}

答案：

1
2
R = {<0,10>,<10,0>,<1,9>,<9,1>,<2,8>,<8,2>,
     <3,7>,<7,3>,<4,6>,<6,4>,<5,5>}
1
S = {<0,4>,<3,3>,<6,2>,<9,1>,<12,0>}

性质：

1
2
R 具有对称性
S 具有反对称性

习题 2.17：关系矩阵与关系性质

题目：设 A={0,1,2,3}，R⊆A×A，且：

1
R={<x,y>|x=y ∨ x+y∈A}

答案：

1
R = I_A ∪ {<0,1>,<1,0>,<0,2>,<2,0>,<0,3>,<3,0>,<1,2>,<2,1>}

按照元素顺序 0,1,2,3，关系矩阵是：

1
2
3
4
5
M(R)=
1 1 1 1
1 1 1 0
1 1 1 0
1 0 0 1

性质：

1
R 是自反的、对称的。

习题 2.22：自反且传递推出 R∘R=R

题目：设 R 是非空集合 A 上的二元关系，证明如果 R 是自反的且传递的，则：

1
R∘R = R

证明：

1
2
3
先证 R∘R⊆R：
若 <x,y>∈R∘R，则存在 z，使 xRz 且 zRy。
R 传递，所以 xRy，即 <x,y>∈R。
1
2
3
再证 R⊆R∘R：
若 xRy，因为 R 自反，所以 yRy。
取 z=y，则 xRy 且 yRy，所以 <x,y>∈R∘R。

所以 R∘R=R。

逆命题不真。反例：取 R=∅，则 R∘R=R，但在非空集合上 R 不自反。

习题 2.29：求闭包

题目：设 A={a,b,c,d}，R⊆A×A，且：

1
R={<a,a>,<b,b>,<a,b>,<c,d>}

答案：

1
2
r(R)=R∪I_A
    ={<a,a>,<b,b>,<c,c>,<d,d>,<a,b>,<c,d>}
1
2
s(R)=R∪R^-1
    ={<a,a>,<b,b>,<a,b>,<b,a>,<c,d>,<d,c>}
1
t(R)=R

因为 R 已经是传递的。

习题 35：证明等价关系

题目：设 R 是非空集合 A 上的二元关系，满足：

1
2
(1) R 是自反的
(2) 若 <x,y>∈R 且 <x,z>∈R，则 <y,z>∈R

证明 R 是 A 上的等价关系。

证明：

  1. 自反性：已知。
  2. 对称性：若 <x,y>∈R，由自反性有 <x,x>∈R。套用条件 (2)，得到 <y,x>∈R。
  3. 传递性：若 <x,y>∈R 且 <y,z>∈R，由对称性得 <y,x>∈R。套用条件 (2)，得到 <x,z>∈R。

所以 R 自反、对称、传递，是等价关系。

习题 39：划分诱导等价关系

题目：设 A={1,2,3,4}，π={{1,2,3},{4}} 是 A 的划分。

由 π 诱导出的等价关系是同块关系：

1
R_π = I_A ∪ {<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>}

商集：

1
A/R_π = {{1,2,3},{4}}

π 的所有加细包括：

1
2
3
4
5
{{1,2,3},{4}}
{{1},{2,3},{4}}
{{2},{1,3},{4}}
{{3},{1,2},{4}}
{{1},{2},{3},{4}}

它们分别诱导同块等价关系；最细的划分诱导 I_A。

习题 47：54 的因子偏序

设 A 是 54 的因子集合，偏序为整除关系：

1
A={1,2,3,6,9,18,27,54}

答案要点：

1
2
3
4
5
最长链有 4 条：
{1,2,6,18,54}
{1,3,6,18,54}
{1,3,9,18,54}
{1,3,9,27,54}

最长链长度为 5，因此至少可以划分成 5 个互不相交的反链，例如：

1
{1}, {2,3}, {6,9}, {18,27}, {54}

最多可以划分成 8 个互不相交的反链，即每个元素单独成一个反链。

习题 52：三元集上的偏序关系数

设 A 是 3 元集，则 A 上共有：

1
19

个偏序关系。

思路：利用偏序关系和哈斯图的一一对应来枚举。三元集上的偏序结构可分为无边、一条覆盖边、两条覆盖边等情况，合计 19 种。

11、复盘清单

  1. 关系就是有序对的集合；R⊆A×B 是从 A 指向 B 的边集合。
  2. 判断关系性质时，先看定义，再用矩阵/图辅助。
  3. 自反看主对角线，对称看矩阵转置，传递看两步路径。
  4. r(R)=R∪I_A，s(R)=R∪R^-1，t(R)=R∪R^2∪R^3∪... 必须熟。
  5. 等价关系是“分类关系”：等价类互不相交并覆盖全集。
  6. 偏序关系是“层级关系”：哈斯图只画覆盖边，不画自环和传递边。
  7. 最大元与极大元、最小元与极小元要分开；最大/最小要求可比较到全体。

12、下一步

第三章进入函数与集合论习题课。复习第二章时，重点先把 关系 = 笛卡尔积的子集、等价关系 = 分类、偏序关系 = 层级 三个直觉稳住，再去做矩阵、闭包和证明题。