离散数学（一）：数理逻辑与集合论

由于计算机中的数据都以离散量的形式存储，处于对研究数据结构和算法的需要，离散数学成为了计算机科学必备的前置科目。离散数学是一门证明较多，实用性较强的学科，因此概念和定理也非常繁杂。

离散量：逻辑量，图，树，整数，布尔代数等
连续量：温度，压力，体积，电压等

命题逻辑

命题逻辑与联结词

所谓命题（proposition），是指一句有真假意义的话。我们用大写的英文字母 $P,Q,R,\cdots$，代表一个抽象的命题，称为命题符号。

如果一个命题为真，则称其真值为1，也用“1”代表一个抽象的真命题；如果一个命题为假，则称其真值为0，也用“0”代表一个抽象的假命题。

命题“$P$ 是不对的”称为 $P$ 的否定，记作 $\neg P$，读作非 $P$.
真值规定：$\neg P$ 为真 $\iff$ $P$ 为假。

命题“$P$ 或者 $Q$”称为 $P,Q$ 的析取（disjunctive），记作 $P\vee Q$，读作 $P$ 或 $Q$.
真值规定：$P\vee Q$ 为真 $\iff$ $P,Q$ 中至少有一个为真。

命题“$P$ 并且 $Q$”称为 $P,Q$ 的合取（conjunction），记作 $P\wedge Q$，读作 $P$ 且 $Q$.
真值规定：$P\wedge Q$ 为真 $\iff$ $P,Q$ 都为真。

自然语言中“或”有两种含义——表示两者可以同时成立，称为可兼或；表示二者只能居其一，不会同时成立，称为不可兼或，或异或（exclusive or），可以表示为：

$$(P\wedge\neg Q)\vee(\neg P\wedge Q)$$

命题“如果 $P$，则 $Q$”称为 $P$ 蕴涵 $Q$（$P$ implies $Q$），记作 $P\rightarrow Q$.
真值规定：$P\rightarrow Q$ 为假 $\iff$ $P$ 为真而 $Q$ 为假。

命题“$P$ 当且仅当 $Q$”称为 $P$ 等价 $Q$（$P$ is equivalent to $Q$），记作 $P\leftrightarrow Q$.
真值规定：$P\leftrightarrow Q$ 为真 $\iff$ $P,Q$ 都为真或都为假。

联结词的运算优先级（从高到低）： $\neg,\wedge,\vee,\rightarrow,\leftrightarrow$

命题公式

设 $G$ 是命题公式，$A_1,\cdots,A_n$ 是出现在 $G$ 中的所有原子（atom），指定 $A_1,\cdots,A_n$ 的一组真值，则称这组真值为 $G$ 的一个解释 $I$，其对应的真值通常记作 $T_{I}(G)$。显然，有 $n$ 个不同原子的公式，共有 $2^n$ 个解释。

$$T_{I}(G)=\{m_1,m_2,\cdots,m_n\}$$

$$m_i=\begin{cases}A_i&\text{当}A_i\text{在}I\text{下为}1\text{时}\\\neg A_i&\text{当}A_i\text{在}I\text{下为}0\text{时}\end{cases}\\ i=1,2,\cdots,n$$

如果 $G$ 在解释 $I$ 下为真，则称 $I$ 满足 $G$；
如果 $G$ 在解释 $I$ 下为假，则称 $I$ 弄假 $G$。

公式 $G$ 在其所有可能的解释下取真值所作出的表，称为 $G$ 的真值表（truth table）。

如果 $G$ 在它的所有解释下都为真，则称其为恒真式（重言式）；
如果 $G$ 在它的所有解释下都为假，则称其为恒假式（矛盾式）；
如果 $G$ 至少存在一个解释 $I$ 满足 $G$，则称其为可满足式。

公式的等价：

如果 $G,H$ 在其任意解释 $I$ 下真值相同，则称公式 $G,H$ 是等价的，记作 $G=H$。
公式 $G,H$ 等价 $\iff$ 公式 $G\leftrightarrow H$ 恒真。

定律	基本等价式
单条件等价式	$G \leftrightarrow H=(G \rightarrow H)\wedge(H \rightarrow G)$
双条件等价式	$G \rightarrow H=\neg G \vee H$
幂等律	$G \vee G=G\\ G \wedge G=G$
交换律	$G \vee H=H \vee G\\ G \wedge H=H \wedge G$
吸收律	$G \vee(G \wedge H)=G\\ G \wedge(G \vee H)=G$
分配律	$G \vee(H \wedge S)=(G \vee H)\wedge(G \vee S)\\ G \wedge(H \vee S)=(G \wedge H)\vee(G \wedge S)$
同一律	$G \vee 0=G\\ G \wedge 1=G$
零一律	$G \vee 1=1\\ G \wedge 0=0$
互补律	$G \vee \neg G=1\\ G \wedge \neg G=0$
De Morgan 律	$\neg(G \vee H)=\neg G \wedge \neg H\\ \neg(G \wedge H)=\neg G \vee \neg H$

利用基本等价式化简命题公式：

例：

$$\begin{aligned} &\quad(P\rightarrow Q)\rightarrow P\wedge Q\\ &=\neg(\neg P\vee Q)\vee(P\wedge Q)\\ &=(P\wedge\neg Q)\vee(P\wedge Q)\\ &=P\wedge(\neg Q\vee Q)\\ &=P\wedge 1=P \end{aligned}$$

利用基本等价式判断命题公式是否恒真：

例：

$$\begin{aligned} &\quad(P\rightarrow Q)\rightarrow((Q\rightarrow R)\rightarrow(P\rightarrow R))\\ &=\neg(\neg P\vee Q)\vee(\neg(\neg Q\vee R)\vee(\neg P\vee R))\\ &=(P\wedge\neg Q)\vee((Q\wedge\neg R)\vee(\neg P\vee R))\\ &=(P\wedge\neg Q)\vee((Q\vee\neg P\vee R)\wedge(\neg R\vee\neg P\vee R))\\ &=(P\wedge\neg Q)\vee((Q\vee\neg P\vee R)\wedge 1)\\ &=(P\wedge\neg Q)\vee(Q\vee\neg P\vee R)\\ &=(P\vee Q\vee\neg P\vee R)\wedge(\neg Q\vee Q\vee\neg P\vee R)\\ &=1\vee 1=1 \end{aligned}$$

所以原命题公式为恒真式。

联结词的完备集

设 $Q$ 是联结词符号集合，若所有命题运算都能由 $Q$ 中符号表示出来，而 $Q$ 的任意真子集无此性质，则称 $Q$ 是一个完备集。

可以证明，$\{\neg,\wedge\}$，$\{\neg,\vee\}$，$\{\neg,\rightarrow\}$ 都是完备集。

证明 $\{\neg,\wedge\}$ 是完备集：

$$\begin{aligned} P\vee Q&=\neg(\neg P\wedge\neg Q)\\ P\rightarrow Q&=\neg P\vee Q=\neg(P\wedge\neg Q)\\ P\leftrightarrow Q&=(P\rightarrow Q)\wedge(Q\rightarrow P)\\ &=(\neg P\vee Q)\wedge(\neg Q\vee P)\\ &=(\neg(P\wedge\neg Q))\wedge(\neg(\neg Q\wedge\neg P)) \end{aligned}$$

证明 $\{\neg,\vee\}$ 是完备集：

$$\begin{aligned} P\wedge Q&=\neg(\neg P\vee\neg Q)\\ P\rightarrow Q&=\neg P\vee Q\\ P\leftrightarrow Q&=(P\rightarrow Q)\wedge(Q\rightarrow P)\\ &=(\neg P\vee Q)\wedge(\neg Q\vee P)\\ &=\neg(\neg(\neg P\vee Q)\vee\neg(\neg Q\vee P)) \end{aligned}$$

证明 $\{\neg,\rightarrow\}$ 是完备集：

$$\begin{aligned} P\vee Q&=\neg P\rightarrow Q\\ P\wedge Q&=\neg(\neg P\vee\neg Q)\\ &=\neg(P\rightarrow\neg Q)\\ P\leftrightarrow Q&=(P\rightarrow Q)\wedge(Q\rightarrow P)\\ &=\neg((P\rightarrow Q)\rightarrow\neg(Q\rightarrow P)) \end{aligned}$$

与非式和或非式

命题“$P$ 与 $Q$ 的否定”称为 $P$ 与 $Q$ 的与非式，记作 $P\uparrow Q$.
真值规定：$P\uparrow Q$ 为真 $\iff$ $P,Q$ 不同时为真。

$$P\uparrow Q=\neg(P\wedge Q)$$

因为 $\{\neg,\wedge\}$ 是完备集，所以 $\{\uparrow\}$ 也是完备集。

命题“$P$ 或 $Q$ 的否定”称为 $P$ 与 $Q$ 的或非式，记作 $P\downarrow Q$.
真值规定：$P\downarrow Q$ 为真 $\iff$ $P,Q$ 同时为假。

$$P\downarrow Q=\neg(P\vee Q)$$

因为 $\{\neg,\vee\}$ 是完备集，所以 $\{\downarrow\}$ 也是完备集。

公式的蕴涵与演绎推理

逻辑公式的一个重要作用就是研究命题推理，除了利用公式的等价关系进行推理以外，公式间的逻辑蕴涵（entailment）关系，也可以反映命题间的演绎推理（deductive reasoning）：

设 $G,H$ 是两个公式，当且仅当对 $G,H$ 的任意解释 $I$，如果 $I$ 满足 $G$，则 $I$ 也满足 $H$ 时，称 $H$ 是 $G$ 的逻辑结果（$G$ 蕴涵 $H$），记作 $G\Rightarrow H$。

$G\Rightarrow H$ $\iff$ $G\rightarrow H$ 是恒真的。

证明：

必要性：任取 $G,H$ 的解释 $I$。
若 $T_I(G)=1$，则由 $G\Rightarrow H$ 可知 $T_I(H)=1$，因此 $T_I(G\rightarrow H)=1$；
若 $T_I(G)=0$，则 $T_I(G\rightarrow H)=1$。
从而，对 $G,H$ 的任意解释 $I$，有 $G\rightarrow H$ 恒真。

充分性：任取 $G,H$ 的解释 $I$，若 $T_I(G)=1$，由 $G\rightarrow H$ 恒真，可知 $T_I(H)=1$，从而有 $G\Rightarrow H$。

设 $G_1,G_2,\cdots,G_n,H$ 是公式，当且仅当 $(G_1\wedge G_2\wedge \cdots\wedge G_n)\Rightarrow H$ 时，称 $H$ 为 $G_1,G_2,\cdots,G_n$ 的逻辑结果（$G_1,G_2,\cdots,G_n$ 共同蕴涵 $H$）。

显然，$(G_1\wedge G_2\wedge \cdots\wedge G_n)\Rightarrow H$ $\iff$ $G_1,G_2,\cdots,G_n\rightarrow H$ 是恒真的。

定理： 如果 $H_1,H_2,\cdots H_m,P$ 共同蕴涵公式 $Q$，则 $H_1,H_2,\cdots H_m$ 共同蕴涵公式 $P\rightarrow Q$。

演绎的定义：

设 $S$ 是一个命题公式的集合，称为前提集合，从 $S$ 推出公式 $G$ 的一个演绎是公式的一个有限序列：

$$G_1,G_2,\cdots,G_k$$

其中，$G_k$ 就是 $G$；$G_i$ 要么属于 $S$，要么是某些 $G_j\ (j<i)$ 的逻辑结果。

此时称从 $S$ 演绎出 $G$，$G$ 为此演绎的逻辑结果，记作 $S\Rightarrow G$。

演绎方法的完备性：

引理：设 $G,H_1,H_2$ 是公式，如果 $G\Rightarrow H_1,G\Rightarrow H_2$，则 $G\Rightarrow(H_1\wedge H_2)$。

