不知道自己多少分，故也就无法评价给分好坏。

稍微评价一下今年期末考的卷子，比往年的会恶心一些，体现在两道应用题，和判断题的一些坑点。但反正理解了，而且概念之类的认真翻翻看看，这张考卷也没什么难的。

回忆一下考卷（如果还有记得更多的可以在评论区说一下）：

第一题：判断题（每题 3 分）（不保证顺序）。

(1) 对于一个公式 \(p\)，若有 \(\vdash p\)，则对于任意公式集 \(\Gamma\)，都有 \(\Gamma \vdash p\)。

(2) 一个公式 \(p\) 是公式集 \(\Gamma\) 的语法推论，则每个让 \(p\) 为真的赋值都会让 \(\Gamma\) 里的所有公式为真。

(3) 用一个项 \(t\) 去替换原子公式 \(p\) 里的自由出现的变元 \(x\)，得到的新公式里会有约束出现的变元。

(4) 忘了。

(5) 忘了。

(6) 给定解释域 \(M\) 后，对于一个给定的常元 \(c\)，存在两个不同项解释 \(\varphi, \psi \in \Phi_M\)，使得 \(\varphi(c) \ne \psi(c)\)。

(7) 忘了。

第二题：忘记了，一个繁琐的推理题。

第三题：给出如下命题的直接与间接证明（18 分）：

\(\vdash (p \to q) \to ( (p \to (q \to r)) \to (p \to r) )\)

第四题：在谓词演算 \(K\) 中证明如下两个命题：

(1) \((p \to \forall x q) \vdash \forall x (p \to q)\)。

(2) \(\forall x (p \to q) \vdash \forall x \neg q \to \forall x \neg p\)。

第五题：将如下公式化为前束合取范式：

\(\neg ( \forall x_1 R_1^2(a, x_1) \to \exists x_1 ( \exists x_2 R_1^3(x_1, x_2, b) \to \forall x_2 \exists x_3 R_2^2(x_2, x_3) ) )\)

第六题：证明如下命题：

一位客人要么坐一等座，要么做二等座，而一位客人坐一等座当且仅当其富裕。并且存在客人不富裕，那么有人坐二等座。

优雅至极的一门学问，之后有空再来细讲。（仗着科大估计没人做正统的数理逻辑，发表自己拙劣的见解）

先写点课程内容，也算是给自己复习。我没去上课，自学主要看的书是复旦大学的教材：郝兆宽、杨睿之、杨跃《数理逻辑：证明及其限度》，下面的语言有的地方可能会和书上不一样。

数理逻辑最初的想法来自 Leibniz 构想的通用文字纲领。我们这门课主要学习了其中最基本的部分：命题逻辑 与 一阶逻辑。可惜的是，在 20 年培养方案改之后，数理逻辑从三学分变成两学分（估计是被量子物理给夺去了学分），删掉了数理逻辑的绝对高峰：Gödel 不完备定理。

命题逻辑以一个一个命题为基本单元，分为语义和语法两个部分。

语法这边，上来先给出了三条公理，然后马上就来了整个数理逻辑基础课里面让大家最头疼的 “直接证明”。“直接证明” 这件事本质上是在做语法游戏，它规定命题演算体系 \(L\) 下的一个内定理 \(\varphi\) 是而且只能是一个可以通过一列有限个字符串，里面的要么是 (L1)、(L2)、(L3) 三条公理，要么是可以使用分离规则 (MP)，得出的。但是“直接证明”实在是过于繁琐，所以又有了演绎定理、反证律和归谬律来帮助大家简化证明。

说到 “直接证明” 为什么不能使用演绎定理，即使是在题目一开始直接当作引理证明完也不能用。本质上还是这个东西是不合规的，你这个玩意不符合那套语法规则。这里可以说一下 “内定理” 和 “外定理” 的区别：“内定理” 又叫 "元定理”，大概就是这套语法规则里可以玩出来的东西，比如 (否定前件律) \(\neg q \to (q \to p)\)，以及大家在习题里看到的各种各样的神秘字符串；而 "外定理“ 大概就是人类通常理解的定理，比如在书上反复用到的归纳原理就算一种 “外定理”，当然演绎定理这些也是 “外定理”。

从本质上来说我们不能在直接证明里使用 “外定理”，是因为命题演算系统 \(L\) 它的语言没办法说明这样一个 “外定理”。比如说，\(L\) 连自然数都无法描述，怎么使用归纳法。“外定理” 实际上是我们在用自己熟知的语言和逻辑，去研究一个 “对象语言 / 逻辑”——命题演算系统 \(L\)。就比如说如果你用了演绎定理，你要怎么根据这个使用了演绎定理的间接证明来写出直接证明呢？至少我觉得反演回去的工作是 non-trivial 的，比你突然想要用 (否定前件律) 了，然后把 (否定前件律) （这个是 “内定理”）的证明抄一遍用上去要困难得多。更别说还要以演绎定理为基础的反证律等。

所以其实我大部分时候，做直接证明题，最感到烦躁的不是不能用演绎定理，而是大致的逻辑链条已经清楚了，但每次用到 “内定理” 却要把其直接证明抄上去。

说了这么多，其实我们已经大致上把命题逻辑的语法部分讲完了，接下来再来看语义部分。这部分显得就特别直白了，可以直接列真值表了！熟悉的与或非也回来了！这部分整个下来是顺风顺水的，后面的合取析取范式，对偶公式等甚至数电就已经学过。

