Chap24 一阶谓词逻辑

1、学习目标

命题逻辑只把整句话看成真假对象，一阶谓词逻辑继续拆开句子内部结构：对象、性质、关系、函数、量词和变元。

本章主线：

一阶语言：规定什么是项，什么是公式。
自由/约束变元：判断量词到底管住了谁。
NL：自然推演系统，在 N 上增加量词规则。
KL：形式系统，在 P 上增加量词公理。
解释与赋值：给公式一个语义世界。
可靠性与和谐性：可证和真之间的关系。
期末题：用证明、反例解释和语义证明收束全章。

Auto_Tutor 中本章资料包括 24.1-24.8 课件、期末考试 和 期末考试答案。下面的“期末题答案”按试卷题号 1-7 整理。

2、一阶谓词逻辑在做什么

命题逻辑的基本单位是命题变元：

1 2	p: 小王是学生 q: 小王会 C++

一阶谓词逻辑把命题继续拆成：

对象：小王、张三、某个自然数
谓词：是学生、会 C++、小于、相等
函数：父亲、后继、加法、乘法
量词：所有、存在

例如：

所有学生都会 C++。
forall x (Student(x) -> Cpp(x))

存在一个学生会 C++。
exists x (Student(x) and Cpp(x))

符号化时最常见的坑是把全称句写成合取、把存在句写成蕴含。经验规则：

1 2	“所有 A 都 B”：forall x (A(x) -> B(x)) “存在 A 是 B”：exists x (A(x) and B(x))

3、一阶语言 L

一阶语言由两类符号组成。

逻辑符号：

个体变元：x0,x1,x2,...，常写 x,y,z
联结词：not, ->，以及作为简写的 and, or, <->
量词：forall, exists
括号、逗号

非逻辑符号：

1
2
3

个体常元：c,a,b,...
谓词符号：F^n,G^n,R^n,...
函数符号：f^m,g^m,h^m,...

其中上标表示元数。比如：

1
2
3

F^1(x)       一元谓词，表示 x 具有性质 F
R^2(x,y)     二元谓词，表示 x 与 y 有关系 R
f^2(x,y)     二元函数，表示由 x,y 算出一个对象

项

项表示一个对象。

形成规则：

1. 个体变元是项。
2. 个体常元是项。
3. 若 f 是 m 元函数符号，t1,...,tm 是项，
   则 f(t1,...,tm) 是项。

例如：

x
c
f(x)
g(f(x),c)

公式

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

1	F(t1,...,tn)

公式形成规则：

1. 原子公式是公式。
2. 若 alpha 是公式，则 not alpha 是公式。
3. 若 alpha,beta 是公式，则 alpha -> beta 是公式。
4. 若 alpha 是公式，x 是个体变元，
   则 forall x alpha、exists x alpha 是公式。

and/or/<-> 通常作为简写使用：

1
2
3

alpha or beta  :=  not alpha -> beta
alpha and beta :=  not (alpha -> not beta)
exists x alpha :=  not forall x not alpha

4、自由变元、约束变元与替换

量词有自己的辖域。

1 2	forall x alpha exists x alpha

在 alpha 中被这个量词管住的 x 是约束出现；没有被任何对应量词管住的出现是自由出现。

例子：

1	forall x F(x,y)

这里：

1 2	x 是约束变元 y 是自由变元

再看：

1	forall x (F(x) -> exists x G(x,y))

外层 forall x 管住 F(x) 中的 x；内层 exists x 重新绑定 G(x,y) 中的 x。这类似程序里的局部变量遮蔽。

替换自由性

把 alpha 中自由出现的 x 替换成项 t，记为：

1	alpha(x/t)

要求：

1	t 对 x 在 alpha 中自由

含义是：替换后，t 里的自由变元不会被 alpha 原有量词错误捕获。

反例：

1 2	alpha = exists y F(x,y) t = y

若直接替换得到：

1	exists y F(y,y)

原来 t 里的自由 y 被 exists y 捕获，语义变了，所以 y 对 x 在 alpha 中不自由。

一阶谓词逻辑的主要失分点不是会不会写量词，而是有没有检查附加条件：替换是否自由、全称引入是否允许、存在消去的新变元是否干净。

5、自然推演系统 NL

NL 是命题自然推演系统 N 加上量词规则。

可以记成：

1	NL = N + 量词规则

四个核心量词规则：

