离散数学入门教程——集合论与逻辑

概述

离散数学是计算机科学和数学的重要基础课程，它研究的是离散的数学结构，而非连续的实数系统。与微积分研究连续变化不同，离散数学关注的是可以被"数出来"的对象——整数、集合、逻辑命题、图、树等。这些概念在计算机科学中有着极其广泛的应用：数据库设计依赖关系理论，程序验证依赖逻辑推理，网络路由依赖图论算法，编译器设计依赖形式语言。

本教程将系统讲解离散数学的五大核心模块：集合论、命题逻辑、谓词逻辑、关系与函数、图论基础。每个知识点都配有典型例题和详细解析，帮助你建立扎实的离散数学基础。

---

一、集合论基础

1.1 集合的概念与表示

集合是离散数学中最基本的概念。集合是由确定的、互不相同的对象组成的一个整体，这些对象称为集合的元素。我们通常用大写字母表示集合（如 A、B、C），用小写字母表示元素（如 a、b、c）。

集合的表示方法有两种：

枚举法：将集合中的元素一一列出，用花括号括起来。

• 例：A = {1, 2, 3, 4, 5} 表示由1到5这五个自然数组成的集合。
• 例：B = {a, e, i, o, u} 表示英语中的五个元音字母。

描述法：用一个性质来描述集合中的元素。

• 例：C = {x | x 是正偶数} = {2, 4, 6, 8, ...}
• 例：D = {x | x² - 5x + 6 = 0} = {2, 3}

元素与集合的关系用 ∈（属于）和 ∉（不属于）表示。若 a 是集合 A 的元素，记作 a ∈ A；否则记作 a ∉ A。

1.2 集合间的关系

子集：若集合 A 中的每个元素都是集合 B 的元素，则称 A 是 B 的子集，记作 A ⊆ B。注意，任何集合都是它自身的子集。

真子集：若 A ⊆ B 且 A ≠ B，则称 A 是 B 的真子集，记作 A ⊂ B。

集合相等：若 A ⊆ B 且 B ⊆ B，则 A = B。

例题：设 A = {1, 2}，B = {1, 2, 3}，判断 A 与 B 的关系。

解：因为 A 中的每个元素（1和2）都在 B 中，所以 A ⊆ B。又因为 B 中有元素3不在 A 中，所以 A ≠ B，因此 A ⊂ B（A 是 B 的真子集）。

1.3 集合运算

集合之间有以下基本运算：

运算	符号	定义
并集	A ∪ B	属于 A 或属于 B 的所有元素
交集	A ∩ B	同时属于 A 和 B 的所有元素
差集	A - B	属于 A 但不属于 B 的所有元素
补集	Ā	全集 U 中不属于 A 的所有元素
对称差	A ⊕ B	属于 A 或属于 B 但不同时属于两者的元素

例题：设全集 U = {1, 2, 3, 4, 5, 6, 7, 8}，A = {1, 2, 3, 4}，B = {3, 4, 5, 6}，求 A ∪ B，A ∩ B，A - B，A ⊕ B。

解：

• A ∪ B = {1, 2, 3, 4, 5, 6}
• A ∩ B = {3, 4}
• A - B = {1, 2}
• A ⊕ B = (A - B) ∪ (B - A) = {1, 2} ∪ {5, 6} = {1, 2, 5, 6}

1.4 集合运算的定律

集合运算满足以下重要定律：

• 交换律：A ∪ B = B ∪ A，A ∩ B = B ∩ A
• 结合律：(A ∪ B) ∪ C = A ∪ (B ∪ C)
• 分配律：A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
• 德摩根律：\(\overline{A ∪ B} = \overline{A} ∩ \overline{B}\)，\(\overline{A ∩ B} = \overline{A} ∪ \overline{B}\)

德摩根律在逻辑推理和电路设计中有重要应用，它告诉我们"取并集再取补"等于"先取补再取交集"。

1.5 幂集