证明：任取 $G,H_1,H_2$ 的一个解释 $I$，若 $I$ 满足 $G$，由假设知，$H_1,H_2$ 都是 $G$ 的逻辑结果，从而 $I$ 满足 $H_1$，又因为 $I$ 满足 $H_2$，故 $I$ 满足 $H_1\wedge H_2$。由 $I$ 的任意性，可得 $G\Rightarrow(H_1\wedge H_2)$。

设 $S$ 是公式集合，$G$ 是一个公式，从 $S$ 演绎出 $G$ 的充要条件是 $G$ 为 $S$ 的逻辑结果。

证明：

必要性：设从 $S$ 演绎出 $G$，令这个演绎为 $G_1,G_2,\cdots,G_k$。
对任意 $G_i\ (i=1,2,\cdots,k)$，只需证明 $G_i$ 是 $S$ 的逻辑结果。

对 $i$ 使用归纳法：

1. 当 $i=1$ 时，因为 $G_1\in S$，显然 $G_1\wedge\cdots\rightarrow G_1$ 恒真，故 $S\Rightarrow G_1$。
2. 当 $i<n$ 时，同理可得 $S\Rightarrow G_i$。
3. 当 $i=n$ 时，若 $G_n\in S$，则 $S\Rightarrow G_n$，归纳完毕。
   若 $G_n$ 是某些 $G_j\ (j<n)$ 的逻辑结果，不妨设 $(G_{j1}\wedge\cdots\wedge G_{jh})\Rightarrow G_n$，其中 $j_1,\cdots,j_n<n$。
   由归纳假设可得，$S\Rightarrow G_{jm},\ m=1,\cdots,h$，又由引理可得 $S\Rightarrow(G_{j1}\wedge\cdots\wedge G_{jh})$，所以综上所述，可得 $S\Rightarrow G_n$，归纳完毕。

充分性：若 $G$ 是 $S$ 的逻辑结果，由演绎的定义可得，$G$ 是演绎 $H_1,H_2,\cdots,H_m,G$ 的逻辑结果，其中 $H_1,H_2,\cdots,H_m$ 是 $S$ 中的所有公式。

演绎定理： 设 $S$ 是前提集合，$G,H$ 是两个公式，如果从 $S\cup\{G\}$ 可演绎出 $H$，则从 $S$ 可演绎出 $G\rightarrow H$。

定律	基本蕴涵式
恒等律	$0\Rightarrow G\\ G\Rightarrow 1$
化简律	$P\wedge Q\Rightarrow P\\ P\wedge Q\Rightarrow Q$
附加律	$P\Rightarrow P\vee Q\\ Q\Rightarrow P\vee Q$
变形化简律	$\neg(P\rightarrow Q)\Rightarrow P\\ \neg(P\rightarrow Q)\Rightarrow\neg Q$
变形附加律	$\neg P\Rightarrow(P\rightarrow Q)\\ Q\Rightarrow(P\rightarrow Q)$
前提引入规则	$P,Q\Rightarrow P\wedge Q$
析取三段论	$\neg P,P\vee Q\Rightarrow Q$
假言推理	$P,P\rightarrow Q\Leftrightarrow Q$
拒取式	$\neg Q,P\rightarrow Q\Leftrightarrow\neg P$
假言三段论	$P\rightarrow Q,Q\rightarrow R\Leftrightarrow P\rightarrow R$
二难推理	$P\vee Q,P\rightarrow R,Q\rightarrow R\Leftrightarrow R$

公式间蕴涵的证明方法：

给出两个公式 $G,H$，证明 $G\Rightarrow H$ 可以使用以下方法：

1. 真值表法，将公式 $G$ 和公式 $H$ 同列在一张真值表中，扫描公式 $G$ 所对应的列，验证该列真值为1的每一项，它所在行上对应公式 $H$ 所对应真值必为1，则 $G\Rightarrow H$；
2. 证 $G\rightarrow$ 是恒真公式；
3. 利用一些基本等价式和基本蕴涵式进行推导；
4. 任取解释 $I$，若 $I$ 满足 $G$，只需证明 $I$ 满足 $H$；
5. 反证法，设结论为假，只需证明前提也为假，即证明 $\neg H\Rightarrow\neg G$。

自然演绎法推理

根据一些基本等价式和基本蕴涵式，可以从公式 $S$ 演绎出公式 $G$，在演绎过程中遵循以下三条基本规则：

规则 P（前提引入规则，premise rule）： 在推导的过程中，可随时引入前提集合中的任意一个前提。
规则 T（逻辑结果引用规则，transformation rule）： 在推导的过程中，可随时引入前面演绎出的某些公式的逻辑结果。
规则 CP（附加前提规则，conclusion premise rule）： 如果需要演绎出的公式是 $P\rightarrow Q$ 的形式，可将 $P$ 作为附加前提使用，而力图去演绎出 $Q$。

例：证明 $\{(P\vee Q),(P\rightarrow R),(Q\rightarrow S)\}\Rightarrow S\vee R$

证法一（不使用规则 CP）：

$$\begin{align} &(1)\quad P\vee Q\tag{P}\\ &(2)\quad \neg P\rightarrow Q\tag{T,1}\\ &(3)\quad Q\rightarrow S\tag{P}\\ &(4)\quad \neg P\rightarrow S\tag{T,2,3}\\ &(5)\quad \neg S\rightarrow P\tag{T,4}\\ &(6)\quad P\rightarrow R\tag{P}\\ &(7)\quad \neg S\rightarrow R\tag{T,5,6}\\ &(8)\quad S\vee R\tag{T,7} \end{align}$$

证法二（使用规则 CP）：

$$\begin{align} &(1)\quad \neg S\tag{CP}\\ &(2)\quad Q\rightarrow S\tag{P}\\ &(3)\quad \neg Q\tag{T,1,2}\\ &(4)\quad P\vee Q\tag{P}\\ &(5)\quad P\tag{T,3,4}\\ &(6)\quad P\rightarrow R\tag{P}\\ &(7)\quad R\tag{T,5,6}\\ &(8)\quad \neg S\rightarrow R\tag{CP,1,7}\\ &(9)\quad S\vee R\tag{T,8} \end{align}$$

析取范式与合取范式

使用真值表来判定命题公式的真假虽然是万能的，但在公式包含原子数较多时，就会显得太过繁琐，为了简化两个命题公式是否等价及一个公式恒真、恒假、可满足的判定，我们引入范式（normal form） 的概念。

原子或原子的否定称为文字，有限个文字的析取式称为一个子句，有限个文字的合取式称为一个短语。一个文字既可以称为是一个子句，也可以称为是一个短语。

有限个短语的析取式称为析取范式（disjunctive normal form，DNF）；
有限个子句的合取式称为合取范式（conjunctive normal form，CNF）。
一个文字、子句、短语既可以看作是析取范式，也可以看作是合取范式。

定理： 对于任意命题公式，都存在与其等价的析取范式与合取范式。

对于公式 $G$，通过如下方法即可得出等价于 $G$ 的范式：

1. 使用基本等价式，将 $G$ 中的逻辑联结词 $\rightarrow,\leftrightarrow$ 消去。
2. 使用 $\neg(\neg H)=H$ 和 De Morgan 律，将 $G$ 中的所有否定号 $\neg$ 都放在原子之前。
3. 反复使用分配律，即可得到等价于 $G$ 的范式。

极小项与主析取范式：

设 $P_1,P_2,\cdots,P_n$ 是 $n$ 个不同原子，一个短语如果恰好包含所有这 $n$ 个原子或其否定，且其排列顺序与 $P_1,P_2,\cdots,P_n$ 的顺序一致，则称此短语为关于 $P_1,P_2,\cdots,P_n$ 的一个极小项（minterm），对任意一个极小项 $m$，有且仅有一个解释使其取1值。显然，共有 $2^n$ 个不同的极小项。

极小项与解释和 $n$ 位二进制数具有一一对应关系，参见下表：

极小项	成真解释	记法
$\neg P\wedge\neg Q\wedge\neg R$	000	$m_0$
$\neg P\wedge\neg Q\wedge R$	001	$m_1$
$\neg P\wedge Q\wedge\neg R$	010	$m_2$
$\neg P\wedge Q\wedge R$	011	$m_3$
$P\wedge\neg Q\wedge\neg R$	100	$m_4$
$P\wedge\neg Q\wedge R$	101	$m_5$
$P\wedge Q\wedge\neg R$	110	$m_6$
$P\wedge Q\wedge R$	111	$m_7$

任意两个不同极小项的合取式恒假，所有极小项的析取式恒真：

$$\bigvee_{i=0}^{2^n-1}m_i=1$$

设命题公式 $G$ 所有不同原子为 $P_1,P_2,\cdots,P_n$，如果 $G$ 的某个析取范式 $G'$ 中的每一个短语都是关于 $P_1,P_2,\cdots,P_n$ 的一个极小项，则称 $G'$ 为 $G$ 的主析取范式（principal disjunctive normal form）。在真值表中，使得公式为真的解释所对应的极小项的析取即为此公式的主析取范式。

定理： 对于任意命题公式，都存在唯一一个与其等价的主析取范式。

设命题公式 $G$ 中所有不同原子为 $P_1,P_2,\cdots,P_n$，则与其等价的主析取范式的求法如下：

1. 将公式 $G$ 化为析取范式 $G'$。
2. 删去析取范式中所有恒假的短语。
3. 用等幂律将短语中重复出现的同一文字化简为只出现一次，例如 $P\wedge P=P$。
4. 对 $G'$ 中的每一个短语进行检查，如果 $G_i'$ 不是关于 $P_1,P_2,\cdots,P_n$ 的极小项，则 $G_i'$ 中必然缺少原子 $P_{j1},\cdots,P_{jk}$，将所有非极小项 $G_i'$ 都化成一些极小项之析取，即可得等价于 $G$ 的主析取范式：

$$\begin{aligned}G_i'&=G_i'\wedge(P_{j1}\vee\neg P_{j1})\wedge\cdots\wedge(P_{jk}\vee\neg P_{jk})\\&=m_{i_1}\vee m_{i_2}\vee\cdots\vee m_{i_{2^k}}\end{aligned}$$

极大项与主合取范式：

和极小项类似，设 $P_1,P_2,\cdots,P_n$ 是 $n$ 个不同原子，一个子句如果恰好包含所有这 $n$ 个原子或其否定，且其排列顺序与 $P_1,P_2,\cdots,P_n$ 的顺序一致，则称此短语为关于 $P_1,P_2,\cdots,P_n$ 的一个极大项（maxterm），对任意一个极大项 $M$，有且仅有一个解释使其取0值。极小项和极大项为相互否定的关系：

$$m_i=\neg M_i,\quad M_i=\neg m_i$$

极大项	成假解释	记法
$P\vee Q\vee R$	000	$M_0$
$P\vee Q\vee\neg R$	001	$M_1$
$P\vee\neg Q\vee R$	010	$M_2$
$P\vee\neg Q\vee\neg R$	011	$M_3$
$\neg P\vee Q\vee R$	100	$M_4$
$\neg P\vee Q\vee\neg R$	101	$M_5$
$\neg P\vee\neg Q\vee R$	110	$M_6$
$\neg P\vee\neg Q\vee\neg R$	111	$M_7$

任意两个不同的极大项的析取式恒真，所有极大项的合取式恒假：

$$\bigwedge_{i=0}^{2^n-1}M_i=0$$

设命题公式 $G$ 所有不同原子为 $P_1,P_2,\cdots,P_n$，如果 $G$ 的某个合取范式 $G'$ 中的每一个子句都是关于 $P_1,P_2,\cdots,P_n$ 的一个极大项，则称 $G'$ 为 $G$ 的主合取范式（principal conjunctive normal form）。在真值表中，使得公式为假的解释所对应的极大项的合取即为此公式的主合取范式。

