离散数学的学习笔记，包含数理逻辑、集合论、图论

因为实际写作时间是很久之前了，有些图过期了，我也不知道补什么…

有些公式渲染有问题，日后无聊再来改了（

数理逻辑

命题逻辑

联结词

汇总

真值表

定义联结词的优先次序为：$\neg,\land,\lor,\rightarrow, \leftrightarrow$

等价公式

定义

两个命题公式 $A,B$ 真值表完全相同，则称二者 等价，记为 $A \iff B$

常用的等价公式

重言式和蕴含式

定义

• 重言式：无论对分量作怎样的真值指派，真值均为 $T$ 的命题公式
• 矛盾式（永假式）：……真值均为 $F$ 的命题公式
• 蕴含式：当且仅当 $P \rightarrow Q$ 为重言式时，称 $P$ 蕴含 $Q$，记作 $P \implies Q$
  • 对于 $P \rightarrow Q$ ， $Q \rightarrow P$ 称为其 逆换式， $\neg P \rightarrow \neg Q$ 称为其 反换式， $\neg Q \rightarrow \neg P$ 称为其 逆反式

定理

命题公式 $A, B$ 等价的充要条件： $A \leftrightarrow B$ 为重言式 或 $P \implies Q$ 且 $Q \implies P$

证明蕴含式

对于 $P \implies Q$ ，满足以下其一：

1. 假定 $P$ 真值为 $T$ ，若由此能推出 $Q$ 的真值为 $T$
2. 假定 $Q$ 真值为 $F$，若由此能推出 $P$ 的真值为 $F$

则 $P \implies Q$ 成立

蕴含的性质

• 对于 $P \implies Q$ ，若 P 为重言式，则 Q 必为重言式
• 蕴含关系式可传递的
• 若 $P \implies Q$ 且 $P \implies R$ 则 $P \implies (Q \land R)$
• 若 $P \implies Q$ 且 $R \implies Q$ 则 $(P \lor R) \implies Q$

最小联结词组

$\{\neg,\lor\}$ 或 $\{\neg,\land\}$ 或 $\{\uparrow\}$ 或 $\{\downarrow\}$

对偶与范式

定义

• 对偶式： 对于命题公式 $A$ ， 将其中所有的 $\land$ 与 $\lor$ 互换，$\uparrow$ 与 $\downarrow$ 互换，$T$ 与 $F$ 互换， 得到新的命题公式 $A^*$ 则称 $A^*$ 与 $A$ 互为对偶式
• 合取范式： 一个命题公式具有形式：$A_1 \land A_2 \land \dots \land A_n$ 时称其为 合取范式
• 析取范式： 一个命题公式具有形式：$A_1 \lor A_2 \lor \dots \lor A_n$ 时称其为 析取范式
• 小项： $n$ 个命题变元的合取式， 每个变元与其否定不能同时出现，且必须出现且仅出现一次
• 大项： $n$ 个命题变元的析取式， 每个变元与其否定不能同时出现，且必须出现且仅出现一次
• 主析取范式： 仅由小项析取所组成的公式
• 主合取范式： 仅有大项合取所组成的公式
• 编码： 对于一个命题变元 $P$ ，$P, \neg P$ 分别记为 $0, 1$ 则对于每个小项/大项可以用二进制编码表示 如 $P \land \neg Q \land R$ 可以表示为 $m_{010}$
• 编码表示主析取/合取范式： 主析取范式可以表示为 $\sum_{i_1, i_2, \dots, i_m}$ 主合取范式可以表示为 $\prod_{j_1, j_2, \dots, j_n}$ 其中的 $i_k$ 为第 $k$ 个小项的二进制编码的十进制数 其中的 $j_k$ 为第 $k$ 个大项的二进制编码的十进制数

求合取/析取范式步骤

1. 将公式中的联结词化为 $\neg,\land,\lor$
2. 利用 德摩根律 将 $\neg$ 移到各个命题变元之前
3. 利用 分配律、结合律 将公式归约为合取/析取范式

求主合取/主析取范式步骤

1. 化归为合取/析取范式
2. 除去合取/析取范式中所有为永真/假的合取/析取项
3. 合并相同的合取/析取项和所有相同的变元
4. 对合取/析取项补入没有出现的命题变元，然后用分配律展开公式

定理

