当前位置：首页 > news >正文

离散数学·集合论深度学习笔记

news 2026/6/16 5:04:20

📚 离散数学·集合论深度学习笔记

涵盖章节：第1章集合 | 第2章二元关系 | 第3章函数

🔷 第1章集合

一、集合的基本概念

1. 集合的定义与表示

定义：集合是由一些确定的、彼此不同的对象组成的整体。

表示方法：

方法	示例
列举法	A = {1, 2, 3, 4, 5}
描述法	A = {x│x ∈ 自然数, x < 6}
文氏图	用封闭曲线表示集合

元素与集合的关系：

a ∈ A— a属于A
a ∉ A— a不属于A

2. 常见集合记号

N = 自然数集 Z = 整数集 Z⁺ = 正整数集 Q = 有理数集 R = 实数集 C = 复数集 ∅ = 空集（不含任何元素）

3. 集合间的关系

关系	符号	定义
子集	A ⊆ B	A的每个元素都是B的元素
真子集	A ⊂ B	A ⊆ B 且 A ≠ B
相等	A = B	A ⊆ B 且 B ⊆ A
真包含	A ⊃ B	B ⊂ A

定理：空集是任何集合的子集，即 ∅ ⊆ A

4. 幂集

定义：集合A的所有子集构成的集合，记作 P(A)

性质：若 │A│ = n，则 │P(A)│ = 2ⁿ

示例：A = {a, b}

P(A) = {∅, {a}, {b}, {a, b}}

二、集合的运算

1. 基本运算

运算	符号	定义	文氏图解
并集	A ∪ B	{x│x∈A 或 x∈B}	两个圆覆盖的所有区域
交集	A ∩ B	{x│x∈A 且 x∈B}	两个圆重叠的区域
差集	A - B	{x│x∈A 且 x∉B}	A圆除去B重叠的部分
补集	~A	E - A（全集E中除去A）	全集除去A的区域
对称差	A⊕B	(A-B) ∪ (B-A)	两个圆不重叠的部分

2. 运算性质

交换律：

A ∪ B = B ∪ A A ∩ B = B ∩ A

结合律：

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

分配律（★重要）：

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

德摩根律（★考频最高）：

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

吸收律：

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

零律与同一律：

A ∪ ∅ = A A ∩ ∅ = ∅ A ∪ E = E A ∩ E = A

三、有穷集合的计数

1. 包含排斥原理（★核心公式）

两个集合：

│A ∪ B│ = │A│ + │B│ - │A ∩ B│

三个集合：

│A ∪ B ∪ C│ = │A│ + │B│ + │C│ - │A ∩ B│ - │A ∩ C│ - │B ∩ C│ + │A ∩ B ∩ C│

n个集合的通用公式：

│A₁ ∪ A₂ ∪ ... ∪ Aₙ│ = Σ│Aᵢ│ - Σ│Aᵢ ∩ Aⱼ│ + Σ│Aᵢ ∩ Aⱼ ∩ Aₖ│ - ... + (-1)ⁿ⁻¹│A₁ ∩ ... ∩ Aₙ│

2. 典型应用场景

题型：三杂志阅读调查

设某调查60人： - 25人读三联生活周刊 - 26人读读者 - 26人读中国国家地理 - 9人读三联+国家地理 - 11人读三联+读者 - 8人读读者+国家地理 - 8人什么也不读 求：阅读全部三种杂志的人数

解法：用包含排斥原理列方程

│三联∪读者∪国家地理│ = 60 - 8 = 52 52 = 25+26+26 - 9-11-8 + │三联∩读者∩国家地理│ 52 = 49 + │三联∩读者∩国家地理│ ∴ │三联∩读者∩国家地理│ = 3

四、典型例题精选

例1判断对错：若 A ∩ B = B，则 A = E（全集）

解答：❌ 错误。

反例：E = {1,2,3}，A = {1,2}，B = {2}
A ∩ B = {2} = B ✓，但 A ≠ E

