Lecture 3

Abstract

一阶逻辑把对象、关系与量词带入模型。我们从序、代数和图的例子理解可表达性，证明可数稠密无端点序的同构结论，再定义签名、自由变量、结构、赋值和满足关系。

我们先问一个问题：我们说一个公式“为真”，究竟是在什么东西里为真？在经典命题逻辑中，给每个命题变元一个真值，就给出了一个模型。一个只涉及 $n$ 个命题变元的公式，只有 $2^n$ 种赋值需要考虑。这个数可能很大，但至少是一份有限的清单。

现在，我们想说的不只是几个整体命题之间的关系，而是“有某个对象具有性质 $P$”“每个具有性质 $P$ 的对象都具有性质 $Q$”。对象是什么、共有多少个、它们之间有哪些关系，都应当进入模型。模型可以是自然数，可以是有理数，也可以是一张图，甚至可以是一个无限结构。这就是今天转向一阶逻辑的理由。

这里的“一阶”不是课程顺序的编号。命题逻辑可以看作零阶的情形；一阶逻辑允许变量指向结构中的个体，并对这些个体作量化。我们先使用经典语义。此前讨论直觉主义逻辑，是为了提醒大家：逻辑可以有不同的语义；今天不再把同一套讨论重复一遍。

先看一个推理，再问公式是什么意思

考虑下面的推理：

$$\exists x\,P(x),\qquad \forall x\,(P(x)\to Q(x)) \quad\Longrightarrow\quad \exists x\,Q(x).$$

它说：某个对象有性质 $P$，而所有有性质 $P$ 的对象都有性质 $Q$，所以某个对象有性质 $Q$。如果暂时把存在量词提供的对象称为 $a$，推理的核心是

$$P(a),\qquad P(a)\to Q(a)\quad\Longrightarrow\quad Q(a) \quad\Longrightarrow\quad \exists x\,Q(x).$$

中间一步仍是熟悉的蕴含消去，新的步骤是：用全称命题得到一个特定对象的实例，以及由一个实例得到存在命题。可是，“暂时把对象称为 $a$”不是任意发明一个具有额外性质的对象；我们也不能从存在某个 $P$ 对象直接推出每个对象都满足 $P$。量词推理规则因此需要关于变量的限制。严格按自然演绎写时，应在临时假设 $P(a)$ 下先得到不再含 $a$ 的结论 $\exists x\,Q(x)$，然后用存在消去撤销 $P(a)$；$a$ 要取不出现在其他未撤销假设和最终结论中的新名字。不能先撤销 $P(a)$，却保留带见证名的 $Q(a)$。

今天我们先给这个证明作为动机，完整的量词引入、消去规则及其变量条件留到后面。我们先把模型与公式的意义弄清楚，再讨论形式证明。

同一个关系符号，在不同结构里可以有不同解释

看看“每个元素都有一个比它小的元素”：

$$\forall x\,\exists y\,(y<x).$$

在自然数的通常严格次序 $(\mathbb N,<)$ 中，这句话是假的。我们取 $\mathbb N=\{0,1,2,\ldots\}$；当 $x=0$ 时，没有更小的自然数。即使把自然数从 $1$ 开始，仍有一个最小元素，结论一样。

在有理数的通常严格次序 $(\mathbb Q,<)$ 中，它是真的：给定 $q\in\mathbb Q$，取 $q-1$ 即可。在语义层面，我们先选定结构，再让 $x,y$ 在这个结构的域里取值。

不过，写成 $<$ 的符号不自动意味着它是一种次序。逻辑只知道这是一个二元关系符号。我们可以把它解释成通常的大小关系，也可以解释成任何二元关系，包括空关系。符号的预期意义，必须由结构或公理来保证。

若要要求一个二元关系是严格线性序，可以写出下面三类条件：

$$\forall x\,\neg(x<x),$$

$$\forall x\forall y\forall z\, ((x<y\land y<z)\to x<z),$$

$$\forall x\forall y\,(x=y\lor x<y\lor y<x).$$