• $\neg A(P_1, P_2, \dots, P_n) \iff A^*(\neg P_1,\neg P_2, \dots, \neg P_n)$
• 若 $A \iff B$ 则 $A^* \iff B^*$
• 任意两个不同的小项的合取式永假
• 全体小项的析取式永真
• 任意两个不同的大项的析取式永真
• 全体大项的合取式永假

推理理论

定义

• 前提、有效结论： 对于命题公式 $H_1,H_2, \dots, H_n, C$ ， 当且仅当 $H_1 \land H_2 \land \dots \land H_n \implies C$， 称 $C$ 是 一组前提 $H_1,H_2, \dots, H_n$ 的 有效结论
• $P$ 规则： 前提在推导过程中的任何时候都可以引入使用
• $T$ 规则： 在推导中，如果有一个或多个公式蕴含着公式 $S$ ，则 $S$ 可以引入推导中

真值表法

1. 列出 $H_1,H_2, \dots, H_n, C$ 的所有对应真值
2. 找出 $H_1,H_2, \dots, H_n$ 全为 $T$ 的行，若这几行对应的 $C$ 也有真值 $T$ 则推理成立

或者

2. 找出 $C$ 为 $F$ 的行， 若这几行对应的 $H_1,H_2, \dots, H_n$ 至少有一个真值为 $F$ 则推理成立

直接证法

例题： 证明 $(P \lor Q) \land (P \rightarrow R) \land (Q \rightarrow S) \implies S \lor R$

解：

注：括号内仅为注释，实际书写中无括号内的内容

间接证法

归谬法

对于要证明 $H_1 \land H_2 \land \dots \land H_n \implies C$ 的情况，

只需要证明 $H_1 \land H_2 \land \dots \land H_n \land \neg C \iff F$，

其中 $\neg C$ 称为 附加条件

例题： 证明：$A \rightarrow B, \neg(B \lor C)$ 可逻辑推出 $\neg A$

解：

$CP$ 规则

对于要证明 $H_1 \land H_2 \land \dots \land H_n \implies R \rightarrow C$ 的情况，

只需要证明 $H_1 \land H_2 \land \dots \land H_n \land R \iff C$，

其中 $R$ 称为 附加条件

例题： 证明：$A \rightarrow (B \rightarrow C), \neg D \lor A, B$ 重言蕴含 $D \rightarrow C$

解：

谓词逻辑

谓词

将 $A(a_1, a_2, \dots, a_n)$ 中的 $A$ 称为 $n$ 元谓词

例如 $A$ 表示“是大学生”，$a$ 表示“张三”，

则 $A(a)$ 表示“张三是大学生”，其中 $A$ 为 一元谓词

命题函数

由一个谓词和一些客体变元组成的表达式，称为 简单命题函数

例如 $L(x, y, z)$

量词

用于划定论域的标记称作量词，

$\forall x, \exists x$ 分别表示 “所有的 $x$”、“存在一些 $x$”

例如：

1. 设 $M(x):x是人，H(x):x要呼吸$ 则 $(\forall x)M(x)\rightarrow H(x)$ 表示 “所有人都是要呼吸的”
2. 设 $P(x):x是质数$ 则 $(\exists x)(P(x))$ 表示 “存在一个数是质数”
3. 设 $M(x):x是人，R(x):x是聪明的$ 则 $(\exists x)M(x)\land(R(x))$ 表示 “一些人是聪明的”

谓词公式与翻译

例题： 数学分析中的极限定义为：仍给一个小正数 $\epsilon$ ，则存在一个正数 $\delta$ ，使得当 $0 < |x - a| < \delta$ 时，有 $|f(x) - b| < \delta$，此时称 $\lim\limits_{x\to a}f(x) = b$

解：

设 $P(x, y):x~大于~y,~~~~Q(x,y):x~小于~y$

则 $\lim\limits_{x\to a}f(x) = b$ 可以表示为：

变元的约束

约束变元的换名

通过对谓词公式换名，使得每个变元在公式中仅以一种约束形式出现

例题： 对 $(\forall x)(P(x) \rightarrow R(x, y)) \land Q(x,y)$ 换名

解： 可换名为 $(\forall z)(P(z) \rightarrow R(z, y)) \land Q(x,y)$

自由变元的代入

例题： 对 $(\forall x)(P(y) \land R(x, y))$ 代入

解： 代入后公式为 $(\forall x)(P(z) \land R(x, z))$

若论域的元素是有限的，如论域元素为 $a_1, a_2, \dots, a_n$，则

谓词演算的等价式和蕴含式

