# Chapter 1 数理逻辑
[TOC]
## Section 1 命题逻辑
### 1-1 命题及其表示法
命题：具有*唯一真值*的*陈述句*
* 原子命题
* 复合命题（分子命题）
> 悖论不是命题，如：我在说谎
真值：T/F
* 命题常量：有确定的真值
* 命题变元：没有确定的真值
### 1-2 命题联结词
* 否定词$\neg p$
| p | $\neg p$ |
|---|----------|
| T | F |
| F | T |
* 合取词 $p \wedge q$
| p | q | $p \wedge q$ |
|---|---|--------------|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
* 析取词 $p \vee q$，又称为可兼或
| p | q | $p \vee q$ |
|:--|:--|:-----------|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
* 单条件联结词（蕴含）$p \rightarrow q$
如果p，则q
p蕴含q
p尽当q
q当且p
| p | q | $p \rightarrow q$ |
|---|---|-------------------|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
**蕴含等值式（蕴含消去）**
**$(p \rightarrow q) \iff( \neg p \vee q)$**
**逆否等值式（Contraposition）**
**$(p \rightarrow q) \iff (\neg q \rightarrow \neg p)$**
* 双条件联结词 $p \rightleftarrows q$
P当且仅当q
| p | q | $p \rightleftarrows q$ |
|---|---|------------------------|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
**$(p \rightleftarrows q) \iff \neg(p \overline{\vee} q)$**
* 命题联结词的优先顺序
$\neg > \wedge > \vee > \rightarrow > \rightleftarrows$
否定 > 析取 > 合取 > 蕴含 > 当且仅当
### 1-3 命题公式与翻译
命题常元：T/F
命题变元：没有确定真值的命题
命题公式：
1. 单个命题变元本身是一个命题公式；
2. 如果$A$是一个命题公式，那么$\neg A$也是命题公式；
3. 如果$A和B$是命题公式，那么$(A\vee B), (A\wedge B), (A \rightarrow B), (A \leftrightarrows B)$都是命题公式；
4. 当且仅当能够有限次应用1，2，3所得到的包含命题变元、联结词和括号的符号串是命题公式
*注：$n个命题变元组成的命题公式共有2^n种真值情况$*
### 1-4 真值表与等价公式
等价$(\iff)$的定义：给定两个命题公式A和B，设$P_1,P_2,\dots,P_n$为所有出现于A和B中的原子变元，若给$P_1,P_2,\dots,P_n$任一组真值指派，A和B的真值都相同，则称A和B是等价的。记作$A \iff B$
**命题定律表**
幂等律：
$P\vee P \iff P$
$P \wedge P \iff P$
分配律：
$P\vee(Q\wedge R)\iff (P\vee Q)\wedge(P\vee R)$
$P\wedge(Q\vee R)\iff (P\wedge Q)\vee(P\wedge R)$
吸收律：
$P\vee(P\wedge Q) \iff P$
$P\wedge(P\vee Q) \iff P$
德摩根律（德摩根定律，De Morgan's laws）:
$\neg(P\vee Q) \iff \neg P \wedge \neg Q$
$\neg(P\wedge Q) \iff \neg P \vee \neg Q$
否定律：
$P\vee \neg P \iff T$
$P \wedge \neg P \iff F$
双箭头联结词等价：
$(P \rightleftarrows Q) \iff (P \to Q) \wedge (Q \to P)$
### 1-5 永真蕴含式
**重言式/永真式**：给定一命题公式，若无论对分量作何指派，其对应的真值永为T，则称该命题公式为重言式或永真式
**矛盾式/永假式**：给定一命题公式，若无论对分量作何指派，其对应的真值永为F，则称该命题公式为矛盾式或永假式
**逻辑等价的重言式判定（Theorem 1-5.3）**: 设A、B为两个命题公式，$A \iff B $当且仅当$A\leftrightarrows B$为一个重言式
*永真蕴含/推出($\Rightarrow$)*：当且仅当$P\to Q$为一个重言式时，称P永真蕴含Q，记作$P\Rightarrow Q$
对$P \to Q$来说
$Q \to P$称为它的反换式；
$\neg P \to \neg Q$称为它的逆换式；
$\neg Q \to \neg P$称为它的逆反换式
**$(P \rightarrow Q) \iff (\neg Q \rightarrow \neg P)$**
**$(Q \rightarrow P) \iff (\neg P \rightarrow \neg Q)$**
>要证$P\Rightarrow Q$，只需证$P\to Q$为一个重言式、
>1. 假设P为真，则去证明Q为真即可
>2. 假设Q为假，则去证明P为假即可
**各常用永真蕴含式集合**：
化简律（Simplification，小推大）：
$P\wedge Q \Rightarrow P$
$P\wedge Q \Rightarrow Q$
***
$\neg P \Rightarrow (P \to Q)$
$Q \Rightarrow P\to Q$
***
$\neg(P\to Q) \Rightarrow P$
$\neg(P\to Q) \Rightarrow \neg Q$
***
**假言推理（肯定前件式，Modus Ponens）**
$P\wedge(P\to Q) \Rightarrow Q$
**拒取式（否定后件式，Modus Tollens）**
$\neg Q \wedge (P\to Q) \Rightarrow \neg P$
***
**析取三段论（Disjunctive Syllogism）**
$\neg P \wedge (P\vee Q) \Rightarrow Q$
***
假言三段论（蕴含传递性，Hypothetical Syllogism）：
$(P\to Q)\wedge(Q\to R) \Rightarrow(P\to R)$
**蕴含式的合取推理**
$(P\to Q)\wedge(R\to S) \Rightarrow(P\wedge R)\to (Q\wedge S)$
$(P\rightleftarrows Q)\wedge (Q\rightleftarrows R) \Rightarrow(P\rightleftarrows R)$
**逻辑等价与双向永真蕴含（Theorem 1-5.4）**: 设P、Q为任意两个命题公式，$P\iff Q$的充分必要条件是$P\Rightarrow Q 且 Q\Rightarrow P$
永真蕴含的性质：
设A、B、C为命题公式
1. 若$A\Rightarrow B$且A是重言式，则B是重言式
2. 若$A \Rightarrow B, B \Rightarrow C, 则 A \Rightarrow C$，即推出关系是*传递*的
3. 若$A\Rightarrow B 且 A\Rightarrow C, 则 A\Rightarrow (B\wedge C)$
4. 若$A\Rightarrow B 且 C\Rightarrow B, 则 (A\vee C)\Rightarrow B$
### 1-6 其他联结词
* 不可兼析取/不可兼或（异或，XOR） $P\overline{\vee}Q$
> 等价 “$\iff$” 的反面
| P | Q | $P\overline{\vee}Q$ |
|---|---|---------------------|
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | F |
**$P\overline{\vee}Q\iff \neg(P\rightleftarrows Q)$**
*不可兼析取的性质：*
设P、Q、R为命题公式
1. $P\overline{\vee}Q \iff Q\overline{\vee}P$
2. $(P\overline{\vee}Q)\overline{\vee}R \iff P\overline{\vee}(Q\overline{\vee}R)$
3. $P\wedge(Q\overline{\vee}R)\iff (P\wedge Q)\overline{\vee}(P\wedge R)$
4. \* $P\overline{\vee}Q\iff (P\wedge \neg Q)\vee(\neg P \wedge Q)$
5. \* $P\overline{\vee}Q\iff \neg(P\rightleftarrows Q)$
6. $P\overline{\vee}P \iff F,\ F\overline{\vee}P \iff P,\ T\overline{\vee}P \iff \neg P$
**Theroem 1-6.1**:
设P、Q、R为命题公式，如果$P\overline{\vee}Q\iff R,\ 则P\overline{\vee}R\iff Q,\ Q\overline{\vee}R\iff P,\ 且P\overline{\vee}Q\overline{\vee}R为一矛盾式$
* 条件否定 $P\xrightarrow{c}Q$
> 蕴含 “$\rightarrow$” 的反面
| P | Q | $P\xrightarrow{c}Q$ |
|---|---|---------------------|
| T | T | F |
| T | F | T |
| F | T | F |
| F | F | F |
**$P\xrightarrow{c}Q\iff \neg(P\to Q)$**
* 与非（NAND） $P\uparrow Q$
> 合取 “$\wedge$” 的反面
| P | Q | $P\uparrow Q$ |
|---|---|---------------|
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | T |
**$(P\uparrow Q)\iff \neg(P\wedge Q)$**
*与非的性质：*
1. $P\uparrow P \iff \neg(P\wedge P)\iff \neg P$
2. $(P\uparrow Q)\uparrow(P\uparrow Q)\iff \neg (P\uparrow Q)\iff P\wedge Q$
3. $(P\uparrow P)\uparrow(Q\uparrow Q)\iff \neg P\uparrow \neg Q \iff \neg(\neg P \wedge \neg Q)\iff P\vee Q$
* 或非（NOR） $P\downarrow Q$
> 析取 “$\vee$” 的反面
| P | Q | $P\downarrow Q$ |
|---|---|-----------------|
| T | T | F |
| T | F | F |
| F | T | F |
| F | F | T |
**$(P\downarrow Q)\iff \neg(P\vee Q)$**
*或非的性质：*
1. $P\downarrow P\iff\neg(P\vee P)\iff \neg P$
2. $(P\downarrow Q)\downarrow(P\downarrow Q)\iff\neg(P\downarrow Q)\iff P\vee Q$
3. $(P\downarrow P)\downarrow(Q\downarrow Q)\iff \neg P \downarrow\neg Q \iff \neg(\neg P \vee \neg Q)\iff P\wedge Q$
*最小联结词组：*$\{\neg,\ \vee\}或\{\neg,\ \wedge\}/\{\uparrow\}或\{\downarrow\}$
### 1-7 对偶与范式
*对偶式*：在给定的命题公式$A$中，将联结词$\vee$与$\wedge$互换，将T与F互换，所得公式$A^*$称为$A$的对偶式
**德摩根推广定理（Theorem 1-7.1，De Morgan）**：设$A和A^*$是对偶式，$P_1, P_2,\dots,P_n$是出现在$A和A^*$中的原子变元，则
$\neg A(P_1, P_2,\dots,P_n)\iff A^*(\neg P_1,\neg P_2,\dots,\neg P_n)$
$A(\neg P_1,\neg P_2,\dots,\neg P_n)\iff\neg A^*(P_1, P_2,\dots,P_n)$
**对偶原理（Theorem 1-7.2）**: 设$P_1, P_2,\dots,P_n$是出现在A和B中的所有原子变元，如果$A\iff B$，则$A^*\iff B^*$
*合取范式（CNF）*：一个命题公式称为合取范式，当且仅当它具有形式：$A_1\wedge A_2 \wedge\cdots\wedge A_n,\ (n\geqslant 1)$，其中$A_1, A_2 , \cdots, A_n$都是由*命题变元*或*其否定*所组成的**析取式**
*析取范式（DNF）*：一个命题公式称为析取范式，当且仅当它具有形式：$A_1\vee A_2 \vee\cdots\vee A_n,\ (n\geqslant 1)$，其中$A_1, A_2 , \cdots, A_n$都是由*命题变元*或*其否定*所组成的**合取式**
**求任何一个命题的合取范式或析取范式**可以通过以下三个步骤：
* Step1. 将公式中所有的联结词化归为$\wedge,\ \vee和\neg$；
* Step2. 利用De Morgan's law将否定符号$\neg$直接移到各个命题变元之前；
* Step3. 利用分配律、结合律将公式化为合取范式或析取范式
*布尔合取/小项（最小项，minterm）*：n个命题变元的合取式，称作布尔合取或小项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次
*布尔析取/大项（最大项，maxterm）*：n个命题变元的析取式，称作布尔析取或大项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次
*E.g.* 两个命题变元P和Q，其小项为$P\wedge Q,\ \neg P\wedge Q,\ P\wedge \neg Q,\ \neg P\wedge \neg Q$，大项类似
*$n个命题变元，共有2^n个小项/大项$*
*小项编码*：设P、Q、R为三个命题变元，则
$m_{000}=\neg P\wedge\neg Q\wedge\neg R$
$m_{100}=P\wedge\neg Q\wedge\neg R$
$m_{010}=\neg P\wedge Q\wedge\neg R$
$m_{001}=\neg P\wedge\neg Q\wedge R$
$\cdots$
$m_{111}=P\wedge Q\wedge R$
共8个
*大项编码*：设P、Q、R为三个命题变元，则
$M_{000}=P \vee Q\vee R$
$M_{100}=\neg P \vee Q\vee R$
$M_{010}=P \vee \neg Q\vee R$
$M_{001}=P \vee Q\vee \neg R$
$\cdots$
$M_{111}=\neg P\vee\neg Q\vee\neg R$
共8个
*小项的性质*：
1. 每个小项当其真值指派与编码相同时，其真值为T，在其余$2^n-1$种指派情况下均为F；
2. 任意两个不同小项的*合取式*永假
E.g. $m_{001}\wedge m_{100}=(\neg P\wedge\neg Q\wedge R)\wedge(P\wedge\neg Q\wedge\neg R)\iff\neg P \wedge P\wedge\neg Q\wedge R\wedge\neg R\iff F$
3. 全体小项的*析取式*为永真：
$\sum\limits_{i=0}^{2^n-1}m_i=m_0\vee m_1\vee\dots\vee m_{2^n-1}\iff T$
*大项的性质*：
1. 每个大项当其指派与编码相同时，其真值为F，在其余$2^n-1$种指派情况下均为T；
2. 任意两个不同大项的*析取式*永真
$M_i \vee M_j \iff T\ (i \ne j)$
3. 全体大项的*合取式*为永假：
$\prod\limits_{i=0}^{2^n-1}M_i=M_0\wedge M_1\wedge\dots\wedge M_{2^n-1}\iff F$
*主析取范式（PDNF）*：对于给定的命题公式，如果有一个*等价公式*，它仅由*小项的析取*所组成，则该等价式称作原式的主析取范式
*主合取范式（PCNF）*：对于给定的命题公式，如果有一个*等价公式*，它仅由*大项的合取*所组成，则该等价式称作原式的主合取范式
**主析取范式的真值表构造定理（Theorem 1-7.3）**: 在真值表中，一个公式的真值为T的指派所对应的小项的析取，即为此公式的主析取范式
**主合取范式的真值表构造定理（Theorem 1-7.4）**: 在真值表中，一个公式的真值为F的指派所对应的大项的合取，即为此公式的主合取范式
**利用基本等价公式求一个命题公式的主析取范式**可以通过以下四个步骤
* Step1. 将命题公式化归为*析取范式*；
* Step2. 除去*析取范式*中所有*永假*的*析取项*；
* Step3. 将*析取式*中重复出现的*合取项*和相同的变元合并；
* Step4. 对*合取项*补添没有出现的命题变元，即添加$\wedge(P\vee\neg P)$,然后应用分配律展开公式
**利用基本等价公式求一个命题公式的主合取范式**可以通过以下四个步骤
* Step1. 将命题公式化归为*合取范式*；
* Step2. 除去*合取范式*中所有*永真*的*合取项*；
* Step3. 将*合取式*中重复出现的*析取项*和相同的变元合并；
* Step4. 对*析取项*补添没有出现的命题变元，即添加$\vee(P\wedge\neg P)$,然后应用分配律展开公式
*注：对于一个命题公式的主析取范式/主合取范式，如果将其命题变元的个数及出现的次序固定后，则此公式的主析取范式/主合取范式就是唯一的*
**总结**：如何判定两个公式等价？
设有两个命题公式P和Q
1. 利用真值表，如果对P和Q中出现的所有原子变元给予任一真值指派，它们的真值都相同，那么P和Q等价；
2. 利用等价定义，如果$P \rightleftarrows Q$为一重言式，那么P和Q等价；
3. $P \iff Q$的充分必要条件是：$P \Rightarrow Q 且 Q\Rightarrow P$
4. 利用主析取范式，如果P和Q二者各自的主析取范式相同，那么P和Q等价
*有效结论*：设A和C式两个命题公式，当且仅当$A\rightarrow C$为一重言式，则$A\Rightarrow C$，称C是A的有效结论，或C可由A逻辑地推出
推广：
设$H_1, H_2, \cdots, H_n, C$是命题公式，当且仅当$H_1 \wedge H_2 \wedge \cdots\wedge H_n\Rightarrow C$，称C是一组前提$H_1, H_2, \cdots, H_n$的有效结论
三种推理方法
1. 真值表法
2. 直接证法
* P规则和T规则
3. 间接证法
* 反证法
* CP规则
*直接证法*：利用一组前提以及公认的推理规则，根据已知的等价或蕴含推演到有效的结论
* P规则：前提在推导过程中的任何时候都可以引入使用
* T规则：在推导中，如果有一个或多个公式，重言蕴含着公式S，则公式S可以引入推导之中
*间接证法*
首先引入*相容*与*不相容*的概念：
假设公式$H_1, H_2, \cdots, H_m$中的命题变元为$P_1, P_2, \cdots, P_n$，对于$P_1, P_2, \cdots, P_n$的一些真值指派，如果能使$H_1, H_2, \cdots, H_m$的真值为T，则称$H_1, H_2, \cdots, H_m$是相容的；如果对$P_1, P_2, \cdots, P_n$的每一组真值指派使得$H_1 \wedge H_2 \wedge \cdots\wedge H_m$的真值均为F，则称公式$H_1, H_2, \cdots, H_m$是不相容的
设$H_1, H_2, \cdots, H_m$为S，现在我们要证$S\Rightarrow C \iff $证明$S\rightarrow C$为一重言式$\iff证明\neg C\rightarrow\neg S$为一重言式$\iff 证明C\vee \neg S$永真$\iff证明S\wedge\neg C永假，即证S与\neg C不相容$
将结论的否定作为前提引入，然后证明它是永假式
*条件证明规则（CP规则，Conditional Proof）*：由$(S\wedge R)\Rightarrow C$，证得$S\Rightarrow(R\rightarrow C)$，称为CP规则，这种规则可以将结论中的R作为附加条件进行证明（特点：结论中出现蕴含式，R就是此蕴含式的前件）![Screenshot 2024-11-18 at 08.29.34]()
## 谓词逻辑
### 1 谓词的概念与表示法
**谓词**：用以刻画客体的*性质*或*关系*的即是谓词
大写字母表示谓词，小写字母表示客体名称
* 简单命题函数：由一个谓词字母和一个非空的客体变元的集合组成的表达式
* 复合命题函数：由一个或n个简单命题函数以及逻辑连接词组合而成的表达式
### 2 命题函数与量词
量词：
1. 全称量词 $\forall$
2. 存在量词 $\exists$
### 3 谓词公式与翻译
1. 谓词公式
在$(\forall x)$中，“是”用$\rightarrow$表示
在$(\exists x)$中，“是”用$\wedge$表示
例：
尽管有人聪明，但未必一切人都聪明
$M(x):x是人，P(x): x是聪明的$
$\Rightarrow \exists x(M(x)\wedge P(x))\wedge \neg(\forall x (M(x)\rightarrow P(x)))$
### 4 变元的约束
1. 自由变元与约束变元
给定$\alpha$是一个谓词公式，其中有一部分公式形式为$(\forall x )P(x)$或$(\exists x)P(x)$。这里$\forall , \exists$后面所跟的$x$叫做量词的*指导变元或作用变元*，$P(x)$叫做相应量词的*作用域或辖域*。在作用域中$x$的一切出现，称为$x$在$\alpha$中的约束出现，$x$也称为被相应量词中的指导变元所约束，即x是约束变元。在$\alpha$中除去约束变元以外所出现的变元称作*自由变元*
> 不是同一个量词后的指导变元，即使它们用了同一个字母，也不代表它们各自作用域中的约束变元是同一个
1. 约束变元的**换名**规则
1. 在换名时要把公式中所有相同的约束变元全部同时改掉
2. 在换名时所用的变元符号在量词作用域内没有出现
2. 自由变元的**代入**规则
1. 在代入时要把公式中所有相同的自由变元全部同时改掉
2. 用以代入的变元与原公式中所有变元的名称不能相同
3. 个体域（客体域）
用特定的集合来表示被约束变元的取值范围
1. 个体域不同，则表示同一命题的谓词公式的形式不同
让$D(x)$表示$x$是要吃饭的，接下来我们想让谓词公式表达“所有人都是要吃饭的”
1. 个体域为：{人}
则$(\forall x)D(x)$
2. 个体域为任意域（全总个体域），则“人”必须先从任意域中分离出来
设$M(x)$表示$x$是人，称$M(x)$为特性谓词
则$\forall x (M(x)\rightarrow D(x))$
2. 个体域不同，则表示同一命题的真值不同
### 5 谓词演算的等价式与蕴涵式
谓词公式的**赋值**：
谓词公式中一般包含命题变元和客体变元，若使用确定的命题或确定的客体取代变元时，就称为对谓词公式进行赋值
$wff$ 的全称为: well-formed formula，合式公式/谓词公式
谓词公式的**等价**：
对于给定的任意两个谓词公式$A$和$B$，假设它们具有相同的个体域$E$，若对$A$和$B$的任意一组变元进行赋值，所得命题的真值相同，则称谓词公式$A$和$B$在$E$上是等价的
谓词公式的**有效性/永真性**：
对于任意给定谓词公式$A$，其个体域为$E$，对于$A$的所有赋值，$A$都为真，则称$A$在$E$上是有效的（永真的）
谓词公式的**可满足性**：
对于谓词公式$A$，如果至少在一种赋值下为真，则称该谓词公式$A$是可满足的
谓词公式的**不可满足性**：
对于谓词公式$A$，如果在所有赋值下都为假，则称该谓词公式$A$是不可满足的
1. 命题公式的推广
当谓词演算中的公式代替命题演算中永真式的变元时，所得的谓词公式即为有效公式
E.g. $(\forall x)(P(x)\rightarrow Q(x))\iff (\forall x)(\neg P(x)\wedge Q(x))$
2. 量词否定律（量词的德摩根律）：量词与$\neg$之间的关系
$\neg(\forall x)P(x)\iff (\exists x)\neg P(x)$
$\neg(\exists x)P(x)\iff (\forall x)\neg P(x)$
> 出现在量词之前的否定，不是否定该量词，而是否定被量化的整个命题
3. 量词作用域的扩张和收缩
量词的作用域中，常有合取项或析取项，如果其中一个为*不含有约束变元的命题*或*含有自由变元的谓词公式*时，则可将该命题/谓词公式移至量词作用域之外，同样地也可将此类命题/谓词公式移至作用域之内
$(\forall x)(A(x)\vee B) \iff ((\forall x)A(x)\vee B)$
$(\forall x)(A(x)\wedge B) \iff ((\forall x)A(x)\wedge B)$
$(\exists x)(A(x)\vee B) \iff ((\exists x)A(x)\vee B)$
$(\exists x)(A(x)\wedge B) \iff ((\exists x)A(x)\wedge B)$
4. 量词分配律：$\{\forall ,\wedge\}$和$\{\exists, \vee \}$等价式
$(\forall x)(A(x)\wedge B(x))\iff (\forall x)A(x)\wedge(\forall x)B(x)$
$(\exists x)(A(x)\vee B(x))\iff (\exists x)A(x)\vee(\exists x)B(x)$
>其中在$A(x)或B(x)$前或整个谓词公式前加$\neg$都可以有相应等价式
5. 常用表2-5.1
$(\forall x)(A(x)\wedge B(x))\iff (\forall x)A(x)\wedge(\forall x)B(x)$
$(\exists x)(A(x)\vee B(x))\iff (\exists x)A(x)\vee(\exists x)B(x)$
\* $(\forall x)A(x) \vee (\forall x)B(x)\Rightarrow (\forall x)(A(x)\vee B(x))$
\* $(\exists x)(A(x)\wedge B(x))\Rightarrow (\exists x)A(x)\wedge (\exists x)B(x)$
***
$\neg(\forall x)A(x)\iff (\exists x)\neg A(x)$
$\neg(\exists x)A(x)\iff (\forall x)\neg A(x)$
***
$(\forall x)(A(x)\vee B) \iff ((\forall x)A(x)\vee B)$
$(\forall x)(A(x)\wedge B) \iff ((\forall x)A(x)\wedge B)$
$(\exists x)(A(x)\vee B) \iff ((\exists x)A(x)\vee B)$
$(\exists x)(A(x)\wedge B) \iff ((\exists x)A(x)\wedge B)$
***
$(\exists x)(A(x)\to B(x))\iff (\forall x )A(x)\to (\exists x)B(x)$
\* $(\exists x)A(x)\to (\forall x)B(x)\Rightarrow (\forall x)(A(x)\to B(x))$
***
$(\forall x)A(x)\to B\iff (\exists x)(A(x)\to B)$
$(\exists x)A(x)\to B\iff (\forall x)(A(x)\to B)$
$B\to (\forall x)A(x)\iff (\forall x)(B\to A(x))$
$B\to (\exists x)A(x)\iff (\exists x)(B\to A(x))$
### 6 前束范式
**前束范式（PNF，Prenex Normal Form）**：
如果一个公式的量词均在开头，而它们的作用域延伸到整个公式的末尾，则称此类公式为前束范式
形如：$(\square v_1)(\square v_2)\cdots(\square v_n)A$
其中：
> 1. $\square$可能是$\forall$或$\exists$
> 2. $v_i(i = 1,2,\cdots,n)是客体变元$
> 3. $A$是*没有量词的*谓词公式
*E.g.* $(\forall x)(\forall y)(\exists z)(Q(x,y)\to R(z)),\dots$
**前束范式存在定理**：任意一个谓词公式，均和一个前束范式等价
**前束合取范式**：
形如：
$(\square v_1)(\square v_2)\cdots(\square v_n)[(A_{11}\vee A_{12}\vee\cdots\vee A_{1l_1})\wedge (A_{21}\vee A_{22}\vee\cdots\vee A_{2l_2})\wedge \cdots \wedge (A_{m1}\vee A_{m2}\vee\cdots\vee A_{ml_m})]$
**前束合取范式存在定理**: 任何一个谓词公式都可转化为与其等价的前束合取范式
**前束析取范式**：
形如：
$(\square v_1)(\square v_2)\cdots(\square v_n)[(A_{11}\wedge A_{12}\wedge\cdots\wedge A_{1l_1})\vee (A_{21}\wedge A_{22}\wedge \cdots\wedge A_{2l_2})\vee \cdots \vee (A_{m1}\wedge A_{m2}\wedge \cdots\wedge A_{ml_m})]$
**前束析取范式存在定理**: 任何一个谓词公式都可转化为与其等价的前束析取范式
转化步骤：
1. 取消多余量词
2. 换名
3. 消去条件连接词
4. 将否定深入
5. 将量词推到左边
### 7 谓词演算的推理理论
四个推理规则：
1. US规则（全称指定规则）
$(\forall x)A(x)\Rightarrow A(c)$
> c是个体域中某个任意客体
2. UG规则（全称推广规则）
$A(c)\Rightarrow (\forall x)A(x)$
> c是个体域中每一个客体
3. ES规则（存在指定规则）
$(\exists x)A(x)\Rightarrow A(c)$
> c是个体域中某个特定的客体
4. EG规则（存在推广规则）
$A(c)\Rightarrow (\exists x)A(x)$
> c是个体域中某个特定的客体