离散数学概念整理（一）：数理逻辑
发布于 2025年11月11日 14:49
命题逻辑
基本等价式
| 编号 | 等价式 | 名称 |
|---|---|---|
| 1 | $\neg \neg A \Leftrightarrow A$ | 双重否定 |
| 2 | $A \land B \Leftrightarrow B \land A$ | 交换律 |
| $A \lor B \Leftrightarrow B \lor A $ | ||
| 3 | $ (A \land B) \land C \Leftrightarrow A \land (B \land C)$ | 结合律 |
| $(A \lor B) \lor C \Leftrightarrow A \lor (B \lor C) $ | ||
| 4 | $A \land (B \lor C) \Leftrightarrow (A \land B) \lor (A \land C)$ | 分配律 |
| $A \lor (B \land C) \Leftrightarrow (A \lor B) \land (A \lor C) $ | ||
| 5 | $\neg(A \land B) \Leftrightarrow \neg A \lor \neg B$ | 德·摩根定律 |
| $\neg(A \lor B) \Leftrightarrow \neg A \land \neg B $ | ||
| 6 | $ A \Leftrightarrow A \lor A$ | 等幂律 |
| $A \Leftrightarrow A \land A$ | ||
| 7 | $A \land T \Leftrightarrow A$ | 同一律 |
| $A \lor F \Leftrightarrow A$ | ||
| 8 | $A \land F \Leftrightarrow F$ | 零律 |
| $A \lor T \Leftrightarrow T$ | ||
| 9 | $A \land (A \lor B) \Leftrightarrow A$ | 吸收律 |
| $A \lor (A \land B) \Leftrightarrow A$ | ||
| 10 | $ A \lor \neg A \Leftrightarrow T$ | 互补律 |
| $A \land \neg A \Leftrightarrow F $ | ||
| 11 | $A \rightarrow B \Leftrightarrow \neg A \lor B$ | 条件式转换律 |
| 12 | $A \leftrightarrow B \Leftrightarrow (A \rightarrow B) \land (B \rightarrow A) \Leftrightarrow (A \land B) \lor (\neg A \land \neg B)$ | 双条件式转化律 |
| $\lnot A \leftrightarrow B \Leftrightarrow \lnot (A \leftrightarrow B)$ | ||
| 13 | $(A \land B) \rightarrow C \Leftrightarrow A \rightarrow (B \rightarrow C) $ | 输出律 |
| 14 | $ (A \rightarrow B) \land (A \rightarrow \lnot B) \Leftrightarrow \lnot A$ | 归谬律 |
基本蕴含式
| 编号 | 蕴含式 | 名称 |
|---|---|---|
| 1 | $A \land B \Rightarrow A$ | 化简式 |
| 2 | $A \land B \Rightarrow B$ | 化简式 |
| 3 | $A \Rightarrow A \lor B$ | 附加式 |
| 4 | $ A \Rightarrow B \rightarrow A$ | 附加式变形 |
| 5 | $B \Rightarrow A \rightarrow B$ | 附加式变形 |
| 6 | $\neg(A \rightarrow B) \Rightarrow A$ | 化简式变形 |
| 7 | $\neg(A \rightarrow B) \Rightarrow \neg B$ | 化简式变形 |
| 8 | $A \land (A \rightarrow B) \Rightarrow B$ | 假言推论 |
| 9 | $\lnot B \land (A \rightarrow B) \Rightarrow \neg A$ | 拒取式 |
| 10 | $\lnot A \land (A \lor B) \Rightarrow B$ | 析取三段论 |
| 11 | $ (A \rightarrow B) \land (B \rightarrow C) \Rightarrow A \rightarrow C$ | 条件三段论 |
| 12 | $ (A \leftrightarrow B) \land (B \leftrightarrow C) \Rightarrow A \leftrightarrow C$ | 双条件三段论 |
| 13 | $(A \rightarrow B) \land (C \rightarrow D) \land (A \land C) \Rightarrow B \land D$ | 合取构造二难 |
| 14 | $(A \rightarrow B) \land (C \rightarrow D) \land (A \lor C) \Rightarrow B \lor D$ | 析取构造二难 |
| $(A \rightarrow B) \land (C \rightarrow B) \land (A \land C) \Rightarrow B$ | 二难推论 | |
| $(A \rightarrow B) \land (C \rightarrow B) \land (A \lor C) \Rightarrow B$ | 二难推论 | |
| 15 | $A \rightarrow B \Rightarrow (A \lor C) \rightarrow (B \lor C)$ | 前后件附加 |
| $A \rightarrow B \Rightarrow (A \land C) \rightarrow (B \land C)$ | ||
| 16 | $A, B \Rightarrow A \land B$ | 合取引入 |
对偶式
在给定的仅使用联结词$\lnot, \land, \lor$的命题公式$A$中，若把$\land$和$\lor$互换，$F$与$T$互换而得到一个命题公式$A^$,则称$A^$为$A$的对偶式
对偶定理
$$ \lnot A(P_1, P_2, \cdots, P_n) \Leftrightarrow A^*(\lnot P_1, \lnot P_2, \cdots, \lnot P_n) $$
$$ A(\lnot P_1, \lnot P_2, \cdots, \lnot P_n) \Leftrightarrow \lnot A^*(P_1, P_2, \cdots, P_n) $$
范式
-
析取泛式：设$A_1, A_2, \cdots, A_m$为简单合取式，称$A_1 \lor A_2 \lor \cdots \lor A_m$为析取范式
-
合取范式：设$B_1, B_2, \cdots, B_n$为简单析取式，称$B_1 \land B_2 \land \cdots \land B_n$为析取范式
主析取范式
- 小项：在含有$n$个命题变元的简单合取式中，若每个命题变元与其否定不同时存在，而二者之一出现一次且仅出现一次，则称该简单合取式为小项
- 小项的编码：1为真0为假，转换为十进制
- 小项的性质
- 没有两个小项是等价的
- $m_i \land m_j \Leftrightarrow F, i \neq j$
- $\bigvee_{i=0}^{2^n-1}m_i \Leftrightarrow T$
- 每个小项只有一个成真指派
- 主析取范式：在给定公式的析取范式中，若简单合取式都是小项，则称该范式为主析取范式
主合取范式
- 大项：在含有$n$个命题变元的简单析取式中，若每个命题变元与其否定不同时存在，而二者之一出现一次且仅出现一次，则称该简单析取式为大项
- 大项的编码：1为假0为真，转换为十进制
- 大项的性质
- 没有两个大项是等价的
- $M_i \land M_j \Leftrightarrow T, i \neq j$
- $\bigwedge_{i=0}^{2^n-1}M_i \Leftrightarrow F$
- 每个大项只有一个成假指派
- 主析取范式：在给定公式的合取范式中，若简单析取式都是大项，则称该范式为主合取范式
归结推理
- 采用以下步骤证明$A_1, A_2, \cdots, A_n \vdash C$
- 将$A_1, A_2, \cdots, A_n, \lnot C$化为合取范式
- 取S为上述各合取范式中所有简单析取式对应的子句的集合
- 寻找S的一个反驳，若能找到，则$A_1, A_2, \cdots, A_n \vdash C$，否则$A_1, A_2, \cdots, A_n \not\vdash C$
谓词逻辑
等价式
- $\lnot (\forall x)A \Leftrightarrow (\exists x) \lnot A$
- $\lnot (\exists x)A \Leftrightarrow (\forall x) \lnot A$
- $(\forall x)(A(x) \lor B) \Leftrightarrow (\forall x)A(x) \lor B$
- $(\forall x)(A(x) \land B) \Leftrightarrow (\forall x)A(x) \land B$
- $(\forall x)(A(x) \rightarrow B) \Leftrightarrow (\exists x)A(x) \rightarrow B$
- $(\forall x)(B \rightarrow A(x)) \Leftrightarrow B \rightarrow (\forall x)A(x)$
- $(\exists x)(A(x) \lor B) \Leftrightarrow (\exists x)A(x) \lor B$
- $(\exists x)(A(x) \land B) \Leftrightarrow (\exists x)A(x) \land B$
- $(\exists x)(A(x) \rightarrow B) \Leftrightarrow (\forall x)A(x) \rightarrow B$
- $(\exists x)(B \rightarrow A(x)) \Leftrightarrow B \rightarrow (\exists x)A(x)$
- $(\forall x)(A(x) \land B(x)) \Leftrightarrow (\forall x)A(x) \land (\forall x)B(x)$
- $(\exists x)(A(x) \lor B(x)) \Leftrightarrow (\exists x)A(x) \lor (\exists x)B(x)$
变换规则
- 约束变元改名定理：令$x$在$A(x)$中是自由出现，$y$是不出现在$A(x)$中的个体变元，则有：
- $(\forall x)A(x) \Leftrightarrow (\forall y)A(y)$
- $(\exists x)A(x) \Leftrightarrow (\exists y)A(y)$
- 置换定理：令$A$为含有子公式$A_1$的公式，用公式$B_1$置换$A_1$得到公式$A'$若$A_1 \Leftrightarrow B_1$，则$A \Leftrightarrow A'$
蕴含式
- $(\forall x)A(x) \lor (\forall x)B(x) \Rightarrow (\forall x)(A(x) \lor B(x))$
- $(\exists x)(A(x) \land B(x)) \Rightarrow (\exists x)A(x) \land (\exists x)B(x)$
- $(\forall x)(A(x) \rightarrow B(x)) \Rightarrow (\forall x)A(x) \rightarrow (\forall x)B(x)$
- $(\forall x)(A(x) \rightarrow B(x)) \Rightarrow (\exists x)A(x) \rightarrow (\exists x)B(x)$
- $(\forall x)(\forall y)A(x, y) \Rightarrow (\forall x)A(x. x)$
- $(\exists x)A(x, x) \Rightarrow (\exists x)(\exists y)A(x, y)$
- $(\exists x)(\forall y)A(x, y) \Rightarrow (\forall y)(\exists x)A(x, y)$
公式范式
-
前束范式：一个公式称为前束范式，如果它有如下形式： $$ (Q_1x_1)(Q_2x_2)\cdots(Q_nx_n)B $$ 其中$Q_i (1 \leq i \leq k)$为$\forall$或$\exists$，$B$为不含有量词的公式
-
斯科伦范式：每个存在量词均在全称量词之前，这样的范式称为斯科伦范式
-
$AI$型斯科伦范式：设$A$是一公式，$(Q_1x_1)(Q_2x_2)\cdots(Q_nx_n)M$是与$A$等价的前束范式，其中$M$为合取范式
-
若$Q_k$是存在量词，且它左边没有全称量词，则取异于出现在$M$中所有个体常元的个体常元$c$，并用$c$代替$M$中中所有的$x_i$，然后在首标中删除$(Q_kx_k)$
- 若$Q_{s_1}, Q_{s_2}, \cdots, Q_{s_m}$是所有出现在存在量词$(Q_rx_r)$左边的全称量词$(m \geq 1, 1 \leq s_1 < s_2 < \cdots < s_m < s_r)$，则取异于出现在$M$中所有函数的$m$元函数$f(x_{s_1}, x_{s_2}, \cdots, x_{s_m})$，用$f(x_{s_1}, x_{s_2}, \cdots, x_{s_m})$代替出现在$M$中的所有$x_r$，然后在首标中删除$(Q_rx_r)$
对首标中的所有存在量词做上述处理后，得到一个在首标中没有存在量词的前束范式，称该范式为公式$A$的$AI$型斯科伦范式，其中用来代替$x_k$和$x_r$的那些个体常元和函数统称为公式$A$的斯科伦函数
归结推理
- 采用以下步骤证明$A_1, A_2, \cdots, A_n \vdash C$
- 将$A_1, A_2, \cdots, A_n, \lnot C$化为$AI$型斯科伦范式$B$
- 由$B$的母式找出相应的子句集$S={C_1, C_2, \cdots， C_m}$
- 寻找S的一个反驳，若能找到，则$A_1, A_2, \cdots, A_n \vdash C$，否则$A_1, A_2, \cdots, A_n \not\vdash C$