离散数学 - 形式演算

Posted on In Views: Word count in article: 5.4k Reading time ≈ 5 mins.

一、数理逻辑总论

1.1 形式

“Logic is about the form of things, but not the things themselves.”

逻辑 = 语法 + 语义，但是并非像自然语言一样，语义占据了统治地位，而语法只起辅助作用。恰恰相反，逻辑更关注语法，即形式。罗素说，数理逻辑是数学中的数学，也就是元数学，它试图构建一个基础，用来支撑庞大的数学体系。从这个角度来看，关注语法，确切的是形式，是十分必要的，因为这个元数学必须适用于所有的数学理论，那么仅仅局限与一个体系的语义，没有办法做到适用于所有体系。就好像数学对客观世界的抽象，如果只纠结于 1 怎么写，1+1=2 的问题，数学是没有长足发展的，只有提炼出未知数 x 这种可以代表一切自然数的东西，才能使数学的概括能力有所提高。我们也可以说，x 是某个特定自然数，比如 1，的形式。就像现在的数理逻辑是比如数论、欧式几何的抽象，所以过于纠结于语义的现象就像在问 “x + 1 里的 x 是多少一样？“没有意义。

1.2 定义形式

有了形式的概念以后，就可以重新思考某些定义，比如联结词当时定义的时候涉及了函数的概念，这说明它是一个语义定义，但是联结词和命题变元的写法并不是在定义联结词的时候定义的，而是在定义公式的时候定义的，那个归纳定义至今记忆犹新，这个定义并不涉及任何语义，所以是个语法定义，但是我在理解的时候还是喜欢用函数的概念理解，这就犯了错误。

1.3 对错与存在

对错就是语义的部分，但是显然这不是逻辑关注的重点，逻辑关注的是存在性。数理逻辑系统是由一串 “符号” 组成的系统，由 “符号” 组成 “式子”，再确定推导规则 。逻辑系统不关注式子的对错，只关心式子是否存在。也就是假定存在某些式子，再确定推导规则，然后按照这些规则看 1 能推导出哪些式子，哪些假定存在的式子就被称为公理。总结起来，逻辑系统关心的是给定公理和推导规则后，判断某个式子是否存在。所以，在学习逻辑系统的过程中，首先要摒弃 “是非对错” 观念，而谨记 “存在与否，是否有效” 观念。

1.4 积木的类比

搭积木是对命题演算很好的比喻，两者具有极佳的相似性：积木不关心材质（他就是一个模型），命题演算不关心语义。积木只能拼出某些形状，比如如果没有胶水，桥就很难搭，命题演算关注完备性，也就是这个系统能不能拼出所有的理论。积木只有有限的几个形状，但是可以组装出很多复杂的零件，然后再组装成装配体，命题演算也呈现这种特征，公理的数量极少，但是可以组装出定理用于证明。积木拼装最关键是严丝合缝，命题推演最重要的是推演规则。总之，积木很好的概括了数理逻辑的形式特点。

二、逻辑推论

2.1 逻辑推论

其实这一章要讲的内容不是语法，而是语义，由于考试的需要，基本的定义不会太涉及，因为时间不富裕，但是基本的精髓还是要有的。就是逻辑推论的证明时语义证明，具体就是表现在大量运用等值演算和真值赋值和解释，这些都是语义特征。

在命题逻辑这一章，比较重要的是逻辑推论的定义，他是如是说的：设 Γ\Gamma 是公式的集合，如果每个满足 Γ\Gamma 的真值赋值都满足 A，则称 A 是 Γ\Gamma 的逻辑推论，记作 Γ⊨A\Gamma \models A。然后就会衍生两个不那么自然的概念。一个是 ⊨A\models A，说明 A 是永真式，因为任何真值赋值都满足空公式集，所以所有真值赋值都满足 A ，也就是 A 是永真式。另一个是 “设 Γ\Gamma 是公式集合，Γ\Gamma 是不可满足的当且仅当任何一个公式都是 Γ\Gamma 的逻辑推论”，因为当 Γ\Gamma 不可满足时，只有 0 个真值赋值可以满足 Γ\Gamma ，所以每个满足 Γ\Gamma 的真值赋值都可以满足任何公式。

在谓词逻辑这一章基本上内容与命题逻辑相同，唯一有一个比较需要注意的是这个 “设 Γ\Gamma 是公式集合，A 是公式，变元 x 不是 Γ\Gamma 中任何公式的自由变元，若 Γ⊨A\Gamma\models A ，则 Γ⊨∀xA\Gamma\models \forall xA” ，我也不知道他为什么这么不自然，他好像与 UG 规则类似。

2.2 命题逻辑的归结法