集合 A 的幂集是 A 的所有子集组成的集合，记作 P(A) 或 2^A。若 |A| = n（A 有 n 个元素），则 |P(A)| = 2ⁿ。

例题：求 A = {a, b, c} 的幂集。

解：P(A) = {∅, , , , {a,b}, {a,c}, {b,c}, {a,b,c}}，共 2³ = 8 个元素。

---

二、命题逻辑

2.1 命题与逻辑联结词

命题是一个能够判断真假的陈述句。命题只有两种取值：真（T 或 1）和假（F 或 0）。

例如："北京是中国的首都"是真命题；"2 > 5"是假命题；"x > 3"不是命题（因为 x 不确定）。

基本逻辑联结词有五个：

联结词	符号	含义	读法
否定	¬p	p 的否定	"非p"
合取	p ∧ q	p 且 q	"p与q"
析取	p ∨ q	p 或 q	"p或q"
蕴涵	p → q	若 p 则 q	"如果p那么q"
等价	p ↔ q	p 当且仅当 q	"p当且仅当q"

关键理解：蕴涵式 p → q 只在"p 真 q 假"时为假，其余情况均为真。这与日常语言中的"如果...那么..."略有不同，要注意区分。

2.2 真值表

真值表是判断复合命题真值的基本工具。

例题：构造 (p → q) ↔ (¬q → ¬p) 的真值表。

解：

p	q	¬p	¬q	p→q	¬q→¬p	(p→q)↔(¬q→¬p)
T	T	F	F	T	T	T
T	F	F	T	F	F	T
F	T	T	F	T	T	T
F	F	T	T	T	T	T

最后一列全为 T，说明 (p → q) ↔ (¬q → ¬p) 是永真式（重言式）。这个等价关系就是逻辑学中著名的逆否命题等价——原命题与其逆否命题等价。

2.3 逻辑等价与推理

常见的逻辑等价公式：

• 双重否定律：¬¬p ≡ p
• 德摩根律：¬(p ∧ q) ≡ ¬p ∨ ¬q；¬(p ∨ q) ≡ ¬p ∧ ¬q
• 条件等价：p → q ≡ ¬p ∨ q
• 吸收律：p ∨ (p ∧ q) ≡ p

推理规则：

• 假言推理（Modus Ponens）：从 p 和 p → q 可推出 q。
• 拒取式（Modus Tollens）：从 ¬q 和 p → q 可推出 ¬p。
• 析取三段论：从 p ∨ q 和 ¬p 可推出 q。

例题：已知"如果下雨，地面就会湿"和"地面没有湿"，能推出什么？

解：设 p = "下雨"，q = "地面湿"。已知 p → q 和 ¬q。由拒取式可推出 ¬p，即"没有下雨"。

---

三、谓词逻辑

3.1 谓词与量词

命题逻辑无法表达"所有的人都是 mortal"这类涉及量化的语句。谓词逻辑通过引入谓词和量词来解决这个问题。

谓词是含有变量的语句，记作 P(x)。例如 P(x)："x 是素数"。当 x 取具体值时，P(x) 就变成了命题。

全称量词 ∀：表示"对所有"。∀x P(x) 表示"对所有 x，P(x) 为真"。 存在量词 ∃：表示"存在某个"。∃x P(x) 表示"存在某个 x，使 P(x) 为真"。

例题：用谓词逻辑表示以下语句：

1. 所有的猫都是动物。
2. 某些学生喜欢数学。

解：

1. 设 C(x)："x 是猫"，A(x)："x 是动物"。则 ∀x(C(x) → A(x))。
2. 设 S(x)："x 是学生"，L(x)："x 喜欢数学"。则 ∃x(S(x) ∧ L(x))。

注意：全称量词用 →（蕴涵），存在量词用 ∧（合取）。这是初学者最容易混淆的地方。

3.2 量词的否定

量词的否定遵循以下规则：

• ¬(∀x P(x)) ≡ ∃x ¬P(x) ——"并非所有x都满足P"等价于"存在某个x不满足P"
• ¬(∃x P(x)) ≡ ∀x ¬P(x) ——"不存在x满足P"等价于"所有x都不满足P"

