Chap1 集合论课程引言、预备知识与集合基本概念

返回：0100 离散数学课程总目录 · 下一章：0102 关系、有序对、闭包、等价关系与序关系

1、资料来源与学习目标

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

资料	内容
1.1 集合论与图论课程引言	课程范围、集合论和图论的研究对象
1.2 预备知识：命题逻辑	命题公式、赋值、等值式、推理定律
1.3 预备知识：一阶谓词逻辑	个体、谓词、量词、解释、前束范式
1.4 集合的概念和集合之间的关系	集合、子集、相等、真子集、空集、全集、幂集、集族、多重集
1.5 集合的运算	并、交、差、对称差、补、广义并、广义交、容斥原理
1.6 基本的集合恒等式	13 组基本集合恒等式、半形式化证明方法
001 习题与答案	补充题、习题 1.3、1.10、1.16、1.13、1.14、1.20

本章的核心目标：把“逻辑语言”和“集合语言”接起来。后面关系、函数、自然数、基数、图论都要用这一章的符号系统来表达。

2、颜色标注

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

3、章节主线

模块	本章要会什么	后续连接
课程引言	知道集合论研究集合、关系、函数、自然数、基数；图论研究顶点和边构成的模型	Chap 2-13 的总地图
命题逻辑	会用真值表、等值式、推理定律判断公式真假和推理正确性	集合恒等式证明
一阶谓词逻辑	会用个体域、谓词、量词把自然语言命题符号化	集合定义、关系定义、函数定义
集合基本概念	分清元素、集合、子集、真子集、空集、全集、幂集、集族、多重集	关系、函数、图的基础
集合运算	熟练写出并、交、差、对称差、补、广义并、广义交的描述法	集合演算、证明题
集合恒等式	记住 13 组基本恒等式，会写半形式化证明	习题和后续证明题

4、课程引言：集合论和图论解决什么问题

集合论的研究对象是集合、关系、函数、自然数、基数、序数。它的思想是：以逻辑为基础，以集合为工具，表示和构造各种数学对象。

图论的研究对象是由顶点和边构成的图。它的思想是：以集合论为基础，以图为工具，为各种二元关系建立模型。

第一章不是单纯背定义，而是在准备一种表达语言。集合语言负责“对象属于哪里”，逻辑语言负责“命题在什么条件下为真”。

典型问题：

如何给集合下定义？
如何用集合定义关系、函数、自然数？
如何比较集合的大小？
什么是图，图能表示哪些连接关系？
什么是欧拉图、哈密顿图、树、平面图、着色、匹配？

5、逻辑预备知识

5.1 命题逻辑

概念	说明
原子命题	不能再分解的简单命题，常用 `p,q,r,...` 表示
真值	`1` 表示真，`0` 表示假
联结词	`¬` 否定，`∧` 合取，`∨` 析取，`→` 蕴涵，`↔` 等价
命题公式	由命题变元和联结词按有限次规则形成的符号串
赋值	给公式中每个命题变元指定 `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)`
德摩根律	`¬(A∨B) ⇔ ¬A∧¬B`，`¬(A∧B) ⇔ ¬A∨¬B`
吸收律	`A∨(A∧B) ⇔ A`，`A∧(A∨B) ⇔ A`
零律	`A∨1 ⇔ 1`，`A∧0 ⇔ 0`
同一律	`A∨0 ⇔ A`，`A∧1 ⇔ A`
排中律	`A∨¬A ⇔ 1`
矛盾律	`A∧¬A ⇔ 0`
双重否定律	`¬¬A ⇔ A`
蕴涵等值式	`A→B ⇔ ¬A∨B`
假言易位	`A→B ⇔ ¬B→¬A`

5.2 一阶谓词逻辑

概念	说明
个体	可以独立存在的客体，具体事物或抽象概念都可以
个体域	个体变元的取值范围，可以有限也可以无限
谓词	表示个体性质或个体之间关系的词，如 `F(x)`、`H(x,y)`
全称量词	`∀x`，表示所有、任意、每一个
存在量词	`∃x`，表示存在、至少有一个、有的
辖域	量词控制的公式范围
约束出现	在量词辖域中被量词绑定的变元出现
自由出现	没有被相应量词绑定的变元出现
解释	指定个体域、常元、函数、谓词之后，公式获得具体含义

自然语言符号化的两个基本模板：

所有有性质 F 的个体都有性质 G：
∀x(F(x)→G(x))

存在有性质 F 同时有性质 G 的个体：
∃x(F(x)∧G(x))

全称命题常用 →，存在命题常用 ∧。比如“人都吃饭”是 ∀x(人(x)→吃饭(x))，不是 ∀x(人(x)∧吃饭(x))。

量词等值式：

类型	公式
有限域消去量词	`∀xA(x) ⇔ A(a1)∧...∧A(an)`，`∃xA(x) ⇔ A(a1)∨...∨A(an)`
量词否定	`¬∀xA(x) ⇔ ∃x¬A(x)`，`¬∃xA(x) ⇔ ∀x¬A(x)`
全称分配	`∀x(A(x)∧B(x)) ⇔ ∀xA(x)∧∀xB(x)`
存在分配	`∃x(A(x)∨B(x)) ⇔ ∃xA(x)∨∃xB(x)`