规则	形式	使用条件
`forall-`	由 `forall x alpha` 推出 `alpha(x/t)`	`t` 对 `x` 在 `alpha` 中自由
`forall+`	由 `alpha` 推出 `forall x alpha`	`x` 不在未解除假设中自由出现
`exists+`	由 `alpha(x/t)` 推出 `exists x alpha`	`t` 对 `x` 在 `alpha` 中自由
`exists-`	由 `exists x alpha` 和从见证推出 `beta`，得到 `beta`	见证变元不能在开放假设和结论中自由出现

直观理解：

forall-：全称命题可以代入任意对象。
forall+：若对象没有特殊性，就能推广到所有对象。
exists+：找到一个例子，就能推出存在。
exists-：用存在见证时，见证必须是新鲜的，不能偷带额外信息。

NL 证明技巧

要证 Sigma |- alpha -> beta：
先证 Sigma, alpha |- beta。

要证 Sigma |- forall x alpha：
先证 Sigma |- alpha，并检查 x 不在 Sigma 中自由出现。

要用 exists x alpha：
引入一个临时见证，证明目标 beta；
最后消去这个临时见证。

要证不是内定理：
通常给一个解释和赋值，让公式为假，再用可靠性排除可证性。

6、形式系统 KL

KL 是一阶谓词演算的形式系统，可以看成：

1	KL = P + 量词公理

它不像 NL 那样接近日常推理，而是使用公理模式和 MP。

KL 的核心公理模式可以按用途记：

K1-K3：命题逻辑 P 的公理模式。

K4：forall x alpha -> alpha(x/t)
    条件：t 对 x 在 alpha 中自由。

K5：alpha -> forall x alpha
    条件：x 不在 alpha 中自由出现。

K6：forall x (alpha -> beta) -> (forall x alpha -> forall x beta)

MP：

1	由 alpha 和 alpha -> beta 推出 beta。

KL 里常用的元定理：

1 2	若 Sigma \|- alpha，且 x 不在 Sigma 的任何公式中自由出现，则 Sigma \|- forall x alpha。

这个定理也正是期末第 7 题。

习题课强调：在一个证明里不要混用不同系统。写 NL 证明就用 NL 的规则；写 KL 证明就用 KL 的公理、元定理和 MP。

7、NL 与 KL 的关系

NL 和 KL 证明风格不同，但表达的可证内容等价。

1 2	NL：自然推演，适合写人能看懂的证明。 KL：公理系统，适合研究元定理和系统性质。

考试时可以这样处理：

1
2
3

要求“在 NL 中证明”：写自然推演路线，标清量词规则和条件。
要求“在 KL 中证明”：写公理/元定理/MP 的链条。
要求“证明”：可用可靠性、完全性、NL/KL 等价性等元结果。

8、解释、赋值与公式真假

一阶语言只有语法还不够，还要给符号解释。

一个解释通常写作：

1	I = <D, {F_i}, {f_j}, {c_k}>

其中：

D：非空论域。
F_i：谓词符号解释成 D 上的关系。
f_j：函数符号解释成 D 上的函数。
c_k：常元符号解释成 D 中的元素。

赋值：

1	sigma : {x0,x1,x2,...} -> D

它把每个个体变元送到论域中的对象。

项的值递归定义：

1
2
3

x^I_sigma = sigma(x)
c^I_sigma = c^I
f(t1,...,tn)^I_sigma = f^I(t1^I_sigma,...,tn^I_sigma)

公式满足关系写作：

1	I \|=_sigma alpha

量词语义：

I |=_sigma forall x alpha
<=> 对任意 a in D，都有 I |=_{sigma[x:=a]} alpha

I |=_sigma exists x alpha
<=> 存在 a in D，使 I |=_{sigma[x:=a]} alpha

反例解释的套路：选一个很小或很熟的论域，例如 {0,1}、自然数、实数；再把谓词解释成相等关系、大小关系、偶数集合、有理数集合等。

9、可靠性、完备性与和谐性

三件事的含义：

1
2
3

可靠性：若 Sigma |- alpha，则 Sigma |= alpha。
完备性：若 Sigma |= alpha，则 Sigma |- alpha。
和谐性：不存在 alpha，使得 |- alpha 且 |- not alpha。

理解方式：

1
2
3

可靠性：证明系统不会证明假的东西。
完备性：语义上必真的东西，证明系统也能证明出来。
和谐性：系统内部不会自相矛盾。

证明不是内定理的标准方法：

1
2
3

1. 给出一个解释 I 和赋值 sigma。
2. 算出 I |=_sigma alpha 不成立。
3. 由可靠性可知 alpha 不可能是内定理。

10、期末题答案

