数理逻辑

tip

逻辑是研究推理的科学，分为形式逻辑和辩证逻辑；数理逻辑使用数学方法研究形式逻辑的科学，又叫符号逻辑；现代数理逻辑有四大分支：

1. 证明论
2. 模型论
3. 递归论
4. 公理化集合论 本章介绍其共同基础——命题演算和谓词演算，即古典数理逻辑。

命题

tip

一个或真或假而不能两者都是的断言（陈述句），若命题为真，则其 真值 为真；

命题可由命题联结词构成 复合命题，常见的联结词有：

1. 合取词 $\wedge$，表示交集；
2. 析取词 $\vee$，表示并集；
3. 蕴含词 $\to$，$P\to Q$ 表示如果 P，那么 Q，P 是一种前提、假设或前件，Q 是结论或后件；当且仅当 P 真 Q 假，该蕴含式为假；
4. 等值词 $\leftrightarrow$，相当于同或，相同为 1，不同为 0；
5. 否定 $\neg$；

联结词的优先级为 $\neg>\wedge>\vee>\to>\leftrightarrow$。

常见公式：

1. $\neg(P\leftrightarrow Q)=\neg P\leftrightarrow\neg Q$
2. $P\to Q=\neg Q\to \neg P=\neg P \vee Q$
3. $P\leftrightarrow Q \iff(P\to Q) \wedge(Q\to P)\iff(\neg P\vee Q)\wedge(\neg Q\vee P)$
4. $P\leftrightarrow Q \iff (P\wedge Q) \vee(\neg P\wedge \neg Q)$

对偶式

当一个式子中只含有 $\neg,\wedge,\vee$，将 $\wedge\vee$ 互换，真假互换，可以得到另一个式子，这两个式子互为对偶式，若将其中的命题变元也取非，则两式等价。

重言式和矛盾式

$\neg P\vee P \iff T$ 永真式称为重 （chong）言式，$\neg P\wedge P \iff F$ 永假式称为矛盾式；当且仅当 $A\leftrightarrow B$ 时 $A\iff B$ 若 $A\to B\iff T$，则 $A\implies B$，称为重言蕴含，证明方法为：

1. 假设前件为真，若能推出后件也为真，则重言蕴含成立；
2. 假设后件为假，若能推出前件也为假，则成立。 一些基础的重言蕴含式：
3. $P\wedge Q\implies P\ or\ Q$
4. $Q\ or\ P\implies P\vee Q$
5. $\neg P\implies P\to Q$
6. $Q\implies P\to Q$

重言蕴含具有自反性、传递性和反对称性 （$A\implies B,B\implies A$，则 $A\iff B$，这是充分必要条件）。

合取/析取范式

如果命题公式可以等价地写成 只用合取/析取 联结词组成的形式 $A_{1}\wedge A_{2}\cdots A_{n}$，其中 $A_{i}$ 是命题变元，或者是其否定形式的 析取/合取式（刚好相反），则称为 合取/析取范式，如 $P\leftrightarrow Q\iff(P\wedge Q)\vee(\neg P\wedge \neg Q)$ 就是一个析取范式，只含有 $\neg,\wedge,\vee$，并且 $\neg$ 一定在命题变元之前。

info

$P\wedge Q$ 即是合取范式 $(P) \wedge (Q)$，也是析取范式 $(P\wedge Q)$。

主合取/析取范式

极小项：$n$ 个命题元的简单合取式，称作布尔合取或极小项，简称为小项。其中每个命题变元与它的否定不能同时存在，但该命题变元必须 且仅出现一次。

我们为小项使用二进制进行编码，如 $\neg P\wedge\neg Q$，编码为 $m_{00}$，一直到 $P\wedge Q$ 编码 $m_{11}$，由 n 个命题变元便有 n 位二进制；列出其真值表，可以发现，只有命题变元的真值和编码相对应，小项的真值才为真，如 $P\wedge Q$ 对应的 $m_{11}$，则只有 $P=1,Q=1$ 才能使小项为真。 因此，全体小项的析取式是永真式。

