# Day 2｜集合与逻辑：从分类到程序推理

集合描述“对象有哪些、如何归类”，逻辑描述“条件是否成立、结论如何推出”。数据库查询、程序分支和数字电路，都建立在这些基本观念上。

## 一、集合：明确对象与范围

### 1. 元素、子集与空集

$x\in A$ 表示 x 是集合 A 的元素；$A\subseteq B$ 表示 A 的每个元素都属于 B；真子集还要求两者不相等。空集 $\varnothing$ 不含任何元素，是任意集合的子集。

**属于是“元素与集合”的关系，包含是“集合与集合”的关系。** 区分两者，才能准确表达数据分类。

### 2. 列举法、描述法与幂集

集合可以直接列举，如 $A=\{1,2,3\}$，也可以用条件描述，如 $B=\{x\in\mathbb R:x>0\}$。

幂集 $\mathcal P(A)$ 是 A 的所有子集组成的集合。若 A 有 n 个元素，则幂集有 $2^n$ 个元素：每个元素都有“选入”和“不选入”两种选择。这也是枚举所有特征子集的组合基础。

### 3. 集合的基本运算

| 运算 | 含义 | 查询直觉 |
| --- | --- | --- |
| $A\cap B$ | 同时属于 A 和 B | 两个条件都满足 |
| $A\cup B$ | 属于 A 或 B，允许同时属于 | 至少满足一个条件 |
| $A^c$ | 全集中不属于 A 的元素 | 排除符合 A 的记录 |
| $A\setminus B$ | 属于 A，但不属于 B | 保留 A，去掉 B |
| $A\triangle B$ | 只属于两者之一 | 恰好满足一个条件 |

补集必须先约定全集。韦恩图适合直观展示这些运算，代码则用条件表达式实现筛选。

## 二、命题逻辑：把判断组合起来

### 1. 且、或、非

命题是具有真值的陈述。$P\land Q$ 表示“且”，$P\lor Q$ 表示“或”，$\neg P$ 表示“非”。逻辑中的“或”通常包含两者都真的情况。

若用 0、1 表示假、真，可以写成：

$$
P\land Q=PQ,\qquad P\lor Q=P+Q-PQ,\qquad\neg P=1-P.
$$

普通加法不能直接表示 OR，否则 $1+1=2$ 会超出布尔取值。

### 2. 蕴含与等价

$P\Rightarrow Q$ 只在“P 真、Q 假”时为假，也可写作 $\neg P\lor Q$。它用于表达“满足前提就必须满足结论”的规则，不自动表示因果。

$P\Leftrightarrow Q$ 表示两者真值相同，即互相蕴含。真值表通过枚举所有输入情况，检查条件表达式是否等价。

### 3. 德摩根定律

$$
\neg(P\land Q)=(\neg P)\lor(\neg Q),
$$

$$
\neg(P\lor Q)=(\neg P)\land(\neg Q).
$$

“不是两门都通过”等价于“至少一门没有通过”。这套变换直接用于简化程序条件、数据库过滤和逻辑电路。

## 三、集合与逻辑的边界

### 1. 无穷也有不同大小

自然数集合可以逐个列举，实数集合却不可数。“都是无限多”不代表它们拥有相同基数，这是集合论超出日常分类直觉的地方。

### 2. 罗素悖论与公理化

如果允许随意构造“所有不包含自身的集合组成的集合”，就会遇到它是否包含自身的矛盾。现代公理集合论通过限制合法构造来避免这类问题；ZFC 是常见的公理体系。

### 3. 形式推理也有适用边界

哥德尔不完备性讨论的是足够表达算术、可有效公理化且一致的形式系统：这样的系统不能证明所有算术真命题。图灵机则把“按规则计算”形式化，为可计算性研究提供模型。

这些结果提醒我们：**规则可以帮助推理，也需要明确规则本身允许做什么。**