第 1 题、证明 `{not, <->}` 不是联结词完全集

要证：

1	{not, <->} 不是联结词完全集。

关键不变量：

1 2	只用 not 和 <-> 构造的二元命题公式，它的成真赋值个数一定是偶数。

证明思路：

对公式中联结词个数做归纳。
若公式是 not beta，则真假集合互补；在二元赋值空间中，偶数性保持。
若公式是 beta <-> gamma，成真赋值由二者同真或同假组成；按归纳假设可证明成真个数仍为偶数。

然后取一个二元真值函数：

f(0,0)=1
f(0,1)=0
f(1,0)=0
f(1,1)=0

它只有 1 个成真赋值，是奇数，所以不能由 {not, <->} 表示。

因此 {not, <->} 不是联结词完全集。

第 2 题、判断两个命题公式是否为 N 的内定理

2.1 `((p -> q) -> q) -> ((q -> p) -> p)`

答案：是 N 的内定理。

自然推演思路：

1. 假设 A: (p -> q) -> q。
2. 假设 B: q -> p。
3. 为了证 p，反设 not p。
4. 在 not p 下，若再假设 p，则矛盾推出 q，
   所以得到 p -> q。
5. 由 A 和 p -> q 得 q。
6. 由 B 和 q 得 p。
7. 与 not p 矛盾，所以推出 p。
8. 依次解除假设，得到：
   ((p -> q) -> q) -> ((q -> p) -> p)

2.2 `(p -> q) -> ((not p -> q) -> not q)`

答案：不是 N 的内定理。

给出成假赋值：

1 2	p = 1 q = 1

计算：

p -> q = 1
not p -> q = 0 -> 1 = 1
not q = 0
((not p -> q) -> not q) = 1 -> 0 = 0

(p -> q) -> ((not p -> q) -> not q)
= 1 -> 0
= 0

由 N 的可靠性，它不是 N 的内定理。

第 3 题、选派 A/B/C 出国进修

设：

1
2
3

p: A 去
q: B 去
r: C 去

题目条件按官方答案符号化为：

1
2
3

1. p -> r
2. q -> not r
3. (p or q) -> not r

令：

1	alpha = (p -> r) and (q -> not r) and ((p or q) -> not r)

化成合取范式：

alpha
= (not p or r) and (not q or not r) and (not(p or q) or not r)
= (not p or r) and (not q or not r) and ((not p and not q) or not r)
= (not p or r) and (not q or not r) and (not p or not r)

满足 alpha 的赋值：

1	000, 010, 001

但题目要求从三人中选 1-2 名，排除 000。

所以方案有 2 种：

1 2	010：只有 B 去 001：只有 C 去

如果把条件 (3) 理解为 not r -> (p or q)，则会得到另一组方案：只有 B 去、只有 C 去、A 和 C 去。期末答案特别指出这是不少同学的另一种理解；本笔记按官方答案整理。

第 4 题、判断两个谓词公式是否为 KL 的内定理

4.1 `exists y forall x F(x,y) -> forall x exists y F(x,y)`

答案：是 KL 的内定理。

直观含义：

1 2	如果存在一个统一的 y，使所有 x 都满足 F(x,y)，那么对每个 x，当然都存在某个 y 使 F(x,y) 成立。

KL 证明骨架：

1. forall x F(x,y) -> F(x,y)                                      K4
2. exists y forall x F(x,y) -> exists y F(x,y)                    已证存在推广形式
3. forall x (exists y forall x F(x,y) -> exists y F(x,y))         全称推广
4. forall x (A -> B(x)) -> (A -> forall x B(x))                   x 不在 A 中自由
5. exists y forall x F(x,y) -> forall x exists y F(x,y)           MP

其中：

1 2	A = exists y forall x F(x,y) B(x) = exists y F(x,y)

4.2 `forall x exists y F(x,y) -> exists y forall x F(x,y)`

答案：不是 KL 的内定理。

反例解释：

1 2	论域 D = R F(x,y) 解释为 x = y

前件：

1	forall x exists y F(x,y)

为真。因为每个实数 x 都可以取 y=x。

后件：

1	exists y forall x F(x,y)

为假。因为不存在一个固定实数 y 等于所有实数。

所以整个蕴含为假。由 KL 的可靠性，它不是 KL 的内定理。

第 5 题、判断两个谓词公式是否为 NL 的内定理

5.1 `exists x (alpha -> beta) -> (forall x alpha -> beta)`

答案：不一定是 NL 的内定理。

反例：