主析取范式 中的每个分式都是小项；若某式子却少某个命题变元如 $R$，可以合取一个永真式 $R\vee\neg R$，再使用分配率整理；或者使用真值表法，直接求出真值为 1 对应的小项，析取即可。

极大项，与小项类似，但是采用析取，并且编码刚好相反，$0$ 表示变元本身，$1$ 表示其否定形式，如 $M_{00}$ 对应 $P\vee Q$，并且与小项编码有对应关系 $M_{i}\iff \neg m_{i}$；只有与编码对应的变元为 $0$，大项真值才为 $0$，如 $M_{00}$ 对应 $P=0,Q=0$，使得 $M_{00}=0$；全体大项的合取式是永假式。

主合取范式 总的每个分式都是大项；同样的，若某个式子缺项，则析取一个永假式 $R\wedge\neg R$，再使用分配率整理；或者使用真值表法，通过真值为 0 的情况求出对应的大项，再合取。

info

如果知道了主析取范式 $A(P,Q,R)$ 中有如下小项：$m_{1},m_{3},m_{5},m_{7}$，即这些情况其值为真，而 $m_{0},m_{2},m_{4},m_{6}$ 使 $A$ 为假，则其主合取范式也就是 $M_{0}\wedge M_{2}\wedge M_{4}\wedge M_{6}$。

tip

还有 主抑或范式 和 主等值范式，因为对于任意的两个不同的极小项，不可能同时为真，因此析取就可以写为抑或 $\oplus$；同理，任意不同的极大项不可能同时为假，则合取就可以写为等值 $\leftrightarrow$。

命题逻辑推理

tip

推理就是根据某几个已知的条件和前提，得出一个新的判断的过程，实际上推理的过程就是证明 永真蕴含式 的过程；具体的，我们引入两个规则：

1. P 规则，推理过程中可以随时引入前提；
2. T 规则，若前面有几个公式重言蕴含某公式 S，则可以将 S 纳入推理过程。

常用公式：

直接推理

直接推理就是利用上述前提直接推理得到有效结论的方法。

间接推理

条件论证：将要证明的结论中的前件作为 附加前提，一起推出后件；条件论证基于 $CP$ 规则（$Conditional\ Proof$），若 $H_{1}\wedge\cdots H_{n}\wedge R\implies S$，则 $H_{1}\wedge \cdots H_{n}\implies R\to S$，证明过程转换为析取，重新将 R 和 S 结合皆可；

不相容定义：对于任意数量的命题公式，对于其中的所有命题变元，若有 指派（即为命题变元赋值）使得所有命题公式的合取为真，则称其相容，否则称其为不相容，即所有指派都不能使其合取为真。

由此引出 反证法，若要证明 $H_{1}\wedge\cdots H_{n}\implies C$ ，只要证明 $H_{1}\wedge\cdots H_{n}\wedge \neg C$ 不相容即可。

谓词逻辑

info

命题逻辑并不能完整表述所有命题之间的联系，如：

1. 所有金属都是导电的；
2. 铜是金属；
3. 铜是导电的。

命题逻辑不能有 1 和 2 推出 3，因为 1 和 2 内部是存在关系的，但是无法用命题逻辑表述。

为此，引入了谓词的概念

个体/客体

能够独立存在的具体的或抽象的事物，通常用 小写字母 表示，分为个体常量，表示某一个特定的或具体的个体，以及个体变元，泛指某一个个体。

谓词

表示个体属性或个体关系的词，称为谓词，使用 大写字母，如 $S:$ 是大学生，$a:$ 小张，则命题小张是大学生可以表示为 $S(a)$；当然谓词括号内可以是多个个体，含有 $n$ 个 个体变元 的谓词被称为 $n$ 元谓词，不带个体变元的谓词称为 $0$ 元谓词（可以带个体常量）。

当谓词是常项时，0 元谓词是命题；若是变项，是命题变元。

命题函数

tip

含有 $n$ 个变元的命题函数是以个体域为定义域，真假为值域的 $n$ 元函数。