这是德摩根律在谓词逻辑中的推广。

3.3 多重量词

当多个量词同时出现时，顺序非常重要：

• ∀x∃y P(x, y)：对每个 x，都存在某个 y 使得 P(x, y) 成立。
• ∃y∀x P(x, y)：存在某个 y，使得对所有 x 都有 P(x, y) 成立。

一般而言，∃y∀x P(x, y) ⇒ ∀x∃y P(x, y)，但反过来不成立。

例题：设论域为实数，P(x, y)："x + y = 0"。

• ∀x∃y P(x, y)：对任意实数 x，都存在实数 y 使 x + y = 0。这为真（取 y = -x）。
• ∃y∀x P(x, y)：存在实数 y，使得对所有实数 x 都有 x + y = 0。这为假（没有一个固定的 y 能满足所有 x）。

---

四、关系与函数

4.1 二元关系

设 A 和 B 是两个集合，从 A 到 B 的二元关系 R 是 A × B 的子集。若 (a, b) ∈ R，记作 aRb。

例题：设 A = {1, 2, 3}，定义关系 R = {(a, b) | a 整除 b}。写出 R 的所有元素。

解：R = {(1,1), (1,2), (1,3), (2,2), (3,3)}。

4.2 关系的性质

设 R 是集合 A 上的关系：

性质	定义	示例
自反性	∀a∈A, (a,a)∈R	"≤" 在实数上是自反的
对称性	(a,b)∈R → (b,a)∈R	"同学关系"是对称的
反对称性	(a,b)∈R 且 (b,a)∈R → a=b	"≤" 是反对称的
传递性	(a,b)∈R 且 (b,c)∈R → (a,c)∈R	"<" 是传递的

同时满足自反、对称、传递的关系称为等价关系。等价关系将集合划分为若干个等价类。

4.3 函数

函数是一种特殊的关系。从 A 到 B 的函数 f 是一个从 A 到 B 的关系，满足 A 中每个元素恰好对应 B 中的一个元素。

函数的分类：

• 单射（一对一）：不同的自变量对应不同的函数值，即 f(a) = f(b) → a = b。
• 满射（映上）：B 中每个元素都是某个 A 中元素的函数值。
• 双射：既是单射又是满射，此时存在反函数 f⁻¹。

例题：判断 f: Z → Z，f(x) = 2x + 1 是否为单射、满射、双射。

解：

• 单射：若 f(a) = f(b)，则 2a + 1 = 2b + 1，得 a = b。是单射。
• 满射：对任意 y ∈ Z，需要存在 x ∈ Z 使 2x + 1 = y，即 x = (y-1)/2。当 y 为偶数时，x 不是整数。不是满射。
• 结论：f 是单射但不是满射，因此不是双射。

---

五、图论基础

5.1 图的基本概念

图 G = (V, E) 由顶点集 V 和边集 E 组成。每条边连接两个顶点。

图的分类：

• 无向图：边没有方向，(u, v) = (v, u)。
• 有向图：边有方向，(u, v) ≠ (v, u)。
• 简单图：没有自环和重边的图。
• 完全图：任意两个不同顶点之间都有边的图，记作 Kₙ。

度：顶点 v 的度 deg(v) 是与 v 相关联的边的数目。在有向图中，分为入度和出度。

握手定理：在无向图中，所有顶点的度之和等于边数的两倍：∑deg(v) = 2|E|。推论：度为奇数的顶点个数为偶数。

5.2 路径与连通性

路径是从一个顶点到另一个顶点经过的边的序列。简单路径是不重复经过顶点的路径。

连通图：任意两个顶点之间都存在路径的图。连通分量：无向图的最大连通子图。

欧拉路径：经过图中每条边恰好一次的路径。欧拉回路：起点和终点相同的欧拉路径。

判定定理：

• 无向图存在欧拉回路 ⟺ 所有顶点的度都是偶数。
• 无向图存在欧拉路径（但不是回路）⟺ 恰好有两个顶点的度是奇数。