定理： 对于任意命题公式，都存在唯一一个与其等价的主合取范式。

设命题公式 $G$ 中所有不同原子为 $P_1,P_2,\cdots,P_n$，则与其等价的主合取范式的求法如下：

1. 将公式 $G$ 化为合取范式 $G'$。
2. 删去合取范式中所有恒真的短语。
3. 用等幂律将子句中重复出现的同一文字化简为只出现一次，例如 $P\vee P=P$。
4. 对 $G'$ 中的每一个子句进行检查，如果 $G_i'$ 不是关于 $P_1,P_2,\cdots,P_n$ 的极大项，则 $G_i'$ 中必然缺少原子 $P_{j1},\cdots,P_{jk}$，将所有非极大项 $G_i'$ 都化成一些极大项之合取，即可得等价于 $G$ 的主合取范式：

$$\begin{aligned}G_i'&=G_i'\vee(P_{j1}\wedge\neg P_{j1})\vee\cdots\vee(P_{jk}\wedge\neg P_{jk})\\&=M_{i_1}\wedge M_{i_2}\wedge\cdots\wedge M_{i_{2^k}}\end{aligned}$$

等价于同一公式的主析取范式 $G'$ 与主合取范式 $G''$ 具有以下关系：

$$\begin{aligned} G''&=\neg\neg G'\\ &=\neg\neg m_0\\ &=\neg(m_1\vee m_2\cdots\vee m_k)\\ &=\neg m_1\wedge\neg m_2\wedge\cdots\wedge\neg m_k\\ &=M_1\wedge M_2\wedge\cdots\wedge M_k \end{aligned}$$

通过如下方法即可将主析取范式转化为主合取范式：

1. 求出 $G$ 的主析取范式中没有包含的所有极小项 $m_i$。
2. 求出与该极小项下标相同的极大项 $M_i$。
3. 将求出的所有极大项合取起来，即可得到 $G$ 的主合取范式 $G'$。

用范式判断公式的等价性：

主析取范式和主合取范式都可以用来判断公式是否等价。因为等价于同一公式的主析取范式和主合取范式都是唯一的，所以假如对应于公式 $G,H$ 的主析取范式或主合取范式不完全相同，则 $G,H$ 不等价。

用范式判断公式的恒真恒假性：

析取范式法：公式 $G$ 是恒假的当且仅当在与其等价的析取范式中，每个短语均至少包含一个原子及其否定。
合取范式法：公式 $G$ 是恒真的当且仅当在与其等价的合取范式中，每个子句均至少包含一个原子及其否定。

主析取范式法：公式恒假时，主析取范式没有极小项（$G'=0$）；公式恒真时，主析取范式包含所有极小项。
主合取范式法：公式恒假时，主合取范式包含所有极大项；公式恒真时，主合取范式没有极大项（$G'=1$）。

另一种判定算法：对任给要判定的命题公式 $G$，设其中有原子 $P_1,P_2,\cdots,P_n$，令 $\bm{P_1}$ 取1值，求 $G$ 的真值，或为1，或为0，或为新公式 $G_1$ 且其中只有原子 $P_2,\cdots,P_n$，再令 $\bm{P_1}$ 取0值，求 $G$ 真值。如此继续，到最终只含0或1为止。若最终结果全为1，则公式 $G$ 恒真；若最终结果全为1，则公式 $G$ 恒假；若最终结果既有1又有0，则公式 $G$ 为可满足式。

例：求 $(P\wedge Q\rightarrow R)\wedge(P\rightarrow Q)\rightarrow(P\rightarrow R)$ 是否恒真。

$P$ 取0值 $\Rightarrow$ 1
$P$ 取1值 $\Rightarrow$ $(Q\rightarrow R)\wedge Q\rightarrow R$

$Q$ 取0值 $\Rightarrow$ 1
$Q$ 取1值 $\Rightarrow$ $R\rightarrow R$

$R$ 取0值 $\Rightarrow$ 1
$R$ 取0值 $\Rightarrow$ 1

最终结果全为1，可得原公式恒真。

谓词逻辑

命题逻辑有一些严重的缺陷，那就是把问题看成一个个孤立的命题，忽略了问题之间的联系，不能反映某些重要的常见的逻辑思维过程。为解决这些问题，我们引入了谓词和谓词逻辑的概念。

谓词逻辑与量词

我们首先提出个体的定义：可以独立存在的物体称为个体（individual），在谓词演算中，个体通常指一个命题里的思维对象；个体变化的范围称为个体域（individual domain），个体域可以是有限的，也可以是无限的；具象的个体称为个体常元（individual constant），抽象的个体称为个体变元（individual variable），变元可以被个体域内的任意一个元素代入。

用用于描述个体的性质或个体之间关系的词就称为谓词（predicate），含有 $n$ 个个体变元的的谓词称为 $\bm n$ 元谓词，记作 $P(x_1,x_2,\cdots,x_n)$。一元谓词用于描述个体的性质，二元或多元谓词用于描述两个或多个个体间的关系，0元谓词中没有个体，退化为命题。

命题“对任意 $x$ 都有 $G(x)$”称为全称命题，记作 $\forall xG(x)$，$\forall x$ 称为全称量词（universal quantifier）。
$\forall xG(x)$ 为真 $\iff$ 对所有个体域内的 $x$，$G(x)$ 均为真；
$\forall xG(x)$ 为假 $\iff$ 至少有一个个体域内的 $x_0$，使 $G(x_0)$ 为假。

命题“存在 $x$ 使得 $G(x)$”称为存在命题，记作 $\exists xG(x)$，$\exists x$ 称为存在量词（existential quantifier）。
$\exists xG(x)$ 为真 $\iff$ 至少有一个个体域内的 $x_0$，使 $G(x_0)$ 为真；
$\exists xG(x)$ 为假 $\iff$ 对所有个体域内的 $x$，$G(x)$ 均为假。

$$\forall xG(x)\Rightarrow G(a)\Rightarrow\exists xG(x)\\ \ \\ \neg\exists xG(x)\Rightarrow\neg \forall xG(x)$$

量词本身不是一个独立的逻辑概念，可以用析取和合取代替。当个体域 $D=\{x_0,x_1,\cdots\}$ 可数时：

$$\forall xG(x)\iff G(x_0)\wedge G(x_1)\wedge\cdots\\ \ \\ \exists xG(x)\iff G(x_0)\vee G(x_1)\vee\cdots$$

量词的约束范围：

当变元至少一次出现在使用这个变元的量词范围之内，则该变元受量词约束，称其为约束变元（bound variable）；当变元至少一次出现在使用这个变元的量词范围之外，则该变元不受量词约束，称其为自由变元（free variable）。一个变元可以既是约束变元又是自由变元。

约束变元的名称可以被更改，但这种改名必须在量词作用区域内各处以及该量词符号中同时进行，并且改成的新约束变元必须有别于改名区域中的所有其它变元。

谓词公式

为了给出谓词公式的定义，我们需要先引入项（term） 的概念。谓词逻辑中的项具有如下递归定义：

1. 个体常元是项；
2. 个体变元是项；
3. 若 $f(x_1,x_2,\cdots,x_n)$ 是 $n$ 元函数符号，则 $x_1,x_2,\cdots,x_n$ 是项，$f(x_1,x_2,\cdots,x_n)$ 也是项；
4. 有限次使用以上规则生成的符号串都是项。

若 $P(x_1,\cdots,x_n)$ 是 $n$ 元谓词符号，$t_1,\cdots,t_n$ 是项，则 $P(x_1,\cdots,x_n)$ 被称为原子。

谓词公式具有如下递归定义：

1. 原子是公式；
2. 若 $G,H$ 是公式，则 $(\neg G)$，$(G\vee H)$，$(G\wedge H)$，$(G\rightarrow)$，$(G\leftrightarrow G)$ 也是公式；
3. 若 $G$ 是公式，$x$ 是 $G$ 中的自由变元，则 $\forall xG$，$\exists xG$ 也是公式；
4. 有限次使用以上规则生成的符号串都是公式。

若公式中无自由变元，或将自由变元看作常元，则称其为封闭公式，只有封闭公式可以看作命题，并且有确定的真值。

谓词公式 $G$ 的一个解释 $\bm I$ 是由非空集合 $D$ （称为论域）和对 $G$ 中出现的个体常元，函数符号，谓词符号以下列规则进行的一组指定组成：

1. 对每个个体常元，指定 $D$ 中一个元素；
2. 对每个 $n$ 元函数符号，指定一个函数；
3. 对每个 $n$ 元谓词符号，指定一个谓词。

例：证明 $\forall x\exists yP(x,y)$ 与 $\exists y\forall xP(x,y)$ 不等价。

证：对函数 $P(x,y)$ 做以下指定：

$$P(1,1)=1,P(1,2)=0,P(2,1)=0,P(2,2)=1$$

考虑论域 $D=\{1,2\}$，并构造在该论域下的解释 $I$，则：

$$T_I(\forall x\exists yP(x,y))=T_I(P(1,1)\vee P(1,2))\wedge(P(2,1)\vee P(2,2))=1\\ T_I(\exists y\forall xP(x,y))=T_I(P(1,1)\wedge P(1,2))\vee(P(2,1)\wedge P(2,2))=0$$

所以二者不等价。

在使用量词时，要注意多重量词的运算顺序和量词的作用范围。

不同的量词运算顺序：

构造解释 $I$：设 $D$ 为自然数集，令函数 $P(x,y):x>y$，则：

（1）

$$T_I(\forall x\exists yP(x,y))=T_I(\exists yP(0,y)\wedge\exists yP(1,y)\wedge\cdots\wedge\exists y(P,n,y)\wedge\cdots)$$

因为

$$T_I(\exists yP(0,y))=T_I(P(0,0)\vee P(0,1)\vee\cdots)=0$$

所以 $T_I(\forall x\exists yP(x,y))=0$

（2）

$$\begin{aligned}T_I(\forall y\exists xP(x,y))&=T_I(\exists xP(x,0)\wedge\exists xP(x,1)\wedge\cdots\wedge\exists xP(x,n)\wedge\cdots)\\&=1\wedge 1\wedge\cdots\wedge 1\wedge\cdots\\&=1\end{aligned}$$

（3）

$$\begin{aligned}T_I(\exists x\forall yP(x,y))&=T_I(\forall yP(0,y)\vee\forall yP(1,y)\vee\cdots\vee\forall yP(n,y)\vee\cdots)\\&=0\vee 0\vee\cdots\vee 0\vee\cdots\\&=0\end{aligned}$$

综上所述，$\forall x\exists yP(x,y)$ 与 $\forall y\exists xP(x,y)$ 与 $\exists x\forall yP(x,y)$ 不等价。

当论域 $D$ 可数时，相邻的同种量词可以交换顺序：

$$\forall x\forall yP(x,y)=\forall y\forall xP(x,y)\\ \exists x\exists yP(x,y)=\exists y\exists xP(x,y)$$

不同的量词作用范围：

$\forall xP(x)\rightarrow P(a)$ 与 $\forall x(P(x)\rightarrow P(a))$

设 $D$ 为个体域，$a\in D$，$P(x)$ 为 $D$ 上任意一个谓词，则：

（1）任取解释 $I$，
若 $P(a)$ 在 $I$ 下为真，则 $\forall xP(x)\rightarrow P(a)$ 在 $I$ 下为真；
若 $P(a)$ 在 $I$ 下为假，则 $\forall xP(x)$ 在 $I$ 下为假，所以 $\forall xP(x)\rightarrow P(a)$ 在 $I$ 下为假。
因此，$\forall xP(x)\rightarrow P(a)$ 为恒真式。

