数理逻辑 应试笔记

该笔记是本人于哈尔滨工业大学（深圳）2021 年春季学期「数理逻辑」课程的笔记，最终课程成绩是满分。授课教师为任世军，是本部经验丰富的老教师。

由于笔记是在考前复习时才逐渐整理的，笔记内容偏应试风格，标题顺序也是按照哈工大「数理逻辑」课程一贯的出题模板来的，涵盖了课程所学，主要包括：命题逻辑、三大系统中定理的证明、谓词逻辑。

命题逻辑部分

求(主)析取/合取范式

一般会涉及到三个原子命题，唯一方法——列真值表。

列真值表的顺序可以依照语法分析树。

主合取看 0，主析取看 1，直接写。列真值表一定要反复检查细节。蕴含的前后件不要看反了。

用完备联结词组表示公式

通常最终结果要化为与非式、或非式。

先把原式子中的「蕴含、等价」全换成「与、或、非」。（可以用等价式化简，但没必要，除非很明显的吸收律）

• 与非：

用德摩根律把 \(\lor\) 全消掉，再把 \(\land\) 用

\[ p\land q\Leftrightarrow \lnot \left( p\uparrow q \right) \]

替换，再把所有的 \(\lnot\) 用下式替换，注意此时 p 可能是个很长的式子。 \[ \lnot p\Leftrightarrow p\uparrow p \]

• 或非：

同理，也是消掉另一个符号，再把或替换了，再替换非。

判断逻辑蕴含/逻辑等价的正确性

1. 逻辑蕴含，一般前提会有多个

通常做法是，给前提均指派为真，利用公式法，推出一系列公式，然后推得右边的公式的值恒为 1，则成立。

如果推不到右边，可以先假设右边为 0（反证法），推出左边的值可以均为 1，则不成立。

注意：假设右边为 1 没用，不充分。

2. 逻辑等价，一般是一对一，两边都比较长

理论上可以用真值表，但是语法分析树太长了。

如果可以一眼判断出不成立，那么枚举一个反例也行。

通常做法是，两边利用公式法化简，最后推出的赋值式相等，则对于任意的指派 \(v\)，都有 \(A^v = B^v\)，故成立。

化简过程中，有一些较长的非、蕴含符号可以替换成与非，如： \[ \begin{aligned} \lnot p\rightarrow q\,\,&\text{换成 } p\lor q \\ \lnot \left( p\rightarrow \lnot q \right) \,\,&\text{换成 } p\land q \end{aligned} \] 避免列赋值式太长。

注意：化简到最后可能形式上不相等，这时候可以两个式子联立消项，看最后是不是永真式，如果不是，同样可以举反例（举反例不好直接想到，因此还是要推理，可以先用 PC 的方法变形看看）。

PC 中定理的证明

依次使用以下方法。

1 逆向推理法（直接法）

对待证明定理进行等价转化，转变成熟悉的形式。常用工具：

• 加前件定理3：去相同前件

• 加后件定理4：去相同后件

• 逆否转换：四种情况

• 前件互换定理2：前件移到里面后

• 公理2：提出前件

• 补前件定理：去单个前件，只需证出后件就可以

• 三段论定理8：需要多次加前件、后件时

例题：

1. 二难推理（后面发现用定理18更好做）

\[ \vdash \left( A\rightarrow C \right) \rightarrow \left( \left( B\rightarrow C \right) \rightarrow \left( \left( A\lor B \right) \rightarrow C \right) \right) \]

观察形式，发现三项都有共同后件 \(C\)，则三项全取逆否 \[ \left( \lnot C\rightarrow \lnot A \right) \rightarrow \left( \left( \lnot C\rightarrow \lnot B \right) \rightarrow \left( \lnot C\rightarrow \lnot \left( \left( A\lor B \right) \right) \right) \right) \] 利用公理 2 及 加前件定理可以去掉前件 \(\lnot C\) \[ \lnot A\rightarrow \left( \lnot B\rightarrow \lnot \left( A\lor B \right) \right) \] 再用逆否转换，前件互换等定理即可逆向