第一条是不自反性，第二条是传递性，第三条保证不同元素可比较。由前两条还可推出不能同时有 $x<y$ 和 $y<x$。把这些句子合取起来，就把我们的讨论限制在严格线性序中了。这里的等号按实际相等解释；它不是任意选择解释的“另一种大小关系”。

能不能用一阶公式刻画自然数的次序？

现在我们把问题变得更有挑战性：能否仅使用 $<$，写一个一阶句子，使它恰好描述自然数的通常次序？

首先，“恰好”必须说清楚。把 $0,1,2,\ldots$ 分别改名为 $a_0,a_1,a_2,\ldots$，只要次序没有改变，逻辑就不应当发现区别。于是我们实际问的是：能否刻画 $(\mathbb N,<)$，直到同构为止？

两个序结构 $(A,<_{A})$ 与 $(B,<_{B})$ 同构，意思是存在双射 $f:A\to B$，并且

$$\forall a,a'\in A,\qquad a<_{A}a'\quad\Longleftrightarrow\quad f(a)<_{B}f(a').$$

这不仅是“把元素重新取名”，还要求关系被完整地保留下来。一阶句子的真假在同构下不变。这里先记住这个原则；它解释了为什么不能要求模型的元素一定要叫作数字 $0,1,2$。

接下来，我们试着收集自然数序的性质。它是线性序，有最小元素，没有最大元素；每个元素有直接后继，而每个非最小元素有直接前驱。为了写得清楚，先引入一个缩写：

$$\operatorname{Succ}(x,y)\;:=\; x<y\land\neg\exists z\,(x<z\land z<y).$$

这个缩写没有增加新的关系符号，它只是说 $y$ 在 $x$ 的右边，而且两者之间没有别的元素。相应条件可写成

$$\exists m\,\forall x\,(m=x\lor m<x), \qquad \forall x\,\exists y\,(x<y),$$

$$\forall x\,\exists y\,\operatorname{Succ}(x,y),$$

$$\forall x\, \bigl((\exists u\,u<x)\to \exists y\,\operatorname{Succ}(y,x)\bigr).$$

为什么要把“直接后继”单独写出来？因为没有最大元素太弱了。有理数也没有最大元素，但给定 $q<r$，中间总有 $(q+r)/2$，所以有理数没有直接后继。

然而，要求直接后继仍然不够。把两份自然数序前后连接，形成

$$\mathbb N+\mathbb N,$$

第一份的每个元素都在第二份的每个元素之前。它仍有最小元素、没有最大元素，而且每个元素有直接后继。问题出在第二份的第一个元素：它不是整个序的最小元素，却没有直接前驱，因为第一份没有最后一个元素。于是我们又补上了非最小元素有直接前驱的条件。

但再看

$$\mathbb N+\mathbb Z.$$

这里把一份整数序整体放在自然数序后面。整数部分没有第一个元素，每个整数都可以在整数部分中找到直接前驱和后继。因而刚才所有条件都成立；这个结构却不是自然数序。自然数部分与整数部分之间有一个“间隔”，但它不是某一对相邻元素之间的空档，也没有一个“进入整数部分的第一点”供公式轻易抓住。

课堂还讨论了更丰富的排列：以一个稠密序作索引，在某些位置放整数块，在最前面放自然数块。要点相同：单凭反复增加眼前这些局部条件，未必能消除额外的块。

我们在这里给出一个以后要证明的结论：在只含次序关系的语言中，自然数序与上述适当的非标准离散序，可以满足相同的一阶句子。一阶逻辑因此不能用一个句子把自然数序刻画到同构为止。正式证明将在后续建立。

这个区别值得记住：同构一定意味着满足同样的一阶句子，反过来未必成立。 如果两个结构满足相同的一阶句子，我们称它们一阶等价。逻辑所能辨认的信息，可以少于完整结构包含的信息。

有理数序：限制为可数结构之后，我们几乎能做到

接着问有理数的次序能否被刻画。一个立即出现的障碍是：$(\mathbb Q,<)$ 是可数的，$(\mathbb R,<)$ 是不可数的，它们不可能同构，但它们满足相同的一阶次序句子。这个不可区分性结论留待后续证明。

可是，如果我们预先保证结构的域是可数的，情况就不同了。考虑一个非空线性序 $(A,<)$，要求它稠密，而且没有端点：

$$\forall x\forall y\, \bigl(x<y\to\exists z\,(x<z\land z<y)\bigr),$$

$$\forall x\,\exists y\,(y<x), \qquad \forall x\,\exists y\,(x<y).$$

线性序、稠密、无端点都是一阶条件；可数性是外部给定的条件。 在这个承诺下，任何满足这些条件的序都与 $(\mathbb Q,<)$ 同构。

我们来把这个正面结果的证明做出来。设

$$\mathbb Q=\{q_0,q_1,q_2,\ldots\},\qquad A=\{a_0,a_1,a_2,\ldots\}$$

是两边的枚举。我们逐步建立有限的、保持次序的部分双射。只在一边不停地选点是不够的：那样最后可能漏掉另一边的元素，所以必须轮流从两边出发。

在“向前”一步，我们取枚举中第一个还没有被配对的 $q_i$，观察它相对于已经配对的有限多个有理数的位置。如果它夹在两个已配对点之间，就在 $A$ 中对应的两点之间选一个尚未使用的点；如果它在所有已配对点左边或右边，就在对应的左侧或右侧选一点。稠密性保证中间可以选点，无端点保证两侧可以选点。有限多个已用点不会把这样的区间用尽：再次应用稠密性或无端点条件，总能取得一个新点。

在“向后”一步，我们取 $A$ 的枚举中第一个尚未配对的 $a_j$，反过来在 $\mathbb Q$ 中找到位置合适、还没有用过的有理数。这样扩展后，部分映射仍然单射，仍保持次序。

设第 $n$ 步得到的有限映射是 $f_n$，并且每一步都扩展前一步。令

$$f=\bigcup_{n\in\mathbb N}f_n.$$

因为每一步总选相应枚举中第一个遗漏的元素，每个 $q_i$ 最终都会进入定义域，每个 $a_j$ 最终都会进入值域，所以 $f$ 是从 $\mathbb Q$ 到 $A$ 的双射。任意一对有理数最终会同时出现在某个有限阶段，而那个阶段保持次序，因此 $f$ 保持次序。它就是所需同构。

这就是来回法（back-and-forth）的一个具体例子。可数性真正用在能把两边列成枚举，并通过可数多步保证每个元素都被覆盖的地方。

代数中的运算：今天把它们编码成关系

不仅次序可以用一阶逻辑讨论。我们也可以表达环中的加法、乘法性质。不过，我们今天刻意使用的是关系语言：把加法记为三元关系 $\operatorname{Add}(x,y,z)$，读成“$x$ 与 $y$ 的和是 $z$”；乘法同样记为 $\operatorname{Mul}(x,y,z)$。

这里有三个参数，而不是两个。第三个参数是候选结果，关系回答这个候选是否正确。若改用二元函数符号 $+$，就可以把 $x+x+x$ 写成一个项；在三元关系语言里，不能直接这样嵌套，必须引入中间结果。例如，“$z$ 是三个 $x$ 的和”写作

$$\exists u\, \bigl(\operatorname{Add}(x,x,u)\land \operatorname{Add}(u,x,z)\bigr).$$

采用函数符号往往更方便，但会增加项和公式定义的工作；今天为了把定义讲清楚，先不把函数加入正式语言。

有加法中性元，可以用一句存在量化表达：

$$\exists e\,\forall x\, \bigl(\operatorname{Add}(e,x,x)\land \operatorname{Add}(x,e,x)\bigr).$$

加法交换律则可以表达为

$$\forall x\forall y\forall z\, \bigl(\operatorname{Add}(x,y,z) \leftrightarrow\operatorname{Add}(y,x,z)\bigr).$$

但也要留意：一个任意的三元关系还不自动是运算的图。如果确实要用它编码一个处处有定义的二元运算，就需要保证每一对输入有且仅有一个输出。例如，加法的这项要求是

$$\forall x\forall y\,\exists z\, \left(\operatorname{Add}(x,y,z)\land \forall w\,(\operatorname{Add}(x,y,w)\to w=z)\right).$$

课堂还提出了“没有零因子”的性质。在已经保证结构是环、$e$ 是加法零元的前提下，它可写为

$$\forall x\forall y\, \bigl(\operatorname{Mul}(x,y,e)\to(x=e\lor y=e)\bigr).$$

其中 $e$ 若不是语言里的常元，就必须由外层量词绑定，并附加它为加法中性元的条件。不能只写一句“$xy=0$”，却把乘法或 $0$ 的解释留在语言之外。

图结构：容易表达的局部性质与困难的整体性质

在图中，域是顶点集，二元关系 $E(x,y)$ 表示相邻。无向简单图的基本条件很容易写：

$$\forall x\,\neg E(x,x), \qquad \forall x\forall y\,(E(x,y)\to E(y,x)).$$

第一条排除自环，第二条要求对称。因为量词遍历所有有序对，第二条也保证反方向的蕴含。如果讨论有向图，就不能默认加上对称条件。

例如，“至少有两个顶点”只需要 $\exists x\exists y\,(x\ne y)$。又例如，存在一个与所有其他顶点相邻的顶点（板书称为 apex），可以写作

$$\exists x\,\forall y\,(y\ne x\to E(x,y)).$$

这里必须说“其他顶点”：简单图没有自环，不能把条件写成 $\forall y\,E(x,y)$。在只有一个顶点的非空图中，这个条件因没有其他顶点而成立。

再看大小为三的支配集：存在三个不同的顶点，使每个顶点或者是其中之一，或者与其中一个相邻。公式是

$$\begin{aligned} \exists x_1\exists x_2\exists x_3\,\bigl(& x_1\ne x_2\land x_1\ne x_3\land x_2\ne x_3\\ &\land\forall y\,(y=x_1\lor y=x_2\lor y=x_3 \lor E(y,x_1)\lor E(y,x_2)\lor E(y,x_3))\bigr). \end{aligned}$$

必须把 $y=x_i$ 的情形写进去，因为我们已经排除了自环。如果不要求三个点互异，表达的是“至多三个点足以支配”，而不是存在一个恰有三个不同顶点的支配集。

连通性却不同。两点连通，是说存在一条有限长度的路径，但没有事先给出长度上限。对任何固定的 $k$，我们都能用有限多个变量写出一条长度不超过 $k$ 的路径；问题是，一个一阶公式不能靠写无限长的析取，来把所有 $k$ 同时列完。

前面自然数与额外整数块的例子也提供了直觉。把严格序中的直接后继关系定义出来，再忘掉其他次序信息，只保留无向相邻关系。自然数给出一条连通的单向无限路径，而 $\mathbb N+\mathbb Z$ 给出一条自然数路径与一条整数路径，它们是分开的。若这两个序满足相同的一阶句子，那么只用由次序定义的相邻关系写公式，也不能区分它们：把每个相邻关系替换成后继或逆后继的定义，就会得到一个次序语言的一阶公式。

于是，图的连通性不能被一个一阶句子在所有图中定义。这个结论在本课仍依赖前面尚待证明的不可区分性；这里的替换解释补出了从序结构到图结构的推理桥梁。

“有环”与不可表达性论证的量词顺序

“图中有一个环”也带来类似困难，但这里我们特别纠正一种证明思路。固定长度的环完全可以写出来。对于 $k\ge3$，写

$$\exists x_0\cdots\exists x_{k-1}\, \left( \bigwedge_{0\le i<j<k}x_i\ne x_j \land \bigwedge_{i=0}^{k-1}E(x_i,x_{(i+1)\bmod k}) \right),$$

就表达存在长度为 $k$ 的环。这里表达的是有这样一个环，不要求这些点之间没有其他边。

所以，我们不能指望找到一张固定的有环图和一张固定的无环图，使它们满足所有相同的一阶句子：第一张图里的某个环总有一个具体有限长度 $k$，而刚才的公式就把它们区分开了。

要否定“有一个句子定义有环”，真正需要的是：对每个候选公式，找出适合这个公式的一对反例。 反例可以随着公式而改变。符号上，所需的是

$$\forall\varphi\;\exists G,H\; \bigl(G\text{ 有环},\ H\text{ 无环},\ (G\models\varphi\Longleftrightarrow H\models\varphi)\bigr),$$

而不是要求

$$\exists G,H\;\forall\varphi\; (G\models\varphi\Longleftrightarrow H\models\varphi).$$

课堂的想法是：根据候选公式的有限观察能力，选取足够大的环，再与合适的无环结构比较。严格量化“足够大”并证明不可区分，需要后面的工具。

把刚才使用的语言正式定义出来

例子积累够了，我们来完成形式化。首先指定词汇表，也叫签名。今天的关系签名 $\sigma$ 由一组关系符号以及一个元数函数组成：

$$\operatorname{arity}:\sigma\to\{1,2,3,\ldots\}.$$

元数是关系需要的参数个数。次序签名有一个二元符号 $<$；图签名有一个二元符号 $E$；前面的代数编码有两个三元符号 $\operatorname{Add},\operatorname{Mul}$。签名本身规定名字和元数，还没有规定关系的内容。

关系符号可以有很多个，甚至无限多个，但一个公式只使用有限多个符号，每个关系符号的元数是有限的。正式板书把元数取在 $\{1,2,3,\ldots\}$ 中；口头还讨论了另一种可行约定：允许零元关系。这种关系没有对象参数，只给出真或假，与命题逻辑中的命题变元相似。以下主要使用正元数关系；若采用允许零元的扩充约定，语义也可相应定义。

我们另备一组变量 $x,y,z,x_1,x_2,\ldots$。若 $R\in\sigma$ 的元数是 $k$，则

$$R(x_1,\ldots,x_k)$$

是原子公式，其中各位置可以重复同一个变量。为统一前面的序、图例子，我们采用带逻辑等号的整理约定：另允许相等原子公式 $x=y$，解释固定为域中真实的相等，不计入可自由解释的关系符号表。

从原子公式出发，可以用命题联结词构造更大的公式，也可以添加量词：如果 $\varphi$ 是公式，那么 $\exists x\,\varphi$ 与 $\forall x\,\varphi$ 也是公式。括号标出结构；若把部分联结词作为缩写，也必须按熟悉的等价定义来理解。由于今天没有函数符号，原子公式的参数是变量，不存在像 $x+(y+z)$ 那样的函数项。

自由变量、束缚变量与作用域

量词绑定的是其作用域中的变量出现。一个变量名字可以在同一公式中既有自由出现，也有束缚出现，所以我们首先区分的是出现位置。例如

$$E(x,y)\land\exists x\,E(x,z)$$

中，左边的 $x$ 是自由的，右边的 $x$ 被 $\exists x$ 绑定；$y,z$ 都是自由变量。整个公式的自由变量集合是 $\{x,y,z\}$。

可以递归计算自由变量集合：

$$\operatorname{FV}(R(x_1,\ldots,x_k))=\{x_1,\ldots,x_k\},$$

$$\operatorname{FV}(\neg\varphi)=\operatorname{FV}(\varphi), \qquad \operatorname{FV}(\varphi\land\psi)= \operatorname{FV}(\varphi)\cup\operatorname{FV}(\psi),$$

$$\operatorname{FV}(\exists x\,\varphi) =\operatorname{FV}(\forall x\,\varphi) =\operatorname{FV}(\varphi)\setminus\{x\}.$$

其他二元联结词同样取两边的并集。没有自由变量的公式叫作句子。

课堂用次序长度的例子说明，变量也能像程序里的局部变量一样被重复使用。在线性序中，“至少有四个元素”最直接写作

$$\exists x_1\exists x_2\exists x_3\exists x_4\, (x_1<x_2\land x_2<x_3\land x_3<x_4).$$

但只用两个变量名字也能写：

$$\exists x\,\exists y\, \bigl(x<y\land \exists x\,(y<x\land\exists y\,(x<y))\bigr).$$

内层 $\exists x$ 重新绑定了 $x$，却没有改变前面 $x<y$ 中原来的那个 $x$；再往内层，$\exists y$ 重新绑定 $y$。沿着作用域读，仍然依次选出了四个严格递增的元素。这个写法不是把四个元素压成两个，而是让两个名字在不同作用域承担不同任务。

一般写公式时，我们建议每次量化都使用一个新的变量名字。除非专门研究“能用几个变量表达”，重复绑定很容易造成误读。改名时也要避免捕获：例如把

$$\exists x\,E(x,y)$$

中的束缚变量 $x$ 改成一个新名字 $z$，得到 $\exists z\,E(z,y)$，意义不变；若直接改成 $y$，得到 $\exists y\,E(y,y)$，原来的自由变量 $y$ 被捕获，意义已经变了。这个例子是对课堂作用域说明的整理补全，正式的代入规则还没有在今天建立。

结构与赋值：公式的真假需要两层信息

给定关系签名 $\sigma$，一个 $\sigma$-结构是

$$\mathcal A=(A,(R^{\mathcal A})_{R\in\sigma}),$$

本文采用标准约定，$A$ 是非空域，而每个 $k$ 元关系符号的解释满足

$$R^{\mathcal A}\subseteq A^k.$$

二元关系是一组有序对，三元关系是一组三元组。零元关系的解释是空元组是否在关系中，从而给出一个真值。域可以有限，也可以无限。相同的签名可以有很多不同结构，它们的域、关系解释都可以不同。

有时我们把结构与它的域都简称为 $A$，但严格说，结构还包括关系的解释。只给出“自然数集合”不够：带次序的自然数与带加法、乘法的自然数，是不同签名下的讨论。

如果公式有自由变量，还需要变量赋值

$$s:\operatorname{Var}\to A.$$

我们写 $\mathcal A,s\models\varphi$，表示公式在结构 $\mathcal A$ 和赋值 $s$ 下为真。例如，单独说“有理数满足 $x<y$”不是一条完整断言：必须说明 $x,y$ 分别指向哪个有理数。取 $s(x)=0,s(y)=1$ 时为真，交换两个值时为假。

即使最终只关心没有自由变量的句子，递归定义也必须处理带自由变量的公式，因为一个句子的子公式可以有自由变量。比如 $\exists x\,P(x)$ 是句子，但要判断它，必须先理解 $P(x)$ 在不同 $x$ 值下的真假。

递归定义满足关系

原子公式的语义就是查关系：

$$\mathcal A,s\models R(x_1,\ldots,x_k) \quad\Longleftrightarrow\quad (s(x_1),\ldots,s(x_k))\in R^{\mathcal A}.$$

对于等号，

$$\mathcal A,s\models x=y \quad\Longleftrightarrow\quad s(x)=s(y).$$

联结词仍按经典真值解释。例如

$$\mathcal A,s\models\neg\varphi \quad\Longleftrightarrow\quad \mathcal A,s\not\models\varphi,$$

$$\mathcal A,s\models\varphi\land\psi \quad\Longleftrightarrow\quad \mathcal A,s\models\varphi\ \text{且}\ \mathcal A,s\models\psi.$$

量词的关键是只改变对应变量的值。记 $s[x\mapsto a]$ 为与 $s$ 在其他变量上一致、但把 $x$ 赋为 $a$ 的新赋值，则

$$\mathcal A,s\models\exists x\,\varphi \quad\Longleftrightarrow\quad \exists a\in A\;\mathcal A,s[x\mapsto a]\models\varphi,$$

$$\mathcal A,s\models\forall x\,\varphi \quad\Longleftrightarrow\quad \forall a\in A\;\mathcal A,s[x\mapsto a]\models\varphi.$$

因此判断 $\forall x\exists y\,(x<y)$ 时，对每个 $x$ 的候选值，都允许重新寻找一个 $y$；不能先选定同一个 $y$，再要求它大于所有 $x$。后者是另一个公式 $\exists y\forall x\,(x<y)$。量词顺序是语义的一部分。

公式的真假只取决于自由变量的赋值：若 $s,t$ 在 $\operatorname{FV}(\varphi)$ 上相同，就有

$$\mathcal A,s\models\varphi \quad\Longleftrightarrow\quad \mathcal A,t\models\varphi.$$

这可以对公式构造作归纳验证；量词步骤正是利用“更新被绑定变量后，两个赋值在子公式剩余的自由变量上一致”。所以句子的真假与赋值无关，我们可以直接写 $\mathcal A\models\varphi$。

“在一个模型里真”与“逻辑上真”

最后把两个层次再分开。给定一个结构，我们已经知道量词在它的域中遍历。若说一个句子逻辑有效，则还要求它在同一签名的所有结构中都真：

$$\models\varphi \quad\Longleftrightarrow\quad \text{对每个非空 }\sigma\text{-结构 }\mathcal A, \ \mathcal A\models\varphi.$$

而可满足是说至少有一个这样的结构使它为真。不存在模型则是不可满足。最开始的存在到存在推理，可以写成一个有效句子：

$$\bigl(\exists x\,P(x)\land \forall x\,(P(x)\to Q(x))\bigr) \to\exists x\,Q(x).$$

我们不需要先指定对象是数字、顶点还是其他东西；任何结构中，只要前提真，就能取到一个 $P$ 的见证，再由全称前提得出它有 $Q$，从而后件真。

这也回答了课堂中的一个疑问：一阶逻辑与命题逻辑之间，并不是“把真值改成自然数”就结束了。一阶逻辑有两层选择：先指定结构，再在结构里选择变量值。若我们固定域为 $\{0,1\}$，固定布尔运算，而只允许量词在这两个值中遍历，就得到量化布尔公式的情形。它比没有量词的命题公式多了内部量化，又比允许任意结构的一般一阶逻辑限制得多。

从计算的角度看，“输入一个公式，问是否存在一个模型”和“固定一个结构，问公式在它里面是否为真”是不同问题。任意模型可以无限，甚至根本无法逐个枚举。

课堂最后明确提出三个问题，前两个回答“NO”，第三个回答“YES”：

1. 输入任意关系签名上的一个一阶句子 $\varphi$，判断是否存在结构 $\mathcal A$ 使 $\mathcal A\models\varphi$。这是一般一阶可满足性问题，不存在对所有输入都终止并正确回答的判定算法。
2. 输入加法、乘法语言中的一个句子 $\varphi$，判断整数结构 $(\mathbb Z,+,\times)$ 是否满足它。即使把结构固定下来，这个真值判定问题仍不可判定。这里加法和乘法仍可按三元关系来编码。
3. 输入同样使用加法、乘法的一阶句子 $\varphi$，判断实数结构 $(\mathbb R,+,\times)$ 是否满足它。这个问题有判定算法。实数比整数多，并不因此使结构的逻辑真值问题更难；扩大域会改变量词的意义，也会改变结构能够表达的信息。

这里的算法问题要求句子具有有限、可有效读取的表示。加法、乘法语言若加入逻辑等号、$0,1$ 及有限编码的整数或有理数系数，上述比较仍然成立。

这三个结论的证明与算法留到后续课程。固定结构本身不是一个保证可判定的条件；结构中有哪些关系、这些关系有多强，同样重要。

学习与考核提示

学习时，我们要能解释定义、重建证明，并面对追问给出例子或反例。课堂说明拟以口试作为主要考核方式，问题列表会事先提供，未成功时可再约时间；作业的主要目的仍是帮助自己学会材料。具体权重、时间和细则在当天还没有完全确定，应以之后的正式通知为准。

来源与补全说明

依据 2026 年 9 月 28 日两段完整转写与既有回放帧整理，时间均为段内时间。关系编码、自由变量递归和避免捕获示例补齐了步骤；逻辑等号与非空域采用整理约定。序的一阶等价、图的不可表达性及末尾判定问题的完整证明留待后课。未取得可确认的配套讲义原件。