§1
离散数学研究离散的、可分立的对象：整数、命题、有限结构、图。集合提供描述这些对象的统一语言，逻辑提供从已知推出未知的规则。本章先建立集合的运算体系并证明德·摩根律，再引入幂集与笛卡尔积这两种"造新集合"的方法，然后转向命题逻辑：联结词、真值表、等值演算与量词。读完会看到集合运算与逻辑联结词其实是同一套结构的两种外衣。
一、集合及其表示
定义（集合）. 集合是若干互不相同对象的无序汇集，这些对象称为它的元素。若 $x$ 是 $A$ 的元素记 $x\in A$，否则记 $x\notin A$。常用两种表示法：列举法 $A=\{1,2,3,5,7\}$ 与描述法 $B=\{x\in\mathbb{Z}\mid 0 包含与相等. 若 $A$ 的每个元素都属于 $B$，称 $A$ 是 $B$ 的子集，记 $A\subseteq B$。$A=B$ 当且仅当 $A\subseteq B$ 且 $B\subseteq A$——这是证明集合相等的标准手法，称为"互相包含法"。空集 $\varnothing$ 是任何集合的子集。有限集 $A$ 的元素个数记 $\lvert A\rvert$，称为基数。
二、集合的基本运算
设全集为 $U$，$A,B\subseteq U$，定义并、交、差、补：
$$ \begin{align*} A\cup B&=\{x\mid x\in A\ \text{或}\ x\in B\},\\ A\cap B&=\{x\mid x\in A\ \text{且}\ x\in B\},\\ A\setminus B&=\{x\mid x\in A\ \text{且}\ x\notin B\},\\ \overline{A}&=U\setminus A=\{x\in U\mid x\notin A\}. \end{align*} $$
若 $A\cap B=\varnothing$，称两集合不相交。对有限集有两集合的容斥恒等式
$$\lvert A\cup B\rvert=\lvert A\rvert+\lvert B\rvert-\lvert A\cap B\rvert,$$
减去交集是因为重叠部分在两个加项中各被数了一次。
三、运算律与德·摩根律
| 名称 | 表达式 |
|---|---|
| 交换律 | $A\cup B=B\cup A$，$A\cap B=B\cap A$ |
| 结合律 | $(A\cup B)\cup C=A\cup(B\cup C)$ |
| 分配律 | $A\cap(B\cup C)=(A\cap B)\cup(A\cap C)$ |
| 吸收律 | $A\cup(A\cap B)=A$ |
| 双重补 | $\overline{\overline{A}}=A$ |
定理（德·摩根律）. 对任意 $A,B\subseteq U$，
$$\overline{A\cup B}=\overline{A}\cap\overline{B},\qquad \overline{A\cap B}=\overline{A}\cup\overline{B}.$$
直观地说："并的补 = 补的交"，"交的补 = 补的并"——取补会把"或"翻成"且"。这条定律在化简布尔表达式、改写循环条件、写数据库查询时反复出现。
四、幂集与笛卡尔积
幂集. $A$ 的全部子集构成的集合 $\mathcal{P}(A)=\{S\mid S\subseteq A\}$。若 $\lvert A\rvert=n$，每个元素在子集中"取或不取"有两种选择，故
$$\lvert\mathcal{P}(A)\rvert=2^{n}.$$
例如 $A=\{a,b\}$ 时 $\mathcal{P}(A)=\{\varnothing,\{a\},\{b\},\{a,b\}\}$，共 $4$ 个。
笛卡尔积. 有序对的集合
$$A\times B=\{(a,b)\mid a\in A,\ b\in B\},\qquad \lvert A\times B\rvert=\lvert A\rvert\cdot\lvert B\rvert.$$
注意 $(a,b)$ 有序，故一般 $A\times B\ne B\times A$。$n$ 重积 $A^{n}$ 是后续讨论关系、字符串、向量的基础。
五、命题与联结词
定义（命题）. 能判断真假且真假唯一的陈述句称为命题，真值记 $T$ 或 $F$。"$3>2$"是命题，"$x>2$"不是（真值随 $x$ 变），后者称为谓词。
| 记号 | 名称 | 读法 | 何时为真 |
|---|---|---|---|
| $\lnot p$ | 否定 | 非 $p$ | $p$ 为假时 |
| $p\land q$ | 合取 | $p$ 且 $q$ | 两者皆真 |
| $p\lor q$ | 析取 | $p$ 或 $q$ | 至少一真（相容或） |
| $p\to q$ | 蕴含 | 若 $p$ 则 $q$ | 仅当 $p$ 真而 $q$ 假时为假 |
| $p\leftrightarrow q$ | 等价 | $p$ 当且仅当 $q$ | 两者真值相同 |
蕴含式的"前假则真"常令初学者困惑：$p$ 为假时承诺没有被违背，故判为真，这称为空真。
六、真值表与等值式
把所有 $2^{n}$ 种赋值列尽即得真值表：
| $p$ | $q$ | $p\land q$ | $p\lor q$ | $p\to q$ | $p\leftrightarrow q$ |
|---|---|---|---|---|---|
| T | T | T | T | T | T |
| T | F | F | T | F | F |
| F | T | F | T | T | F |
| F | F | F | F | T | T |
若两公式真值表完全相同，称二者等值，记 $\equiv$。常用等值式：
$$ \begin{align*} p\to q&\equiv\lnot p\lor q,\qquad p\to q\equiv\lnot q\to\lnot p,\\ \lnot(p\land q)&\equiv\lnot p\lor\lnot q,\qquad \lnot(p\lor q)\equiv\lnot p\land\lnot q,\\ p\leftrightarrow q&\equiv(p\to q)\land(q\to p). \end{align*} $$
第二行正是逻辑版的德·摩根律。恒真的公式称重言式，恒假的称矛盾式。
七、量词
对含自由变元的谓词 $P(x)$，用量词把它闭合成命题：全称量词 $\forall x\,P(x)$ 表示论域中每个 $x$ 都使 $P(x)$ 真；存在量词 $\exists x\,P(x)$ 表示至少有一个 $x$ 使 $P(x)$ 真。否定规则为"否定穿过量词要变号"：
$$\lnot\forall x\,P(x)\equiv\exists x\,\lnot P(x),\qquad \lnot\exists x\,P(x)\equiv\forall x\,\lnot P(x).$$
多重量词的顺序不可交换：在实数域上 $\forall x\,\exists y\,(y>x)$ 为真，而 $\exists y\,\forall x\,(y>x)$ 为假（不存在最大实数）。
八、例题与解答
例题1（验证德·摩根律）
取 $U=\{1,2,3,4,5,6\}$，$A=\{1,2,3\}$，$B=\{3,4\}$，验证 $\overline{A\cup B}=\overline{A}\cap\overline{B}$，并给出一般证明。
解： 数值验证：$A\cup B=\{1,2,3,4\}$，故 $\overline{A\cup B}=\{5,6\}$。又 $\overline{A}=\{4,5,6\}$，$\overline{B}=\{1,2,5,6\}$，所以 $\overline{A}\cap\overline{B}=\{5,6\}$，两侧相同。
一般证明用互相包含法：任取 $x\in\overline{A\cup B}$，则 $x\notin A\cup B$，即 $x$ 既不属于 $A$ 也不属于 $B$，于是 $x\in\overline{A}$ 且 $x\in\overline{B}$，故 $x\in\overline{A}\cap\overline{B}$；反向每一步可逆，两集合互相包含从而相等。✓
例题2（写真值表）
判断 $(p\to q)\land(q\to r)\to(p\to r)$ 是否为重言式。
解： 该式若为假，需右侧 $p\to r$ 假，即 $p=T,\ r=F$，同时左侧两个蕴含皆真。由 $p=T$ 与 $p\to q$ 真得 $q=T$；再由 $q=T,\ r=F$ 得 $q\to r=F$，与左侧为真矛盾。故不存在使整式为假的赋值，它是重言式——这正是假言三段论的合法性证明。✓
练习
1. 设 $A=\{1,2,3,4\}$，$B=\{3,4,5\}$，求 $A\cup B$、$A\cap B$、$A\setminus B$ 与 $\lvert\mathcal{P}(A)\rvert$。
2. 写出 $\lnot(p\to q)$ 的等值化简式，并说明其含义。
3. 把"并非所有学生都通过了考试"用量词符号表示并化简。
参考答案.
1. $A\cup B=\{1,2,3,4,5\}$；$A\cap B=\{3,4\}$；$A\setminus B=\{1,2\}$；$\lvert\mathcal{P}(A)\rvert=2^{4}=16$。
2. $\lnot(p\to q)\equiv\lnot(\lnot p\lor q)\equiv p\land\lnot q$，即"若 $p$ 则 $q$"为假当且仅当前件成立而后件不成立。
3. 设 $P(x)$ 表示"学生 $x$ 通过考试"，原句为 $\lnot\forall x\,P(x)$，化简为 $\exists x\,\lnot P(x)$，即"存在某个学生没有通过"。
本章小结
- 集合用列举法或描述法表示，相等通过互相包含法证明。
- 并交差补构成完整运算体系，容斥恒等式 $\lvert A\cup B\rvert=\lvert A\rvert+\lvert B\rvert-\lvert A\cap B\rvert$。
- 德·摩根律：补运算把并翻成交、把交翻成并，逻辑中对应否定把"或"翻成"且"。
- 幂集大小 $2^{n}$，笛卡尔积大小为基数之积且有序。
- 命题逻辑五联结词由真值表定义，蕴含式仅在"前真后假"时为假。
- 量词否定要变号，多重量词顺序不可随意交换。
本章互动演示见页面底部交互图（集合 Venn 图与德·摩根律 setVenn）。
互动演示
拖动下方控件观察动态过程。