永真不见了

1

谓词公式的换名

∀x(Q(x,y)→∀y(P(x,y)→R(y)))此公式中y既有约

束出现又有自由出现。为了避免变元的约束和自

由的同时出现，引起概念上的混乱，可以对约束

进行改名使得同一个变元要么自由出现变元进行改名，使得同个变元要么自由出现，

要么约束出现，之所以可以这么做，是因为一个

公式的约束变元所用的符号跟公式的真假是无关

的。比如公式∀yP(y)和∀x(P(x)具有同样的意义。

换名规则

1.约束变元可以换名，但是自由变元不能够换名，

换名时应对量词辖域内所出现的该约束变元都进

行换名。

2.

换名后用的符号一定是该辖域内没有的变元名称。换名后用的符号定是该辖域内没有的变元名称

例如：∀x(Q(x,y)→∀y(P(x,y)→R(y)))∧∀xD(x)

可以换名为：

∀x(Q(x,y)→∀z(P(x,z)→R(z)))∧∀uD(u)

但是不能够换为：∀x(Q(x,y)→∀x(P(x,x)→R(x)))

∧∀uD(u)，因为此时改变了变元的约束关系

第二章谓词逻辑

§2.1谓词和量词

§2.2项和公式

§2.3解释和赋值

§2.4永真式

§2.5等值演算

§2.6逻辑推论

作业

§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。

显然,A是永真式当且仅当¬A是永假式，A是永假

式当且仅当¬A是永真式，永真式一定是可满

足式，可满足式未必是永真式。A是永假式

当且仅当A不是可满足式

∀xP(x，y)→∀xP(x，y)是永真式，因为不管

怎样指定解释和赋值，这个蕴含式得前件

和后件总有相同得真值由连接词和后件总有相同得真值，由连接词→得真

值表知道该公式总为真。该公式得永真性

是由连接词得性质决定得，与谓词和量词

得意义无关，这类永真式称为重言式。

定义2.17用谓词逻辑公式B

1

,…,B

n

分别同时替换

命题逻辑公式A中不同命题变元p

1

,…,p

n

得到的谓

词逻辑公式记为，并称其为A的替换实例。

命题逻辑永真式的替换实例称为重言式。

重言式的永真性是由联结词的意义决定的，而与对

量词符号、谓词符号、函数符号、常元等的解释无

言

n

n

pp

BB

A,,

,,

1

1

L

L

关。∀xP(x)→∀xP(x)是重言式，无论如何解释全

称量词符号∀和谓词符号P的意义，蕴涵式

∀xP(x)→∀xP(x)的前后件的真值总是一样的，而

蕴涵联结词的真值表决定了它总是真。

∀xP(x)→P(a)不是重言式，如果将全称量词符号

∀的意义解释为存在量词，它就可能假。

2

如何辨别一个公式是不是重言式呢？

把原子公式和形式为∀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))

∀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，这不是命

题逻辑永真式。

定理2.4重言式一定是永真式。

证明将命题逻辑公式A的替换实例记为

A*。任取解释I和I中赋值v，指定真值赋值v

I,v

如下：

n

n

pp

BB

A,,

,,

1

1

L

L

⎧

ppvBI是若))((

11

归纳证明：对于每个命题逻辑公式A，

v

I,v

(A)=I(A*)(v)

⎪

⎩

⎪

⎨

=

nn

v

ppvBI

pvI

是若))((

,MM

1.若A是p

i

，其中1≤i≤n，则A*是B

i

，

2.若A是¬B，则A*是¬B*，

v

I,v

(A)=¬v

I,v

(B)=¬I(B*)(v)=I(A*)(v)

3.

若AB→CA*B*→C*

))(())(()(*

,

,vAIvBIpAv

i

v

ivI

vI===

是，则是，

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*是永真

式。

重言式都是永真式，永真式未必是重言式。

永真式都是可满足式，可满足式未必是永真式。

一个公式是永假式当且仅当它不是可满足式。

从语义上划分，谓词逻辑公式可分为以下四类：

1.重言式，如P(x)→P(x)。

2.不是重言式的永真式，如∀

xPx→∃xPx。()()

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))

永

公式的类型

可满足式

假

式

