离散数学-Week4
离散数学-第4周小结
集合论基础
集合的概念与发展历史
朴素集合论（康托尔，G. Cantor）
- 从自然数与康托尔集合论出发可建立起整个数学大厦
- 集合论成为现代数学的基石
- “一切数学成果可建立在集合论基础上”这一发现使数学家们为之陶醉
罗素（Russell）悖论——第三次数学危机
- 揭示了朴素集合论的矛盾
- 推动了公理化集合论的发展
公理化集合论系统
- ZFC（策梅洛-弗兰克尔集合论）
- NBG（冯·诺依曼-博内斯-哥德尔集合论）
- 类型论
基本定义
集合与元素
- 集合：数学中最基本的概念，没有严格的定义；由确定的、彼此不同的对象结合在一起的联合体；理解为某些个体组成的整体；常用A,B,C等表示
- 元素：构成集合的对象称为该集合的元素；用a,b,c表示
- 属于关系：
- x ∈ A (x属于A)：x是A的元素
- x ∉ A (x不属于A)：x不是A的元素
集合的分类
- 无穷集：元素个数无限的集合
- 有穷集（有限集）：元素个数有限的集合；|A|表示A中元素个数
- k元集：k个元素的集合，k ≥ 0
- 可数集合/不可数集合：每个元素与”自然数集N”的某个子集某个元素之间能/不能建立一一对应的集合
集合的表示法
列举法
如 A = {a, b, c, d}, N = {0,1,2,…}
描述法
{x | P(x)} 如 N = {x | x是自然数}
说明
- 集合中的元素各不相同，如 {1,2,3} = {1,1,2,3}
- 集合中的元素没有次序，如 {1,2,3} = {3,1,2} = {1,3,1,2,2}
- 有时两种方法都适用，可根据需要选用
常用集合
- 自然数集N，整数集Z，正整数集Z⁺，有理数集Q
- 非零有理数集Q_，实数集R，非零实数集R_，复数集C
- 区间[a,b],(a,b)等
集合之间的关系
包含（子集）
设A、B为集合，如果A中的每个元素都是B中的元素，则称A为B的子集合，简称子集。这时也称A被B包含，或B包含A，记作A ⊆ B。 包含的符号化表示：A ⊆ B ⇔ ∀x(x ∈ A → x ∈ B)
不包含
如果A不被B包含，则记作A ⊈ B 不包含的符号化表示：A ⊈ B ⇔ ∃x(x ∈ A ∧ x ∉ B)
相等
设A、B为集合，如果A ⊆ B且B ⊆ A，则称A与B相等。 相等的符号化表示：A = B ⇔ A ⊆ B ∧ B ⊆ A
不相等
A ≠ B ⇔ A ⊈ B ∨ B ⊈ A
真包含（真子集）
A ⊂ B ⇔ A ⊆ B ∧ A ≠ B
示例
A = {1,2,3}, B = {x | x ∈ R ∧ |x| ≤ 1}, C = {x | x ∈ R ∧ x² = 1}, D = {-1,1}
- C ⊆ B, C ⊂ B, C ⊈ A
- A ⊈ B, B ⊈ A
- C = D
性质
- A ⊆ A （自反性）
- A ⊆ B ∧ B ⊆ C ⇒ A ⊆ C （传递性）
空集与全集
空集∅
不含任何元素的集合 示例：{x | x² < 0 ∧ x ∈ R} = ∅ 定理1.1 空集是任何集合的子集 证明：用归谬法。假设不然，则存在集合A，使得∅ ⊈ A，即存在x，x ∈ ∅且x ∉ A，矛盾。
推论
空集是惟一的 证明：假设存在∅₁和∅₂，则∅₁ ⊆ ∅₂且∅₂ ⊆ ∅₁，因此∅₁ = ∅₂
全集E
限定所讨论的集合都是E的子集
幂集
定义
幂集P(A)：A的所有子集组成的集合，即 P(A) = {x | x ⊆ A}
示例
设A = {a,b,c}
- A的0元子集：∅
- A的1元子集：{a}, {b}, {c}
- A的2元子集：{a,b}, {a,c}, {b,c}
- A的3元子集：{a,b,c}
P(A) = {∅, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}}
定理1.2 如果 |A| = n，则 |P(A)| = 2ⁿ
集合运算
并
A ∪ B = {x | x ∈ A ∨ x ∈ B}
交
A ∩ B = {x | x ∈ A ∧ x ∈ B}
相对补
A - B = {x | x ∈ A ∧ x ∉ B}
对称差
A ⊕ B = (A - B) ∪ (B - A) = (A ∪ B) - (A ∩ B)
绝对补
~A = E - A = {x | x ∉ A}
示例
设E = {0,1,…,9}, A = {0,1,2,3}, B = {1,3,5,7,9}
- A ∪ B = {0,1,2,3,5,7,9}
- A ∩ B = {1,3}
- A - B = {0,2}
- A ⊕ B = {0,2,5,7,9}
- ~A = {4,5,6,7,8,9}
- ~B = {0,2,4,6,8}
运算顺序说明
- 只使用圆括号
- 运算优先级：
- (1) 括号
- (2) ~和幂集
- (3) 其他
- 同级别的按从左到右运算
实例分析
例1：集合描述
设全集 E = {x | x 是北京某大学学生}，子集定义如下：
- A = {x | x 是北京人}
- B = {x | x 是走读生}
- C = {x | x 是数学系学生}
- D = {x | x 是喜欢听音乐的学生}
各集合特征描述：
- (A ∪ D) ∩ ~C = {x | x 是北京人或喜欢听音乐，但不是数学系学生}
- ~A ∩ B = {x | x 是外地走读生}
- (A - B) ∩ D = {x | x 是北京住校生，并且喜欢听音乐}
- ~D ∩ ~B = {x | x 是不喜欢听音乐的住校生}
例2：无限集合运算
设 Aᵢ = [0, 1/i)，Bᵢ = (0, i)，i = 1, 2, …
有限并交：
- $\bigcup_{i=1}^{n} A_i = [0, 1)$
- $\bigcap_{i=1}^{n} A_i = [0, 1/n)$
- $\bigcup_{i=1}^{n} B_i = (0, n)$
- $\bigcap_{i=1}^{n} B_i = (0, 1)$
无限并交：
- $\bigcup_{i=1}^{\infty} A_i = [0, 1)$
- $\bigcap_{i=1}^{\infty} A_i = {0}$
- $\bigcup_{i=1}^{\infty} B_i = (0, +\infty)$
- $\bigcap_{i=1}^{\infty} B_i = (0, 1)$
基本集合恒等式
- 幂等律：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 ∩ C)
- 分配律：
- A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
- A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
- 德摩根律：
- 绝对形式：~(B ∪ C) = ~B ∩ ~C，~(B ∩ C) = ~B ∪ ~C
- 相对形式：A - (B ∪ C) = (A - B) ∩ (A - C)，A - (B ∩ C) = (A - B) ∪ (A - C)
- 吸收律：A ∪ (A ∩ B) = A，A ∩ (A ∪ B) = A
- 零律：A ∪ E = E，A ∩ ∅ = ∅
- 同一律：A ∪ ∅ = A，A ∩ E = A
- 排中律：A ∪ ~A = E
- 矛盾律：A ∩ ~A = ∅
- 余补律：~∅ = E，~E = ∅
- 双重否定律：~~A = A
- 补交转换律：A - B = A ∩ ~B
- 对称差恒等式：
- 交换律：A ⊕ B = B ⊕ A
- 结合律：(A ⊕ B) ⊕ C = A ⊕ (B ⊕ C)
- 交对对称差的分配律：A ∩ (B ⊕ C) = (A ∩ B) ⊕ (A ∩ C)
- A ⊕ ∅ = A，A ⊕ E = ~A
- A ⊕ A = ∅，A ⊕ ~A = E
注意：∪ 对 ⊕ 没有分配律。 反例：- A = {a,b,c}, B = {b,c,d}, C = {c,d,e}
- A ∪ (B ⊕ C) = {a,b,c} ∪ {b,e} = {a,b,c,e}
- (A ∪ B) ⊕ (A ∪ C) = {a,b,c,d} ⊕ {a,b,c,d,e} = {e}
- 两者不等
- A ⊆ A ∪ B，B ⊆ A ∪ B
- A ∩ B ⊆ A，A ∩ B ⊆ B
- A - B ⊆ A
- A ∪ B = B ⇔ A ⊆ B ⇔ A ∩ B = A ⇔ A - B = ∅
- A ⊕ B = A ⊕ C ⇒ B = C（对称差消去律）
集合证明方法
方法一：根据定义证明
通过元素法证明集合包含或相等
方法二：利用已知集合等式
通过集合演算证明
证明示例
例3：基本恒等式证明
(1) 交换律 A ∪ B = B ∪ A
- ∀x, x ∈ A ∪ B ⇒ x ∈ A 或 x ∈ B ⇒ x ∈ B 或 x ∈ A ⇒ x ∈ B ∪ A
- 得证 A ∪ B ⊆ B ∪ A
- 同理可证 B ∪ A ⊆ A ∪ B
(2) 分配律 A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
- ∀x, x ∈ A ∪ (B ∩ C) ⇒ x ∈ A 或 (x ∈ B 且 x ∈ C)
- ⇒ (x ∈ A 或 x ∈ B) 且 (x ∈ A 或 x ∈ C)
- ⇒ x ∈ (A ∪ B) ∩ (A ∪ C)
- 得证 A ∪ (B ∩ C) ⊆ (A ∪ B) ∩ (A ∪ C)
- 类似可证反向包含
(3) 零律 A ∪ E = E
- 根据并的定义：E ⊆ A ∪ E
- 根据全集定义：A ∪ E ⊆ E
(4) 同一律 A ∩ E = A
- 根据交的定义：A ∩ E ⊆ A
- ∀x, x ∈ A ⇒ x ∈ E ⇒ x ∈ A ∩ E
- 得证 A ⊆ A ∩ E
例4：吸收律证明
A ∪ (A ∩ B) = A
证明：
- A ∪ (A ∩ B)
- = (A ∩ E) ∪ (A ∩ B) （同一律）
- = A ∩ (E ∪ B) （分配律）
- = A ∩ (B ∪ E) （交换律）
- = A ∩ E （零律）
- = A （同一律）
例5：差集恒等式证明
(A - B) - C = (A - C) - (B - C)
证明：
- (A - C) - (B - C)
- = (A ∩ ~C) ∩ ~(B ∩ ~C) （补交转换律）
- = (A ∩ ~C) ∩ (~B ∪ ~~C) （德摩根律）
- = (A ∩ ~C) ∩ (~B ∪ C) （双重否定律）
- = (A ∩ ~C ∩ ~B) ∪ (A ∩ ~C ∩ C) （分配律）
- = (A ∩ ~C ∩ ~B) ∪ (A ∩ ∅) （矛盾律）
- = A ∩ ~C ∩ ~B （零律、同一律）
- = (A ∩ ~B) ∩ ~C （交换律、结合律）
- = (A - B) - C （补交转换律）
例6：对称差恒等式证明
(A ∪ B) ⊕ (A ∪ C) = (B ⊕ C) - A
证明：
- (A ∪ B) ⊕ (A ∪ C)
- = [(A ∪ B) - (A ∪ C)] ∪ [(A ∪ C) - (A ∪ B)]
- = [(A ∪ B) ∩ ~A ∩ ~C] ∪ [(A ∪ C) ∩ ~A ∩ ~B]
- = (B ∩ ~A ∩ ~C) ∪ (C ∩ ~A ∩ ~B)
- = [(B ∩ ~C) ∪ (C ∩ ~B)] ∩ ~A
- = [(B - C) ∪ (C - B)] ∩ ~A
- = (B ⊕ C) - A
例7：幂集包含关系证明
若 A ⊆ B，则 P(A) ⊆ P(B)
证明：
- ∀x, x ∈ P(A) ⇔ x ⊆ A
- ⇒ x ⊆ B （已知 A ⊆ B）
- ⇔ x ∈ P(B)
例8：对称差等价形式证明
A ⊕ B = A ∪ B - A ∩ B
证明：
- A ⊕ B = (A ∩ ~B) ∪ (~A ∩ B)
- = (A ∪ ~A) ∩ (A ∪ B) ∩ (~B ∪ ~A) ∩ (~B ∪ B)
- = (A ∪ B) ∩ (~B ∪ ~A)
- = (A ∪ B) ∩ ~(A ∩ B)
- = A ∪ B - A ∩ B
证明方法
待证明命题的形式
三种基本形式
- 形式1：若A，则B （A → B）
- 形式2：A当且仅当B （A ↔ B）
- 形式3：证明B （B） 说明：形式2和形式3都可归结为形式1
直接证明法
做法
假设A为真，证明B为真
例1：奇数的平方仍是奇数
命题：若n是奇数，则n²也是奇数
证明：
假设n是奇数，则存在k ∈ N，使得n = 2k + 1
于是：
n2=(2k+1)2=4k2+4k+1=2(2k2+2k)+1n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1n2=(2k+1)2=4k2+4k+1=2(2k2+2k)+1
得证n²是奇数
间接证明法
做法
证明”若B不成立，则A不成立”，即证明 ¬B → ¬A
例2：平方为奇数则原数为奇数
命题：若n²是奇数，则n也是奇数
证明：
用间接证明法，只要证：若n是偶数，则n²也是偶数
假设n是偶数，则存在k ∈ N，使得n = 2k
于是：
n2=(2k)2=4k2=2(2k2)n^2 = (2k)^2 = 4k^2 = 2(2k^2)n2=(2k)2=4k2=2(2k2)
得证n²是偶数
归谬法（反证法）
做法
设A成立，假设B不成立，推出矛盾
例3：集合等式证明
命题：若A - B = A，则A ∩ B = ∅
证明：
用归谬法，假设A ∩ B ≠ ∅，则存在x，使得
x ∈ A ∩ B ⇔ x ∈ A 且 x ∈ B
⇒ x ∈ A - B 且 x ∈ B （因为A - B = A）
⇔ (x ∈ A 且 x ∉ B) 且 x ∈ B
⇒ x ∉ B 且 x ∈ B，矛盾
例4：证明√2是无理数
证明：
假设√2是有理数，存在正整数n, m，使得√2 = m/n
不妨设m/n为既约分数。于是m = n√2，m² = 2n²
m²是偶数，从而m是偶数。设m = 2k，得：
(2k)2=2n2⇒n2=2k2(2k)^2 = 2n^2 \Rightarrow n^2 = 2k^2(2k)2=2n2⇒n2=2k2
这又得到n也是偶数，与m/n为既约分数矛盾
注：间接证明法是归谬法的特殊形式：由B不成立推出A不成立，与前提A成立矛盾
穷举法（分情况证明法）
适用情况
待证明的命题形式为 A = A₁ ∨ A₂ ∨ … ∨ Aₖ → B
做法
证明A₁ → B, A₂ → B, …, Aₖ → B 均为真
例5：最大值结合律
命题：max(a, max(b,c)) = max(max(a,b),c)
证明：
通过分情况讨论a, b, c的大小关系，验证所有情况下等式成立
举反例——证明命题为假
例6：集合命题的反例
命题：若A ∩ B = A ∩ C，则B = C
证明：
反例：取A = {a,b}, B = {a,b,c}, C = {a,b,d}
有A ∩ B = A ∩ C = {a,b}
但B ≠ C，故命题不成立
构造性证明法
做法
在A为真的条件下，构造出具有这种性质的客体
例7：连续合数存在性
命题：对于每个正整数n，存在n个连续的正合数
证明：
令x = (n + 1)!
则x + 2, x + 3, …, x + n + 1是n个连续的正合数：
i | x + i, i = 2, 3, …, n + 1
非构造性证明
特点
- 证明过程中不举例而只证明语句是否正确
- 强调证明存在性，但不一定提供构造方法
- 通常使用反证法或归谬法等技巧
- 可能告诉我们某个对象存在，但不告诉我们如何构造
与构造性证明的区别
- 构造性证明：强调建设性和实际构造
- 非构造性证明：侧重于逻辑推理和存在性证明
例8：素数无限性
命题：对于每个正整数n，存在大于n的素数
证明：
令x等于所有小于等于n的素数的乘积加1
则x不能被所有小于等于n的素数整除
于是，x或者是素数，或者能被大于n的素数整除
因此，存在大于n的素数