（2）构造解释 $I$：设论域 $D=\{1,2\}$，$a=1$，令 $P(1)=0,P(2)=0$，则：

$$\begin{aligned}T_I(\forall x(P(x)\rightarrow P(a)))&=T_I((P(1)\rightarrow P(1))\wedge(P(2)\rightarrow P(1)))\\&=1\wedge 0 \\&=0\end{aligned}$$

因此，$\forall x(P(x)\rightarrow P(a))$ 不为恒真式。

综上所述，$\forall xP(x)\rightarrow P(a)$ 与 $\forall x(P(x)\rightarrow P(a))$ 不等价。

谓词公式的等价与蕴涵

谓词公式的等价与蕴涵和命题公式类似。因为对任意谓词公式 $G,H$，在解释 $I$ 下，$G,H$ 就是两个命题，所以命题逻辑中给出的基本等价式在谓词逻辑中仍然成立；同理，命题逻辑中给出的基本蕴涵式在谓词逻辑中也仍然成立。

此外，谓词逻辑还引入了一些新的常用基本等价式与蕴涵式：

定律	基本等价式
量词辖域扩张及收缩律 $\\$（$H$ 不含约束变元 $x$）	$\forall x(G(x)\vee H)=\forall xG(x)\vee H\\ \exists x(G(x)\vee H)=\exists xG(x)\vee H\\ \forall x(G(x)\wedge H)=\forall xG(x)\wedge H\\ \exists x(G(x)\wedge H)=\exists xG(x)\wedge H$
量词转化律	$\neg\forall xG(x)=\exists x\neg G(x)\\ \neg\exists xG(x)=\forall x\neg G(x)$
量词分配律	$\forall xG(x)\wedge\forall xH(x)=\forall x(G(x)\wedge H(x))\\ \exists xG(x)\vee\exists xH(x)=\exists x(G(x)\vee H(x))$
量词分配律（改名）	$\forall xG(x)\vee\forall xH(x)=\forall x\forall y(G(x)\vee H(y))\\ \exists xG(x)\wedge\exists xH(x)=\exists x\exists y(G(x)\wedge H(y))$

定律	基本蕴涵式
量词分配律	$\exists x(A(x)\wedge B(x))\Rightarrow\exists xA(x)\wedge\exists yB(y)\\ \forall xA(x)\vee\forall yB(y)\Rightarrow\forall x(A(x)\vee B(x))\\ \forall x(A(x)\rightarrow B(x))\Rightarrow\forall xA(x)\rightarrow\forall xB(x)$

对于谓词公式 $A,B$，一般有如下证明 $A\Rightarrow B$ 的方法：

方法一： 证明 $A\rightarrow B$ 是恒真公式。

例：证明 $\exists x\exists y(A(x)\wedge B(y))\Rightarrow\exists xA(x)$ 为恒真公式。

只需证明 $\exists x\exists y(A(x)\wedge B(y))\rightarrow\exists xA(x)$ 为恒真公式：

$$\begin{aligned} &\quad\exists x\exists y(A(x)\wedge B(y))\rightarrow\exists xA(x)\\ &=\exists xA(x)\wedge\exists yB(y)\rightarrow\exists xA(x)\\ &=\neg\exists xA(x)\vee\neg\exists yB(y)\vee\exists xA(x)\\ &=(\neg\exists xA(x)\vee\exists xA(x))\vee\neg\exists yB(y)\\ &=1\vee\neg\exists yB(y)\\ &=1 \end{aligned}$$

方法二： 由基本等价式和基本蕴涵式推导出 $A\Rightarrow B$.

例：证明 $(\exists xA(x)\rightarrow\forall xB(x))\Rightarrow\forall x(A(x)\rightarrow B(x))$ 为恒真公式。

$$\begin{aligned} \exists xA(x)\rightarrow\forall xB(x)&=\neg\exists xA(x)\vee\forall xB(x)\\ &=\forall x(\neg A(x))\vee\forall xB(x)\\ &\Rightarrow\forall x(\neg A(x)\vee B(x))\\ &=\forall x(A(x)\rightarrow B(x)) \end{aligned}$$

方法三： 任取解释 $I$，若 $I$ 满足 $A$，只需证明 $I$ 也满足 $B$.

方法四： 证明 $\neg B\Rightarrow\neg A$.

例：证明 $\exists x(A(x)\vee B(x))\Rightarrow\forall xA(x)\vee\exists xB(x)$ 为恒真公式。

证法一（方法三）：任取解释 $I$，假设 $\exists x(A(x)\vee B(x))$ 在 $I$ 下为真，则对 $D$ 中每个元素 $x$，都有 $A(x)\vee B(x)$ 为真。

1. 若对 $D$ 中某个元素 $x_0$，$B(x_0)$ 为真，则 $\exists x_0B(x_0)$ 为真，因此 $\forall x_0A(x_0)\vee\exists x_0B(x_0)$ 为真；
2. 若对 $D$ 中每个元素 $x$，$B(x)$ 均为假，则必然 $A(x)$ 均为真，即 $\forall xA(x)$ 为真，因此 $\forall x_0A(x_0)\vee\exists x_0B(x_0)$ 为真。

综上所述，可推得 $\exists x(A(x)\vee B(x))\Rightarrow\forall xA(x)\vee\exists xB(x)$.

证法二（方法四）：假设存在解释 $I$ 使 $\exists x(A(x)\vee B(x))$ 为假，则 $\forall xA(x)$ 和 $\exists xB(x)$ 均为假，即 $D$ 中存在元素 $x_0$，使 $A(x_0)$ 为假，且对 $D$ 中任意元素 $x$，$B(x)$ 均为假，于是 $A(x_0)\vee B(x_0)$ 为假，所以 $\exists x(A(x)\vee B(x))$ 在 $I$ 下为假。

因此，$\exists x(A(x)\vee B(x))\Rightarrow\forall xA(x)\vee\exists xB(x)$.

前束范式

如果量词均在公式的开头，并且它们的作用域延伸到整个公式的末端，则该公式被称作前束范式（prenex normal form），它的形式如下：

$$Q_1x_1Q_2x_2\cdots Q_nx_nM,\quad i=1,2,\cdots,n$$

其中 $Q_ix_i$ 是 $\forall x_i$ 和 $\exists x_i$ 中的一种，$M$ 是不含量词的公式，我们将 $Q_1x_1Q_2x_2\cdots Q_nx_n$ 称为首标，将 $M$ 称为母式。

定理： 对任何公式 $G$，都存在与其等价的前束范式。

通过如下算法，可将公式 $G$ 化为与其等价的前束范式：

1. 使用基本等价式，将 $G$ 中的 $\leftrightarrow$ 与 $\rightarrow$ 删除：

$$\begin{aligned}(K\leftrightarrow H)&=(K\rightarrow H)\wedge(H\rightarrow K)\\ (K\rightarrow H)&=\neg K\vee H\end{aligned}$$

2. 使用 $\neg(\neg H)=H$，De Morgan 律和量词转化律，将 $G$ 中的所有否定号 $\neg$ 都放在原子之前。

3. 如果必要的话，对约束变元进行改名。

4. 使用量词辖域扩张与分配律将所有量词都提到 $G$ 的最左边。

Skolem（斯科伦）范式

如果公式 $G$ 是前束范式，并且可以消除它的所有存在量词，生成与原公式可满足性等价（并不一定等价） 的公式 $S$，则称公式 $G$ 可以 Skolem 化（Skolemization），消除存在量词后得到的公式 $S$ 称作 Skolem 范式（Skolem normal form）。

所谓可满足性等价，可以理解为以下两点：

1. 满足 $S$ 的解释满足 $G$；
2. 满足 $G$ 的解释，适当扩充后可满足 $S$.

设 $Q_1x_1Q_2x_2\cdots Q_nx_nM$ 式与 $G$ 等价的前束范式，并且 $M$ 为合取范式形式，通过如下规则对 $G$ 进行 Skolem 化：

1. 若 $Q_r$ 是存在量词，并且它左边没有全称量词，则取异于 $M$ 中所有个体常元的常元 $c$，并用 $c$ 代替 $M$ 中所有的 $x_r$，然后在首标中删除 $Q_rx_r$.

2. 若 $Q_{s_1},Q_{s_2},\cdots,Q_{s_m}\ (m\geq 1,1\leq s_1<s_2<\cdots<s_m<r)$ 是所有出现在 $Q_rx_r$ 左边的全称量词，则取异于 $M$ 中所有函数的 $m$ 元函数 $f(x_{s_1},x_{s_2},\cdots,x_{s_m})$，用该函数代替 $M$ 中所有的 $x_r$，然后在首标中删除 $Q_rx_r$.

用于代替 $x_r$ 的常元和函数称为公式 $G$ 的 Skolem 函数。

例：将下面公式化为 Skolem 范式：

$$\forall x\forall y(A(x)\to B(x,y))\to(\exists yC(y)\to\exists zD(z))$$

先将其化成母式为合取范式的前束范式：

$$\exists x\exists y\forall t\exists z[(A(x)\vee\neg C(t)\vee D(z))\wedge(\neg B(x,y)\vee\neg C(t)\vee D(z))]$$

用 $a$ 代替 $x$，用 $b$ 代替 $y$，用 $f(t)$ 代替 $z$，即可得到公式的 Skolem 范式：

$$\forall t[(A(a)\vee\neg C(t)\vee D(f(t)))\wedge(\neg B(a,b)\vee\neg C(t)\vee(f(t)))]$$

定理： 设 $S$ 为公式 $G$ 的 Skolem 范式，则公式 $G$ 恒假的充要条件是公式 $S$ 恒假。（恒假性等价）

证明：

假设 $G$ 恒假，而 $S$ 可满足，由 $G$ 与 $S$ 的可满足性等价可知，$G$ 应该是可满足的，产生了矛盾；
假设 $S$ 恒假，而 $G$ 可满足，由 $G$ 与 $S$ 的可满足性等价可知，$G$ 应该是可满足的，也产生了矛盾。

故该定理成立。

例：假设 $\exists x\forall yM(x,y)$ 是公式 $G$ 的前束范式，其中 $M(x,y)$ 是仅仅包含变量 $x,y$ 的母式。设 $f$ 是不出现在 $M(x,y)$ 中的函数符号，证明：$G$ 是恒真的当且仅当 $\exists xM(x,f(x))$ 是恒真的。

分析：要证明 $G$ 恒真当且仅当 $\exists xM(x,f(x))$ 恒真，只需证明 $\neg G$ 恒假当且仅当 $\neg\exists xM(x,f(x))$ 恒假。

证：因为

$$\begin{aligned} \neg G&=\forall x\exists y(\neg M(x,y))\\ \neg\exists xM(x,f(x))&=\forall x(\neg M(x,f(x))) \end{aligned}$$

又因为 $\forall x(\neg M(x,f(x)))$ 是 $\neg G$ 的 Skolem 范式，所以二者恒假性等价，原命题得证。

高阶逻辑概述

在之前，我们所使用的谓词逻辑都处在一阶逻辑系统下，但一些命题并不能用一阶逻辑来确切表述。例如：设 $G(x)$ 是一元谓词，则命题“对任意一元谓词 $G(x)$，命题 $\forall xG(x)$ 都为真。”应当用“公式 $\forall G(\forall xG(x))$ 为恒真式”来表述，这就是一个典型的高阶逻辑命题。

在公式 $\forall G(\forall xG(x))$ 中，不仅有关于个体变元 $x$ 的量词，还有关于谓词符号的量词，由这样的公式所组成的逻辑系统就被称为高阶逻辑。在高阶逻辑中，不仅判定问题不可解，甚至连一个完备的公理系统都没有。

集合代数

集合论所讨论和研究的对象是集合（set），所谓集合，是我们将一系列客体的总和而考虑为的一个整体，这些客体叫作该集合的元素（element），若有一个集合 $A$ 和一个元素 $a$，并且集合 $A$ 包含元素 $a$，可以记作 $a\in A$。