例2化简：(A ∩ B) ∪ (A - B)

解答：

(A ∩ B) ∪ (A - B) = (A ∩ B) ∪ (A ∩ ~B) = A ∩ (B ∪ ~B) = A ∩ E = A

例3证明：P(A) ∩ P(B) = P(A ∩ B)

证明：

X ∈ P(A) ∩ P(B) ⇔ X ⊆ A ∧ X ⊆ B ⇔ X ⊆ A ∩ B ⇔ X ∈ P(A ∩ B)

🔷 第2章二元关系

一、有序对与笛卡儿积

1. 有序对

定义：由两个元素x和y按一定顺序排列成的二元组，记作⟨x,y⟩

性质：

当 x ≠ y 时，⟨x,y⟩ ≠ ⟨y,x⟩
⟨x,y⟩ = ⟨u,v⟩ ⇔ x = u 且 y = v

2. 笛卡儿积

定义：A × B = {⟨x,y⟩│ x∈A, y∈B }

性质：

不满足交换律（A×B ≠ B×A）
不满足结合律
对并和交满足分配律
若 A=∅ 或 B=∅，则 A×B = ∅

计数：│A│ = m, │B│ = n ⇒ │A×B│ = mn

二、二元关系

1. 定义

二元关系R：所有元素都是有序对的集合（空集也是二元关系）

从A到B的关系：R ⊆ A × B
A上的关系：R ⊆ A × A

关系计数：

从A到B的二元关系个数：2^(m·n)
A上的二元关系个数：2^(n²)

2. 特殊关系

关系	符号	定义
空关系	∅	不含任何有序对
全域关系	E_A	A × A
恒等关系	I_A	{⟨x,x⟩│ x∈A}

3. 关系的三种表示法（★核心考点）

表示法	方式	适用场景
集合表达式	枚举所有有序对 R = {⟨1,2⟩, ⟨2,3⟩}	小型关系
关系矩阵	布尔矩阵，M_R(i,j)=1 当⟨i,j⟩∈R	判断性质、做运算
关系图	顶点+有向边	直观判断传递性等

三、关系的五种性质（★必考）

性质	矩阵特征	图特征	定义
自反	主对角线全1	每个顶点有环	∀x∈A, ⟨x,x⟩∈R
反自反	主对角线全0	每个顶点无环	∀x∈A, ⟨x,x⟩∉R
对称	矩阵对称	有边必有反向边	若⟨x,y⟩∈R则⟨y,x⟩∈R
反对称	对称位置不同时为1(x≠y)	无双向边	若⟨x,y⟩∈R,⟨y,x⟩∈R 则x=y
传递	M²中1的位置M中也1	两步路径必有直连边	若⟨x,y⟩,⟨y,z⟩∈R则⟨x,z⟩∈R

关键记忆：

自反 ≠ 反自反（一个关系可以既不自反也不反自反）
对称 ≠ 反对称（恒等关系I_A既对称又反对称！）
传递性的判断方法：若不存在x,y,z使得⟨x,y⟩∈R且⟨y,z⟩∈R，则空满足传递性

四、关系运算

1. 基本运算

运算	定义	说明
定义域	dom R = {x│∃y, ⟨x,y⟩∈R}	第一元素集合
值域	ran R = {y│∃x, ⟨x,y⟩∈R}	第二元素集合
域	fld R = dom R ∪ ran R
逆	R⁻¹ = {⟨y,x⟩│ ⟨x,y⟩∈R}	交换顺序
右复合	F∘G = {⟨x,z⟩│∃y, ⟨x,y⟩∈F∧⟨y,z⟩∈G}	中间桥梁y
限制	R↾A = {⟨x,y⟩∈R│ x∈A}	只保留第一元素在A中
像	R[A] = ran(R↾A)	限制后的值域
幂	R⁰ = I_A, Rⁿ⁺¹ = Rⁿ∘R	关系复合自身