永真式

重言式

非重言的永真式

非永真的可满足式

3

例2.17判断∀xA→类型，其中项t对于公式A

中的x是可代入的。

永真式，设解释I和I中赋值v使得I()(v)=0，

因为I(A)(v[x/I(t)(v)])=I()(v)=0，又I(t)(v)∈D

I

，

)])

x

t

A

x

t

A

x

t

A

所以有论域中元素使得I(A)(v[x/I(t)(v)])＝0

所以I(∀xA)(v)=0。

但是不能保证∀xA→总是重言式，例如，

∀xP(x)→P(a)就不是重言式。它只能是p和

p→q这样的非永真的命题逻辑公式的替换实例。

x

t

A

当项t对于公式A中的变元x不可代入时，公式

可能不是永真的，举反例如下：

取A为∃yP(x,y)，t为y，则为∃yP(y,y)。因

为∃yP(x,y)中变元的约束出现数为2，而∃yP(y,y)

中变元的约束出现数为3，所以项t对于公式A中

xI

x

t

A

x

t

AxA→∀

的变元x不可代入。给解释I如下：

D

I

={1,2}，PI(x,y)=1当且仅当x≠y。

则I(∀x∃yP(x,y))=1，而I(∃yP(y,y))=0，所以

∀x∃yP(x,y)→∃yP(y,y)

不是永真式。

例2.19设n是正整数，x

1

,…,x

n

是不同变元，项

t

1

,…,t

n

对于公式A中的x

1

,…,x

n

是可代入的，则

是永真式。

证明任取解释I和I中赋值v。如果

)1则对于任意

n

n

xx

ttn

AAxx,,

,,1

1

1

L

L

L→∀∀

I(∀x

1

…∀x

n

A)(v)=1，则对于任意d

1

,…,d

n

∈D

I

，

I(A)(v[x

1

/d

1

,…,x

n

/d

n

])=1

所以，

因此，是永真式。