集合的性质：

1. 确定性：任何一个对象，要么是这个集合的元素，要么不是。

2. 互异性：集合中不允许出现重复的元素。

3. 无序性：我们不考虑集合中元素的顺序。

4. 多样性：集合中的元素可以是任意的对象，相互独立，不要求一定要具备明显的相同特征。

集合的常见定义：

1. 空集（empty set）：一个没有任何元素的集合，记作 $\emptyset$，$\varnothing$ 或 $\{\}$，空集是唯一的，并且是任何集合的子集。

2. 全集（univerasal set）：所讨论的对象的全体组成的集合，记作 $E$ 或 $U$。

3. 有限集（finite set）：包含有限个元素的集合，元素数（基数）表示为 $|A|$。

4. 无限集（finite set）：包含无限个元素的集合。

5. 相等集合：当两个集合所包含的元素完全一样，则称这两个集合相等。

6. 子集（subset）：设 $A,B$ 是两个集合，若 $A$ 的元素都是 $B$ 的元素，则称 $A$ 是 $B$ 的子集，也称 $A$ 包含于 $B$，记作 $A\subseteq B$。

7. 真子集（proper subset）：设 $A,B$ 是两个集合，若 $A\subseteq B$ 且 $A\neq B$，则称 $A$ 是 $B$ 的真子集，也称 $A$ 真包含于 $B$，记作 $A\subset B$。

常见的集合表示法：

1. 列举法：将集合中的元素一一列举，或列出足够多的元素以反映集合中元素的特征。

2. 描述法：通过描述集合中元素的共同特征来表示集合：

$$A=\{x|x的特征\}$$

3. 文氏图（又称韦恩图，Venn diagram）:

康托尔的朴素集合论公理

1. 外延公理：
任意两个集合相等，当且仅当它们中的各个元素都是相同的。

2. 抽象公理：
任给一个性质，都有一个满足该性质的对象所组成的集合。

3. 选择公理：
每个集合都有一个选择函数。

康托尔的朴素集合论公理看上去很美好，但是罗素悖论（Russell’s paradox） 的出现推翻了抽象公理，这里不作过多介绍。

集合的运算

1. 交集（intersection）：
设 $A,B$ 是两个集合，所有属于 $A$ 并且属于 $B$ 的元素组成的集合，称为 $A$ 和 $B$ 的交集。

$$A\cap B=\{x|x\in A\wedge x\in B\}$$

2. 并集（union）：
设 $A,B$ 是两个集合，所有属于 $A$ 或属于 $B$ 的元素组成的集合，称为 $A$ 和 $B$ 的并集。

$$A\cup B=\{x|x\in A\vee x\in B\}$$

并集和交集拥有对应的推广运算：

设 $A_1,A_2,\cdots,A_n$ 是 $n$ 个集合，则

$$A_1\cup A_2\cup\cdots\cup A_n\Leftrightarrow\bigcup_{i=1}^nA_i$$

$$A_1\cap A_2\cap\cdots\cap A_n\Leftrightarrow\bigcap_{i=1}^nA_i$$

3. 差集（difference）：
设 $A,B$ 是两个集合，所有属于 $A$ 但不属于 $B$ 的元素组成的集合，称为 $A$ 和 $B$ 的差集。

$$A-B=\{x|x\in A\ 且\ x\notin B\}$$

4. 补集（complement）：
设 $A$ 是一个集合，全集 $E$ 与 $A$ 的差集称为 $A$ 的补集或余集，记作 $\overline A$。

$$\overline A = E - A$$

补集和差集的关系：$A-B=A\cap\overline B$

5. 对称差（symmetric difference）：
设 $A,B$ 是两个集合，则它们的对称差（环和）类似于布尔代数中的异或运算：

$$A\oplus B=(A-B)\cup(B-A)=(A\cup B)-(A\cap B)$$

6. 幂集（power set）：
指的是一个集合的所有子集所组成的新的集合，集合 $A$ 的幂集记作 $\rho(A)$ 或 $2^A$。

定理： 若 $A$ 为有限集，则

$$|\rho(A)|=C_n^0+C_n^1+\cdots+C_n^n=2^n$$

推论 1： $x\in\rho(A)$ 的充要条件为 $x\subseteq A$。

推论 2： 设 $A,B$ 是两个集合，$A\subseteq B$ 的充要条件为 $\rho(A)\subseteq\rho(B)$。

基本运算律：

运算律	公式
幂等律	$A\cap A=A\\ A\cup A=A$
交换律	$A\cap B=B\cap A\\ A\cup B=B\cup A$
结合律	$(A\cap B)\cap C=A\cap(B\cap C)\\ (A\cup B)\cup C=A\cup(B\cup C)$
分配律	$A\cap(B\cup C)=(A\cap B)\cup(A\cap C)\\ A\cup(B\cap C)=(A\cup B)\cap(A\cup C)$
吸收律	$A\cap(A\cup B)=A\\ A\cup(A\cap B)=A$
互补律	$A\cap\overline A=\emptyset\\ A\cup\overline A=E$
De Morgan 律	$\overline{(A\cap B)}=\overline A\cup\overline B\\ \overline{(A\cup B)}=\overline A\cap\overline B$
同一律	$E\cap A=A\\ \emptyset\cup A=A$
零一律	$\emptyset\cap A=\emptyset\\ E\cup A=E$
双重否定律	$\overline{\overline A}=A$

与集合有关的证明

证明集合的包含关系：

利用上面我们所了解的集合基本概念，我们可以尝试证明集合的包含关系，常见的有以下几种证法：

方法一： 利用定义来证明集合的包含关系。

要证明 $A\subseteq B$，首先任取 $x\in A$，再演绎地证出 $x\in B$ 成立。特别地，当 $A$ 是无限集时，因为我们不能对 $x\in A$，逐一地证明 $x\in B$ 成立，所以证明 $x$ 是任取的就至关重要。

方法二： 利用包含关系的传递性。

设法找到一个集合 $T$，满足 $A\subseteq T$ 且 $T\subseteq B$，由包含关系的传递性可得 $A\subseteq B$。

方法三： 利用 $A\subseteq B$ 的等价定义：

$$A\cup B=B\iff A\cap B=A\iff A-B=\emptyset$$

方法四： 利用已知包含式的并、交等运算符得到新的包含式。

例：证明若 $A\cap C\subseteq B\cap C$ 且 $A-C\subseteq B-C$，则 $A\subseteq B$.

证：

$$\begin{aligned} (A\cap C)\cup(A-C)&\subseteq(B\cap C)\cup(B-C)\\ (A\cap C)\cup(A\cap\overline C)&\subseteq(B\cap C)\cup(B\cap\overline C)\\ A\cap(C\cap\overline C)&\subseteq B\cap(C\cap\overline C)\\ A\cap E&\subseteq B\cap E\\ A&\subseteq B \end{aligned}$$

方法五： 反证法：

例：证明若 $A\cap C\subseteq B\cap C$ 且 $A-C\subseteq B-C$，则 $A\subseteq B$.

证：若不然，则有 $x\in A$ 且 $x\notin B$，
若 $x\in C$，则 $x\in A\cap C$ 但 $x\notin B\cap C$，与 $A\cap C\subseteq B\cap C$ 矛盾；
若 $x\notin C$，则 $x\in A-C$ 但 $x\notin B-C$，与 $A-C\subseteq B-C$ 矛盾，
因此 $A\subseteq B$.

证明集合的相等关系：

方法一： 利用定义来证明集合的相等关系。

若 $A,B$ 是有限集，证明 $A=B$ 可通过逐一比较两集合所有元素均一一对应相等；若 $A,B$ 是无限集，通过证明集合包含关系的方法证 $A\subseteq B\wedge B\subseteq A$ 即可。

方法二： 反证法。

方法三： 利用集合算律和集合等式。

利用集合的基本算律以及已证明的集合等式，通过相等变换将待证明的等式左（右）边的集合化到右（左）边的集合，或者两边同时相等变换到同一集合。

二元关系

有序对与笛卡尔积

在介绍二元关系之前，我们首先来了解一下有序n元组（ordered n-tuples），按一定顺序依次给出 $n$ 个客体 $x_1,x_2,\cdots,x_n$，由它们组成有序n元组 $(x_1,x_2,\cdots,x_n)$，通俗点说——有序n元组就是将顺序作为属性一部分的集合。

两个有序n元组 $(x_1,x_2,\cdots,x_n)$ 与 $(y_1,y_2,\cdots,y_n)$ 相等的充要条件是对任意 $i\in\{1,2,\cdots,n\}$，皆有 $x_i=y_i$。元素相同但次序不同的有序n元组一般是不相等的。

对于有序n元组，当 $n=2$ 时，将其称作有序二元组，也称作有序对或序偶。若 $a\neq b$，则 $(a,b)\neq(b,a)$，两个有序对 $(a,b)$ 和 $(b,a)$ 相等的充要条件是 $a=c,b=d$。

笛卡尔积：

有了有序对的概念，接下来我们引入一种新的运算，称作笛卡尔积或直积，下面这种运算被称作二元笛卡尔积：

$$A\times B=\{(x,y)|x\in A\wedge y\in B\}$$

同理还有三元笛卡尔积等等：

$$A\times B\times C=\{(x,y,z)|x\in A\wedge y\in B\wedge z\in C\}$$

下面我们所说的笛卡尔积皆为二元笛卡尔积。

笛卡尔积有以下性质：

1. 若 $|A|=m,|B|=b$，则 $|A\times B|=|A|\times|B|=mn$
2. 对任意集合 $A$，有 $A\times\emptyset=\emptyset$，$\emptyset\times A=\emptyset$
3. 笛卡尔积不满足交换律，即 $A\times B\neq B\times A$。
4. 笛卡尔积不满足结合律，即 $(A\times B)\times C\neq A\times(B\times C)$。
5. 直积运算对并和交运算满足分配律：

$$A\times(B\times C)=(A\times B)\cup(A\times C)\\ (B\cup C)\times A=(B\times A)\cup(C\times A)\\ A\times(B\cap C)=(A\times B)\cap(A\times C)\\ (B\cap C)\times A=(B\times A)\cap(C\times A)$$

6. 设 $A,B,C,D$ 是集合，若 $A\subseteq C$ 且 $B\subseteq D$，则 $A\times B\subseteq C\times D$。

关系的定义

设 $A_1,A_2,\cdots,A_n$ 是 $n$ 个集合，集合 $A_1\times A_2\times\cdots\times A_n$ 的一个子集 $F$ 称为 $A_1,A_2,\cdots,A_n$ 上的一个 $\bm n$ 元关系。

特别地，集合 $A\times B$ 的一个子集 $R$，称为集合 $A$ 与 $B$ 上的一个二元关系，简称为关系。

对于 $x\in A,y\in B$：

• 若 $(x,y)\in R$，则称 $x,y$ 有关系 $R$，记作 $xRy$；
• 若 $(x,y)\notin R$，则称 $x,y$ 没有关系 $R$，记作 $x\cancel Ry$。

$\bm A$ 上的二元关系：

若 $A=B$，则称 $R$ 为 $A$ 上的二元关系。

1. $A\times A$ 的任一子集都是 $A$ 上的一个关系。
2. 若 $|A|=n$，则 $A$ 上的关系又有 $2^{n^2}$ 个。
3. $A$ 上的三种特殊关系：
   空关系：$\emptyset$
   全域关系：$E_A=A\times A$
   恒等关系：$I_A=\{(x,x)|x\in A\}$
4. $\overline R=E_A-R=A\times A-R$

关系的表示法

集合表示法： 直接使用定义，这种表示法便于书写。

例：设 $A=\{1,2,3,4\}$，$A$ 上的一个关系可以表示为