语言 L = {F,G}
alpha = F(x)
beta = G(x)
论域 D = R
F 解释为整个实数集 R
G 解释为有理数集 Q
赋值 sigma(x) = sqrt(2)

计算：

1	exists x (F(x) -> G(x)) 为真

因为可取一个有理数作为见证，此时 F(x) 与 G(x) 都真。

1	forall x F(x) 为真

因为 F 被解释为整个实数集。

但：

1	G(x) 在 sigma(x)=sqrt(2) 下为假

所以：

1	forall x alpha -> beta

为假，进而整个公式为假。由可靠性可知它不是 NL 的内定理。

5.2 `forall x (alpha -> beta) -> (exists x alpha -> beta)`

答案：是 NL 的内定理。

使用条件：

1	x 不在 beta 中自由出现。

自然推演证明：

1. 假设 forall x (alpha -> beta)。
2. 假设 exists x alpha。
3. 对 exists x alpha 使用 exists-，取一个新见证 a，使 alpha(x/a) 成立。
4. 由 forall x (alpha -> beta) 和 forall- 得：
   alpha(x/a) -> beta
5. 由 alpha(x/a) 与 alpha(x/a) -> beta 得 beta。
6. 因为 a 不在 beta 和开放假设中自由出现，
   可由 exists- 得 beta。
7. 解除假设 exists x alpha，得到：
   exists x alpha -> beta
8. 再解除假设 forall x (alpha -> beta)，得到：
   forall x (alpha -> beta) -> (exists x alpha -> beta)

若 x 在 beta 中自由出现，上面的结论一般不成立。量词定理的“变量不自由出现”条件不能省略。

第 6 题、证明 `forall x alpha -> alpha(x/t)` 为永真式

条件：

1	t 对 x 在 alpha 中自由

语义证明：

任取解释 I 和赋值 sigma。假设：

1	I \|=_sigma forall x alpha

由全称量词语义：

1	对任意 a in D，都有 I \|=_{sigma[x:=a]} alpha

特别取：

1	a = t^I_sigma

即项 t 在解释 I 和赋值 sigma 下的值。

于是：

1	I \|=_{sigma[x:=t^I_sigma]} alpha

又因为 t 对 x 在 alpha 中自由，根据替换引理：

1	I \|=_sigma alpha(x/t)

所以：

1	I \|=_sigma forall x alpha -> alpha(x/t)

由于 I 和 sigma 任意，该公式是永真式。

期末答案特别提醒：不能只写“这是 KL 公理，所以永真”。题目要求语义证明，直接拿公理当理由会扣分。

第 7 题、全称推广定理

命题：

1
2
3

若 Sigma |- alpha，
且个体变元 x 不在 Sigma 的任何公式中自由出现，
则 Sigma |- forall x alpha。

证明思路：对 Sigma |- alpha 的 KL 证明序列长度做归纳。

设证明序列为：

1	alpha1, alpha2, ..., alphan = alpha

归纳目标：

1	对每个 i，都有 Sigma \|- forall x alphai。

基础情形：

alphai 是公理：
  forall x alphai 仍可由 KL 的公理/推广结果得到。

alphai 属于 Sigma：
  因为 x 不在 Sigma 的任何公式中自由出现，
  所以 x 不在 alphai 中自由出现。
  由 K5 得 alphai -> forall x alphai。
  又 Sigma |- alphai，
  用 MP 得 Sigma |- forall x alphai。

归纳步骤：

若 alphak 由 alphaj 和 alphaj -> alphak 经 MP 得到，则由归纳假设：

1 2	Sigma \|- forall x alphaj Sigma \|- forall x (alphaj -> alphak)

再用 K6：

1 2	forall x (alphaj -> alphak) -> (forall x alphaj -> forall x alphak)

两次 MP 得：

1	Sigma \|- forall x alphak

归纳完成，所以：

1	Sigma \|- forall x alpha

11、复盘清单

1. 会区分项、原子公式和一般公式。
2. 会判断自由变元、约束变元和量词辖域。
3. 会判断 t 对 x 在 alpha 中是否自由。
4. 会写 forall/exists 的语义。
5. 会用反解释证明公式不是内定理。
6. NL 证明要检查 forall+ 和 exists- 的附加条件。
7. KL 证明要分清 K4/K5/K6 和 MP 的使用。
8. 看到 forall x exists y 与 exists y forall x，要警惕量词顺序不能交换。
9. 语义证明不要偷换成“它是公理所以成立”。
10. 可靠性用来从“有成假解释”推出“不是内定理”。