类似题： \[ \vdash \left( A\rightarrow C \right) \rightarrow \left( \left( B\rightarrow C \right) \rightarrow \left( \left( \left( A\rightarrow B \right) \rightarrow B \right) \rightarrow C \right) \right) \]

也必须用逆否来做。

2. 作业题5（常规做法是演绎定理，其他都很麻烦）

\[ \vdash \left( A\rightarrow \left( B\rightarrow C \right) \right) \rightarrow \left( \left( C\rightarrow D \right) \rightarrow \left( A\rightarrow \left( B\rightarrow D \right) \right) \right) \]

先前件互换可使得后件两项都含 \(A\) \[ \left( C\rightarrow D \right) \rightarrow \left( \left( A\rightarrow \left( B\rightarrow C \right) \right) \rightarrow \left( A\rightarrow \left( B\rightarrow D \right) \right) \right) \,\, \] 发现去掉前件 \(A\) 后还可以去掉前件 \(B\)

但是再用一次前件互换即可得到定理4的形式 \[ \left( C\rightarrow D \right) \rightarrow \left( \left( B\rightarrow C \right) \rightarrow \left( B\rightarrow D \right) \right) \]

3. 砍头操作

砍头操作有两种办法：将 \[ \left( \lnot A\rightarrow B \right) \rightarrow \left( \left( \lnot A\rightarrow \lnot B \right) \rightarrow A \right) \] 变成 \[ B\rightarrow \left( \left( \lnot A\rightarrow \lnot B \right) \rightarrow A \right) \] 方法一：先添前件（用公理1再分离）变成 \[ B\rightarrow \left( \left( \lnot A\rightarrow B \right) \rightarrow \left( \left( \lnot A\rightarrow \lnot B \right) \rightarrow A \right) \right) \] 再用公理2分离，前件是公理1的形式，后件自然成立，总计要4行

方法二：直接用三段论定理8，因为 \[ B\rightarrow \left( \lnot A\rightarrow B \right) \] 显然成立，用三段论定理8接上，只需要2行，但是要分条件（有可能不允许使用定理8，如作业题PC1）

4. 反公理2（19 年试卷的答案，思路清奇，没用定理18）

\[ \vdash \left( \left( A\rightarrow B \right) \rightarrow \left( A\rightarrow C \right) \right) \rightarrow \left( A\rightarrow \left( B\rightarrow C \right) \right) \]

一开始观察三项前件都有 \(A\)，以为可以用类似二难推理的办法做。

但是！注意到整体的形式是「两项推一项」，与二难推理不同，因此不能用公理2来提出前件，再去掉前件。

观察发现，后件 \(A\to(B\to C)\) 可以用一次前件互换定理，得到 \[ \vdash \left( \left( A\rightarrow B \right) \rightarrow \left( A\rightarrow C \right) \right) \rightarrow \left( B\rightarrow \left( A\rightarrow C \right) \right) \] 此时有共同的后件，可以用加后件定理快速解决。

2 利用定理18

定理18证明的简便性和方法1相近，尝试方法1失败后，若形式符合\((A \to B)\to C\)，可以考虑定理18

将原式子拆成 \(\lnot A \to C\) 和 \(B \to C\) ，再用方法1

例题：

1. 反公理2（书上用演绎定理证明，很简短）

\[ \vdash \left( \left( A\rightarrow B \right) \rightarrow \left( A\rightarrow C \right) \right) \rightarrow \left( A\rightarrow \left( B\rightarrow C \right) \right) \]

如果看前两项，想用逆推的方法解决，但是发现加前件定理用不了，因为接不上。直接考虑定理18。

• 拆成

\[ \left( A\rightarrow C \right) \rightarrow \left( A\rightarrow \left( B\rightarrow C \right) \right) \] 只需前件互换，去掉后件即可证明。

• 拆成