注意：∀ 对 ∨ 一般不能分配，∃ 对 ∧ 一般不能分配。

前束范式是形如：

1	Q1x1 Q2x2 ... Qkxk B

其中 Qi 是 ∀ 或 ∃，B 中不含量词。求前束范式时，常用量词否定、辖域扩张/收缩和换名规则。

6、集合基本概念

在朴素集合论中，集合被当作基本概念使用，不能再用更基础的概念精确定义。

概念	定义	易错点
集合	通常用大写字母 `A,B,C,...` 表示	集合中的元素互不相同，且不规定顺序
元素	若 `a` 是 `A` 的元素，记作 `a∈A`	`∈` 描述元素和集合的关系
列举法	`A={a,b,c,d}`	只适合能清楚列出的集合
描述法	`{x	P(x)}`
子集	`B⊆A ⇔ ∀x(x∈B→x∈A)`	`⊆` 描述两个集合之间的关系
集合相等	`A=B ⇔ ∀x(x∈A↔x∈B)`	证明集合相等通常证双向包含
真子集	`A⊂B ⇔ A⊆B ∧ A≠B`	真子集要求不能相等
空集	不拥有任何元素的集合，记作 `∅`	`∅` 是集合，不是“什么都没有的符号”
全集	当前讨论范围内包含所有对象的集合，记作 `E`	全集是相对的，不唯一
幂集	`P(A)={x	x⊆A}`
集族	以集合为元素的集合	幂集是典型集族
多重集	允许元素重复出现的集合模型	普通集合可看作重复度不超过 1 的多重集

必记结论：