2.2.1 子句

文字的有穷集合叫做子句，不包含任何文字的子句叫做空子句，记为 □\Box。然后我们在让一个子句对应一个公式，就是对应一个简单析取式，析取式的项就是集合中的文字，显然 □\Box 对应的是永假式 0 。说子句 C1C_1 和子句 C2C_2 推出 C3C_3 是说两个对应的公式推出第三个公式，就是两个简单析取式推出第三个简单析取式。我们说满足一个子句，就是满足这个集合中的一个文字就够了，这与常见的满足集合不同，满足集合一般是满足集合中的所有公式。

2.2.2 子句集

子句的集合叫做子句集，注意子句集是集合的集合，同时也要注意到，因为子句对应的是公式，所以子句集也同时是一个我们常见的公式集。所有说满足一个子句集，就是要满足所有的子句。

2.2.3 归结子句

设 L1L_1 和 L2L_2 是相反的文字，并且在子句 C1C_1 和子句 C2C_2 中分别出现，称子句 (C1−{L1})⋃(C2−{L2})(C_1-\{L_1\})\bigcup(C_2-\{L_2\}) 是前两者的归结子句（记为 C3C_3 ）。有性质：C1,C2⊨C3C_1,C_2\models C_3 ，如果用乘法的思想理解，去掉相反文字的过程就是去掉方程组不可能解的过程，那么再用乘法连接后就是一个新的可以代表原来两个方程的一个新方程。

2.2.4 反驳

设 SS 是一个子句集合，如果子句序列 C1,…,CnC_1,\dots ,C_n 中每个子句满足以下任意一个条件，则称该子句序列为 SS 的一个反驳

  • Ci∈SC_i \in S

  • CiC_i 是 CjC_j 和 CkC_k 的归结子句，且 i,j<ki,j<k

  • CnC_n 是 □\Box

    这个反驳其实是 SS 和由 SS 衍生的归结子句集合的并集的一个拓扑序列，路径就是存在归结子句，终点就是空子句。

2.2.5 条件转换

A1,…,An⊨BA_1,\dots ,A_n\models B 等价于 A1∧⋯∧An∧¬BA_1\wedge\dots\wedge A_n\wedge\neg B 为永假式，我们可以进行如下转化

  • 将 A1,…,An,BA_1,\dots ,A_n, B 转换为合取范式（不是主范式，因为没必要）

  • 取 SS 为上述合取范式所有简单析取式对应的子句的集合

  • 如果能找到这样的一个反驳，就说明能推出，不然则不能

这么做的依据是这样的，因为反驳最后会推出空语句，可以理解为 S⊨0S\models 0，所以 S 是不可满足的，也就是说 A1∧⋯∧An∧¬BA_1\wedge\dots\wedge A_n\wedge\neg B 为永假式。就可以说明问题了，仔细思考这一过程，其实跟因式分解还是有很大关系的。

还是应该看到，归结法与语义推理紧密联系，所以他是语义推理的一部分，而不是形式推理系统的一部分，他也不具有可以抽象出证明形式的特点，他只不过是一种特殊的算法罢了。

2.3 谓词逻辑的归结法

2.3.1 总论

因为谓词逻辑更加复杂，所以为了把他限制在一个比较统一的模式里，就必须引入一大堆规范，而把原来嘈杂的公式转换成规范的形式，就不一定保证还具有原来的信息，所以书中会采取一大堆证明和叙述来描述这些转换造成的影响，但是由于我看不懂，所以在这章里面主要讲三个方面：基本的规范是怎样的，归结法的思路是什么，怎么使用归结法。

2.3.2 文字，子句

P(x),¬P(x)P(x),\neg P(x) 是相反的文字，但是 P(x),¬P(y)P(x),\neg P(y) 不是相反的文字，文字的集合被称为子句，但是与命题逻辑不同的是，谓词逻辑对应的是一个闭包，而不是简单的析取式，也就是说讨论的基本单元是一种特殊的语句（这也是对斯科伦范式的召唤）（语句就是不含自由变元的公式，也就是说他的取值只受解释的影响）

2.3.3 基系列

不出现变元的文字称为基文字，基文字的有穷集合叫做基子句，如果一个代换使得原来的子句变成了基子句，那么就称这个基子句是原来子句的基实例。

赫布兰德定理：设 S1S_1 是由子句集 SS 中的全体子句的所有基实例组成的集合。若 SS 不可满足，则有 S1S_1 的有穷子集不可满足。

赫布兰德解释将所有的基项解释为他自己，但是没有规定谓词符号的意义，这是一种限制，是为了避免大量的复杂字符串，我们用赫布兰德解释对其进行了限制，我们可以证明，如果一个语句集是可满足的，那么必然存在一个赫布兰德解释满足它，也就是说，这种限制并没有造成任何不利的影响。