\[ \lnot \left( A\rightarrow B \right) \rightarrow \left( A\rightarrow \left( B\rightarrow C \right) \right) \] 比较复杂，需要前件互换，再摘掉 A

（注意：这一步可以不需要前件互换，只需用公理1+三段论，直接砍后件头）

（附注：砍后件头，倒过来书写时其实是加后件头，与前面的砍头操作不同） \[ \lnot \left( A\rightarrow B \right) \rightarrow \left( B\rightarrow C \right) \] 然后再换前件，因为前面的 \(\lnot\) 是在整体上的，必须要和单体进行一次逆否转换 \[ B\rightarrow \left( \lnot \left( A\rightarrow B \right) \rightarrow C \right) \] 再对里面做逆否，此时 \(\lnot\) 已经转移到单独的 \(C\) 上了 \[ B\rightarrow \left( \lnot C\rightarrow \left( A\rightarrow B \right) \right) \] 需要前件互换，再摘掉 \(\lnot C\)

（注意：这一步可以不需要前件互换，只需用公理1+三段论，直接砍后件头）

• 补充

\[ \lnot \left( A\rightarrow B \right) \rightarrow \left( B\rightarrow C \right) \]

前面的 \(\lnot\) 是在整体上的，还有另一种办法可以消去

因为 \(\lnot (A \to B)\) 可以推出 \(A\) 或 \(\lnot B\) ，利用三段论定理可以接上去。

此题可以用 \(\lnot B\)，转化后的形式是定理6。

2. 二难推理

\[ \vdash \left( A\rightarrow C \right) \rightarrow \left( \left( B\rightarrow C \right) \rightarrow \left( \left( A\lor B \right) \rightarrow C \right) \right) \]

二难推理系列的题目，比思维流更好的办法其实是定理18，并且套路十分明显。

• 拆成

\[ \lnot A\rightarrow \left( \left( B\rightarrow C \right) \rightarrow \left( \left( A\lor B \right) \rightarrow C \right) \right) \]

首先第一部分，由于 \(C\) 在后件的两个后件，此时用加后件定理可以轻松消去 \(C\)。 \[ \lnot A\rightarrow \left( \left( A\lor B \right) \rightarrow B \right) \] 再用一次前件互换定理，发现就是定理1。

• （这一步纯套路，每题都是一样）拆成

\[ C\rightarrow \left( \left( B\rightarrow C \right) \rightarrow \left( \left( A\lor B \right) \rightarrow C \right) \right) \]

此时不能直接用加后件了，否则最前面的 \(C\) 消不掉。直接前件互换， \[ \left( B\rightarrow C \right) \rightarrow \left( C\rightarrow \left( \left( A\lor B \right) \rightarrow C \right) \right) \] 发现后件是公理1，于是摘掉前件，成立。

类似题： \[ \vdash \left( A\rightarrow C \right) \rightarrow \left( \left( B\rightarrow C \right) \rightarrow \left( \left( \left( A\rightarrow B \right) \rightarrow B \right) \rightarrow C \right) \right) \]

也可以用同样的套路秒做。

3 反证法

前两种方法都想不出来的情况下考虑，书写过程会相对繁琐。

1. 基本方法

假定原定理为0，按照依次将式子标上0和1，直到推出矛盾（一般会有多处，找容易的）。

证明时显而易见的（前几条）可以不用加注释，可以理解成真值表的体现。

后面的推理过程可以按标0和1的顺序来，通常都是由大后件的结论往前件找矛盾。

最常使用：三段论定理，用于把 \(\lnot P\) 接上去，最后才能转到矛盾。

2. 推演技巧

最无脑的方法是把所有单项都用 \(\lnot P\) 推出来，再进行排列组合出矛盾。

高级的方法是抓住「矛盾块」（通常是原式的一端），再把「另一个矛盾块」通过逆向推理法（直接法）证到原式的另一端，即可。

4 演绎定理