结论	说明
空集是一切集合的子集	对任意集合 `A`，都有 `∅⊆A`
空集唯一	任意两个空集互相包含，因此相等
集合相等要证双向包含	`A=B` 可证 `A⊆B` 且 `B⊆A`
幂集大小	若 `

最容易错的是 ∈ 和 ⊆ 的层级。∅⊆A 对任意集合都成立；但 ∅∈A 只有在 A 的元素里真的包含空集时才成立。

7、集合运算

运算	表达	含义
并集	`A∪B={x	x∈A∨x∈B}`
交集	`A∩B={x	x∈A∧x∈B}`
不相交	`A∩B=∅`	两个集合没有公共元素
相对补集	`A-B={x	x∈A∧x∉B}`
对称差	`A⊕B=(A-B)∪(B-A)`	只属于其中一个集合
绝对补集	`~A={x	x∈E∧x∉A}`
广义并	`∪A={x	∃z(x∈z∧z∈A)}`
广义交	`∩A={x	∀z(z∈A→x∈z)}`

边界：当 A=∅ 时，∪A=∅，但 ∩A 无意义。

集合运算优先级：

第一类：绝对补、幂集、广义交、广义并，按从右到左。
第二类：初级并、初级交、相对补、对称差，按括号；无括号时从左到右。

8、集合恒等式与证明方法

设 E 是全集，A,B,C 为 E 的任意子集。

名称	公式
幂等律	`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)`
德摩根律	`~(A∪B)=~A∩~B`，`~(A∩B)=~A∪~B`
吸收律	`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`

集合恒等式的证明套路：任取元素 x，把 x∈集合表达式 翻译成命题逻辑表达式，然后用命题逻辑等值式化简。

例如证明分配律：

x∈A∪(B∩C)
⇔ x∈A ∨ x∈(B∩C)
⇔ x∈A ∨ (x∈B ∧ x∈C)
⇔ (x∈A∨x∈B) ∧ (x∈A∨x∈C)
⇔ x∈(A∪B) ∧ x∈(A∪C)
⇔ x∈(A∪B)∩(A∪C)

所以 A∪(B∩C)=(A∪B)∩(A∪C)。

9、习题与答案

补充题 1：用真值表证明德摩根律

以 ¬(p∧q) ⇔ ¬p∨¬q 为例：

p	q	`¬(p∧q)`	`¬p∨¬q`
0	0	1	1
0	1	1	1
1	0	1	1
1	1	0	0

两列真值完全相同，所以 ¬(p∧q) ⇔ ¬p∨¬q。同理可证 ¬(p∨q) ⇔ ¬p∧¬q。

补充题 2：命题符号化并求前束范式

题目：“有些乌龟比有些兔子跑得快。”

用全总个体域，令：

符号	含义
`F(x)`	`x` 是乌龟
`G(y)`	`y` 是兔子
`H(x,y)`	`x` 比 `y` 跑得快

答案：

1 2	∃x(F(x)∧∃y(G(y)∧H(x,y))) ⇔ ∃x∃y(F(x)∧G(y)∧H(x,y))

最终前束范式是：

1	∃x∃y(F(x)∧G(y)∧H(x,y))

补充题 3：给出解释，使左端为假，右端为真

题目：

1	∀x(A(x)→B(x)) ⇒ ∃xA(x)→∃xB(x)

答案不唯一。取个体域为自然数集，令：

1 2	A(x)：x 是偶数 B(x)：x 是奇数

此时 ∀x(A(x)→B(x)) 为假，因为偶数不一定是奇数；而 ∃xA(x)→∃xB(x) 为真，因为自然数集中既存在偶数，也存在奇数。

习题 1.3：判断包含关系和属于关系

答案页给出的正确项为：

1	(1), (4), (5), (6), (8), (9)

复盘重点：

∅⊆∅ 正确，空集是一切集合的子集。
∅∈∅ 错误，因为空集没有任何元素。
∅∈{∅} 正确，因为 {∅} 的唯一元素就是 ∅。
∅⊆{∅} 正确，因为空集是一切集合的子集。
{∅}∈{∅} 错误，右边唯一元素是 ∅，不是 {∅}。
{a,b}⊂{a,b,{a,b}} 正确，右边比左边多一个元素 {a,b}。

判断这种题时先问一句：左边整体是“元素”还是“集合”？∈ 要求左边作为一个元素出现在右边；⊆/⊂ 要求左边每个元素都属于右边。

习题 1.10：设 `A={a}`，判断关系

先算：

1 2	P(A) = {∅,{a}} PP(A) = P(P(A)) = {∅,{∅},{{a}},{∅,{a}}}

正确项为：

1	(1), (2), (4), (5)

关键解释：

{∅}∈PP(A) 正确，因为 {∅} 是 PP(A) 的一个元素。
{∅}⊆PP(A) 正确，因为 ∅∈PP(A)。
{∅,{∅}}∈PP(A) 错误，因为它不是 P(A) 的子集。
{∅,{∅}}⊆PP(A) 正确，因为 ∅ 和 {∅} 都属于 PP(A)。
{∅,{a}}∈PP(A) 正确，因为 {∅,{a}}=P(A)，而 P(A)∈P(P(A))。
{∅,{a}}⊆PP(A) 错误，因为 {a} 不是 PP(A) 的元素。

习题 1.16：化简集合

题目：

1
2
3

(1) ∪{{3,4},{{3},{4}},{3,{4}},{{3},4}}
(2) ∩{PPP(∅),PP(∅),P(∅),∅}
(3) ∪{PPP{∅},PP{∅},P{∅}}

答案：

小题	结果
(1)	`{3,4,{3},{4}}`
(2)	`∅`
(3)	`{∅,{∅}}`

其中 (2) 的原因是参与广义交的集族中有 ∅，公共元素为空。

习题 1.13：证明包含式并判断等号成立条件

题目：设 A,B,C 为任意三个集合：

证明 (A-B)-C ⊆ A-(B-C)。
在什么条件下等号成立？

证明：

左 = (A-B)-C
   = (A∩~B)∩~C
   ⊆ A∩~B
   = A-B

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

因为左边 (A-B)-C 是 (A-B) 去掉 C 后的部分，而右边包含整个 (A-B)，所以：

1	(A-B)-C ⊆ A-(B-C)

等号成立的充要条件是：

A∩C = ∅

理由：

1 2	(A-B)-C = (A-B)∩(A-C) A-(B-C) = (A-B)∪(A∩C)

若 A∩C=∅，右边不会额外多出 A∩C；同时 A-C=A，左边也回到 A-B。所以两边相等。

习题 1.14：由交集条件证明集合相等

题目：设 A,B,C 为任意集合，已知：

1 2	A∩B = A∩C ~A∩B = ~A∩C

证明 B=C。

答案：

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

理解：A 和 ~A 把全集切成两块。已知 B 和 C 在这两块里的交集都一样，所以整体也一样。

习题 1.20：由两部分包含推出整体包含

题目：设 A,B,C 为三个集合，已知：

1 2	A∩C ⊆ B∩C A∩~C ⊆ B∩~C

证明 A⊆B。

答案：

A = A∩E
  = A∩(C∪~C)
  = (A∩C)∪(A∩~C)
  ⊆ (B∩C)∪(B∩~C)
  = B∩(C∪~C)
  = B∩E
  = B

所以 A⊆B。

10、复盘清单

看到 ∈、⊆、⊂，先判断两边的层级：元素、集合，还是集族。
证明集合相等，优先考虑双向包含、元素任取法或全集分块法。
化简差集，优先改写成 A-B=A∩~B。
证明集合恒等式，可以把 x∈集合表达式 翻译成命题逻辑表达式。
做量词题时先定个体域，再写谓词，再选 ∀ 或 ∃。
全称命题常配 →，存在命题常配 ∧。
广义交遇到空集族时要小心：∩∅ 无意义；但若集族中包含空集，则交集是 ∅。

11、下一步

第二章进入关系、有序对、笛卡尔积和二元关系。复习第一章时，最好先把 集合 = 对象容器、谓词 = 对象性质/关系、逻辑 = 判断真假 这三层分清楚，再进入关系的性质和闭包。