离散数学·集合论深度学习笔记涵盖章节第1章 集合 | 第2章 二元关系 | 第3章 函数 第1章 集合一、集合的基本概念1. 集合的定义与表示定义集合是由一些确定的、彼此不同的对象组成的整体。表示方法方法示例列举法A {1, 2, 3, 4, 5}描述法A {x│x ∈ 自然数, x 6}文氏图用封闭曲线表示集合元素与集合的关系a ∈ A— a属于Aa ∉ A— a不属于A2. 常见集合记号N 自然数集 Z 整数集 Z⁺ 正整数集 Q 有理数集 R 实数集 C 复数集 ∅ 空集不含任何元素3. 集合间的关系关系符号定义子集A ⊆ BA的每个元素都是B的元素真子集A ⊂ BA ⊆ B 且 A ≠ B相等A BA ⊆ B 且 B ⊆ A真包含A ⊃ BB ⊂ A定理空集是任何集合的子集即 ∅ ⊆ A4. 幂集定义集合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重叠的部分补集~AE - 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 252626 - 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 v2. 笛卡儿积定义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 × BA上的关系R ⊆ A × A关系计数从A到B的二元关系个数2^(m·n)A上的二元关系个数2^(n²)2. 特殊关系关系符号定义空关系∅不含任何有序对全域关系E_AA × 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 则xy传递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. 哈斯图画法规则用顶点表示元素若 xy则x画在y的下方若y覆盖x不存在z使得xzy则在x和y间连线3. 特殊元素★高频考点设(A,≤)为偏序集B⊆A元素定义极大元y∈BB中不存在比y大的元素极小元y∈BB中不存在比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. 函数的定义函数fA→B是满足以下条件的从A到B的二元关系(1) 处处有定义dom f A (2) 单值性若⟨x,y⟩∈f且⟨x,z⟩∈f则yz记法f(x) y 表示 ⟨x,y⟩ ∈ f2. 函数的类型★核心考点类型英文定义单射入射injection∀x₁≠x₂, f(x₁)≠f(x₂)满射映上surjectionran f B双射一一对应bijection既是单射又是满射直观判断单射不同x对应不同y2个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)∘f2. 逆函数定义若f是双射则存在逆函数f⁻¹: B→Af⁻¹(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) ∪_{k1}^{n} Rᵏ对n元集上的关系等价关系 ⇔ 划分 对应表等价关系R划分π A/RxRy 当且仅当 x,y在同一个划分块等价类就是划分块自反每个元素属于某个块对称划分块中元素对称传递划分块中元素传递 附录二考研/考试常见题型题型一集合恒等式证明方法按定义展开 → 用运算律化简 → 得到另一侧题型二关系性质综合判断方法画关系图/矩阵 → 逐条检查五大性质题型三等价关系与商集方法先验证三条性质 → 找等价类 → 写出商集题型四偏序集的特殊元素方法画哈斯图 → 在图中找极大/极小元 → 找上界/下界题型五函数类型判断方法检查单值性和定义域 → 检查单射/满射本笔记基于《离散数学学习指导与习题解析第3版》第1-3章内容整理