没啥好说的，一般不给用，对三个以上变量比较友好，提取出所有前件后就可以用直接法证明。

ND 中定理的证明

思维流

本质是逆向推理法，逆推的同时可以注意左端项的逻辑规律（赋1，看矛盾）

结合常见形式及解决套路可以更快解决。

1. 当右端项包含 \(\lnot\) 时：

\[ \lnot A\land \lnot B\vdash \lnot \left( A\lor B \right) \]

用 \(\lnot +\) 规则把右端项挪到左边时，要导出矛盾，往往这个矛盾是右端项的部分，如析取、合取的部分。

此时的惯常做法是将这两个矛盾合取，如 \(A\land \lnot A\) ，这个式子必定为0，事实上左边此时的两个式子已经自相矛盾。

当然不一定要用 \(A\land \lnot A\)，因为左边矛盾的情况下，赋1可以推出很多对矛盾，只是这个最常见。

2. 当左端项有 \(\lor\) 时：

\[ \lnot A\lor \lnot B\vdash \lnot \left( A\land B \right) \]

充分利用析取，将其两项分别放到左端，用 \(\in\) 规则把两项先推出来。

左端多出来的两项最终也需要消去。

• 这就需要 \(\lor-\) 规则，因此上面推出来的两式要最后导出到同一个目标，通常是\(A\land \lnot A\)，这类式子。
• 也有可能是需要 \(\to +\) 规则，把小项拿到右边当前件。

注意：如果 \(\lor\) 是含在某个大的式子里，也可以将小项直接拿到外面来推。

3. 当右端项有 \(\lor\) 时：

\[ \lnot \left( A\land B \right) \vdash \lnot A\lor \lnot B \]

一般可以用 \(\lor -\) 简化，只需证一半，但是保留哪一半要根据左边的情况推理，即思维流。

但有时也不能上来就简化，因为左边的条件可能太宽泛了（太少了），因此可能要加上一些小项再看。

这时候常用的是 \(-\) 规则。这也是最难用的一个规则。

4. 当左端项有 \(\land\) 时：

\[ A\land \left( {B}\lor {C} \right) \vdash \left( {A}\land {B} \right) \lor \left( {A}\land {C} \right) \]

利用 \(\land -\) 规则，将两个子命题拆出来。

当然不能白拆，要和前几条综合起来用，往往时加入了很多项后，用这个来助攻。

5. 当右端项有 \(\land\) 时：

可能是要把两个细分都推出来。 \[ \lnot \left( {A}\lor {B} \right) \vdash \lnot {A}\land \lnot {B} \] 也可能是要整个推出，即生成未出现过的项，常用 \(\lor-\) 规则。 \[ \left( A\land {B} \right) \lor \left( {A}\land {C} \right) \vdash {A}\land \left( {B}\lor {C} \right) \]

6. 在右端生成从未出现过的项：

常用 \(\lor-\) 规则，但是这种必须有理有据的推出，而且左端要含 \(\lor\)。

另一个方法是 \(\lnot -\)，矛盾可以推任意。

• 通常的用法是：

\[ \begin{aligned} XXX, A, \lnot A&\vdash A \\ XXX, A, \lnot A&\vdash \lnot A \\ XXX, A, \lnot A&\vdash B \end{aligned} \]

• 然后再想办法消掉多出来的单项，如

\[ XXX, \lnot A\vdash A\rightarrow B \]

• 或者再利用 \(\lor-\) ，二者结合，如

\[ \begin{aligned} XXX, A, \lnot A&\vdash B \\ XXX, A, B&\vdash B \\ XXX, A&\vdash \lnot A\lor B \\ XXX, A&\vdash B \end{aligned} \]

例：（需要用到两种引入方法） \[ \left( A\lor B \right) \land \left( \lnot B\lor C \right) \vdash A\lor C \] 按照思维流推断，发现最开始可以引入 \(B\)，\(\lnot B\) 的矛盾推任意。

而右端项的析取，一次只能推一半。