$$R=\{(1,1),(1,2),(1,3),(2,1),(2,2)\}$$

关系矩阵（relation matrix）表示法： 这种表示法便于存储。

给定两个有限集合 $A=\{a_1,\cdots,a_m\},B=\{b_1,\cdots,b_n\}$，$R$ 为 $A$ 与 $B$ 上的一个二元关系，则可以用以下关系矩阵 $M_R=[r_{ij}]_{m\times n}$ 来表示 $R$：

$$\begin{bmatrix} r_{11}&r_{12}&\cdots&r_{1n}\\ r_{21}&r_{22}&\cdots&r_{2n}\\ \vdots&\vdots&&\vdots\\ r_{m1}&r_{m2}&\cdots&r_{mn} \end{bmatrix}$$

其中若 $(a_i,b_j)\in R$，则 $r_{ij}=1$；否则 $r_{ij}=0$.

关系矩阵表示与矩阵的行列对应的集合。

关系图（digraph of relations）表示法： 这种表示法较为直观清晰。

给定两个有限集合 $A=\{a_1,\cdots,a_m\},B=\{b_1,\cdots,b_n\}$，$R$ 为 $A$ 到 $B$ 的一个二元关系。

首先在平面上作 $m$ 个结点代表 $a_1,\cdots,a_m$，再另外作 $n$ 个结点代表 $b_1,\cdots,b_n$.

关系（有向）图常用来表示 $A\times A$ 的子集，即 $A$ 上的关系。令集合 $A$ 中的每个元素对应图中的一个点吗，$A$ 上关系 $R$ 中的每个有序对 $(a,b)$ 在图中表示为有从 $a$ 到 $b$ 的一条有向弧。

关系的运算

关系是集合的一种，所以处理集合的方法对关系都是有效的，因此我们也可以为关系定义一套类似于集合的运算。

1. 关系的交：
对任意 $x,y\in A$，有

$$\begin{aligned} x(R\cap S)y&\iff(x,y)\in R\cap S\\ &\iff(x,y)\in R\ 并且\ (x,y)\in S\\ &\iff xRy\ 并且\ xSy \end{aligned}$$

$$R\cap S=\{(x,y)|x\in A,y\in A,xRy\wedge xSy\}$$

2. 关系的并：
对任意 $x,y\in A$，有

$$\begin{aligned} x(R\cup S)y&\iff(x,y)\in R\cup S\\ &\iff(x,y)\in R\ 或\ (x,y)\in S\\ &\iff xRy\ 或\ xSy \end{aligned}$$

$$R\cup S=\{(x,y)|x\in A,y\in A,xRy\vee xSy\}$$

3. 关系的差：
对任意 $x,y\in A$，有

$$\begin{aligned} x(R-S)y&\iff(x,y)\in R-S\\ &\iff xRy\ 并且\ x\cancel Sy \end{aligned}$$

$$R-S=\{(x,y)|x\in A,y\in A,xRy\wedge x\cancel Sy\}$$

4. 关系的余：
对任意 $x,y\in A$，有

$$\begin{aligned} x\overline Ry&\iff(x,y)\in\overline R\\ &\iff x\cancel Ry \end{aligned}$$

$$\overline R=A\times A-R=\{(x,y)|x\in A,y\in A,x\cancel Ry\}$$

5. 子关系：
设 $R,S$ 是集合 $A$ 上的两个关系，若 $R\subseteq S$，则称 $R$ 为 $S$ 的子关系。

• 从集合的角度：$R$ 是 $S$ 的子集。
• 从关系矩阵的角度：$M_R$ 为 $1$ 的地方，$M_S$ 一定也为 $1$。
• 从关系图的角度：$R$ 关系图中有的弧，$S$ 关系图中一定也有。

6. 逆关系：
设 $R$ 是集合 $A$ 上的一个关系，称 $R^{-1}$ 为 $R$ 的逆关系：

$$R^{-1}=\{(y,x)|x\in A,y\in A,并且\ xRy\}$$

$$xR^{-1}y\iff(x,y)\in R^{-1}\iff yRx$$

• 从集合的角度：将 $R$ 的每个有序对的顺序颠倒过来得到 $R^{-1}$。
• 从关系矩阵的角度：$M_R^{-1}$ 为 $M_R$ 的转置矩阵。
• 从关系图的角度：将 $R$ 关系图中每条有向弧的方向反过来得到 $R^{-1}$ 的关系图。

7. 关系的乘积：
设 $R,S$ 是集合 $A$ 上的两个关系，称 $R\cdot S$ 为关系 $R$ 和 $S$ 的乘积或合成：

$$R\cdot S=\{(x,y)|x\in A,y\in A,并且存在\ z\in A\ 使得\ xRz,zSy\}$$

• 对 $A$ 上任意的关系 $R$，有

$$R\cdot I_A=I_A\cdot R=R$$

• 从关系矩阵的角度：若对 $\{0,1\}$ 中的元素的加法使用逻辑加，则对 $A$ 上的任意关系 $R,S$，都有：

$$M_{R\cdot S}=M_R\cdot M_S$$

• 从关系图的角度：将 $R,S$ 关系图中由两条方向一致的弧连接起来的元素改为用一条弧连接。

例：证明 $(R\cdot S)\cdot T\subseteq R\cdot(S\cdot T)$

证：任取 $(x,y)\in(R\cdot S)\cdot T$，即 $x(R\cdot S)\cdot Ty$，
由关系乘积的定义可知，存在 $z\in A$ 使得

$$x(R\cdot S)z,\quad zTy$$

同样对 $x(R\cdot S)z$，存在 $z'\in A$ 使得

$$xRz',\quad z'Sz$$

故由 $z'Sz$ 和 $zTy$ 可知 $z'(S\cdot T)y$，
又由 $xRz'$ 得 $xR\cdot(S\cdot T)y$，即 $(x,y)\in R\cdot(S\cdot T)$，
又因为 $(x,y)\in(R\cdot S)\cdot T$，综上所述，原式成立。

8. 关系的幂：
由于关系的乘法运算满足结合律，因此可以用“幂”表示集合 $A$ 上同一个关系的乘积，有：

$$R^n=\underbrace{R\cdot R\cdot\cdots\cdot R}_{n\times R}$$

关系的幂满足如下定义：

