第 5 讲 · 谓词语言、量词与可代入

命题逻辑把“所有人都会死”整体压成一个命题变元，看不见“所有人”和“苏格拉底”之间的结构。谓词逻辑把句子继续拆成对象、函数、关系和量词。

一阶语言有哪些符号

逻辑符号包括：

• 变元 $x,y,z,\ldots$；
• 联结词；
• 量词 $\forall,\exists$；
• 括号和逗号。

非逻辑符号包括：

• 常元 $a,b,c,\ldots$；
• $n$ 元函词 $f,g,\ldots$；
• $n$ 元谓词 $P,Q,R,\ldots$。

“非逻辑”不是“不讲逻辑”，而是它们的含义随研究对象改变。例如 $+$ 在自然数和矩阵上解释成不同运算。

先生成项，再生成公式

项表示对象：

1. 常元是项；
2. 变元是项；
3. 若 $t_1,\ldots,t_n$ 是项，$f$ 是 $n$ 元函词，则 $f(t_1,\ldots,t_n)$ 是项。

原子公式由谓词作用于项得到：

$$P(t_1,\ldots,t_n).$$

再用联结词和量词递归生成合式公式：

$$\neg A,\quad A\land B,\quad A\to B, \quad\forall xA,\quad\exists xA.$$

量词顺序改变含义

$$\forall x\exists y\,R(x,y)$$

说“每个 $x$ 都能找到某个 $y$”；不同 $x$ 可以使用不同 $y$。

$$\exists y\forall x\,R(x,y)$$

要求先固定同一个 $y$，再对所有 $x$ 生效，通常更强。

例如在整数上令 $R(x,y)$ 表示 $x<y$：

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

为真，取 $y=x+1$；而

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

为假，因为整数没有统一上界。

量词辖域与变量出现

在

$$\forall x\bigl(P(x)\lor Q(x,y)\bigr)$$

中，$\forall x$ 的辖域是括号里的整个公式。$x$ 的两次出现都受它约束，$y$ 自由。

一个变元符号可以在同一公式中既自由又约束。例如

$$P(x)\land\forall xQ(x)$$

第一个 $x$ 自由，后一个 $x$ 受量词约束。判断时看的是“每一次出现”，不是只看字母。

没有自由变元的公式叫语句或闭公式。语句在给定结构中不再依赖变量赋值；开公式则仍像一个带参数的命题形式。

自然语言符号化

令 $H(x)$ 表示“$x$ 是人”，$M(x)$ 表示“$x$ 会死”，常元 $s$ 表示苏格拉底：

$$\forall x(H(x)\to M(x)),$$ $$H(s),$$

因此希望推出 $M(s)$。

“存在唯一一个对象满足 $P$”应写成存在性加唯一性：

$$\exists x\left( P(x)\land \forall y(P(y)\to y=x) \right).$$

“并不是每个实数都小于它的平方”是

$$\neg\forall x\bigl(Real(x)\to Less(x,x^2)\bigr),$$

也等值于

$$\exists x\bigl(Real(x)\land\neg Less(x,x^2)\bigr).$$

代入为什么需要条件

记 $A[x/t]$ 为用项 $t$ 替换 $A$ 中 $x$ 的自由出现。

考虑

$$A=\forall y\,R(x,y).$$

若直接把 $x$ 换成 $y$，得到

$$\forall y\,R(y,y).$$

原本代入项中的 $y$ 应该自由，却被现有量词 $\forall y$ 绑定，意义变了。这叫变量捕获，所以 $y$ 对 $A$ 中的 $x$ 不可代入。

正确做法是先换名：

$$\forall yR(x,y)\equiv\forall zR(x,z),$$

再代入：

$$A[x/y]=\forall zR(y,z).$$

可代入的判断

若项 $t$ 中出现自由变元 $y$，则 $t$ 对公式中自由变元 $x$ 可代入，要求所有被替换的 $x$ 都不处在 $\forall y$ 或 $\exists y$ 的辖域内。

公理

$$\forall xA\to A[x/t]$$

也必须满足这个条件。考试中漏写“$t$ 对 $x$ 可代入”，公理模式就不完整。