auto_ai 知识库

Appearance

集合论是离散数学的起点。本笔记梳理集合的基本概念与运算、三大类证明方法（直接/间接/归纳）以及递归定义（集合、函数、树的递归构造）。

集合的基本概念 ​

集合表示与关系 ​

  • 集合：没有重复元素的整体。表示方法：列举法、描述法
  • 元素与属于：a∈A（a 属于 A），a∉A
  • 包含：A⊆B 当且仅当 A 的每个元素都是 B 的元素
  • 相等：A=B 当且仅当 A⊆B 且 B⊆A（外延公理）
  • 空集 ∅：不含任何元素；全集 U：包含讨论范围内所有元素
  • 幂集 P(A)：A 的所有子集构成的集合，|P(A)| = 2^|A|

集合运算 ​

运算记号含义
并A∪B属于 A 或属于 B
交A∩B同时属于 A 和 B
差A−B属于 A 但不属于 B
补~A 或 A̅U − A
对称差A⊕B(A−B)∪(B−A)
  • 若 A∩B = ∅，称 A 与 B 不相交
  • 文氏图用于直观验证集合恒等式

集合恒等式（重要） ​

名称等式
幂等律A∪A = A，A∩A = A
交换律A∪B = B∪A，A∩B = B∩A
结合律(A∪B)∪C = A∪(B∪C)
分配律A∩(B∪C) = (A∩B)∪(A∩C)
德摩根律~(A∪B) = ~A∩~B，~(A∩B) = ~A∪~B
吸收律A∪(A∩B) = A，A∩(A∪B) = A
双重否定~(~A) = A

证明方法（考点） ​

直接证明与间接证明 ​

  1. 直接证明：从已知条件出发，依据公理定理推出结论
  2. 间接证明（反证法）：假设结论不成立，推出矛盾。常用于证明"不存在""唯一性""无穷性"（如"素数有无穷多个"）
  3. 构造性证明：给出具体构造对象来证明存在性

数学归纳法（核心考点） ​

证明 ∀n∈N，P(n) 成立：

  1. 基础步：验证 P(0)（或 P(1)）成立
  2. 归纳步：假设 P(k) 成立，证明 P(k+1) 成立

归纳假设是跳板：必须用上假设才叫归纳证明。常用于：求和公式、整除性质、递推数列性质。

一一对应证明法 ​

在两个集合之间建立双射，则两集合元素个数相等。例：淘汰赛 100 名选手决出冠军需 99 场比赛 ⇔ 每场比赛淘汰 1 人 ⇔ 淘汰 99 人。

递归定义（考点） ​

递归定义包含：基础条款（直接定义最小元素）+ 归纳条款（由已有元素构造新元素）+ 极小性条款（只有上述两步得到的才是该集合的元素）。

经典递归定义实例 ​

对象基础条款归纳条款
Fibonacci 数列F0=1, F1=1Fn = F(n−1) + F(n−2)
阶乘F(1)=1F(n) = n·F(n−1)
Hanoi 塔移动次数T(1)=1T(n) = 2T(n−1)+1，解为 T(n)=2^n−1
二叉树空树是树根 + 左右子树是树

一句话总结 ​

集合是离散数学的"地基语言"，证明三大法宝是反证法、数学归纳法、一一对应；递归定义 = 基础条款 + 归纳条款，会写 Hanoi 塔的递推式是基本要求。

相关概念 ​