2024年3月17日发(作者：漆雕夏柳)
谓词公式的换名
∀x (Q(x ,y) →∀y(P(x, y) →R(y)))此公式中y既有约
束出现又有自由出现。为了避免变元的约束和自
由的同时出现，引起概念上的混乱，可以对约束
变元进行改名，使得同进行改名使得同一个变元要么自由出现个变元要么自由出现，
要么约束出现，之所以可以这么做，是因为一个
公式的约束变元所用的符号跟公式的真假是无关
的。比如公式∀yP(y) 和∀x(P(x) 具有同样的意义。
第二章谓词逻辑
§2.1谓词和量词
§2.2项和公式
§2.3解释和赋值
§2.4永真式
§2.5等值演算
§2.6逻辑推论
作业
显然,A是永真式当且仅当
¬
A是永假式，
A是永
假
式当且仅当
¬
A是永
真
式，永真式一定是可满
足式，可满足式未必是永真式。
A是永
假
式
当且仅当
A不是可满足式
∀xP(x
，
y)→∀xP(x
，
y) 是永真式，因为不管
怎样指定解释和赋值，这个蕴含式得前件
和后件总有相同得真值和后件总有相同得真值，由连接词由连接词→得真
值表知道该公式总为真。该公式得永真性
是由连接词得性质决定得，与谓词和量词
得意义无关，这类永真式称为重言式。
换名规则
1.约束变元可以换名，但是自由变元不能够换名，
换名时应对量词辖域内所出现的该约束变元都进
行换名。
2.
换名后用的符号一定是该辖域内没有的变元名称。换名后用的符号定是该辖域内没有的变元名称
例如：∀x (Q(x ,y) →∀y(P(x, y) →R(y)))∧∀x D(x)
可以换名为：
∀x (Q(x ,y) →∀z(P(x, z) →R(z)))∧∀u D(u)
但是不能够换为：∀x (Q(x ,y) →∀x(P(x,x) →R(x)))
∧∀u D(u)，因为此时改变了变元的约束关系
§2.4 永真式
定义2.16设A 是公式。
1.如果A 在每个解释中为真，则称A 为永真式，
也称
A 为逻辑有效的公式。
2.如果A 在每个解释中为假，则称A 为永假式，
也称A 为矛盾式，不可满足式。
3.如果有解释I 和I 中赋值v 使得I(A)(v) = 1 ，
则称A 为可满足式，并称解释I 和赋值v 满
足A。
定义2.17用谓词逻辑公式B
1
,…, B
n
分别同时替换
命题逻辑公式A 中不同命题变元p
1
,…, p
n
得到的谓
词逻辑公式记为
A
p
1
,
n
B
L
,p
1
,
L
,B
n
，并称其为A 的替换实例。
命题逻辑永真式的替换实例称为重言式。
重言式的永真性是由联结词的意义决定的，而与对
量词符号、谓词符号、函数符号、常元等的解释无
关。∀xP(x)→∀xP(x) 是重言式，无论如何解释全言
称量词符号∀和谓词符号P 的意义，蕴涵式
∀xP(x)→∀xP(x) 的前后件的真值总是一样的，而
蕴涵联结词的真值表决定了它总是真。
∀xP(x)→P(a) 不是重言式，如果将全称量词符号
∀的意义解释为存在量词，它就可能假。
1
如何辨别一个公式是不是重言式呢？
把原子公式和形式为∀xA的公式统称为初等公式。
如果把初等公式看做命题变元，不同的初等公式看
做不同的命题变元，该公式成为命题逻辑的永真式，
则该公式就是谓词逻辑的重言式。例如，公式
(∀xA →∀x(A ∨B))→
((∀xB →∀x(A ∨B)) →(∀xA ∨∀xB →∀x(A ∨B)))
是重言式，因为在这个公式中有三个初等公式
∀xA, ∀xB, ∀x(A ∨B)，如果把它们分别看做命题变
元p, q, r，则该公式成为命题逻辑永真式
(p→r) →((q→r) →(p∨q→r))
定理2.4重言式一定是永真式。
证明将命题逻辑公式A 的替换实例
A
p
1
,
L
,p
n
B
1
,
L
,B
n
记为
A
*
。任取解释I 和I 中赋值v ，指定真值赋值v
I, v
如下：
⎧
I(B
1
)(v)若p是p
p
v
I,v
=
⎪
1
⎨
⎪
MM
⎩
I
(
B
n
)(
v
)若
p
是
p
n
归纳证明：对于每个命题逻辑公式A ，
v
I, v
(A) = I(A
*
)(v)
重言式都是永真式，永真式未必是重言式。
永真式都是可满足式，可满足式未必是永真式。
一个公式是永假式当且仅当它不是可满足式。
从语义上划分，谓词逻辑公式可分为以下四类：
1.重言式，如P(x)→P(x)。
2.不是重言式的永真式，如∀
xP(x)→∃xP(x)。
3.非永真的可满足式，如∃xP(x)→∀xP(x)。
4.永假式，如P(x)∧¬P(x)，∀xP(x)∧¬P(x)。
以下公式是重言式：
A→(B →A), (¬A →¬B) →(B →A),
(A→(B →C)) →((A →B) →(A →C))
∀xP(x)→∃xP(x)是永真式，但不是重言式。
∀xP(x)→∃xP(x)是∀xP(x)→¬∀x¬P(x)的缩写。
将初等公式∀xP(x)和∀x¬P(x) 分别看作命题变元
p 和q，则∀xP(x)→¬∀x¬P(x) 成为p →¬q，这
不是命题逻辑永真式不是命题逻辑永真式。
∀xP(x)→∀yP(y)是永真式，但不是重言式。
将初等公式∀xP(x)和∀yP(y) 分别看作命题变元p
和q，则∀xP(x)→∀yP(y) 成为p →q，这不是命
题逻辑永真式。
1.若A 是p
i
，其中1 ≤i≤n，则A
*
是B
i
，
v
v
I,v
(A)=p
I,v
i
=I(B
i
)(v)=I(A
*
)(v)
2.若A 是¬B，则A
*
是¬B
*
，
v
I, v
(A) = ¬v
I, v
(B) = ¬I(B
*
)(v) = I(A
*
)(v)
3.
若A 是B→C，则A
*
是B
*
→C
*
，
v
I, v
(A) = v
I, v
(B) →v
I, v
(C)
= I(B
*
)(v) →I(C
*
)(v) = I(A
*
)(v)
若A 是命题逻辑永真式，则对于任意解释I 和I 中
任意赋值v ，I(A
*
)(v) = v
I, v
(A) = 1，所以A
*
是永真
式。
公式的类型
重言式
永
可满足式
永真式
假
式
非重言的永真式
非永真的可满足式
2
例2.17判断∀xA →
A
x
t
类型，其中项t 对于公式A
中的x 是可代入的。
永真式，设解释I 和I 中赋值v 使得I( )(
A
x
t
v) = 0，
因为I(A)(v[x/I(t)(v)]) = I( )(
A
x
t
v) = 0，又I(t)(v)∈D
I
，
所以有论域中元素使得I(A)(v[x/I(t)(v)]) )])＝0
所以I(∀xA)(v) = 0。
但是不能保证∀xA →
A
x
t
总是重言式，例如，
∀xP(x) →P(a) 就不是重言式。它只能是p 和
p→q 这样的非永真的命题逻辑公式的替换实例。
例2.19设n 是正整数，x
1
,…, x
n
是不同变元，项
t
1
,…, t
n
对于公式A 中的x
1
,…, x
n
是可代入的，则
x
1
x
n
A
L
,x
n
t
1
,
是永真式。
∀L∀→
A
x
1
,
L
,t
n
证明任取解释I 和I 中赋值v。如果
I(∀x
1
…∀x
n
A)(v) = 1)1，则对于任意则对于任意d
1
,…, d
n
∈D
I
，
I(A)(v[x
1
/d
1
,…, x
n
/d
n
]) = 1
所以，
I(A
x
1
,
t
L
,x
n
1
,
L
,t
n
)(v)=I(A)(v[x
1
/I(t
1
)(v),
L
,x
n
/I(t
n
)(v)])=1
因此，
∀
x
→
A
x
1
,
n
1
L∀
x
n
A
t
L
,x
1
,
L
,t
n
是永真式。
例2.18 判断语句∀y∃xP(x, y) →∃x∀yP(x, y)类型
解：是非永真的可满足式。
若解释I 使得I(∀y∃xP(x, y) →∃x∀yP(x, y)) = 0，则I
满足∀y∃xP(x, y)，但是不满足∃x∀yP(x, y)。对于每
个d∈D
I
，存在c
d
∈D
I
使得P
I
(c
d
, d) = 1。c
d
中的下
标d d表示c
d d
依赖于d，对不同的d，c
d d
可能不同。
因此，可能没有同一个c∈D
I
使得对于每个d∈D
I
，
P
I
(c, d) = 1。I 不满足∃x∀yP(x, y) 是可能的。
显然，∀y∃xP(x, y) →∃x∀yP(x, y) 不是永假式。
我们只需找出两个解释，其中一个使它假，另一个
使它真。
当项t 对于公式A 中的变元x 不可代入时，公式
∀xA→A
x
t
可能不是永真的，举反例如下：
取A 为∃yP(x, y)，t 为y，则
A
x
t
为∃yP(y, y)。因
为∃yP(x, y) 中变元的约束出现数为2，而∃yP(y, y)
中变元的约束出现数为3，所以项t 对于公式A 中
的变元x x不可代入。给解释I I如下：
D
I
= {1, 2}，P
I
(x, y) = 1 当且仅当x≠y。
则I (∀x∃yP(x, y)) = 1 ，而I(∃yP(y, y)) = 0 ，所以
∀x∃yP(x, y) →∃yP(y, y)
不是永真式。
例2.18 判断语句∃x∀yP(x, y) →∀y∃xP(x, y) 类型
解：永真式，不是重言式。
若解释I 满足∃x∀yP(x, y)，则有d∈D
I
使得对于每
个c∈D
I
，P
I
(d, c) = 1。因此，对于每个c∈D
I
，都
有同一个d∈D
I
使得P
I
(d, c) = 1。这表明I满足
∀y∃xP(x, y)。
因此，∃x∀yP(x, y) →∀y∃xP(x, y) 是永真式。
∃x∀yP(x, y) →∀y∃xP(x, y) 是
¬∀x¬∀yP(x, y) →∀y¬∀x¬P(x, y)
的缩写，¬p→q 不是命题逻辑永真式。
给定使其为真的解释I 如下：论域D
I
= {d, e}，
P
I
(d,d) = 0，P
I
(d,e) = 0，P
I
(e,d) = 0，P
I
(e,e) = 0
I(∀y∃xP(x, y)) = 0，I(∃x∀yP(x, y)) = 0，
所以I(∀y∃xP(x, y)→∃x∀yP(x, y)) = 1。
给定使其为假的解释I′如下：论域D
I′
= {d, e}，
P
I′
(d,d) = 1, P
I′
(d,e) = 0, P
I′
(e,d) = 0, P
I′
(e,e) = 1
I′(∀y∃xP(x, y)) = 1，I′(∃x∀yP(x, y)) = 0，
所以I′(∀y∃xP(x, y)→∃x∀yP(x, y)) = 0。
3
例2.18 判断
语句∃x(P(x) →Q(x)) →(∃xP(x) →
∃xQ(x)) 的类型是什么？
若解释I 不满足该语句，则I(∃x(P(x) →Q(x))) = 1
且I(∃xP(x) →∃xQ(x)) = 0，因而I(∃xP(x)) = 1，
I(∃xQ(x)) = 0。存在a∈D
I
使得P
I
(a) = 1，并且对于
每个d∈D
I
，Q
I
(d) = 0。若还有b∈D
I
使得
P
I
(b) = 0，则则I(∃x(P(x) →Q(x))) = 1。因此，可得因此可得
到使得该语句为假的解释I 如下：
D
I
={a, b}，P
I
(a) = 1，P
I
(b) = 0，Q
I
(a) = Q
I
(b) = 0
该语句的一个模型I′如下：
D
I′
={a}，P
I′
(a) = Q
I′
(a) = 1
该语句是非永真的可满足式。
设I 是一个解释，P 是一元谓词符号，我们可把论
域D
I
上的一元谓词P
I
看作D
I
的子集
{ x | x∈D
I
∧P
I
(x) = 1}
I(∃xP(x)) = 1 当且仅当P
I
≠∅
I(∀xP(x)) = 1 当且仅当P
I
= D
I
I(∀x(P(x) →Q(x))) = 1 当且仅当P
I
⊆Q
I
I(∀x(P(x) ↔Q(x))) = 1 当且仅当P
I
= Q
I
I(∀x(P(x) ∨Q(x))) = 1 当且仅当P
I
∪Q
I
= D
I
I(∃x(P(x) ∧Q(x))) = 1 当且仅当P
I
∩Q
I
≠∅
可取不满足(∃xP(x) ↔∃xQ(x)) →∃x(P(x) ↔Q(x))
的解释I 如下。
D
I
= {a, b}，P
I
(a) = 0, P
I
(b) = 1, Q
I
(a) = 1, Q
I
(b) = 0
(∃xP(x) ↔∃xQ(x)) →∃x(P(x) ↔Q(x))不是永真式。
可取满足(∃xP(x) ↔∃xQ(x)) →∃x(P(x) ↔Q(x)) 的
解释I′如下。如下
D
I′
= {a, b}，P
I′
(a) = Q
I′
(a) = 0，P
I′
(b) = Q
I′
(b) = 1
I′(∃xP(x) ↔∃xQ(x)) = 1，I′(∃x(P(x) ↔Q(x))) = 1
(∃xP(x) ↔∃xQ(x)) →∃x(P(x) ↔Q(x)) 不是永假式，
是非永真的可满足式。
语句∀x(P(x) →P(a)) 的类型是什么？
解释I 使得I(∀x(P(x) →P(a))) = 0，当且仅当存在
d∈D
I
使得P
I
(d ) →P
I
(a
I
) = 0，即P
I
(d ) = 1 且
P
I
(a
I
) = 0。这是可以办到的。可取解释I 如下。
D
I
= {a, b}，P
I
(a) = 0，P
I
(b) = 1，a
I
= a
I(∀x(P(x) )→P(a))) )))
= (P
I
(a) →P
I
(a)) ∧(P
I
(b) →P
I
(a)) = 0
可取满足语句∀x(P(x) →P(a)) 的解释I′如下。
D
I′
= {b}，P
I′
(b) = 1，a
I′
= b
I′(∀x(P(x) →P(a))) = P
I′
(b) →P
I′
(b) = 1
语句∀x(P(x) →P(a)) 是非永真的可满足式。
语句(∃xP(x) ↔∃xQ(x)) →∃x(P(x) ↔Q(x)) 的类型
是什么？
解释I 使得I(∃xP(x) ↔∃xQ(x)) = 1 当且仅当
(P
I
= Q
I
= ∅) 或者(P
I
≠∅且Q
I
≠∅)。
解释I 使得I(∃x(P(x) ↔Q(x))) = 1 当且仅当
P
I
∩Q
I
≠∅或者(∼P
I
)∩(∼Q
I
)≠∅。
1.若P
I
= Q
I
= ∅，则(∼P
I
)∩(∼Q
I
)=D
I
≠∅。
2.若P
I
≠∅且Q
I
≠∅，这时P
I
∩Q
I
= ∅且
(∼P
I
)∩(∼Q
I
)= ∅是可能的。
这表明该语句可能不是永真式。
要判断一个公式A 的类型，首先分析它在一个解
释和该解释中的一个赋值下的意义，看其是否能够
成为真命题或假命题，得出关于A 的类型的初步
结论。若估计A 是永真式（或永假式），则证明
对于任意解释I 和I 中任意赋值v，I(A)(v) = 1（或
I(A)(v)) = 0）。若估计若估计A 不是永真式不是永真式（或永假式），或永假式，
则具体给出一个解释I 和I 中一个赋值v 使得
I(A)(v) = 0（或I(A)(v) = 1）。
因此，若估计A 是非永真的可满足式，则需具体
给出解释I 和I 中赋值v ，以及解释I′和I′中赋值
v′，使得I(A)(v) = 1，I′(A)(v′) = 0。
4
设W 是一个集合，S 是W 的子集，P 是以W 中元
素为输入的程序。
若P 满足以下条件：如果以S 中元素为输入，则P
运行终止且输出“是”；如果以不在S 中的元素为
输入，则P 运行终止且输出“否”。我们称P 解
决了S 的判定问题。如果有一个程序解决了S 的判
定问题，就称S 的判定问题是可解的。
若P 满足以下条件：如果以S 中元素为输入，则P
运行终止且输出“是”，如果以不在S 中的元素为
输入，则P 运行不终止；我们就称P 部分地解决
了S 的判定问题。如果有一个程序部分地解决了S
的判定问题，就称S 的判定问题是半可解的。
公式A 是永真式当且仅当A 的闭包是永真式。
证明设A 的闭包是∀x
1
…
∀x
n
A 。
(⇒) 设A 是永真式。
任取解释I 和任意d
1
,
…
, d
n
∈D
I
，令I 中赋值v 满
足v(x
i
)) = d
i
, i = 1 ,
…
, n。因为A 是永真式，所以
I(A)(v) = 1，因此I(∀x
1
…
∀x
n
A ) = 1。这表明A 的
闭包是永真式。
(⇐) 因为∀x
1
…
∀x
n
A →A是永真式，所以若A 的
闭包是永真式，则A 也是永真式。
作业
11. (4), (5), (6), (7)12. (6)
取W 为所有一阶逻辑公式的集合，取S 为所有永
真式的集合。可以证明，S 的判定问题是半可解的，
但不是可解的，即一阶谓词逻辑是半可判定的，但
不是可判定的。
若取S 为所有重言式的集合，可以证明，S 的判定
问题是可解的。
取W 为所有二阶逻辑公式的集合，取S 为所有永
真式的集合。可以证明，S 的判定问题不是半可解
的。
公式A 是永假式当且仅当A 的存在闭包是永假式。
证明设A 的存在闭包是∃x
1
…
∃x
n
A。
(⇒) 设A 是永假式。
任取解释I 和任意d
1
,
…
, d
n
∈D
I
，令I 中赋值v 满
足v(x
i
)) = d
i
, i = 1 ,
…
, n。因为A 是永假式，所以
I(A)(v) = 0，因此I(∃x
1
…
∃x
n
A) = 0。这表明A 的存
在闭包是永假式。
(⇐) 因为A →∃x
1
…
∃x
n
A 是永真式，所以若A 的
存在闭包是永假式，则A 也是永假式。
5
2024年3月17日发(作者：漆雕夏柳)
谓词公式的换名
∀x (Q(x ,y) →∀y(P(x, y) →R(y)))此公式中y既有约
束出现又有自由出现。为了避免变元的约束和自
由的同时出现，引起概念上的混乱，可以对约束
变元进行改名，使得同进行改名使得同一个变元要么自由出现个变元要么自由出现，
要么约束出现，之所以可以这么做，是因为一个
公式的约束变元所用的符号跟公式的真假是无关
的。比如公式∀yP(y) 和∀x(P(x) 具有同样的意义。
第二章谓词逻辑
§2.1谓词和量词
§2.2项和公式
§2.3解释和赋值
§2.4永真式
§2.5等值演算
§2.6逻辑推论
作业
显然,A是永真式当且仅当
¬
A是永假式，
A是永
假
式当且仅当
¬
A是永
真
式，永真式一定是可满
足式，可满足式未必是永真式。
A是永
假
式
当且仅当
A不是可满足式
∀xP(x
，
y)→∀xP(x
，
y) 是永真式，因为不管
怎样指定解释和赋值，这个蕴含式得前件
和后件总有相同得真值和后件总有相同得真值，由连接词由连接词→得真
值表知道该公式总为真。该公式得永真性
是由连接词得性质决定得，与谓词和量词
得意义无关，这类永真式称为重言式。
换名规则
1.约束变元可以换名，但是自由变元不能够换名，
换名时应对量词辖域内所出现的该约束变元都进
行换名。
2.
换名后用的符号一定是该辖域内没有的变元名称。换名后用的符号定是该辖域内没有的变元名称
例如：∀x (Q(x ,y) →∀y(P(x, y) →R(y)))∧∀x D(x)
可以换名为：
∀x (Q(x ,y) →∀z(P(x, z) →R(z)))∧∀u D(u)
但是不能够换为：∀x (Q(x ,y) →∀x(P(x,x) →R(x)))
∧∀u D(u)，因为此时改变了变元的约束关系
§2.4 永真式
定义2.16设A 是公式。
1.如果A 在每个解释中为真，则称A 为永真式，
也称
A 为逻辑有效的公式。
2.如果A 在每个解释中为假，则称A 为永假式，
也称A 为矛盾式，不可满足式。
3.如果有解释I 和I 中赋值v 使得I(A)(v) = 1 ，
则称A 为可满足式，并称解释I 和赋值v 满
足A。
定义2.17用谓词逻辑公式B
1
,…, B
n
分别同时替换
命题逻辑公式A 中不同命题变元p
1
,…, p
n
得到的谓
词逻辑公式记为
A
p
1
,
n
B
L
,p
1
,
L
,B
n
，并称其为A 的替换实例。
命题逻辑永真式的替换实例称为重言式。
重言式的永真性是由联结词的意义决定的，而与对
量词符号、谓词符号、函数符号、常元等的解释无
关。∀xP(x)→∀xP(x) 是重言式，无论如何解释全言
称量词符号∀和谓词符号P 的意义，蕴涵式
∀xP(x)→∀xP(x) 的前后件的真值总是一样的，而
蕴涵联结词的真值表决定了它总是真。
∀xP(x)→P(a) 不是重言式，如果将全称量词符号
∀的意义解释为存在量词，它就可能假。
1
如何辨别一个公式是不是重言式呢？
把原子公式和形式为∀xA的公式统称为初等公式。
如果把初等公式看做命题变元，不同的初等公式看
做不同的命题变元，该公式成为命题逻辑的永真式，
则该公式就是谓词逻辑的重言式。例如，公式
(∀xA →∀x(A ∨B))→
((∀xB →∀x(A ∨B)) →(∀xA ∨∀xB →∀x(A ∨B)))
是重言式，因为在这个公式中有三个初等公式
∀xA, ∀xB, ∀x(A ∨B)，如果把它们分别看做命题变
元p, q, r，则该公式成为命题逻辑永真式
(p→r) →((q→r) →(p∨q→r))
定理2.4重言式一定是永真式。
证明将命题逻辑公式A 的替换实例
A
p
1
,
L
,p
n
B
1
,
L
,B
n
记为
A
*
。任取解释I 和I 中赋值v ，指定真值赋值v
I, v
如下：
⎧
I(B
1
)(v)若p是p
p
v
I,v
=
⎪
1
⎨
⎪
MM
⎩
I
(
B
n
)(
v
)若
p
是
p
n
归纳证明：对于每个命题逻辑公式A ，
v
I, v
(A) = I(A
*
)(v)
重言式都是永真式，永真式未必是重言式。
永真式都是可满足式，可满足式未必是永真式。
一个公式是永假式当且仅当它不是可满足式。
从语义上划分，谓词逻辑公式可分为以下四类：
1.重言式，如P(x)→P(x)。
2.不是重言式的永真式，如∀
xP(x)→∃xP(x)。
3.非永真的可满足式，如∃xP(x)→∀xP(x)。
4.永假式，如P(x)∧¬P(x)，∀xP(x)∧¬P(x)。
以下公式是重言式：
A→(B →A), (¬A →¬B) →(B →A),
(A→(B →C)) →((A →B) →(A →C))
∀xP(x)→∃xP(x)是永真式，但不是重言式。
∀xP(x)→∃xP(x)是∀xP(x)→¬∀x¬P(x)的缩写。
将初等公式∀xP(x)和∀x¬P(x) 分别看作命题变元
p 和q，则∀xP(x)→¬∀x¬P(x) 成为p →¬q，这
不是命题逻辑永真式不是命题逻辑永真式。
∀xP(x)→∀yP(y)是永真式，但不是重言式。
将初等公式∀xP(x)和∀yP(y) 分别看作命题变元p
和q，则∀xP(x)→∀yP(y) 成为p →q，这不是命
题逻辑永真式。
1.若A 是p
i
，其中1 ≤i≤n，则A
*
是B
i
，
v
v
I,v
(A)=p
I,v
i
=I(B
i
)(v)=I(A
*
)(v)
2.若A 是¬B，则A
*
是¬B
*
，
v
I, v
(A) = ¬v
I, v
(B) = ¬I(B
*
)(v) = I(A
*
)(v)
3.
若A 是B→C，则A
*
是B
*
→C
*
，
v
I, v
(A) = v
I, v
(B) →v
I, v
(C)
= I(B
*
)(v) →I(C
*
)(v) = I(A
*
)(v)
若A 是命题逻辑永真式，则对于任意解释I 和I 中
任意赋值v ，I(A
*
)(v) = v
I, v
(A) = 1，所以A
*
是永真
式。
公式的类型
重言式
永
可满足式
永真式
假
式
非重言的永真式
非永真的可满足式
2
例2.17判断∀xA →
A
x
t
类型，其中项t 对于公式A
中的x 是可代入的。
永真式，设解释I 和I 中赋值v 使得I( )(
A
x
t
v) = 0，
因为I(A)(v[x/I(t)(v)]) = I( )(
A
x
t
v) = 0，又I(t)(v)∈D
I
，
所以有论域中元素使得I(A)(v[x/I(t)(v)]) )])＝0
所以I(∀xA)(v) = 0。
但是不能保证∀xA →
A
x
t
总是重言式，例如，
∀xP(x) →P(a) 就不是重言式。它只能是p 和
p→q 这样的非永真的命题逻辑公式的替换实例。
例2.19设n 是正整数，x
1
,…, x
n
是不同变元，项
t
1
,…, t
n
对于公式A 中的x
1
,…, x
n
是可代入的，则
x
1
x
n
A
L
,x
n
t
1
,
是永真式。
∀L∀→
A
x
1
,
L
,t
n
证明任取解释I 和I 中赋值v。如果
I(∀x
1
…∀x
n
A)(v) = 1)1，则对于任意则对于任意d
1
,…, d
n
∈D
I
，
I(A)(v[x
1
/d
1
,…, x
n
/d
n
]) = 1
所以，
I(A
x
1
,
t
L
,x
n
1
,
L
,t
n
)(v)=I(A)(v[x
1
/I(t
1
)(v),
L
,x
n
/I(t
n
)(v)])=1
因此，
∀
x
→
A
x
1
,
n
1
L∀
x
n
A
t
L
,x
1
,
L
,t
n
是永真式。
例2.18 判断语句∀y∃xP(x, y) →∃x∀yP(x, y)类型
解：是非永真的可满足式。
若解释I 使得I(∀y∃xP(x, y) →∃x∀yP(x, y)) = 0，则I
满足∀y∃xP(x, y)，但是不满足∃x∀yP(x, y)。对于每
个d∈D
I
，存在c
d
∈D
I
使得P
I
(c
d
, d) = 1。c
d
中的下
标d d表示c
d d
依赖于d，对不同的d，c
d d
可能不同。
因此，可能没有同一个c∈D
I
使得对于每个d∈D
I
，
P
I
(c, d) = 1。I 不满足∃x∀yP(x, y) 是可能的。
显然，∀y∃xP(x, y) →∃x∀yP(x, y) 不是永假式。
我们只需找出两个解释，其中一个使它假，另一个
使它真。
当项t 对于公式A 中的变元x 不可代入时，公式
∀xA→A
x
t
可能不是永真的，举反例如下：
取A 为∃yP(x, y)，t 为y，则
A
x
t
为∃yP(y, y)。因
为∃yP(x, y) 中变元的约束出现数为2，而∃yP(y, y)
中变元的约束出现数为3，所以项t 对于公式A 中
的变元x x不可代入。给解释I I如下：
D
I
= {1, 2}，P
I
(x, y) = 1 当且仅当x≠y。
则I (∀x∃yP(x, y)) = 1 ，而I(∃yP(y, y)) = 0 ，所以
∀x∃yP(x, y) →∃yP(y, y)
不是永真式。
例2.18 判断语句∃x∀yP(x, y) →∀y∃xP(x, y) 类型
解：永真式，不是重言式。
若解释I 满足∃x∀yP(x, y)，则有d∈D
I
使得对于每
个c∈D
I
，P
I
(d, c) = 1。因此，对于每个c∈D
I
，都
有同一个d∈D
I
使得P
I
(d, c) = 1。这表明I满足
∀y∃xP(x, y)。
因此，∃x∀yP(x, y) →∀y∃xP(x, y) 是永真式。
∃x∀yP(x, y) →∀y∃xP(x, y) 是
¬∀x¬∀yP(x, y) →∀y¬∀x¬P(x, y)
的缩写，¬p→q 不是命题逻辑永真式。
给定使其为真的解释I 如下：论域D
I
= {d, e}，
P
I
(d,d) = 0，P
I
(d,e) = 0，P
I
(e,d) = 0，P
I
(e,e) = 0
I(∀y∃xP(x, y)) = 0，I(∃x∀yP(x, y)) = 0，
所以I(∀y∃xP(x, y)→∃x∀yP(x, y)) = 1。
给定使其为假的解释I′如下：论域D
I′
= {d, e}，
P
I′
(d,d) = 1, P
I′
(d,e) = 0, P
I′
(e,d) = 0, P
I′
(e,e) = 1
I′(∀y∃xP(x, y)) = 1，I′(∃x∀yP(x, y)) = 0，
所以I′(∀y∃xP(x, y)→∃x∀yP(x, y)) = 0。
3
例2.18 判断
语句∃x(P(x) →Q(x)) →(∃xP(x) →
∃xQ(x)) 的类型是什么？
若解释I 不满足该语句，则I(∃x(P(x) →Q(x))) = 1
且I(∃xP(x) →∃xQ(x)) = 0，因而I(∃xP(x)) = 1，
I(∃xQ(x)) = 0。存在a∈D
I
使得P
I
(a) = 1，并且对于
每个d∈D
I
，Q
I
(d) = 0。若还有b∈D
I
使得
P
I
(b) = 0，则则I(∃x(P(x) →Q(x))) = 1。因此，可得因此可得
到使得该语句为假的解释I 如下：
D
I
={a, b}，P
I
(a) = 1，P
I
(b) = 0，Q
I
(a) = Q
I
(b) = 0
该语句的一个模型I′如下：
D
I′
={a}，P
I′
(a) = Q
I′
(a) = 1
该语句是非永真的可满足式。
设I 是一个解释，P 是一元谓词符号，我们可把论
域D
I
上的一元谓词P
I
看作D
I
的子集
{ x | x∈D
I
∧P
I
(x) = 1}
I(∃xP(x)) = 1 当且仅当P
I
≠∅
I(∀xP(x)) = 1 当且仅当P
I
= D
I
I(∀x(P(x) →Q(x))) = 1 当且仅当P
I
⊆Q
I
I(∀x(P(x) ↔Q(x))) = 1 当且仅当P
I
= Q
I
I(∀x(P(x) ∨Q(x))) = 1 当且仅当P
I
∪Q
I
= D
I
I(∃x(P(x) ∧Q(x))) = 1 当且仅当P
I
∩Q
I
≠∅
可取不满足(∃xP(x) ↔∃xQ(x)) →∃x(P(x) ↔Q(x))
的解释I 如下。
D
I
= {a, b}，P
I
(a) = 0, P
I
(b) = 1, Q
I
(a) = 1, Q
I
(b) = 0
(∃xP(x) ↔∃xQ(x)) →∃x(P(x) ↔Q(x))不是永真式。
可取满足(∃xP(x) ↔∃xQ(x)) →∃x(P(x) ↔Q(x)) 的
解释I′如下。如下
D
I′
= {a, b}，P
I′
(a) = Q
I′
(a) = 0，P
I′
(b) = Q
I′
(b) = 1
I′(∃xP(x) ↔∃xQ(x)) = 1，I′(∃x(P(x) ↔Q(x))) = 1
(∃xP(x) ↔∃xQ(x)) →∃x(P(x) ↔Q(x)) 不是永假式，
是非永真的可满足式。
语句∀x(P(x) →P(a)) 的类型是什么？
解释I 使得I(∀x(P(x) →P(a))) = 0，当且仅当存在
d∈D
I
使得P
I
(d ) →P
I
(a
I
) = 0，即P
I
(d ) = 1 且
P
I
(a
I
) = 0。这是可以办到的。可取解释I 如下。
D
I
= {a, b}，P
I
(a) = 0，P
I
(b) = 1，a
I
= a
I(∀x(P(x) )→P(a))) )))
= (P
I
(a) →P
I
(a)) ∧(P
I
(b) →P
I
(a)) = 0
可取满足语句∀x(P(x) →P(a)) 的解释I′如下。
D
I′
= {b}，P
I′
(b) = 1，a
I′
= b
I′(∀x(P(x) →P(a))) = P
I′
(b) →P
I′
(b) = 1
语句∀x(P(x) →P(a)) 是非永真的可满足式。
语句(∃xP(x) ↔∃xQ(x)) →∃x(P(x) ↔Q(x)) 的类型
是什么？
解释I 使得I(∃xP(x) ↔∃xQ(x)) = 1 当且仅当
(P
I
= Q
I
= ∅) 或者(P
I
≠∅且Q
I
≠∅)。
解释I 使得I(∃x(P(x) ↔Q(x))) = 1 当且仅当
P
I
∩Q
I
≠∅或者(∼P
I
)∩(∼Q
I
)≠∅。
1.若P
I
= Q
I
= ∅，则(∼P
I
)∩(∼Q
I
)=D
I
≠∅。
2.若P
I
≠∅且Q
I
≠∅，这时P
I
∩Q
I
= ∅且
(∼P
I
)∩(∼Q
I
)= ∅是可能的。
这表明该语句可能不是永真式。
要判断一个公式A 的类型，首先分析它在一个解
释和该解释中的一个赋值下的意义，看其是否能够
成为真命题或假命题，得出关于A 的类型的初步
结论。若估计A 是永真式（或永假式），则证明
对于任意解释I 和I 中任意赋值v，I(A)(v) = 1（或
I(A)(v)) = 0）。若估计若估计A 不是永真式不是永真式（或永假式），或永假式，
则具体给出一个解释I 和I 中一个赋值v 使得
I(A)(v) = 0（或I(A)(v) = 1）。
因此，若估计A 是非永真的可满足式，则需具体
给出解释I 和I 中赋值v ，以及解释I′和I′中赋值
v′，使得I(A)(v) = 1，I′(A)(v′) = 0。
4
设W 是一个集合，S 是W 的子集，P 是以W 中元
素为输入的程序。
若P 满足以下条件：如果以S 中元素为输入，则P
运行终止且输出“是”；如果以不在S 中的元素为
输入，则P 运行终止且输出“否”。我们称P 解
决了S 的判定问题。如果有一个程序解决了S 的判
定问题，就称S 的判定问题是可解的。
若P 满足以下条件：如果以S 中元素为输入，则P
运行终止且输出“是”，如果以不在S 中的元素为
输入，则P 运行不终止；我们就称P 部分地解决
了S 的判定问题。如果有一个程序部分地解决了S
的判定问题，就称S 的判定问题是半可解的。
公式A 是永真式当且仅当A 的闭包是永真式。
证明设A 的闭包是∀x
1
…
∀x
n
A 。
(⇒) 设A 是永真式。
任取解释I 和任意d
1
,
…
, d
n
∈D
I
，令I 中赋值v 满
足v(x
i
)) = d
i
, i = 1 ,
…
, n。因为A 是永真式，所以
I(A)(v) = 1，因此I(∀x
1
…
∀x
n
A ) = 1。这表明A 的
闭包是永真式。
(⇐) 因为∀x
1
…
∀x
n
A →A是永真式，所以若A 的
闭包是永真式，则A 也是永真式。
作业
11. (4), (5), (6), (7)12. (6)
取W 为所有一阶逻辑公式的集合，取S 为所有永
真式的集合。可以证明，S 的判定问题是半可解的，
但不是可解的，即一阶谓词逻辑是半可判定的，但
不是可判定的。
若取S 为所有重言式的集合，可以证明，S 的判定
问题是可解的。
取W 为所有二阶逻辑公式的集合，取S 为所有永
真式的集合。可以证明，S 的判定问题不是半可解
的。
公式A 是永假式当且仅当A 的存在闭包是永假式。
证明设A 的存在闭包是∃x
1
…
∃x
n
A。
(⇒) 设A 是永假式。
任取解释I 和任意d
1
,
…
, d
n
∈D
I
，令I 中赋值v 满
足v(x
i
)) = d
i
, i = 1 ,
…
, n。因为A 是永假式，所以
I(A)(v) = 0，因此I(∃x
1
…
∃x
n
A) = 0。这表明A 的存
在闭包是永假式。
(⇐) 因为A →∃x
1
…
∃x
n
A 是永真式，所以若A 的
存在闭包是永假式，则A 也是永假式。
5