2. 运算性质

R∘(S∪T) = R∘S ∪ R∘T R∘(S∩T) ⊆ R∘S ∩ R∘T (R⁻¹)⁻¹ = R (F∘G)⁻¹ = G⁻¹∘F⁻¹ R∘I_A = I_A∘R = R

五、关系闭包

定义：包含R且具有某种性质的最小关系

闭包	符号	公式
自反闭包	r®	R ∪ I_A
对称闭包	s®	R ∪ R⁻¹
传递闭包	t®	R ∪ R² ∪ R³ ∪ …（Rⁿ,n为A中元素个数）

重要性质：

R自反 ⟹ s®和t®自反
R对称 ⟹ r®和t®对称
R传递 ⟹ r®传递（s®不一定传递！）

六、等价关系与划分（★重点）

1. 等价关系

定义：自反 + 对称 + 传递

等价类：[x]R = {y│y∈A, ⟨x,y⟩∈R}

等价类性质：

(1) [x] 是A的非空子集 (2) 若xRy，则[x] = [y] (3) 若 ¬(xRy)，则 [x] ∩ [y] = ∅ (4) ∪{[x]│x∈A} = A

商集：A/R = {[x]R│x∈A}

2. 划分

划分：满足以下条件的子集族π：

(1) ∅ ∉ π（划分块非空） (2) π中任意两集合不交 (3) ∪π = A

等价关系 ⇔ 划分一一对应

七、偏序关系与哈斯图（★重点）

1. 偏序关系

定义：自反 + 反对称 + 传递，记作 ≤

可比性：x与y可比 ⟺ x≤y 或 y≤x

全序（线序）：任意两元素均可比的偏序

2. 哈斯图

画法规则：

用顶点表示元素
若 x<y，则x画在y的下方
若y覆盖x（不存在z使得x<z<y），则在x和y间连线

3. 特殊元素（★高频考点）

设(A,≤)为偏序集，B⊆A

元素	定义
极大元	y∈B，B中不存在比y大的元素
极小元	y∈B，B中不存在比y小的元素
最大元	y∈B，∀x∈B有 x≤y
最小元	y∈B，∀x∈B有 y≤x
上界	y∈A，∀x∈B有 x≤y
下界	y∈A，∀x∈B有 y≤x
上确界	上界中的最小元
下确界	下界中的最大元

重要区别：

极大元/极小元一定在B中
上界/下界可以在A中但不在B中
B可能没有最大元但可以有极大元

八、典型例题精选

例1判断关系性质

A = {1,2,3}, R = {⟨1,2⟩, ⟨2,1⟩}

答：

对称：✓（有⟨1,2⟩也有⟨2,1⟩）
传递：✓（没有两条连续的路径，空满足）
自反：✗（缺少⟨1,1⟩,⟨2,2⟩,⟨3,3⟩）
反对称：✗（有双向边）

例2构造等价关系

A = {1,2,3,4}, 划分π = {{1,2},{3,4}}，求对应的等价关系R

答：

R = {⟨1,1⟩,⟨1,2⟩,⟨2,1⟩,⟨2,2⟩,⟨3,3⟩,⟨3,4⟩,⟨4,3⟩,⟨4,4⟩}

例3哈斯图找特殊元素

偏序集({2,4,6,8,12,24}, 整除关系)

极大元：24
极小元：2
若B = {4,6}：
- 上界：12, 24
- 下界：2
- 上确界：12
- 下确界：2

🔷 第3章函数

一、函数的基本概念

1. 函数的定义

函数f：A→B是满足以下条件的从A到B的二元关系：

(1) 处处有定义：dom f = A (2) 单值性：若⟨x,y⟩∈f且⟨x,z⟩∈f，则y=z

记法：f(x) = y 表示 ⟨x,y⟩ ∈ f

2. 函数的类型（★核心考点）