个体域默认就是所有个体，是最大的个体域。

caution

命题函数并不是命题，只有将具体个体传入其中或用足够量词约束才是命题。

量词

在命题中对个体量化的词被称为 量词，如 所有的 大学生都是人，这里的所有的就是量词。

量词可以分为存在量词 $\exists$ 和全称量词 $\forall$，量词后的变元是量词的 指导变元。

如所有的自然数都是整数，设 $I(x)$ 表示 $x$ 是整数，个体域为所有自然数，则

$$\forall x(l(x))$$

若不指定个体域，则默认全体个体，可以设 $N(x)$ 表示 $x$ 是自然数，修改命题为：

$$\forall x(N(x)\to l(x))$$

info

每个人都有一个生母 的命题是？

答案

若设个体域是人，$M(x,y)$ 表示 $y$ 是 $x$ 的生母，则 $\forall x\exists y(M(x,y))$；若使用默认个体域，添加 $P(x)$ 表示 $x$ 是人，则 $\forall x(P(x)\to\exists y(P(y)\wedge M(x,y)))$

对于全称量词，其特性谓词（用于限制域的）常做蕴含前件；存在量词的特性的特性谓词常做合取项。

量词前面也可以加 $\neg$，$\neg \exists x(A(x))\iff\forall \neg x(A(x))$，反之亦然。

量词的作用域（辖域）：紧跟量词后面的括号；若其中包含自由变元，则可以拿出来，或者将外面的自由变元放进来，达到扩充与收缩辖域的效果，有两个比较反直觉的公式：

1. $\forall xA(x)\to B\iff \exists x(A(x)\to B)$
2. $\exists xA(x)\to B\iff \forall x(A(x)\to B)$

证明过程将蕴含化简为析取。

自由变元和约束变元：前者不受量词约束，后者不然；$n$ 元谓词添加 $k$ 个量词，则变为了 $n-k$ 元谓词，若无自由变量，谓词公式则变为一个命题。

自由变元换元，将和约束变量相同名称的自由变元换成谓词公式中不存在的名称。

tip

如何使用量词表示唯一，如每个自然数都有唯一的后继数。

答案

令 $A(x,y)$ 表示 $y$ 是 $x$ 的后继数，$E(x,y)$ 表示相等，取个体域为自然数，则

$

\forall x\exists y(A(x,y)\to \exists z(A(x,z)\to E(y,z)))

$

消去量词，可以通过

量词分配，全称量词和合取分配，存在量词和析取分配，而：

1. $\exists x(A(x)\wedge B(x))\implies \exists xA(x)\wedge \exists xB(x)$，前者是两个相同的 x，后者只是同名，前者范围小于后者，则前者可以推出后者；
2. $\forall xA(x)\vee \forall xB(x)\implies \forall x(A(x)\vee B(x))$；
3. $\exists x(A(x)\to B(x))\iff \forall xA(x)\to \exists xB(x)$；
4. $\exists xA(x)\to\forall xB(x)\implies\forall x(A(x) \to B(x))$。

前束范式

所有量词前都没有连接词，并且都在公式最前面，辖域覆盖整个公式，就是 前束范式；求解步骤一般是：

1. 消去连接词 $\to,\leftrightarrow$，便于辖域扩充
2. 将 $\neg$ 后移；
3. 对变元进行换名，为辖域扩充做准备；
4. 提取量词。

谓词演算推理理论

全称特指规则（Universal Specialization, US），如 $\forall xA(x)\implies A(c)$，$c$ 表示任意指定的个体，这里的个体满足原式为真；

存在特指规则（Existential Specialization, ES），如 $\exists xA(x)\implies A(c)$，$c$ 表示能使原式为真的 某个个体；

存在推广规则（Existential Generalization, EG），$A(c)\implies \exists xA(x)$；

存在推广规则（Universal Generalization, UG），$A(c)\implies \ xA(x)$；

caution

存在特指一般在全称特指之前进行，因为可能需要指定为同一个个体，若先进行全称特指，则其范围太大，可能不包含后续的存在特指。