再来是命题逻辑 \(L\) 的完备性和可靠性，这是一个小的高潮，它告诉我们：语义与语法是统一的。完备性指的是：每个在人看来很对的命题，也就是重言式，都可以在 \(L\) 中用那套语法规则玩出来。这个是对 \(L\) 表达能力的刻画，它可以推出我们想要的东西。而可靠性则更进一步要求了 \(L\) 别推出我们不想要的东西：每个 \(L\) 的 “内定理”（可以用语法玩出来的东西），都要是重言式。

证明可靠性相对容易，只需要发现 (L1)、(L2)、(L3) 都是重言式，并且对 (MP) 也封闭即可。

而证明完全性，我们要先进行一个转化：

引理：下列命题等价：(1) 如果 \(\Sigma\) 一致，则 \(\Sigma\) 可满足；(2) 如果 \(\Sigma \models \alpha\)，则 \(\Sigma \vdash \alpha\)。

依此我们可以将完全性定理的证明转化为去证明每一个一致集都是可满足的。而后者的证明又有：

 Lindenbaum 引理：每一个一致的公式集 \(\Sigma\) 都可以扩张成一个极大一致集 \(\Delta\)。

做法就是把可数多个公式一个一个尝试往里加。有了极大一致集，我们容易从中读出一种赋值：\(\bar{v}(\varphi) = 1 \Leftrightarrow \varphi \in \Delta\)，这样我们就证明了完全性定理。这两个定理给出一个附属结果：命题逻辑 \(L\) 是可判定的，你想要判定是否有 \(\Sigma \vdash \alpha\)，只需要列真值表就可以了，虽然这样很慢。

书上还提到了别的一些杂项，如唯一读法引理，和其他的命题演算系统（极小系统和 Heyting 系统），由此引出直觉逻辑：否定排中律可以无限制地运用。Gödel 的另一个著名理论是：直接逻辑的真值种类必须有无穷多个。由此可见直觉逻辑与经典逻辑的不同。

接下来到了一阶逻辑（谓词逻辑），它是命题逻辑的扩充。命题逻辑以整个命题为基本单位，这无法接触到个体对象，使得量词无法介入。一阶逻辑定义项集，以原子公式为基本单位。

在语法部分，一阶逻辑比命题逻辑多了几条公理。我看的书里是没有 (Gen) 规则，科大的书里是有的。我暂且觉得没有 (Gen) 规则更好：一个是更加清楚，有 (Gen) 之后演绎定理和反正律都要额外加条件；另一个原因之后在语义部分会提及。这部分倒是没有 “直接证明” 题了，估计是太过复杂了。

语法这部分还要注意理解自由出现和约束出现，以及各种东西能不能替换，这个是一阶逻辑引入量词后必须注意的一部分（哑元的艺术）。

到了语义部分，和命题逻辑不一样，一阶逻辑的语义不再是 trivial 的真假赋值。为了细化一阶逻辑中个体对象的部分，我们必须引入解释域 \(\mathfrak{U}\)，让常元对应集合上的一个元素，函数对应集合上的函数，谓词对应集合上的关系。而有解释域还不够，因为变元的值还没有被确定，所以还要再来项解释 \(s\)，并扩充成整个公式集的解释 \(\bar{s}\)。

有了这个那 \(\Sigma \models \alpha\) 怎么定义呢？我看的书和科大的书定义是不同的：

当然每个人感受不一样，可能有的觉得科大书上的定义很自然。

接下来又到了可靠性与完备性的环节，同命题逻辑一样，一阶逻辑的语义和语法也是一致的。对于可靠性定理还是去证明各个公理和 (MP) 都可以，只不过花的工作更多一点。

而对于完备性，我们先把一阶逻辑 \(K\) 进行扩充，添加可数个新常元，变成 \(K_c\)。并且添加 Henkin 公理：\(\exists x \varphi \to \varphi_c^x\)，其中 \(c\) 是新的常元，而 \(\varphi_c^x\) 表示把 \(\varphi\) 中所有自由出现的 \(x\) 替换成 \(c\) 得到的公式。

可以这么理解 Henkin 公理：对每一个存在性的语句都添加一个直接证据 \(c\)，所以扩充 \(K\) 和添加 Henkin 公理的目的都是 “消去量词”，使得从中可以比较容易的读出一个可能的解释域和项解释。

我们记 Henkin 公理集为 \(\Theta\)，可以证明 \(\Sigma \cup \Theta\) 还是一致的，这时候我们在和命题逻辑一样，运用 Lindenbaum 引理，将 \(\Sigma \cup \Theta\) 扩充成极大一致集 \(\Delta\)，从这一公式集中容易读出一种解释域和项解释：

(1) 论域 \(\mathfrak{U}\) 为 \(K_c\) 上所有项的集合；(2) 一个谓词 \(P\)，其对应 \(\bar{P}\) 为：\((t_1, t_2, \ldots, t_n) \in \bar{P} \Leftrightarrow P(t_1, t_2, \ldots, t_n) \in \Delta\)；(3) 函数对应和谓词类似；(4) 常元 \(c\) 直接对应于自身。

这样可以验证我们就找到了一个解释域和赋值，如果一阶逻辑中还包含等词，我们需要考虑由等词划分得到的商集。然后还是根据命题逻辑中的转化，我们由此得出完备性定理。

与命题逻辑很不一致的地方是，\(\Sigma \vdash \alpha\) 这件事在一阶逻辑中变得不好弄了。命题逻辑只需要列真值表，但是一阶逻辑中解释域和项解释都是无穷多的，也就是解释个数的区别。实际上，一阶逻辑是不可判定的。

PS：数院的陈卿老师说过：

不要碰数理逻辑和集合论这种形式化的东西，水太深。

由此可见数理逻辑的深邃。

中国科大 woc

害惨了我