类型	英文	定义
单射（入射）	injection	∀x₁≠x₂, f(x₁)≠f(x₂)
满射（映上）	surjection	ran f = B
双射（一一对应）	bijection	既是单射又是满射

直观判断：

单射：不同x对应不同y（2个x不能映射到同一个y）
满射：B中每个y都能被射到
双射：A和B的元素"一一配对"

函数计数：

A→B的函数个数：│B│^│A│
单射个数：P(│B│, │A│) = │B│!/(│B│-│A│)! (当│A│≤│B│)
满射个数：│B│!·S(│A│,│B│)（第二类斯特林数）
双射个数：│A│!（当│A│=│B│）

二、复合函数与逆函数

1. 复合函数

定义：f∘g(x) = f(g(x))

性质：

(1) f,g单射 ⟹ f∘g单射 (2) f,g满射 ⟹ f∘g满射 (3) f,g双射 ⟹ f∘g双射 (4) 复合函数不满足交换律 (5) 复合函数满足结合律：h∘(g∘f) = (h∘g)∘f

2. 逆函数

定义：若f是双射，则存在逆函数f⁻¹: B→A

f⁻¹(y) = x 当且仅当 f(x) = y

性质：

f⁻¹∘f = I_A f∘f⁻¹ = I_B

三、集合的基数

1. 等势

定义：集合A与B等势（A≈B）当且仅当存在从A到B的双射

常见等势关系：

N ≈ Z ≈ Q（可数集） R ≈ (0,1)（不可数集） R ≈ [0,1]

2. 可数集与不可数集

类型	基数	含义
有限集	n	有n个元素
可数无穷集	ℵ₀	与自然数集N等势，如整数集、有理数集
不可数集	ℵ₁	与实数集R等势

康托尔定理：任何集合A与其幂集P(A)不等势

推论：不存在"最大的集合"

3. 基数比较

施罗德-伯恩斯坦定理：
若A与B的某个子集等势，且B与A的某个子集等势，则A≈B

四、典型例题精选

例1判断函数类型

f: N → N, f(n) = 2n

答：

单射：✓（n₁≠n₂ ⟹ 2n₁≠2n₂）
满射：✗（奇数值无法取到，如1,3,5…不在值域中）
类型：单射非满射

例2判断函数类型

f: R → [0, +∞), f(x) = x²

答：

满射：✓（∀y≥0，存在x=√y使得f(x)=y）
单射：✗（f(-1)=f(1)=1）
类型：满射非单射

例3构造双射

构造从 Z（整数集）到 N（自然数集）的双射

解答：

f(x) = { 2x, 当 x ≥ 0 { -2x-1, 当 x < 0 验证： 0→0, 1→2, 2→4, ... (正偶数) -1→1, -2→3, -3→5, ... (奇数)

🎯 学习建议

层次	内容	建议
基础	集合运算、文氏图、关系矩阵、哈斯图	多画图，直观理解比死记硬背更有效
进阶	等值演算(集合恒等式证明)、关系性质判断、闭包计算	背熟德摩根律和分配律，学会反证法
综合	等价关系与划分、偏序特殊元素、康托尔定理	理解"关系⇔划分"的对偶性，掌握基数比较方法

📚 附录一：常用公式速查

集合恒等式

A ∪ (A ∩ B) = A （吸收1） A ∩ (A ∪ B) = A （吸收2） A - (B ∪ C) = (A-B) ∩ (A-C) （德摩根导数） (A - B) ∪ (B - A) = (A ∪ B) - (A ∩ B) （对称差）

关系闭包公式

r(R) = R ∪ I_A s(R) = R ∪ R⁻¹ t(R) = ∪_{k=1}^{n} Rᵏ（对n元集上的关系）

等价关系 ⇔ 划分对应表

等价关系R	划分π = A/R
xRy 当且仅当 x,y在同一个划分块	等价类就是划分块
自反	每个元素属于某个块
对称	划分块中元素对称
传递	划分块中元素传递