推一半的时候，还是需要引入新项，此时用 \(\lor-\) ，因为左端项还有个析取（隐藏在合取中）可以用，将两个子项单独拿出来放到左边，即可推出。

7. 当左端项有 \(\to\) 时：

由于ND中没有分离规则，所以要利用好这个 \(\to\) 需要先在左端加上前件，用两次 \(\in\) 规则。

最后再用 \(\to -\) 规则把后件推到右端。

8. 当左端项包含 \(\lnot\) 时：

\[ \lnot ( A\to B ) \vdash A\land \lnot B \]

想按照逻辑推出东西基本不可能，最好的办法是利用已有的一个 \(\lnot\) ，制造矛盾，使得矛盾可以推任意，或者 \(\lnot +\)。

但是如果要制造矛盾，必须引入新的变量，这样左边就会多一个元素，即使 \(\lnot -\) 推出了任意，但左边也不符合。

因此可以用 \(\lnot +\) 规则，在左边引入一个待求右端项的 \(\lnot\) ，推出矛盾后再用反证法把待求变量移到右边，此时可能要用 \(\lnot \lnot-\) 规则。

FC 中定理的证明

两种书写格式

1. 用 PC 中的公式序列，最后再补上 \(\Gamma\) ，不用序号，用「从而...」连接结论。

   常用于 FC 反证法定理8、双向证明（先证后证）

2. 用 ND 中的演绎序列，直接证出结果（书写内容多），如果此时要用 PC 或者 FC 的定理，需要在公式前面写 \(\vdash\)，并在下一条用分离规则导出（注意：不用写用若干次 \(+\) 规则）。

   常用于 FC 存在消除定理10

具体证明过程依次使用以下方法。

存在消除定理

当式子左端有 \(\exists xA\) 或 \(\exists x(A\to B)\) 的量词时，优先考虑用存在消除定理10。

在左端补上 \(A\) 或 \((A\to B)\) ，并用 ND 中的规则推出想要的右端项。

接着就可以用存在消除定理把左端补上的东西消除了。 \[ \begin{aligned} &\left( 1 \right) \exists v\left( B\rightarrow A \right) , B\rightarrow A, B\vdash A \\ &\left( 2 \right) \exists v\left( B\rightarrow A \right) , B\vdash \exists v\left( B\rightarrow A \right) \\ &\left( 3 \right) \exists v\left( B\rightarrow A \right) , B\vdash A\,\, \end{aligned} \] 注意：虽说「存在」消除定理，但是最后消掉的是 \(\exists x\) 里面的东西。

警告：使用该方法时，(3) 式中左右端项都不能有 \(v\) 的自由出现！

反证法定理

反证法不一定是最优解，但是是最 FC 的做法，一般标准答案会用。当右端的整体上有个 \(\lnot\) 打头，或者右端有个 \(\exists x\) 时，建议使用。

\[ \begin{aligned} &\text{从而}\varGamma \vdash A\,\,\text{且} \varGamma \vdash \lnot A \\ &\text{从而公式集}\varGamma \text{不一致，由}FC\text{反证法定理}8 \\ &\text{得}\forall vB\rightarrow A\vdash \lnot \forall v\lnot \left( B\rightarrow A \right) \end{aligned} \]

注意：如果左右都有 \(\exists x\)，优先用存在消除定理。

思维流

前两种方法都不可以使用的时候考虑，跟 ND 中的证明没啥区别。可能会用到一些 PC 中的定理，如三段论定理8、逆否定理、以及一些小套件（定理6，定理9）。

其他小技巧

1. FC 定理 9 平时用的少，但是有时有妙用。

\[ \begin{aligned} &\left( 1 \right) \exists v\left( B\rightarrow A \right) , B\vdash A \\ &\left( 2 \right) \exists v\left( B\rightarrow A \right) , \forall vB\vdash A \end{aligned} \]