1)]))((/,),)((/[)(())((

11

,,

,,

1

1

==vtIxvtIxvAIvAI

nn

xx

tt

n

nLL

L

n

n

xx

ttn

AAxx,,

,,1

1

1

L

L

L→∀∀

例2.18判断语句∃x∀yP(x,y)→∀y∃xP(x,y)类型

解：永真式，不是重言式。

若解释I满足∃x∀yP(x,y)，则有d∈D

I

使得对于每

个c∈D

I

，PI(d,c)=1。因此，对于每个c∈D

I

，都

有同一个d∈D

I

使得PI(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不是命题逻辑永真式。

例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

使得PI(c

d

,d)=1。c

d

中的下

d

dd

标d表示c

d

依赖于d，对不同的d，c

d

可能不同。

因此，可能没有同一个c∈D

I

使得对于每个d∈D

I

，

PI(c,d)=1。I不满足∃x∀yP(x,y)是可能的。

显然，∀y∃xP(x,y)→∃x∀yP(x,y)不是永假式。

我们只需找出两个解释，其中一个使它假，另一个

使它真。

给定使其为真的解释I如下：论域D

I

={d,e}，

PI(d,d)=0，PI(d,e)=0，PI(e,d)=0，PI(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}，

PI′(d,d)=1,PI′(d,e)=0,PI′(e,d)=0,PI′(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。

4

例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

使得PI(a)=1，并且对于

每个d∈D

I

，QI(d)=0。若还有b∈D

I

使得

则因此可得PI(b)=0，则I(∃x(P(x)→Q(x)))=1。因此，可得

到使得该语句为假的解释I如下：

D

I

={a,b}，PI(a)=1，PI(b)=0，QI(a)=QI(b)=0

该语句的一个模型I′如下：

D

I′

={a}，PI′(a)=QI′(a)=1

该语句是非永真的可满足式。

语句∀x(P(x)→P(a))的类型是什么？

解释I使得I(∀x(P(x)→P(a)))=0，当且仅当存在

d∈D

I

使得PI(d)→PI(aI)=0，即PI(d)=1且

PI(aI)=0。这是可以办到的。可取解释I如下。

D

I

={a,b}，PI(a)=0，PI(b)=1，aI=a

))))I(∀x(P(x)→P(a)))

=(PI(a)→PI(a))∧(PI(b)→PI(a))=0

可取满足语句∀x(P(x)→P(a))的解释I′如下。

D

I′

={b}，PI′(b)=1，aI′=b

I′(∀x(P(x)→P(a)))=PI′(b)→PI′(b)=1

语句∀x(P(x)→P(a))是非永真的可满足式。

设I是一个解释，P是一元谓词符号，我们可把论

域D

I

上的一元谓词PI看作D

I

的子集

{x|x∈D

I

∧PI(x)=1}

I(∃xP(x))=1当且仅当PI≠∅

I(∀xP(x))=1当且仅当PI=D

I

I(∀x(P(x)→Q(x)))=1当且仅当PI⊆QI

I(∀x(P(x)↔Q(x)))=1当且仅当PI=QI

I(∀x(P(x)∨Q(x)))=1当且仅当PI∪QI=D

I

I(∃x(P(x)∧Q(x)))=1当且仅当PI∩QI≠∅

语句(∃xP(x)↔∃xQ(x))→∃x(P(x)↔Q(x))的类型

是什么？

解释I使得I(∃xP(x)↔∃xQ(x))=1当且仅当

(PI=QI=∅)或者(PI≠∅且QI≠∅)。

解释I使得I(∃x(P(x)↔Q(x)))=1当且仅当

PI∩QI≠∅或者(∼PI)∩(∼QI)≠∅。

1.若PI=QI=∅，则(∼PI)∩(∼QI)=D

I

≠∅。

2.若PI≠∅且QI≠∅，这时PI∩QI=∅且

(∼PI)∩(∼QI)=∅是可能的。

这表明该语句可能不是永真式。

可取不满足(∃xP(x)↔∃xQ(x))→∃x(P(x)↔Q(x))

的解释I如下。

D

I

={a,b}，PI(a)=0,PI(b)=1,QI(a)=1,QI(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}，PI′(a)=QI′(a)=0，PI′(b)=QI′(b)=1

I′(∃xP(x)↔∃xQ(x))=1，I′(∃x(P(x)↔Q(x)))=1

(∃xP(x)↔∃xQ(x))→∃x(P(x)↔Q(x))不是永假式，

是非永真的可满足式。

要判断一个公式A的类型，首先分析它在一个解

释和该解释中的一个赋值下的意义，看其是否能够

成为真命题或假命题，得出关于A的类型的初步

结论。若估计A是永真式（或永假式），则证明

对于任意解释I和I中任意赋值v，I(A)(v)=1（或

IAv)=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。

5

设W是一个集合，S是W的子集，P是以W中元

素为输入的程序。

若P满足以下条件：如果以S中元素为输入，则P

运行终止且输出“是”；如果以不在S中的元素为

输入，则P运行终止且输出“否”。我们称P解

决了S的判定问题。如果有一个程序解决了S的判

定问题，就称S的判定问题是可解的。

若P满足以下条件：如果以S中元素为输入，则P

运行终止且输出“是”，如果以不在S中的元素为

输入，则P运行不终止；我们就称P部分地解决

了S的判定问题。如果有一个程序部分地解决了S

的判定问题，就称S的判定问题是半可解的。

取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满

足vx)=d,i=1,…,n。因为A是永真式，所以(

i

)

i

I(A)(v)=1，因此I(∀x

1

…∀x

n

A)=1。这表明A的

闭包是永真式。

(⇐)因为∀x

1

…∀x

n

A→A是永真式，所以若A的

闭包是永真式，则A也是永真式。

公式A是永假式当且仅当A的存在闭包是永假式。

证明设A的存在闭包是∃x

1

…∃x

n

A。

(⇒)设A是永假式。

任取解释I和任意d

1

,…,d

n

∈D

I

，令I中赋值v满

足vx)=d,i=1,…,n。因为A是永假式，所以(

i

)

i

I(A)(v)=0，因此I(∃x

1

…∃x

n

A)=0。这表明A的存

在闭包是永假式。

(⇐)因为A→∃x

1

…∃x

n

A是永真式，所以若A的

存在闭包是永假式，则A也是永假式。

作业

11.(4),(5),(6),(7)12.(6)