例题：判断以下图是否存在欧拉回路：K₄（4个顶点的完全图）。

解：K₄ 中每个顶点的度都是 3（奇数），因此不存在欧拉回路。

5.3 树

树是无回路的连通图。树的等价定义（以下条件等价）：

• G 是连通的且无回路
• G 中任意两个顶点之间有且仅有一条简单路径
• G 连通且 |E| = |V| - 1
• G 无回路且 |E| = |V| - 1

生成树：包含图 G 所有顶点的子树。

二叉树：每个顶点最多有两个子节点的树，在计算机科学中用于搜索、排序等操作。

例题：一棵有 100 个顶点的树有多少条边？

解：由树的性质 |E| = |V| - 1 = 100 - 1 = 99 条边。

---

练习题

题目一

设 A = {1, 2, 3, 4, 5}，B = {2, 4, 6, 8}，C = {1, 3, 5, 7}。求 (A ∩ B) ∪ C。

答案：A ∩ B = {2, 4}，所以 (A ∩ B) ∪ C = {2, 4} ∪ {1, 3, 5, 7} = {1, 2, 3, 4, 5, 7}。

题目二

构造真值表判断 (p ∧ (p → q)) → q 是否为重言式。

答案：

p	q	p→q	p∧(p→q)	(p∧(p→q))→q
T	T	T	T	T
T	F	F	F	T
F	T	T	F	T
F	F	T	F	T

最后一列全为 T，因此 (p ∧ (p → q)) → q 是重言式。这其实就是假言推理的逻辑形式化。

题目三

用谓词逻辑表示语句"每个学生都读过至少一本小说"，并写出其否定的等价形式。

答案： 设 S(x)："x 是学生"，N(y)："y 是小说"，R(x, y)："x 读过 y"。 原命题：∀x(S(x) → ∃y(N(y) ∧ R(x, y)))。 否定：∃x(S(x) ∧ ∀y(N(y) → ¬R(x, y)))。 含义：存在某个学生，他没有读过任何小说。

题目四

设 A = {a, b, c}，R = {(a,a), (b,b), (c,c), (a,b), (b,a)}。判断 R 是否具有自反性、对称性、传递性。

答案：

• 自反性：(a,a), (b,b), (c,c) 都在 R 中，满足自反性。
• 对称性：(a,b) ∈ R 且 (b,a) ∈ R，其他元素对的对称性显然成立，满足对称性。
• 传递性：(a,b) ∈ R 且 (b,a) ∈ R，需要 (a,a) ∈ R，成立。(b,a) ∈ R 且 (a,b) ∈ R，需要 (b,b) ∈ R，成立。满足传递性。 结论：R 是等价关系。

题目五

一棵二叉树有 50 个叶子节点，如果它是满二叉树（每个非叶节点恰好有两个子节点），那么它有多少个非叶节点？总共有多少个节点？

答案： 在满二叉树中，叶子数 L = 非叶节点数 I + 1（这是满二叉树的性质）。 因此 I = L - 1 = 50 - 1 = 49。 总节点数 = L + I = 50 + 49 = 99。

---

总结

离散数学是计算机科学的数学基石。本教程涵盖了五大核心模块：

1. 集合论：集合的表示、运算和幂集，是整个离散数学的语言基础。
2. 命题逻辑：用真值表分析复合命题，掌握逻辑等价和推理规则。
3. 谓词逻辑：引入量词表达更复杂的语句，理解量词否定的德摩根律。
4. 关系与函数：理解关系的性质（自反、对称、传递、反对称），掌握函数的分类。
5. 图论：图的基本概念、连通性、欧拉路径、树的性质。

学习离散数学的关键在于多做练习。每个概念都需要通过大量例题来加深理解。建议学完每个知识点后，立即完成对应的练习题，检验自己的掌握程度。离散数学的思维方式——严谨的逻辑推理、集合化思考、图的建模能力——将伴随你整个计算机科学学习生涯。