赫布兰德解释，定理和基的概念，确保了谓词逻辑可以向命题逻辑进行转换，毕竟确定了常元，运算函数的谓词就像一个命题变元一样了。这在之后为谓词逻辑的归结法的完备性打下基础。其实其他地方用的不多。但是这种向常元转换的思想在证明归结子句性质时用到了。

2.3.4 归结子句

设 C1,C2C_1,C_2 是子句，如果存在代换 σ1,σ2\sigma_1,\sigma_2 和相反的文字 L1,L2L_1,L_2 ，使得 L1∈C1σ1L_1\in C_1\sigma_1 且 L2∈C2σ2L_2\in C_2\sigma_2，则称 (C1σ1−{L1})⋃(C2σ2−{L2})(C_1\sigma_1-\{L_1\})\bigcup(C_2\sigma_2-\{L_2\}) 为 C1,C2C_1,C_2 的归结子句，同样有 C1,C2⊨C3C_1,C_2\models C_3 。这个性质保证了归结法的正确性。

2.3.5 斯科伦范式

量词都在前面的公式叫做前束范式，去掉量词以后的公式叫做原公式的母式。

前束范式的无 ∃\exist 前束范式指的是涉及存在量词的都用常元换掉。

斯科伦范式指的是母式为合取范式的无 ∃\exist 前束范式。

三、命题逻辑的公理系统

3.1 一种证明思路

考虑公理二和公理三只要结合 MP 规则，就可以把原来要证的蕴含式，转换为一个新的蕴含式，证明的第一步就是利用这些条件尽可能把蕴含式弄得简简单单的，然后证明这个简简单单的蕴含式。

证这个蕴含式的思路是利用传递律，我们可以从前件开始写定理，然后一步步地写到后件，然后定理就证完了。最后把用到的连接定理都进行证明就可以了。

但是这种思路是跟还原演绎定理思路矛盾的，所以二者必取其一。应该是这种思路更好一些，是因为当应用超过两次演绎定理以后，就会用到 T33 定理，那个定理很难证明。所以这种思路更好一些。

3.2 协调性

3.2.1 定义

对每个公式 AA ，有 Γ⊢A\Gamma\vdash A 则 Γ\Gamma 是不协调的，否则， Γ\Gamma 是协调的。

3.2.2 定理

若 Γ⊢p∧¬p\Gamma\vdash p\wedge\neg p，则 Γ\Gamma 是不协调的，其实 Γ\Gamma 推出任何一个永假式，都是不协调的。

3.2.3 性质

协调等价于可满足。

3.3 紧致性

3.3.1 第一形式

若 Γ⊨A\Gamma\models A ，则存在 Γ\Gamma 的有穷子集 Γ′\Gamma^\prime ，满足 Γ′⊨A\Gamma^\prime\models A 。这是因为推演是一个有限的序列，所以由推演中出现的公式构成的 Γ′\Gamma^\prime 满足条件。再借助完备性即可得证。

3.3.2 第二形式

若 Γ\Gamma 不可满足，则有 Γ\Gamma 的有穷子集不可满足。

这是因为当 Γ\Gamma 不可满足时，有 Γ\Gamma 推出永假式（ Γ\Gamma 协调，则 Γ\Gamma 可满足的逆否命题），则由第一形式可知 Γ′\Gamma^\prime 推出永假式，所以 Γ′\Gamma^\prime 不可满足。

3.3.3 理解

紧致性定理的作用在于，它将对无穷公式集的语义性质的讨论归结为对它的的一个有穷子集的语义性质的讨论，紧致性定理讨论的是逻辑的语义性质，没有涉及语法公理系统。

四、谓词逻辑的公理系统

4.1 区别

谓词逻辑公理系统与命题逻辑公理系统有一些区别。首先表现为谓词逻辑推演的前提集是语句集（也就是不受赋值影响的公式），这与逻辑推论，也就是语义证明中的不同，语义证明没有要求集合 Γ\Gamma 是语句集，只要是公式集就好了。这就衍生出一个问题，因为谓词逻辑公理系统的公理模式并没有要求语句，所以会有一大部分东西是没有办法借助命题逻辑的模式证明的，所以谓词逻辑有他独有的推理工具，具体表现为两个方面，一个是增加了新的公理，为了进行原始证明（不涉及各种定理的证明）。另一种是定理证明，原来以演绎定理为主导的证明因为演绎定理受到了语句的限制，需要进行新的补充，也就是常元替换法和重言式替换法。相应的，将定理证明转换为原始证明的方法也要进一步提高。