$$\left\{\begin{aligned} &R^0=I_A\\ &R^{n+1}=R^n\cdot R,\quad n\in N \end{aligned}\right.$$

关系的幂具有以下基本性质：

• 设 $R$ 是 $A$ 上的关系，$m,n$ 为任意自然数，有

$$R^m\cdot R^n=R^{m+n}\\ (R^m)^n=R^{mn}$$

• 设集合 $A$ 的元素数为 $n$，$R$ 是 $A$ 上的二元关系，那么存在自然数 $i,j\ (0\leq i<j\leq 2^{n^2})$ 使得 $R^i=R^j$.

• 设 $R$ 是集合 $A$ 上的关系，若存在自然数 $i,j\ (i<j)$，使得 $R^i=R^j$，则有

$$R^{i+k}=R^{j+k},\quad k\in N\\ R^{i+kp+m}=R^{i+m},\quad k,m\in N,p=j-i$$

证明：$R^{i+kp+m}=R^{i+m}$，其中 $k,m\in N,p=j-i$

$$\begin{aligned} R^{i+kp+m}&=R^{i+(j-i)+(k-1)(j-i)+m}=R^{j+(k-1)(j-1)+m}\\ &=R^{i+(k-1)(j-i)+m}=R^{i+(j-i)+(k-2)(j-i)+m}\\ &=R^{j+(k-2)(j-i)+m}=R^{i+(k-2)(j-i)+m}\\ &\ \ \vdots\\ &=R^{i+(j-i)+m}=R^{j+m}=R^{i+m} \end{aligned}$$

特殊关系

1. 自反关系（reflexive）：
集合 $A$ 上有关系 $R$，对于每一个 $x\in A$，都有 $xRx$.

• $R$ 是自反的 $\iff$ $I_A\subseteq R$ $\iff$ $R^{-1}$ 是自反的
• 从关系矩阵的角度：$M_R$ 的主对角线元素都为1。
• 从关系图的角度：$R$ 的关系图中每一点均有到自身的弧。

2. 反自反关系（irreflexive）：
集合 $A$ 上有关系 $R$，对于每一个 $x\in A$，都有 $x\cancel Rx$.

• $R$ 是反自反的 $\iff$ $I_A\cap R=\emptyset$
• 从关系矩阵的角度：$M_R$ 的主对角线元素都为0。
• 从关系图的角度：$R$ 的关系图中每一点均没有到自身的弧。

3. 对称关系（symmetric）：
集合 $A$ 上有关系 $R$，如果 $xRy\ (x\in A,y\in A)$，都有 $yRx$.

• $R$ 是对称的 $\iff$ $R^{-1}=R$
• 从关系矩阵的角度：$M_R$ 为对称矩阵。
• 从关系图的角度：$R$ 的关系图中不同的两点间若有弧相连，则必定是成对出现的。

4. 反对称关系（antisymmetric）：
集合 $A$ 上有关系 $R$，如果 $xRy,yRx$，则必有 $x=y$；或者说，如果 $xRy,x\neq y$，则必有 $y\cancel Rx$.

• $R$ 是反对称的 $\iff$ $R\cap R^{-1}\subseteq I_A$
• 从关系矩阵的角度：$M_R$ 中以主对角线为对称的元素都不同时为1。
• 从关系图的角度：$R$ 的关系图中任意两个不同点之间的有向弧都不成对出现。

5. 传递关系（transitive）：
集合 $A$ 上有关系 $R$，对于 $x\in A,y\in A,z\in A$，如果 $xRy,yRz$，则必有 $xRz$.

• $R$ 有传递性 $\iff$ $R^2\subseteq R$
• 从关系矩阵的角度：如果 $M_{R^2}$ 中某元素 $s_{ij}=1$，那么 $M_R$ 相应位置元素 $r_{ij}$ 也一定为1.
• 从关系图的角度：$R$ 的关系图中的任意三点 $a,b,c$，若存在 $a$ 到 $b$ 的有向弧，$b$ 到 $c$ 的有向弧，则必然存在 $a$ 到 $c$ 的有向弧。

关系名称	拥有的特殊关系
空集上的空关系 $\emptyset$	自反、反自反、对称、反对称、传递
非空集合上的空关系 $\emptyset$	反自反、对称、反对称、传递
恒等关系 $I_A\ (|A|>0)$	自反、对称、反对称、传递
全域关系 $E_A\ (|A|>1)$	自反、对称、传递

关系的闭包

所谓闭包，指的就是对原关系的序偶进行一些扩充，使得原关系满足某种特殊性质，并且要求对原关系的改动最小化。

设 $A$ 是非空集合，$R$ 是 $A$ 上的二元关系。称 $R'$ 是 $R$ 的自反/对称/传递闭包，$R'$ 满足：

1. $R'$ 是自反/对称/传递的。
2. $R\subseteq R'$
3. 对 $A$ 上的任意关系 $R''$，若 $R\subseteq R''$，且 $R''$ 是自反/对称/传递的，则必有 $R'\subseteq R''$.

$R$ 的自反/对称/传递闭包分别记作 $r(R),s(R),t(R)$，称此处的 $r,s,t$ 为闭包运算。

闭包定理：

1. $r(R)=I_A\cup R$
2. $s(R)=R\cup R^{-1}$
3. $\displaystyle t(R)=\bigcup_{i=1}^\infty R^i$ （直到 $R^i$ 为空集为止）

等价关系与等价类

设 $A$ 是一个非空集合，$R$ 是 $A$ 上的二元关系。如果 $R$ 同时具有自反、对称、传递性，则称 $R$ 是一个等价关系（equivalence relation），通常记作 $\cong$。

设 $A$ 是一个非空集合，$R$ 是 $A$ 上的等价关系。$A$ 的一个非空子集 $M$ 叫作关于 $R$ 的一个等价类，其满足

1. 若 $a\in M,b\in M$，则 $aRb$
2. 若 $a\in M,b\notin M$，则 $a\cancel Rb$
   或 $a\in M,aRb$，则 $b\in M$

可以将等价类看作是拥有某一共同特征的元素组成的集合，等价关系即为集合中的元素所拥有的关系。

通常，用 $[a]_R$ 表示包含元素 $a$ 的等价类，$a$ 称为该等价类的代表元：

$$[a]_R=\{x|(x,a)\in R\}$$

定理1： 设 $\cong$ 是非空集合 $A$ 上的等价关系，于是等价类是存在的。

证明：任取 $a\in A$，令 $M=\{x|x\in A\ \text{并且}\ x\cong a\}$，

（1）显然，$a\in M$，$M$ 非空。

（2）任取 $x_1\in M,x_2\in M$，则有 $x_1\cong a,x_2\cong a$，而 $\cong$ 具有对称性和传递性，所以 $x_1\cong x_2$.

（3）任取 $x_1\in M$，若 $x_1\cong y$，则由 $x_1\cong a$，$\cong$ 具有对称性和传递性，可得 $y\cong a$，所以 $y\in M$.

综上所述，可以认为 $M$ 为关于 $\cong$ 的一个等价类。

定理2： 设 $\cong$ 是非空集合 $A$ 上的等价关系，$M_1,M_2,\cdots$ 是 $A$ 中关于 $\cong$ 的所有等价类，则有

$$A=M_1\cup M_2\cup\cdots$$

并且

$$M_i\cap M_j=\emptyset\quad(i\neq j)$$

换句话说，集合 $A$ 上的等价关系把 $A$ 分成了互不相交的等价类。

证明：

任取 $M_i,M_j,i\neq j$，假设 $M_i\cap M_j\neq\emptyset$，则必然存在 $x\in M_i\cap M_j$.
任取 $a\in M_i$，$b\in M_j$，都有 $a\cong M_i$，$b\cong M_j$，所以 $a\cong b$，即 $M_i=M_j$，产生矛盾，
所以 $M_i\cap M_j=\emptyset$

任取 $a\in A$，令 $M=\{x|x\in A\ \text{并且}\ x\cong a\}$，由定理1可知，$M$ 是一个等价类，故必然存在 $k$，使得 $M_k=M$，
因为 $a\in M$，所以 $a\in M_1\cup M_2\cup\cdots\cup M_k\cup\cdots$，即 $A\subseteq M_1\cup M_2\cup\cdots$
又易得 $M_1\cup M_2\cup\cdots\subseteq A$，
所以 $A=M_1\cup M_2\cup\cdots$

划分与商集

称集合 $A$ 的子集族 $C$ 为 $A$ 的划分（partition），如果满足以下条件：

1. 若 $B\in C$，则 $B\neq\emptyset$
2. $\displaystyle\bigcup_{B\in C}B=A$
3. 对任意的 $B$，$B'\in C$，若 $B\neq B'$，则 $B\cap B'=\emptyset$

则称 $C$ 中元素为划分的单元，或划分块。

我们规定，$A=\emptyset$ 时只有划分 $\emptyset$。

设 $R$ 是非空集合 $A$ 上的等价关系，以 $R$ 的所有不同等价类为元素作成的集合称为 $A$ 关于 $R$ 的商集（quotient set），简称 $A$ 的商集，记作 $A/R$。

划分和等价关系能由以下定理联系在一起：

1. 设 $A$ 为非空集合，$R$ 为 $A$ 上的任意一个等价关系，则对应的商集 $A/R$ 恰为 $A$ 的一个划分。
2. 设 $A$ 为非空集合，$C$ 为 $A$ 的任意一个划分，令 $R_C=\{(x,y)|x,y\in A\ \text{并且}\ x,y\ \text{属于}\ C\ \text{的同一划分块}\}$，则 $R_C$ 为 $A$ 上的等价关系。

$I_A,E_A,R_{ij}$ 均为等价关系，并且用它们划分集合 $A$ 可以得：

$$\begin{aligned} A/I_A&=\left\{ \{ a_1 \},\{ a_2 \},\cdots,\{ a_n \} \right\}\\ A/E_A&=\left\{ \{ a_1,a_2,\cdots,a_n \} \right\}\\ A/R_{ij}&=\left\{ \{ a_i,a_j \},\{ a_{k_1} \},\{ a_{k_2} \},\cdots,\{ a_{k_{n-2}} \} \right\} \end{aligned}$$

其中 $k_1,k_2,\cdots,k_{n-2}$ 均不等于 $i$ 或 $j$，共有 $C_n^2$ 个这样的关系 $R_{ij}$。

等价关系 $\bm\Rightarrow$ 商集：
关键：求出该等价关系下集合 $A$ 的每个元素所在的等价类。

例：$A=\{a,b,c\}$，$A$ 的一个等价关系 $I_A$，求 $A/I_A$。

$$\begin{aligned} &I_A=\{(a,a),(b,b),(c,c)\}\\ &[a]_{I_A}={a},[b]_{I_A}={b},[c]_{I_A}={c}\\ &A/I_A=\left\{\{ a\},\{b\},\{c\}\right\} \end{aligned}$$

商集 $\bm\Rightarrow$ 等价关系：
关键：$R=I_A\cup\{(),(),\cdots\}$

例：$A=\{a,b,c\}$，$A$ 的一个商集 $A/R=\left\{\{a\},\{b,c\}\right\}$，求对应的等价关系 $R$。

$$\begin{aligned} R&=\{(a,a),(b,b),(c,c),(b,c),(c,b)\}\\ &=I_A\cup\{(b,c),(c,b)\} \end{aligned}$$

划分的加细：

设 $C$ 和 $C'$ 都是集合 $A$ 的划分，若 $C$ 的每个划分块都包含于 $C'$ 的某个划分块中，则称 $C$ 是 $C'$ 的加细（refinement）。

定理： $C$ 是 $C'$ 的加细当且仅当 $R_C\subseteq R_{C'}$.

第二类斯特林（Stirling）数：

第二类斯特林数用于研究将元素划分成若干集合，每个集合非空的方案数，因此又称斯特林子集数。用 $\begin{Bmatrix}n\\m\end{Bmatrix}$ 表示将 $n$ 个元素划分成 $m$ 个集合，读作 $n$ 子集 $m$。

我们能发现第二类斯特林数的几个特例：

$$\begin{Bmatrix}n\\0\end{Bmatrix}=0,\begin{Bmatrix}n\\1\end{Bmatrix}=1,\begin{Bmatrix}n\\2\end{Bmatrix}=2^{n-1}-1,\begin{Bmatrix}n\\n-1\end{Bmatrix}=C_n^2,\begin{Bmatrix}n\\n\end{Bmatrix}=1$$

考虑若 $n$ 个元素要形成 $m$ 个集合，第 $n$ 个元素要么单独成一个集合，要么放入前 $n-1$ 个元素构成的 $m$ 个集合中的一个，可以写出如下递推关系式：

$$\begin{Bmatrix}n\\m\end{Bmatrix}=m\begin{Bmatrix}n-1\\m\end{Bmatrix}+\begin{Bmatrix}n-1\\m-1\end{Bmatrix}$$

利用第二类斯特林数求集合的划分个数：
设集合 $A$ 有 $n$ 个元素，则其划分个数为：

$$\begin{Bmatrix}n\\1\end{Bmatrix}+\begin{Bmatrix}n\\2\end{Bmatrix}+\cdots+\begin{Bmatrix}n\\n\end{Bmatrix}$$

序关系

偏序关系：

设 $R$ 是集合 $A$ 上的一个关系，如果 $R$ 具有自反性、反对称性、传递性，则称 $R$ 为一个偏序关系（partial ordering relation），或半序关系，部分序关系，通常写为 $\leq$。

集合 $A$ 在偏序关系 $R$ 下做成一个偏序集（partial ordered set，poset），或半序集，部分序集，记作 $(A,R)$。

一个偏序集的子集仍为偏序集，并且

$$(A,R)\Rightarrow(B,R\cap(B\times B)),\quad B\subseteq A$$

证明：

（1）$R\cap(B\times B)$ 是自反的：

任取 $x\in B$，则 $(x,x)\in B\times B$，由 $x\in B$，$B\subseteq A$，可得 $x\in A$，又因为 $R$ 是 $A$ 上的自反关系，所以 $(x,x)\in R$.
因此，$(x,x)\in R\cap(B\times B)$，即 $R\cap(B\times B)$ 是自反的。

（2）$R\cap(B\times B)$ 是反对称的：

若 $(x,y)\in R\cap(B\times B)$，$(y,x)\in R\cap(B\times B)$，则 $(x,y)\in R$ 而且 $(y,x)\in R$.
因为 $R$ 是反对称的，所以 $x=y$，即 $R\cap(B\times B)$ 也是反对称的。

（3）$R\cap(B\times B)$ 是传递的：

若 $(x,y)\in R\cap(B\times B)$，$(y,z)\in R\cap(B\times B)$，则 $(x,y)\in R$，$(y,z)\in R$，由 $R$ 有传递性可知，$(x,z)\in R$.
另外，$(x,y)\in B\times B$，$(y,z)\in B\times B$，显然 $B\times B$ 是 $B$ 的全域关系 $E_B$，则 $(x,z)\in B\times B$.
因此 $(x,z)\in R\cap(B\times B)$，即 $R\cap(B\times B)$ 是传递的。

全序关系：

设 $(A,\leq)$ 是一个偏序集，对任意 $x,y\in A$，如果 $x\leq y$ 或 $y\leq x$，则称 $x$ 与 $y$ 可比；否则称 $x$ 与 $y$ 不可比。一个偏序集的子集，其中任意两个元素都可比，则称该子集为一条链。

如果 $(A,\leq)$ 本身就是一条链，则称此处的“$\leq$”为全序关系（totally ordering relation），称 $(A,\leq)$ 为全序集（totally ordered set）。

一个偏序集的子集不一定为偏序集，但也满足

$$(A,R)\Rightarrow(B,R\cap(B\times B)),\quad B\subseteq A$$

拟序关系：

设 $R$ 是集合 $A$ 上的一个关系，如果 $R$ 具有反自反性、传递性，则称 $R$ 为一个拟序关系（quasi-ordering relation），通常写为 $<$。

拟序关系隐含了反对称性。

证明：

若 $R=\emptyset$，则 $R$ 具有反自反性、传递性，并且具有反对称性。

若 $R\neq\emptyset$，任取 $(x,y)\in R$，即 $xRy$，因为 $R$ 具有反自反性，所以 $x\neq y$。
假设 $R$ 不具有反自反性，则存在 $x,y$ 使得 $xRy,yRx$，又由传递性可得 $xRx$，与反自反性相矛盾。
因此，对任意 $xRy$ 都没有 $yRx$，即 $R$ 是反对称的。

哈斯图（Hasse diagram）：

哈斯图以平面上的点代表偏序集中的元素：

若两元素 $x\leq y$，且 $x\neq y$，则

1. 将 $x$ 画在 $y$ 的下面。
2. 若没有不同于 $x,y$ 的元素 $z$，使得 $x\leq z\leq y$（$y$ 覆盖 $x$），则将 $x,y$ 用直线连接。

设 $(A,\leq)$ 是一个偏序集，则