量词与联结词 $\neg$ 的关系

有关量词的等价式

有关量词的蕴含式

多元谓词的等价/蕴含式

前束范式

定义

• 前束范式： $(\square v_1)(\square v_2)\dots(\square v_n)A$
• 前束合取范式： $(\square v_1)(\square v_2)\dots(\square v_n)[(A_{11}\lor A_{12} \lor \dots\lor A_{1l_1})\land(A_{21}\lor A_{22} \lor \dots\lor A_{2l_2})\land\dots\land(A_{m1}\lor A_{m2} \lor \dots\lor A_{ml_m})]$
• 前束析取范式： $(\square v_1)(\square v_2)\dots(\square v_n)[(A_{11}\land A_{12} \land \dots\land A_{1l_1})\lor(A_{21}\land A_{22} \land \dots\land A_{2l_2})\lor\dots\lor(A_{m1}\land A_{m2} \land \dots\land A_{ml_m})]$

例题： 将 $D:(\forall x)[(\forall y)P(x) \lor (\forall z)q(z, y) \rightarrow \neg (\forall y)R(x, y)]$ 化为前束合取范式

解：

谓词演算的推理理论

例题： 证明 $(\forall x)(H(x) \rightarrow M(x)) \land H(s) \iff M(s)$

解：

集合论

集合

集合的概念及表示

定义

• 子集（包含）： 若有 $(\forall x)(x \in A \rightarrow x \in B)$ 则称 $A$ 为 $B$ 的子集 或 $A$ 包含在 $B$ 内， 记作 $A \subseteq B$

  • 包含关系具有自反性、传递性

• 真子集： 若有 $(\forall x)(x \in A \rightarrow x \in B) \land (\exists x)(x \in B \land x \not\in A)$ 则称 $A$ 是 $B$ 的真子集， 记作 $A \subset B$

• 空集： 不包含任何元素的集合，记作 $\varnothing$

  • $\varnothing \ne \{\varnothing\}, \varnothing \in \{\varnothing\}$

• 全集： 在一定范围内，若所有集合均为某一个集合的子集， 则该集合称为 全集，记作 $E$

• 幂集： 给定集合 $A$ ，由 $A$ 的所有子集为元素组成的集合， 称为集合 $A$ 的 幂集，记作 $\mathscr{P}(A)$

• 编码表示幂集：

  $$例如:设~S = \{a, b, c\},~ 则 \\ \mathscr{P}(S) = \{S_i|i \in J\}, \\ J = \{i|i是二进制数且 000 \le i \le 111\}，\\ 其中~S_{000}=\varnothing$$

定理

• 集合 $A,B$ 相等的充要条件为：二者互为子集
• 对于任意一个集合 $A$ ，$\varnothing \subseteq A$
• 给定一个有 $n$ 个元素的集合 $A$ ，则 $\mathscr{P}(A)$ 有 $2^n$ 个元素

集合的运算

定义

• 交集 $\cap$：

  $$S = A \cap B = {x|(x \in A) \land (x \in B)}$$

  $S$ 称为 $A$ 和 $B$ 的 交集

• 并集 $\cup$：

  $$S = A \cup B = {x|(x \in A) \lor (x \in B)}$$

  $S$ 称为 $A$ 和 $B$ 的 并集

• 补集 $-$：

  $$S = A - B = \{x|x\in A \land x \not\in B\} = A \cap \sim B = A - (A \cap B)$$

  $S$ 称为 $B$ 对于 $A$ 的补集

  • $E-A$ 称为 $A$ 的 绝对补，记作 $\sim{A}$

• 对称差 $\oplus$：

  $$\begin{align} S = A \oplus B &= \{x|x \in A \bar\lor x \in B\} \\ &= (A - B) \cup (B - A) \\ &= (A \cap \sim B) \cup (B \cap \sim A) \\ &= (A \cup B) - (A \cap B) \end{align}$$

  $S$ 称为 $A$ 和 $B$ 的 对称差

定理

• 公式

  $$\begin{align} 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 \cup (A \cap B) &= A \\ A \cap (A \cup B) &= A \\ \sim (A \cup B) &= \sim A \cap \sim B \\ \sim (A \cap B) &= \sim A \cup \sim B \\ A \cap (B - C) &= (A \cap B) - (A \cap C) \end{align}$$