2. FC 也有演绎定理，并且考试中可以直接使用。（省步骤，不然就得用 ND 中复杂的规则来代替）

   比如往左放就要用 \((+)\) 再用 \((\to-)\) 规则，往右放就要用 \((\to +)\) 规则。

3. 全称推广定理 和 定理1 是互逆的关系，是 PC/ND 系统与 FC 联系的关键。常用于导出待证明式子右端项。

4. 补充：使用 FC 定理时，有的定理有限制。

• 公理4 （项 t 对 v 可代入）
• 公理6 （v 在 A 中无自由出现）
• 全称推广定理5 （v 在 \(\Gamma\) 中无自由出现）
• 定理9 （v 在 \(\Gamma\) 中无自由出现）
• 存在消除定理10 （v 在 \(\Gamma\) 和 B 中无自由出现）（在最后一行前后都无自由出现）

谓词演算部分

构造语义和指派

语义就是 \(U=<D,I>\) 即论域和解释，其中论域部分令 \(D=\{1, 2\}\)。

解释部分 \(I\) 要加横杠，分别对常元、函词、谓词做一个映射。构造时根据要求，巧妙选择。 \[ \begin{aligned} &\bar{a}=1 \\ &\bar{f}\left( 1,1 \right) =1,\bar{f}\left( 1,2 \right) =1,\bar{f}\left( 2,1 \right) =1,\bar{f}\left( 2,2 \right) =1 \\ &\bar{R}=\left\{ 1,2 \right\} ,\bar{P}=\left\{ \left( 1,1 \right) \right\} ,\bar{Q}=\oslash \end{aligned} \] 注意：函词是个体映射到个体，谓词是取这些个体时值为 True。一元谓词跟函词很容易混淆。

指派 \(s\) 就是给变元取值。 \[ \bar{x}=2,\bar{y}=1 \] 注意：书写时展开函词的时候，横杠都要加上。特别是多层函词时。 \[ \overline{f\left( x,y \right) }=\bar{f}\left( \bar{x},\bar{y} \right) \] 判断真假的时候，简单的直接写 T 或 F 就可以（需要横杠），表示映射。

但是含有任意、存在量词的必须用标准写法（不用横杠）拆去。 \[ \begin{aligned} &\models _U\left( \forall x \right) P\left( x \right) \left[ s \right] \,\, iff.\models _UP\left( x \right) \left[ s\left( x|1 \right) \right] \,\,\text{且} \models _UP\left( x \right) \left[ s\left( x|2 \right) \right] \\ &\models _U\left( \exists x \right) P\left( x \right) \left[ s \right] \,\, iff.\models _UP\left( x \right) \left[ s\left( x|1 \right) \right] \,\,\text{或} \models _UP\left( x \right) \left[ s\left( x|2 \right) \right] \end{aligned} \]

构造自然语句的形式化

格式要注意，在开头要令出谓词、函词，一般不需要论域（除非真的只有一种个体词）。

每个出现的个体词都应该有对应的谓词，如「作家」「作品」「小说」「学生」「实数」。

一个基本原则：$$

常用短语：

• 并非所有：\(\lnot \forall x\)
• 有且仅有、唯一：$x( R( x ) u( R( u ) E( x, u ) ) ) $
• 不是就是、要么要么：$x( R( x ) P( x ) Q( x ) ) $

例题：形式化表示第二数学归纳法。 \[ \begin{aligned} & \text{令谓词：} \\& F\left( x \right) \text{表示当}n=x\text{时，命题成立；} \\& L\left( x,k \right) \text{表示}x<k\text{；} \\& P\left( x \right) \text{表示}x\text{是正整数。} \\& \left( 1 \right) F\left( 1 \right) \\& \left( 2 \right) \forall k\left( \left( P\left( k \right) \land \forall x\left( P\left( x \right) \land L\left( x,k \right) \rightarrow F\left( x \right) \right) \right) \rightarrow F\left( k \right) \right) \\& \left( 3 \right) \forall x\left( P\left( x \right) \rightarrow F\left( x \right) \right) \end{aligned} \]