1. 如果 $A$ 中有一个元素 $a$，对于所有的 $x\in A$，都有 $x\leq a\ (a\leq x)$，则称 $a$ 为集合 $A$ 的最大元（最小元）。
2. 如果 $A$ 中除了元素 $a$ 自身，不存在 $x\in A$，使得 $a\leq x\ (x\leq a)$，则称 $a$ 为集合 $A$ 的极大元（极小元）。
3. 对于 $A$ 的子集 $M$，如果存在 $a\in A$，使得对任意 $m\in M$，都有 $m\leq a\ (a\leq m)$，则称 $a$ 为子集 $M$ 的上界（下界）。
4. 对于 $A$ 的子集 $M$，如果存在一个 $M$ 的上界 $a$，对于 $M$ 的任意上界 $x$，都有 $a\leq x$，则称 $a$ 为子集 $M$ 的上确界。
5. 对于 $A$ 的子集 $M$，如果存在一个 $M$ 的下界 $a$，对于 $M$ 的任意上下界 $x$，都有 $x\leq a$，则称 $a$ 为子集 $M$ 的下确界。

定理： 设 $(A,\leq)$ 是一个偏序集，并且 $B\subseteq A$，则

1. 若 $b$ 为 $B$ 的最大元（最小元），则 $b$ 必为 $B$ 的上确界（下确界）。
2. 若 $b$ 为 $B$ 的上界（下界），且 $b\in B$，则 $b$ 必为 $B$ 的最大元（最小元）。
3. 若 $B$ 有上确界（下确界），则其上确界（下确界）唯一。

映射

设 $A,B$ 是两个集合，若对 $A$ 的每个元素 $a$，规定了 $B$ 的一个确定元素 $b$ 与之对应，则称此对应为 $A$ 到 $B$ 内的一个映射（mapping），记作 $\sigma$，并且

$$\sigma(a)=b$$

$b$ 称为 $a$ 的像（image），$a$ 称为 $b$ 的原像（pre-image），集合 $A$ 称为映射 $\sigma$ 的定义域（domain），$\sigma$ 的值域也称为像的集合，表示为

$$\sigma(A)=\{b|\sigma(a)=b,\forall a\in A\}$$

显然，$\sigma(A)$ 是 $B$ 的子集。

映射的关系定义法： 设 $A,B$ 是两个集合，$\sigma$ 是 $A$ 到 $B$ 的关系。如果对任意 $a\in A$，都有 $B$ 中唯一的 $b$，满足 $(a,b)\in\sigma$，则称 $\sigma$ 为 $A$ 到 $B$ 内的一个映射。

设集合 $A$ 拥有 $m$ 个元素，集合 $B$ 拥有 $n$ 个元素，则集合 $A$ 到集合 $B$ 恰好有 $n^m$ 个映射。

映射的分类

1. 满射：
设 $\sigma$ 是 $A$ 到 $B$ 内的映射（$|A|\geq|B|$），如果 $B$ 中每一个元素都一定是 $A$ 中某元素的像，则称 $\sigma$ 是 $A$ 到 $B$ 上的满射（surjective onto）。

2. 单射：
设 $\sigma$ 是 $A$ 到 $B$ 内的映射（$|A|\leq|B|$），如果对任意 $a,b\in A$ 且 $a\neq b$，都有 $\sigma(a)\neq\sigma(b)$，则称 $\sigma$ 是 $A$ 到 $B$ 的单射（injection）。

3. 双射（一一映射）：
设 $\sigma$ 是 $A$ 到 $B$ 内的映射（$|A|=|B|$），如果 $\sigma$ 既是 $A$ 到 $B$ 的满射，又是 $A$ 到 $B$ 的单射，则称 $\sigma$ 为 $A$ 到 $B$ 的双射（bijection），或一一映射（one-to-one correspondence）。

逆映射

设 $A,B$ 是两个集合，$\sigma$ 是 $A$ 到 $B$ 的双射，则 $\sigma$ 的逆关系 $\sigma^{-1}$ 称为 $\sigma$ 的逆映射（inverse mapping）。

对任意 $a\in A$，都有

$$\sigma^{-1}(\sigma(a))=a$$

推论： 设 $A,B$ 是两个集合，$\sigma$ 是 $A$ 到 $B$ 的双射，则 $\sigma^{-1}$ 是 $B$ 到 $A$ 的双射。

交集的逆映射满足：

$$\sigma^{-1}(A\cap B)\subseteq\sigma^{-1}(A)\cap\sigma^{-1}(B)$$

映射的乘积

设 $\sigma$ 是集合 $A$ 到集合 $B$ 内的映射，$\tau$ 是集合 $B$ 到集合 $C$ 内的映射，称 $\tau\cdot\sigma$ 为映射 $\tau$ 与 $\sigma$ 的乘积，即对任意 $a\in A$，有

$$(\tau\cdot\sigma)(a)=\tau(\sigma(a))$$

映射的乘积满足结合律，但是不满足交换律。

$$(\sigma\cdot(\tau\cdot\rho))(x)=((\sigma\cdot\tau)\cdot\rho)(x)=\sigma(\tau(\rho(x)))$$

将集合 $M$ 中元素映射到自身的变换称为恒等映射（identity mapping）
，记作 $I$。如果 $\tau\cdot\sigma=\sigma\cdot\tau=I$，则 $\tau,\sigma$ 均为双射，并且 $\tau=\sigma^{-1}$.

集合的可数性

基数

基数（cardinal number），是在集合论中被用于刻画任意集合大小的一个概念，也称为集合的势。设 $A,B$ 为两集合，若 $A$ 与 $B$ 之间存在双射，则称 $A$ 与 $B$ 基数相同（对等，等势或等浓），记作 $|A|=|B|$.

• 当集合 $A$ 为有限集时，它的基数为非负整数，且与集合 $A$ 的元素个数相等。

• 把自然数集合的基数记作阿列夫零 $\aleph_0$，凡是与自然数集合等势的集合 $A$，其基数 $|A|=\aleph_0$.

集合的等势关系是一个等价关系。集合按照等势关系分成等价类，每个等价类的共同的数量特征，称为该等价类中集合的基数。

集合基数的不对等关系 $\leq$ 是一个偏序关系。若 $A$ 与 $B$ 的某一子集有一一对应关系，则 $|A|\leq |B|$；若 $A$ 与 $B$ 的某一真子集有一一对应关系（即 $A$ 与 $B$ 没有一一对应关系），则 $|A|<|B|$.

基数的三歧性定理（trifideity theorem）：
对任意集合 $A,B$，或者 $|A|<|B|$，或者 $|A|=|B|$，或者 $|B|<|A|$，同时只能有一个式子成立。

康托尔-伯恩斯坦定理（Cantor-Bernstein theorem）：
若存在 $A$ 的子集 $A'$ 和 $B$ 的子集 $B'$，使得 $|A|=|B'|$ 且 $|B|=|A'|$，则 $|A|=|B|$.
即若 $|A|\leq|B|$ 且 $|B|\leq |A|$，则 $|A|=|B|$.

可数集合

一个集合，如果它的元素为有限个，或者它的元素与自然数集合之间存在双射，则称此集合为可数集合。否则称该集合为不可数集合。元素不是有限的可数集合称为可数无穷集合。

藉由定义，我们可以得到集合 $A$ 为可数无穷集合的充要条件：集合 $A$ 中的元素可排列为 $A=\{a_1,a_2,\cdots,a_n,\cdots\}$，即可以将其元素编号。

定理：

• 设 $A_1,A_2,\cdots,A_n,\cdots$ 是可数无穷多个可数集合的序列，则 $\displaystyle\bigcup_{i=1}^\infty A_i$ 是可数集合。即可数无穷多个可数集合的并集仍是可数集合。

• 设 $A,B$ 是可数无穷集合，则 $A\times B$ 仍是可数集合。
  推论：若 $A_1,A_2,\cdots,A_n$ 是可数集合，则 $A_1\times A_2\times\cdots\times A_n$ 仍是可数集合。

• 可数集合的子集仍为可数集合。

• 有理数集合 $\mathbb Q$ 是可数集合。

• 实数集 $\mathbb R$，区间 $(a,+\infty)$、$[a,b]$、$[a,b)$、$(a,b]\ (a\neq b)$ 等都是不可数的，且与区间 $(0,1)$ 和 $[0,1]$ 等势，将其基数记为 $c$。

• 设 $A_1,A_2,\cdots,A_n,\cdots$ 是互不相交的集合序列，它们的基数都是 $c$，则 $\displaystyle\bigcup_{i=1}^\infty A_i$ 的基数也是 $c$。即可数（无穷）个基数为 $c$ 的集合的并集基数仍为 $c$。

证明 $(0,1)$ 区间内的实数不可数：

假设我们可以将 $(0,1)$ 区间内的数排成一个序列：

$$\begin{cases} P_1=0.a_{11}a_{12}a_{13}\cdots\\ P_2=0.a_{21}a_{22}a_{23}\cdots\\ P_3=0.a_{31}a_{32}a_{33}\cdots\\ \quad\vdots\\ P_k=0.a_{k1}a_{k2}a_{k3}\cdots a_{kk}\cdots\\ \quad\vdots \end{cases}$$

考虑下面的数：

$$0.r_1r_2\cdots r_k\cdots\quad(k=1,2,\cdots)$$

其中

$$r_k=\begin{cases} 1&a_{kk}\neq 1\\ 2&a_{kk}=1\\ \end{cases}$$

显然，这个数是 $(0,1)$ 区间内的数，但却无法放进我们所构造的序列中。对序列中的任意一个数 $0.a_{k1}a_{k2}a_{k3}\cdots a_{kk}\cdots$，因为 $r_k\neq a_{kk}$，所以

$$0.a_{k1}a_{k2}a_{k3}\cdots a_{kk}\cdots\neq 0.r_1r_2\cdots r_k\cdots$$

与我们的假设产生矛盾，所以 $(0,1)$ 区间内的实数不可数。

判断可数集合的方法：

1. 按照可数集合的定义，若 $A$ 为有限集，则 $A$ 一定是可数集合，否则若 $A$ 与自然数集之间存在双射，则 $A$ 是可数集合。

2. 若 $A$ 与某可数集合之间存在双射，则 $A$ 是可数集合。

3. 若 $A$ 中所有元素都可以按照某种规律进行排序，则 $A$ 是可数集合。

4. 若 $A$ 是 $n\ (n>1)$ （或可数无限个）个可数集合的并集，则 $A$ 是可数集合。

5. 若 $A$ 是某个已知可数集合的子集，则 $A$ 是可数集合。

6. 若 $A$ 是 $n\ (n>1)$ 个可数集合的笛卡尔积，则 $A$ 是可数集合。

康托尔定理（Cantor’s theorem）：
集合 $A$ 的幂集的基数大于 $A$ 的基数。

证明：

假设 $\sigma$ 为 $A$ 到 $\rho(A)$ 上的满射，令

$$B=\{x\mid x\in A\wedge x\notin\sigma(x)\}$$

显然，$B\subseteq A$，于是，存在唯一一个元素 $b\in A$，使得 $\sigma(b)=B$.

若 $b\in B$，则 $b\notin\sigma(b)=B$，产生矛盾；
若 $b\notin B$，因为 $\sigma(b)=B$，所以 $b\notin\sigma(b)$，则 $b\in B$，产生矛盾。

综上所述，不存在 $A$ 到 $\rho(A)$ 上的满射，所以

$$|A|<|\rho(A)|$$

连续统问题

我们可以构造基数任意大的集合，如 $|\mathbb R|<|\rho(\mathbb R)|<\cdots$

按照基数的大小可以排列为：

$$0,1,2,\cdots,n,\cdots,\aleph_0,\aleph_1,\aleph_2,\cdots$$

所谓连续统问题（continuum hypothesis），即已知 $\aleph_0<c$，问 $\aleph_1<c$ 是否成立？
换句话说就是：能否找到一实数集的子集，它是不可数集合，但又不能与实数集合建立一一对应。

连续统假设为 $\aleph_1=c$.

连续统假设无法在目前已有的集合论公理下被证明或证伪。