• $$A \subseteq B \implies \begin{align} &1.~A \cap B = A \\ &2.~A \cup B = B \\ &3.~\sim B \subseteq \sim A \\ &4.~(B - A) \cup A = B \end{align} \\ \\$$

集合的划分与覆盖

定义

• 覆盖： 给定一个集合 $S = \{S_1, S_2, \dots, S_m\}$ 使得 $\bigcup\limits_{i=1}^{m}S_i = A$ 则称 $S$ 为 $A$ 的 覆盖
• 划分： 若 $S$ 是 $A$ 的覆盖的同时，有 $S_i \cap S_j = \varnothing(i\ne j)$ 则称 $S$ 为 $A$ 的 划分
• 交叉划分： 对于一个集合的两种划分 $\{A_1, A_2, \dots, A_r\},\{B_1, B_2, \dots, B_s\}$ ， 所有 $C_k = A_i \cap B_j \ne \varnothing$ 组成的集合，称为是原来两种划分的 交叉划分
• 加细： 给定集合 $X$ 的任意两个划分 $\{A_1, A_2, \dots, A_r\},\{B_1, B_2, \dots, B_s\}$ ， 若对于每一个 $A_j$ 都有 $B_k$ 使得 $A_j \subseteq B_k$ ，则称 $\{A_1, A_2, \dots, A_r\}$ 为 $\{B_1, B_2, \dots, B_s\}$ 的 加细

定理

• 对于同一个集合的两种划分，其交叉划分 仍是 原集合的一种划分
• 两种划分的交叉划分，都是原来两种划分的加细

关系

序偶

定义

• 序偶： 序偶用于表示事物之间的关系，记作 $\langle a_1,a_2,\dots,a_n \rangle$，称为 $n$ 元组

• 笛卡尔乘积/直积：

  $$A \times B = \{\langle x, y \rangle | (x \in A) \land (y \in B)\}$$

  这使得两个元素集合构造出一个序偶集合

  • 由于序偶内的元素顺序不可变，所以 $A \times B \ne B \times A$
  • 由于 $\langle a, \langle b, c \rangle \rangle$ 不是三元组， 所以 $(A \times B) \times C \ne A \times (B \times C)$ ，且前者得到的才是三元组

• 记 $\overbrace{A \times A \times \dots \times A}^n = A^n$

定理

• 对于任意三个集合 $A, B, C$ ，有

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

• 若 $C \ne \varnothing$ 则

  $$A \subseteq B \iff A \times C \subseteq B \times C \iff C \times A \subseteq C \times B$$

• 设 $A, B, C, D$ 为四个非空集合，则

  $$A \subseteq C \land B \subseteq D \iff A \times B \subseteq C \times D$$

关系及其表示

定义

• 关系： 将一个由序偶组成的集合称为一个 关系，记作 $R$ ， $R$ 中的任一序偶 $\langle a, b \rangle$ 可以记作 $\langle a,b \rangle \in R$ 或 $xRy$ 不在 $R$ 中的任一序偶可以记作 $\langle a,b \rangle \not\in R$ 或 $x \not R y$

• 前域、值域、域： $dom~R$ 称为 $R$ 的前域，$ran~R$ 称为 $R$ 的值域， 二者一起称作 $R$ 的域，记作 $FLD~R$

  $$\mathrm{dom}~R = \{x|(\exists y)(\langle x,y \rangle \in R)\} \\ \mathrm{ran}~R = \{y|(\exists x)(\langle x,y \rangle \in R)\} \\ \mathrm{FLD}~R = \mathrm{dom}~R \cup \mathrm{ran}~R$$

• 直积与关系： 对于任一两个集合 $X, Y$ ，二者的直积 $X \times Y$ 的子集 $R$ 称为 $X$ 到 $Y$ 的关系 对于其子集 $X \times Y, \varnothing$ ，分别称为 $X$ 到 $Y$ 的 全域关系 和 空关系

• 恒等关系：

  $$I_X = \{\langle x, x \rangle| x \in X\}$$

  $I_X$ 称为 $X$ 上的 恒等关系

• 关系矩阵： 对于矩阵 $M_R = [r_{ij}]_{m\times n}$ 其中

  $$r_{i,j} = \begin{cases} 1, \langle x_i, y_j \rangle \in R \\ 0, \langle x_i, y_j \rangle \not\in R \end{cases} ~~~~,~i =1, 2, \dots, m;~j = 1, 2, \dots, n.$$

  这样的矩阵称为 $R$ 的 关系矩阵