第 14 章　谓词逻辑

优质

小牛编辑

135浏览

2023-12-01

现在要把注意力转移到一般化的命题逻辑，也就是“谓词”逻辑或者说“一阶”逻辑上。谓词是指返回布尔值的具有0个或更多变量的函数。因此，谓词可能有时为真有时为假，这取决于其参数的值。例如，我们将看到csg (C,S,G )这样的谓词逻辑原子操作数。其中，csg 是谓词名，而C、S 和G 则是参数。可以将该表达式视作图8-1中数据库关系“课程-学号-成绩”的逻辑表示。只要C、S 和G 满足学号S 的学生在课程C 中得到成绩G，它就返回TRUE，否则返回FALSE。

用谓词代替命题变量作为原子操作数，提供的语言要比只涉及命题的表达式更为强大。其实，谓词逻辑的表达力足以构成很多实用编程语言的基础，比如Prolog（Programming in logic）和8.7节中我们提到过的SQL语言。谓词逻辑还应用在推理系统或“专家”系统中，比如自动化医疗诊断程序和定理证明程序。

14.1　本章主要内容

我们将在14.2节介绍谓词。谓词在正式地表示思路方面提供了比命题变量强大得多的能力。虽然存在重大差异，但谓词逻辑的设计与第12章中命题逻辑的设计是可以类比的。

谓词逻辑的表达式可以由使用命题逻辑运算符的谓词构建（14.3节）。
“量词”是命题逻辑中没有类比物的谓词逻辑运算符（14.4节）。我们可以利用量词陈述某表达式对某个参数的所有值都为真，或陈述该参数至少存在一个值使得该表达式为真。
谓词逻辑表达式的“解释”是谓词和变量可能的含义（14.5节），它们与命题逻辑中的真值赋值是类似的。
谓词逻辑的重言式是指对所有解释都为真的表达式。某些谓词逻辑的重言式与命题逻辑的重言式是类似的（14.6节），而另一些则不具相似性（14.7节）。
谓词逻辑中的证明可以用与命题逻辑证明相类似的方式进行（14.8节和14.9节）。

14.10节要讨论谓词逻辑与计算问题解答有关的含义，我们会发现以下现象。

命题是重言式并不说明它在某个证明系统中是可证的。
特别要指出的是，哥德尔不完备性定理表明，存在某种特定形式的处理整数的谓词逻辑，在这种谓词逻辑中没有哪种证明系统可以证明每一个重言式。
此外，图灵定理表明，存在我们可以陈述但无法用任何计算机解决的问题。这种问题的例子之一是，某给定的C语言程序是否会在处理某些输入时进入无限循环。

14.2　谓词

谓词是对命题变量的一般化。回想一下12.10节，假设我们有3个命题：r（“天在下雨”）、u（“乔伊带着伞”）和w（“乔伊被淋湿”）。还进一步假设有3个前提，或者说我们假设为真的表达式：r→u（“如果天在下雨，那么乔伊带着伞”）、 $u\to\overline{w}$ （“如果乔伊带伞了，那么他不会被淋湿”），以及 $\overline{r}\to\overline{w}$ （“如果没有下雨，乔伊不会被淋湿”）。

对乔伊为真的事情对玛丽、苏还有比尔等人也为真，因此可以把命题u 看作u_Joe，而w 就是命题w_Joe 。如果这样看的话，就有前提

r →u_Joe， $u_{joe}\to\overline{w}_{joe}$ 和 $\overline{r}\to\overline{w}_{joe}$

如果定义命题u_Mary 表示玛丽带着她的伞，并定义w_Mary 表示玛丽被淋湿，那么就有了一组类似的前提：

r →u_Mary， $u_{Mary}\to\overline{w}_{Mary}$ 和 $\overline{r}\to\overline{w}_{Mary}$

我们可以继续像这样，引入命题谈论所知道的所有个体X，并用新命题u_X 和w_X 陈述与命题r 相关的前提，即

r →u_X， $u_X\to\overline{w}_X$ 和 $\overline{r}\to\overline{w}_X$

现在就要讲到谓词的概念了。与无限的命题集合u_X 和w_X 不同的是，可以将符号u 定义为接受参数X 的谓词。表达式u(X )可以解释为在说“X 带着他（她）的伞”。可能对某些X 的值而言，u(X )为真，而对其他X 的值来说，u(X )为假。同样，w 可以是谓词，粗略地讲，w(X )就表示“X 被淋湿”。

命题变量r 也可以被当作具有0个参数的谓词。也就是说，下不下雨并不像u 和w 那样取决于个体X 。

现在可以把前提用谓词表示成如下形式。

1. r →u(X )。（对任何个体X，如果天在下雨，那么X 带着他或她的伞。）

2. u(X )→NOT w (X )。（不管你是谁，如果你带着伞，就不会被淋湿。）

3. NOT r →NOT w (X )。（如果不下雨，那么没人会被淋湿。）

14.2.1　原子公式

原子公式（atomic formula）是具有0个或更多参数的谓词。例如，u(X )是具有谓词u 和一个参数（这里的参数是变量X）的原子公式。一般而言，参数要么是变量，要么是常量。1尽管原则上讲常量的值可以是任何类型的，但我们通常会假设这些值是整数、实数或字符串。

1谓词逻辑还允许参数是单个变量或常量之外的更复杂的表达式。这对我们在本书中没有讨论到的某些用途来说是很重要的。因此，本章中我们将只会看到变量和常量作为谓词的参数。

变量是那些可以接受任何常量作为其值的符号。我们不应该把“变量”与第12章“命题变量”中的“变量”弄混。事实上，命题变量等价于没有参数的谓词，而且我们会把表示原子公式的p 写成具有谓词名p 和0个参数的形式。

所有参数都是常量的原子公式就叫作基本原子公式（ground atomic formula）。非基本原子公式（nonground atomic formula）可以用常量或变量作为参数，但至少有一个参数一定是变量。请注意，作为没有参数的原子公式，任何命题的“所有参数都是常量”，因此是基本原子公式。

14.2.2　常量和变量的区分

我们要使用以下约定来区分常量和变量。变量名总是以大写字母开头，常量是用以下几种方式表示的：

1. 以小写字母开头的字符串；

2. 12或14.3这样的数字；

3. 带引号的字符串。

因此，如果要把课程CS101表示为常量，就可以将其写为“CS101”。2

2常量在逻辑中通常称为“原子”。不巧的是，“原子公式”也时常被称为“原子”，因此一般会避免使用术语“原子”。

像常量这样的谓词将会用以小写字母开头的字符串表示。我们不可能把谓词与常量弄混，因为常量只可能出现在原子公式的参数中，而谓词是不可能出现在那里的。

示例 14.1

我们可以用谓词名csg 表示8.2节讨论过的“课程-学号-成绩”关系中所含的信息。原子公式csg(C,S,G )可以被视作在说：对变量C、S 和G，学号为S 的学生选修了课程C，并得到了成绩G。换句话说，当我们用常量c 代替C，用s 代替S，并用g 代替G 时，当且仅当学号为s 的学生选修了课程c 并取得成绩g，csg (c,s,h)的值为TRUE。

还可以通过用常量作为参数，把关系中的特定事实（即元组）表示为基本原子公式。例如，图8-1中第一个元组可以表示为csg ("CS101",12345,"A")，断言学号为12345的学生CS101课程的成绩是A。最后，可以在参数中混用常量与变量，因此就可能看到csg ("CS101",S,G )这样的原子公式。如果变量S 和G 的取值(s,g )满足学号为s 的学生选修了课程CS101并取得成绩g，则该原子公式为真，否则就为假。

14.2.3　习题

利用本节中的约定，确定以下内容是常量、变量、基本原子公式还是非基本原子公式。

(a) CS205

(b) cs205

(d) “cs205”

(e) p(X,x )

(f) p(3,4,5)

(g) “p(3,4,5)”

14.3　逻辑表达式

第12章中为命题逻辑使用过的概念（文字、逻辑表达式、子句等）沿用到了谓词逻辑中。在下一节中我们还会引入两种额外的运算符来构成逻辑表达式。不过，逻辑表达式构造背后的基本思路在命题逻辑和谓词逻辑中基本是相同的。

14.3.1　文字

文字要么是原子公式，要么是原子公式的否定。如果在原子公式的参数中没有变量，那么相应的文字就是基本文字（ground literal）。

示例 14.2

p(X,a)是原子公式并且是文字。它不是基本的，因为根据我们的决定，它的参数X 是变量。NOT p(X,a)是文字，但它不是原子公式，也不是基本文字。表达式p(a,b)和NOT p(a,b)都是基本文字，但只有前者是（基本）原子公式。

就像命题逻辑那样，可以用上横线代替NOT运算符。不过，当横线用在很长的表达式上时，就会容易混淆，因此与第12章相比，在本章中会更常见到NOT。

14.3.2　逻辑表达式

我们可以像12.3节中用命题变量构建表达式那样，用原子公式构建表达式。这里将继续使用第12章中讨论过的AND、OR、NOT、→和≡运算符，以及其他的逻辑连接符。而在下一节中，我们会介绍“量词”，也就是可以在谓词逻辑中用来构建表达式，但在命题逻辑中没有类比物的运算符。

就像横线是NOT的简化符号那样，可以继续用并置（没有运算符）来表示AND并用+表示OR。不过，我们并不经常使用这些简化符号，因为它们可能让谓词逻辑中较长的表达式变得难以理解。

下面的例子应该能让大家对逻辑表达式的含义有所领悟。不过，要注意到这里的讨论对其进行了非常大的简化，而我们要到14.5节才会讨论“解释”，以及它们为谓词逻辑中的逻辑表达式赋予的含义。

示例 14.3

假设有谓词csg 和snap，它们分别可以解释为第8章中介绍过的“课程-学号-成绩”与“学号-姓名-地址-电话”这两个关系。并假设我们想要找到名为“C.Brown”的学生CS101课程的成绩。就可以断言以下逻辑表达式

(csg (“CS101”,S,G )AND snap (S,“C.Brown”,A,P ))→answer (G )　　　　　　(14.1)

这里的answer 是另一个谓词，如果G 是某个名为“C.Brown”的学生CS101课程的成绩，它就适用于成绩G 。

在我们“断言”某个表达式时，就说明了不管用什么值替换其变量，该表达式的值都为TRUE。粗略地讲，(14.1)这样的表达式可以按照以下方式解释。如果用常量代替各变量，则各原子公式就成了基本原子公式。通过参考“现实世界”，或是在列出某给定谓词为真的基本原子公式的关系中进行查找，可以确定一个基本原子公式是真还是假。在用0或1代替各个基本原子公式时，可以为表达式本身求值，就像第12章中为命题逻辑表达式求值那样。

在表达式(14.1)的情况中，可以取图8-1和图8-2a中的元组为真。特别要说的是，

csg("CS101",12345,"A")

和

snap(12345,“C.Brown”,“12 Apple St.”,“555-1234”)

为真。然后可以设

S=12345
G=“A”
A=“12 Apple St.”
P=“555-1234”

这让(14.1)的左边成了1 AND 1，它的值当然是1。原则上讲，我们对谓词answer 没有任何了解。不过，我们断言了(14.1)，这意味着不管用什么值替代其中的变量，它的值都是TRUE。因为它的左边根据上述替换得到了TRUE，所以右边不可能为FALSE。因此我们推导出了answer("A")为真。

14.3.3　其他术语

我们还会使用其他与命题逻辑相关联的术语。一般来说，当本章中讲到命题变量时，说的就是所有原子公式，其中包括不含参数的谓词（即命题变量）作为特例。例如，子句是一组由OR运算符连接的文字。同样，如果表达式是子句的AND，那么就说它是合取范式。如果表达式是多个项的OR，而这些项各自是文字的AND，那么这样的表达式就是析取范式。

14.3.4　习题

1. 为问题“L. Van Pelt的PH100课程取得了什么成绩？”写出类似(14.1)的表达式。假设事实如图8-1和图8-2所示，其参数有什么值时能让answer 显然为真？为展现该答案的真实性，对变量进行了怎样的替换？

2. 设cdh 是代表图8-2c中“课程-日子-时刻”关系的谓词，而cr 则是对应图8-2d中“课程-教室”关系的谓词。为问题“C.Brown星期一上午9点在哪里？”（更精确地讲，是“C.Brown选修的星期一上午9点上课的课程在哪个教室上课？”）写出类似(14.1)的表达式。假设事实如图8-1和图8-2所示，其参数有什么值时能让answer 显然为真？为展现该答案的真实性，对变量进行了怎样的替换？

3. ** 8.7节中讨论过的各种关系代数运算可以用类似(14.1)的表达式在谓词逻辑中表示出来。例如，(14.1)本身就等价于关系代数表达式

π_成绩(δ_{课程="CS101"}AND _{姓名="C.Brown"}(CSG⋈SNAP))

说明选择、投影、联接、并、交、差这些运算用谓词逻辑中“表达式蕴含答案”的形式表示出来是什么样子，然后将8.7节的示例中给出的各关系代数表达式转化成逻辑表达式。

14.4　量词

我们回到涉及无参数谓词r（“天在下雨”），以及单参数谓词u (X )（“X 带着伞”）和w (X )（“X 被淋湿”）的例子。你可能希望断言“如果下雨，那么某人会淋湿”。也许会尝试

r →w (“乔伊”)OR w (“莎莉”)OR w (“苏”) OR w (“山姆”)OR…

但这一尝试会以失败告终，原因如下。

1. 可以把表达式写成有限个表达式的OR，但不能把它写成无限个表达式的OR；

2. 不知道所谈论个体的完全集。

要表示一批通过为某个变量替换所有可能的值形成的表达式的OR，就需要一种额外的方式来创建谓词逻辑表达式。这一运算符是∃，读作“存在”。我们将其用在(∃X )w(X )这样的表达式中，或者粗略地将其表述为“存在某一个体X，满足X 被淋湿”。一般而言，如果E 是任何逻辑表达式，那么(∃X )(E )也是逻辑表达式。3其大概的含义为，至少存在一个X 的值使得E 为真。更精确地讲，对E 中其他变量的各种取值来说，可以找出某个X 的值（在所有情况中并不一定是同样的值）使得E 为真。

3表达式E 两边的括号有时是必要的，有时是不必要的，这取决于该表达式的具体内容。当我们在本节稍后的内容中讨论优先级和结合性时，情况就会变得更清楚了。∃X 周围的括号是该符号的一部分，因此总是必需的。

同样，我们不能写出下面这样的无限个表达式的AND。

u (“乔伊”)AND u (“莎莉”) AND u (“苏”) AND u (“山姆”)…

要构造一系列通过为某给定变量替换所有可能的值形成的表达式的AND，需要符号∀（称为“对所有的”）。例如，(∀X )u(X )就表示“对所有的X，X 都带着伞”。一般而言，对任何逻辑表达式E，(∀X )(E )意味着，对E 中其他变量所有可能的取值来说，用来替换X 的每个常量都能使E 为真。

符号∀和∃就叫作量词。有时候也会把∀叫作全称量词（universal quantifier），把∃叫作存在量词（existential quantifier）。

示例 14.4

表达式r →(∀X )(u(X )ORw(X ))意味着“如果下雨，那么对所有的个体X，要么X 带着伞，要么X 被淋湿”。请注意，量词可以应用于任意表达式，而不只是前面所述例子中的原子公式。

再举个例子，可以把表达式

(∀C )(((∃S )csg (C,X,"A"))→((∃T )csg (C,T,"B")))　　　　　　(14.2)

解释为，“对所有的课程C，如果存在学号为S 的学生该课程的成绩为A，那么一定存在学号为T 的学生该课程的成绩为B”。不那么严谨地讲就是“如果给了A，那么也必须给B”。

第三个示例表达式是

((∀X)NOT w(X))OR((∃Y)w(Y))　　　　　　(14.3)

粗略地讲就是，“要么所有个体X 都不被淋湿，要么至少有一个个体Y 被淋湿”。表达式(14.3)与本示例中的其他两个表达式是不同的，因为这个表达式是重言式——也就是说，不管谓词w 的含义是什么，该表达式都为真。(14.3)的真实性与“雨天”的属性没有任何关系。不管使谓词w 为真的值构成的集合S 是什么，要么S 为空（即对所有X，w(X )都为假），要么S 不为空（也就是，存在某个Y 使得w(Y )为真）。

14.4.1　逻辑表达式的递归定义

作为回顾，我们要给出谓词逻辑中这类逻辑表达式的递归定义。

依据。每个原子公式都是表达式。

归纳。如果E 和F 是逻辑表达式，那么以下表达式也是逻辑表达式。

1. NOT E、E AND F、E OR F、E →F 和 E≡F。粗略地讲，我们也允许使用NAND这样的其他命题逻辑运算符。

2. 对任何变量X，(∃X )E 和 (∀X )E。原则上讲，X 甚至不需要在E 中出现，虽然实践中这样的表达式很难“说得通”。

14.4.2　运算符的优先级

一般而言，需要在所有用到表达式E 和F 的地方为其加上括号。不过，就像我们已经看到的其他代数那样，通常可以出于运算符优先级的原因删掉一些括号。这里要继续使用12.4节定义的运算符优先级，NOT（最高）、AND、OR、→和≡（最低）。不过，量词在所有运算符中有着最高的优先级。

示例 14.5

(∃X )p(X )OR q(X )会被分组为

((∃X )p(X ))OR q(X )

同样，表达式(14.3)中外层那两对括号是多余的，所以可以将其写为

(∀X )NOT w(X )OR(∃X )w(Y )

还可以消除(14.2)中的两对括号，并将其写为

(∀C )((∃S)csg(C,S,"A")→(∃T )csg(C,T,"B"))

(∀C )后整个表达式两侧的括号是必要的，这样才能把“对所有的C ”应用到整个表达式上。

量词的次序
混淆量词的次序是个常见的逻辑错误，例如，有人可能误认为(∀X )(∃Y )与(∃X )(∀Y )含义相同，但它们是不同的。例如，如果粗略地把loves(X,Y )解释为“X 爱Y”，那么(∀X)(∃Y)loves(X,Y)就表示“每个人都爱某个人”，也就是说，对每个个体X，至少存在一个个体Y 是X 所爱的。另一方面(∃Y )(∀X )loves(X,Y )则表示，存在某个被每个人所爱的个体Y ——这是个非常幸运的Y，如果存在这样的人的话。

请注意，量词(∀X )和(∃X )所带的括号并不是用于分组的，它们应该被看作表示量词的符号的一部分。还有，请记住量词和NOT都是一元的前缀运算符，而且唯一明智的分组方式就是从右边起为它们分组。

示例 14.6

因此表达式(∀X )NOT(∃Y)p(X,Y )被分组为

(∀X )(NOT((∃Y )p(X,Y )))

并表示“对所有的X，都不存在Y 使得p(X,Y )为真”。换句话说就是，不存在使得p(X,Y )为真的X 和Y 的取值对。

14.4.3　约束变量和自由变量

量词与表达式中的变量相互作用的方式是很微妙的。要解决这一问题，首先要想到C语言中局部变量和全局变量的概念。假设如图14-1所示，X 被定义为C语言程序中的外部变量。假设X 不是在main函数中声明的，那么main函数中对X 的引用就是对外部变量的引用。另一方面，函数f中也声明了局部（自动控制）变量X，而函数f中对X 的所有引用都是对该局部变量的引用。

C语言程序中对X 的声明与量词(∀X )或(∃X )存在着很近的相似性。如果有表达式(∀X )E 或(∃X)E，那么该量词就相当于为表达式E 声明了局部的X，就像E 是函数，而X 被声明为该函数的局部变量那样。

在接下来的内容中，有必要用符号Q 来表示任一量词。具体来说就是，用(QX )代表“应用于X 的某个量词”，也就是(∀X )或(∃X )。

int X;
    …
main()
{
    …
    ++X;
    …
}

void f()
{
    int X;
    …
}

图 14-1　局部变量和全局变量

如果E 具有某个形如(QX )F 的子表达式，那么该子表达式就像是E 中声明的程序块，而E 在自身对X 进行了声明。在F 中对X 的引用就引用了由这一(QX )“声明的”X，而E 中F 之外的部分所使用的X 则引用了X 的其他声明——要么是与E 相关联的量词，要么是与包含在E 中但限制了所考虑的X 的某个表达式相关联的量词。

图 14-2　对应(∀X )u(X )OR(∀X )w(X )表达式树

示例 14.7

考虑表达式

(∀X )u(X )OR(∀X )w(X )　　　　　　(14.4)

粗略地讲，该表达式的含义是“要么每个人都带着伞，要么每个人都被淋湿”。我们可能不相信这一命题的真实性，但这里要拿它来当例子考虑。表达式(14.4)的表达式树如图14-2所示。请注意，第一个量词(∀X )只在它的子孙u 中使用X，而第二个量词(∀X )只在它的子孙w 中使用X。要区分所使用的X 是在哪个量词中“声明”的，就只能从该X 向上追溯，直到遇到量词(QX )为止。因此这里所使用的两个X 引用了不同的“声明”，而且它们之间没有任何关系。

要注意可以为(14.4)中X 的两个“声明”使用不同变量，将其写作(∀X )u(X )OR(∀Y )w(Y )。一般来说，总是可以为谓词逻辑表达式的变量重命名，从而使同一变量不会出现在两个量词中。这种情况与C语言这样的编程语言是类似的，我们在编程语言中会为程序中的变量重命名，这样相同的变量名就不会使用在两个声明中。例如，在图14-1中，可以把函数f中变量名X的所有实例都变为任何新变量名Y。

示例 14.8

再举个例子，考虑表达式

(∀X )(u(X )OR(∃X )w(X ))

粗略地讲，其含义是“对各个体，要么该个体带着伞，要么存在某一（可能是另一）个体被淋湿”。该表达式的表达式树如图14-3所示。请注意，w 中使用的X 指的是X 限定了私密性的“声明”，也就是存在量词。换句话说，如果从w(X )沿着树向上行进，那么在遇到全称量词之前会遇到存在量词。不过，u 中所使用的X 就不在该存在量词的“范围”内。如果从w(X )上行，首先会遇到全称量词。可以把该表达式写为

(∀X )(u(X )OR(∃Y )w(Y ))

这样就没有哪个变量会出现在两个量词中了。

图 14-3　对应(∀X )(u(X )OR(∃X )w(X ))的表达式树

如果在逻辑表达式E 的表达式树中，涉及某个变量X 的量词是该X 的最低祖先，就可以说该变量X 是受量词Q(X)约束的。如果某个X 不受任何量词约束，那么该X 就是自由变量。因此量词就像是以该量词为根节点的子树T 局部的“声明”。这些量词会应用到T 中除了以具有同样变量的另一个量词为根节点的子树之外的各个节点。而自由变量就像是全局变量之于某一函数那样，它们的“声明”是在所考虑的表达式之外进行的。

示例 14.9

考虑表达式

u(X )OR(∃X )w(X )

也就是说，“要么X 带着伞，要么有某个人会被淋湿”。相应的表达式树如图14-4所示。正如之前的例子中那样，这里出现的两个X 指的是不同个体。w 中出现的X 是受到存在量词约束的。不过，在u 中出现的X 之上没有对应X 的量词，因此这次出现的X 在给定的表达式中是自由变量。这个例子说明，在某表达式中同一变量可能同时作为自由变量和作为约束变量出现，所以在某些情况下，我们会说“作为约束变量出现”而不是直接说“约束变量”。示例14.7和14.8中的表达式表明，出现在不同位置的相同变量，也可能分别受到出现在不同位置的相同量词的约束。

图 14-4　对应u(X )OR(∃X )w(X )的表达式树

14.4.4　习题

1. 从以下表达式中删除多余的括号。

(a) (∀X )((∃Y )(NOT(p(X )OR(p(Y )AND q(X )))))

(b) (∃X )((NOT p(X ))AND((∃Y )(p(Y ))OR(∃X )(q(X,Z ))))

2. 为习题1中的表达式画出表达式树。如果出现的变量是受量词约束的，则指出它是受哪个量词约束的。

3. 重写习题1中的表达式(b)，使得其中的量词不含相同的变量。

4. * 在前文附注栏“量词的次序”中，我们谈论了量词loves(X,Y )，并为其给出了预料之中的粗略解释。不过，正如我们将在14.5节中看到的，谓词没有具体的解释，而且也可以拿loves来谈论整数而非个人，并为loves(X,Y )给出Y=X+1这样的粗略解释。在这种解释下，比较(∀X )(∃Y )loves(X,Y )和(∃Y )(∀X )loves(X,Y )的含义。它们的粗略解释各是什么？如果可能的话，大家会相信哪个？

5. * 利用之前例子中的谓词csg，写出断言以下内容的表达式。

(a) C.Brown是个A等生（即他所有课程的成绩都是A）。

(b) C.Brown不是A等生。

6. * 设计文法，描述合法的谓词逻辑表达式。大家可以使用常量和变量这样具有象征性的终结符，而且不需要考虑重复括号的问题。

14.5　解释

直到现在，我们对谓词逻辑表达式有何“含义”，或者说是对如何为表达式赋予含义的了解还是相当模糊。这里要通过先回顾命题逻辑表达式E 的“含义”来阐释这一主题。命题逻辑表达式的含义是接受“真值赋值”（为E 中的命题变量指定真值0和1的情况）作为参数，并产生0或1作为结果的函数。根据给定的真值赋值，用0或1替代表达式E 中的各原子操作数，并求出E 的值，从而确定结果。换句话说，逻辑表达式E 的含义就是为各组真值赋值给出相应E 值（0或1）的真值表。

而真值赋值是接受命题变量作为参数，并为各参数返回0或1的函数。换句话说，可以把真值赋值视为给各命题变量给定某一真值（0或1）的表格。图14-5展示了这两种函数的角色。

图 14-5　命题逻辑中表达式的含义

在谓词逻辑中，为谓词指定常数0或1（TRUE或FALSE）是不够的，除非谓词不含参数，而这种情况下它们从本质上讲就是命题变量。不过，为谓词赋的值本身是歌函数，它接受谓词参数的值作为输入，并产生0或1作为输出。

更加精确地讲，首先必须从变量可能的取值中选取一些值构成非空的定义域D。这一定义域可以是任何内容：整数、实数，或由没有特殊名称或意义的值构成的某个集合。不过，假设定义域含有出现在表达式本身中的所有常量。

现在，设p是具有k个参数的谓词。那么谓词p的解释就是接受定义域元素到p 中k 个参数的赋值作为输入，并返回0或1（TRUE或FALSE）的函数。或者说，可以把p的解释看作具有k 列的关系。对让p 在该解释中为真的各参数赋值来说，在该关系中都存在相应的元组。4

4与第8章中谈论的关系不同，作为谓词解释的关系可能具有无限多的元组。

现在可以把表达式E 的解释定义为：

1. 非空的定义域D，含有E 中出现的任何常量，

2. 对E 中出现的各谓词p 的解释，以及

3. D 中对应表达式E 各自由变量的值（如果存在自由变量的话）。

解释与“对谓词的解释”分别如图14-6a和图14-6b所示。请注意，解释在谓词逻辑中的角色就相当于真值赋值在命题逻辑中的作用。

图 14-6　谓词逻辑中表达式的含义

示例 14.10

考虑以下谓词逻辑表达式：

p(X,Y )→(∃Z )(p(X,Z )AND p(Z,Y ))　　　　　　(14.5)

谓词p 一种可能的解释（我们将称其为解释I₁）如下所述。

1. 定义域D 是实数集。

2. 只要U< V，p(U,V )就为真。也就是说，p 的解释是有序对(U,V )的无限集构成的关系，其中满足U 和V 都是实数而且U 小于V。

那么(14.5)就表示，对任何实数X 和Y，如果X< Y，则存在某个Z 严格位于X 和Y 之间，也就是说，有X< Z< Y。对解释I₁而言，(14.5)总是为真。如果X< Y，就可以选择Z=(X+Y)/2，也就是X 和Y 的平均数，然后就能确定X< Z 且Z< Y。如果X≥Y，那么该蕴涵式的左边为假，则(14.5)显然为真。

我们可以根据谓词p 的解释I₁，通过选择任何实数作为自由变量X 和Y，为(14.5)构建无数的解释。根据我们刚才所说的，这些对应(14.5)的解释都能使(14.5)为真。

谓词p 第二种可能的解释I₂如下：

1. D 是整数集；

2. 当且仅当U< V 时，p(U,V )为真。

现在，我们可以声明(14.5)为真，除非Y=X+1。因为如果Y 比X 大2或者更多，那么Z 就可以被选为X+1。这样就是满足X< Z< Y 的情况。如果X≤Y，那么p(X,Y )为假，则(14.5)还是为真。不过，如果Y=X+1，那么p(X,Y )为真，但不存在严格处于X 和Y 之间的整数Z。因此这种情况下对每个整数Z 而言，p(X,Z )和p(Z,Y )都为假，则蕴涵式的右边，即(∃Z )(p(X,Z )AND p(Z,Y ))不为真。

通过为自由变量X 和Y 赋整数值，可以将I₂扩展为表达式(14.5)的解释。以上分析说明了，除了Y=X+1情况下外，(14.5)对任何这样的解释都为真。

对p 的第三种解释I₃是抽象的，不像之前的解释I₁和I₂那样具有常见的数学含义。

1. D 是三个符号a、b、c 的集合。

2. 如果UV 是aa、ab、ba、bc、cb、cc 其中之一，则p(U,V )为真，若UV为ac、bb 和ca，则p(U,V )为假。那么刚好有(14.5)对9对XY 都为真。在每种情况下，要么p(X,Y )为假，要么存在Z 使得(14.5)的右边为真。图14-7列举了这9种情况。通过为自由变量X 和Y 指定由a、b、c 构成的任意赋值组合，我们有9种方式可以把I₃扩展为(14.5)的解释。

X	Y	为何为真
a	a	Z=a 或b
a	b	Z=a
a	c	p(a,c)为假
b	a	Z=a
b	b	p(c,a)为假
b	c	Z=c
c	a	p(b,b)为假
c	b	Z=c
c	c	Z=b 或c

图 14-7　使用解释I₃的情况下(14.5)的值

14.5.1　表达式的含义

回想一下，命题逻辑中表达式的含义就是从真值赋值到真值0和1的函数，如图14-5b所示。也就是说，真值赋值陈述了与表达式原子操作数的值有关的所有信息，然后为该表达式求值得到0或1。同样，在谓词逻辑中，表达式的含义是接受解释（我们需要利用该解释为原子操作数求值），并返回0或1的函数。表达式含义的这一概念如图14.6c所示。

示例 14.11

考虑示例14.10中的表达式(14.5)。(14.5)中的自由变量是X 和Y。如果给定的是示例14.10中对p 的解释I₁（p 是针对实数的<），而且给定了值X＝3.14和Y＝3.5，那么(14.5)的值就是1。其实，正如我们在示例14.10中讨论过的，有着对p 的解释I₁，任何X 和Y 的值都使该表达式的值是1。同样的结论也适用于对p 的解释I₃，从定义域{a，b，c }中选取的任何X 和Y 的值都会让(14.5)的值为1。

另一方面，如果给定了解释I₂（p 是针对整数的<），以及值X=3和Y=4，那么就像我们在示例14.10中讨论过的，(14.5)的值是0。如果有解释I₂，而且自由变量的值分别是X=3和Y=5，那么(14.5)的值是1。

要完成对表达式“含义”的定义，必须正式地定义如何把原子操作数的指针转化成整个表达式的真值。之前我们已经利用直觉，根据的是对命题逻辑的逻辑连接符作用方式的理解，以及考虑量词的直觉。给定某解释I 以及定义域D，表达式的值的正式定义就是对给定的表达式E 的表达式树进行的结构归纳。

依据。如果表达式树是单个叶子节点，那么E 是原子公式p(X₁,…,X_k) 。这些X_i全都要么是常量、要么是表达式E 的自由变量。解释I 为各变量给定了值，这样一来就拥有了p 所有参数的值。同样，I 表明了在以这些值作为参数的情况下p 是真还是假。而该真值就是表达式E的值。

归纳。现在，必须假设给定的表达式E 对应的表达式树根节点位置是运算符。这存在若干种情况，具体取决于E 的根节点位置是什么运算符。

首先，考虑一下E 形如E₁ AND E₂的情况，也就是说，根节点处的运算符是AND。归纳假设可以应用于子表达式E₁和E₂。因此可以在解释I 之下为E₁求值。5同样，可以在解释I 之下为E₂求值。如果求出的值都是1，那么E 的值就是1，否则E 的值是0。

5严格地讲，要从I 中除去那些只出现在E 中但没有出现在E₁中的对应谓词p 的解释。还有，必须放弃那些出现在E中但没有出现在E₁中的自由变量的值。不过，如果解释中包含进没有用到的额外信息，是不存在任何概念困难的。

像OR或NOT这样的其他逻辑运算符的归纳也是如法炮制。对OR而言，我们会为两个子表达式求值，并且只要有任何一个子表达式得出值1，就为表达式得出值1。而对NOT来说，我们会为那一个子表达式求值，并得出该表达式的值的否定，而对其他命题逻辑运算符来讲，处理方法也都是一样的。

现在假设E 形如(∃X )E₁。根节点运算符就是该存在量词，而且我们可以将归纳假设应用于子表达式E₁。E₁中的谓词都出现在E 中，而E₁中的自由变量都是E 的自由变量，可能还要加上X。6因此，我们可以为定义域D 中的各个值v 构建对应E₁的解释I，以及我们称之为解释J_v 的对变量X 的赋值v。对各个值v，我们会问，在解释J_v 之下E₁是否为真。如果至少存在一个这样的值v，那么我们说E=(∃X )E₁为真，否则就说E 为假。

6技术上讲，即使对E₁应用了涉及X 的量词，E₁还是可能不含任何作为自由变量的X。在这种情况下，量词可能也不存在，但我们没有阻止它出现。

最后，假设E 形如(∀X )E₁。归纳假设还是适用于E₁。现在要问，对定义域D 中的每个值v，在解释J_v 之下E₁是否为真。如果是，就说E 的值是1，如果不是，E 的值就是0。

示例 14.12

这里在给定对p 的解释I₂，以及对应自由变量X 和Y 的值分别是3和7的情况下，要为表达式(14.5)求值。对应(14.5)的表达式树如图14-8所示。我们看到，根节点处的运算符是→。之前并未明确介绍过这种情况，不过原则应该是很清楚的。整个表达式可以写成E₁→E₂，其中E₁是p(X,Y )，而E₂是(∃Z )(p(X,Z )AND p(Z,Y ))。因为→的含义，所以除了E₁为真而且E₂为假的情况，整个表达式(14.5)都为真。

图 14-8　对应(14.5)的表达式树

E₁，也就是p(X,Y )，是很容易求值的。因为X=3，Y=7，而且当且仅当X< Y 时p(X,Y )为真，所以可以得出E₁为真。为E₂求值则更为困难。我们必须为Z 考虑所有可能的值v，以了解是否至少存在一个值使p(X,Z ) AND p(Z,Y )为真。例如，如果尝试Z=0，那么p(Z,Y )为真，但p(X,Z )为假，因为X=3是不小于Z 的。

能否计算表达式的值？
大家可能会怀疑在E 是(∃X )E₁或(∀X )E₁的情况下，我们对表达式E 值为1的定义。如果定义域D 是无限的，那么我们已经提出的在各解释J_v 之下为E₁求值的测试就不需要对应其执行的算法。从本质上讲，要求我们为存在量词执行以下函数
for (each v in D)
    if (E₁ is true under interpretation J_v)
        return TRUE;
return FALSE;
并为全称量词执行如下函数
for (each v in D)
    if (E₁ is false under interpretation J_v)
        return FALSE;
return TRUE;
尽管这些程序的目的很明确，但它们都不是算法，因为若定义域D 是无限的，则要进行无数次循环。不过，虽然可能没法分辨E 是真还是假，但我们还是给出了E 何时为真的正确定义，也就是说，我们为量词∀和∃赋予了预期的含义。在很多实际且实用的情形中，我们将能够分清E 是真还是假。在另一些情况中，我们会看到E 是真还是假都是没关系的，例如涉及将表达式变形为等价形式的情况。可以在不知道是否存在令E₁这样的子表达式为真的值v 的情况下，根据两个表达式的值的定义来推理它们是等价的。

如果考虑这种情况，就会看到，要使p(X,Z )AND p(Z,Y )为真，就需要v 的值满足3< v（从而让p(X,Z )为真），并满足v< 7（从而使p(Z,Y )为真）。例如，v=4就能使p(X,Z )AND p(Z,Y )为真，并因此证明了E₂，或者说证明了(∃Z )(p(X,Z )AND p(Z,Y ))对给定的解释而言为真。

现在可知E₁和E₂都为真。因为当E₁和E₂都为真时E₁→E₂为真，所以可以得出结论，在谓词p 具有解释I₂，而且X=3，Y=3的情况下，表达式(14.5)的值是1。

14.5.2　习题

1. 分别为以下各表达式给出一种使其为真的解释以及一种使其为假的解释。

(a) (∀X )(∃Y )(loves(X,Y ))

(b) p(X )→ NOT p(X )

(d) (p(X,Y )AND p(Y,Z ))→p(X,Z )

2. 解释一下，为什么每种解释都能使表达式p(X )→p(X )为真。

14.6　重言式

回想一下，在命题逻辑中，如果对每种真值赋值而言，表达式的值都是1，就说该表达式是重言式。同样的概念在谓词逻辑中也是成立的。如果对E 的每种解释，E 的值都是1，则说表达式E 是重言式。

示例 14.13

就像在命题逻辑中那样，“随机的”谓词逻辑表达式很少是重言式。例如，我们在示例14.10中研究过的表达式(14.5)，或者说

p(X,Y )→(∃Z )(p(X,Z )AND p(Z,Y ))`

在某些针对谓词p 的解释之下总为真，但是存在像示例14.10中的I₂这样的解释：p 是针对整数的<，让该表达式不总是为真，比如，对X=1和Y=2，该表达式为假。因此，该表达式不是重言式。

表达式

q(X ) OR NOT q(X )

就是个重言式。这里，不管为谓词q 使用什么解释，或者为自由变量X 赋什么值，都是没关系的。如果所选择的解释使得q(X )为真，那么该表达式为真。

14.6.1　替换原则

命题逻辑重言式是谓词逻辑重言式的丰富来源。我们在12.7节中介绍过的替换原则表明，可以取任意命题逻辑重言式，对其中的命题变量进行任何替换，得到的结果仍然是重言式。如果允许用谓词逻辑表达式替换命题变量，那么该原则仍然成立。例如，示例14.13中提到过的重言式q(X )OR NOT q(X )，就是用表达式q(X )替换了重言式p OR NOT p 中的命题变量p。

用谓词逻辑表达式替换命题变量时替换原则成立的原因，与用命题表达式替换命题变量时该原则成立的原因基本相同。在用q(X )这样的表达式替代表达式中出现的某一命题变量p 时，我们知道，对任何解释来说，所替换的表达式不管出现在何处都有着相同的值。因为原有的（我们要对其进行替换的）命题逻辑表达式是重言式，所以在将其中某个命题变量全部替换为0，或者全部替换为1时，该表达式总是为真。

例如，在表达式q(X ) OR NOT q(X )中，不管q 的解释是什么或X 的值是什么，q(X )要么为真，要么为假。因此，这个表达式要么变成1 OR NOT 1，要么变成0 OR NOT 0，而这两个式子的值都是1。

14.6.2　表达式的等价

和命题逻辑中一样，如果两个谓词逻辑表达式E 和F 满足E ≡F 是重言式，就可以定义它们是等价的。在讲到谓词逻辑表达式等价时，12.7节中介绍过的“以相等换相等原则”继续成立。也就是说，如果E₁等价于E₂，那么可以用E₂代替任一表达式F₁中的E₁，得到的表达式F₂将是等价的，也就是说F₁≡F₂。

示例 14.14

AND运算的交换律是(p AND q )≡(q AND p )。现在，如果有(p(X )AND q(Y,Z ))OR q(X,Y )这样的表达式，那么可以用q(Y,Z ) AND p(X )替换p(X ) AND q(Y,Z )，产生另一个表达式

(q(Y,Z ) AND p(X ))OR q(Y,Z )

并知道

((p(X )AND q(Y,Z ))OR q(X,Y )≡((q(Y,Z )AND p(X ))OR q(X,Y ))

还有一些更微妙的等价谓词逻辑表达式。通常，我们会认为等价表达式有着相同的自由变量和谓词，不过有些情况下自由变量和（或）谓词可以是不同的。例如，表达式

(p(X )OR NOT p(X ))≡(q(Y )OR NOT q(Y ))

就是重言式，因为≡两边的表达式如我们在示例14.13中论证过的都是重言式。因此，在表达式p(X )OR NOT p(X )OR q(X )中可以用q(Y )OR NOT q(Y )替换p(X )OR NOT p(X )，从而得到

(p(X )OR NOT p(X )OR q(X ))≡(q(Y)OR NOT q(Y )OR q(X ))

因为≡的左边是重言式，所以还可以得出

q(Y )OR NOT q(Y )OR q(X )

是重言式的结论。

14.6.3　习题

解释以下各表达式为何是重言式。也就是说，我们为命题逻辑重言式替换了什么样的谓词逻辑表达式？

(a) (p(X )OR q(Y ))≡(q(Y )OR p(X ))

(b) (p(X,Y )AND p(X,Y ))≡p(X,Y )

14.7　涉及量词的重言式

涉及量词的谓词逻辑重言式在命题逻辑中没有直接的参照物。本节要探究这些重言式，并展示如何利用它们处理表达式。而主要成果就是可以将任何表达式转换成量词全在开头位置的等价表达式。

14.7.1　变量的重命名

在C语言中，可以改变局部变量的名称，只要对所有用到该局部变量的地方进行统一修改即可。类似地，也可以改变量词中用到的变量，只要对所有出现受到该量词约束的这一变量的地方进行修改。还有，就像在C语言中那样，一定要谨慎选择新的变量名，因为如果选择的名称已经在所考虑函数之外定义，那么就可能改变程序的含义，就会造成严重的错误。

记住这种重命名，我们可以考虑以下类型的等价，以及在何条件下它是重言式。

(QX )E≡(QY )E'　　　　　　(14.6)

其中E' 是把E 中所有受到这里明确给出的量词(QX )约束的X 替换为Y 后得到的。我们说(14.6)是重言式，只要E 中没有出现自由变量Y。要知道原因，可以考虑任一对应(QX )E 的解释I。或者等价地，对应(QY)E'，因为两个量词化表达式的自由变量和谓词是相同的。如果通过为X 给定值v 扩展过的I 使得E 为真，那么I 和对应Y 的值v 也能让E' 为真。相反，如果通过为X 给定值v 扩展的I 使E 为假，那么扩展的 I 和对应Y 的v 也使E' 为假。

如果量词Q 是∃，那么假设存在对应X 的值v 使得E 为真，就存在某个对应Y 的值v，使得E' 为真，相反，假设存在X 的值v 使得E 为假，就存在对应Y 的值v 使得E' 为假。如果Q 是∀，那么当且仅当所有的Y 值使E' 为真时，所有的X 值使E 为假。因此，对任一量词而言，在给定的任一解释I之下，当且仅当(QY )E' 在相同解释下为真时，(QX )E 才为真，这就证明了如下表达式是重言式。

(QX )E≡(QY )E'

示例 14.15

考虑刚好是重言式的表达式

((∃X )p(X,Y ))OR NOT((∃X )p(X,Y ))　　　　　　(14.7)

我们要展示如何为这两个X 中的一个重命名，以形成两个量词中使用不同变量的另一个重言式。

如果设表达式(14.6)中的E 是p(X,Y )，并且选择变量Z 扮演(14.6)中Y 的角色，就有重言式((∃X )p(X,Y ))≡((∃Z )p(Z,Y ))。也就是说，如果要构造表达式E'，就要用Z 替换E=p(X,Y )中的X，从而得到p(Z,Y )。因此，可以“以相等换相等”，把(14.7)中的第一个(∃X )p(X,Y )替换为(∃Z )p(Z,Y )，以得出表达式

((∃Z )p(Z,Y ))OR NOT((∃X )p(X,Y ))

该表达式等价于(14.7)，因此也是重言式。

请注意，也可以用Z 替换(14.7)第二半中的X，是否这样做都是无关紧要的，因为这两个量词定义了没有关系的不同变量，只不过在(14.7)中它们都被命名为X。不过，我们应该明白，任何一个∃X 都不能用∃Y 替代，因为在出现的两个子表达式p(X,Y )中都是自由变量。

也就是说，((∃X )p(X,Y ))≡c 不是重言式(14.6)的实例，因为Y 是p(X,Y )中的自由变量。要知道这为什么不是重言式，可以设把p 解释为针对整数的<。那么对自由变量Y 的任何值，比方说Y=10，表达式(∃X )p(X,Y )都为真，因为我们可以设X=9。不过该等价的右边——(∃Y )p(X,Y )——为假，因为没有哪个整数严格小于自身。

同样，也不能用(∃Y )p(X,Y )替换(14.7)中(∃X )p(X,Y )的第一个实例。因为得到的表达式

((∃Y )p(Y,Y ))OR NOT((∃X )p(X,Y ))　　　　　　(14.8)

也不可能是重言式。这里还是设p 的解释为针对整数的<，并设自由变量Y 的值是10。请注意，在(14.8)中，出现在p(X,Y )中的两个Y 都是受到量词(∃Y )约束的，只有出现在p(X,Y )中的最后一个Y 是自由的。那么(∃Y )p(Y,Y )对这一解释而言为假，因为没有Y 的值比它自身小。另一方面，当Y=10（或其他任何整数）时，(∃X )p(X,Y )为真，所以NOT((∃X )p(X,Y ))为假。这样一来，表达式(14.8)对这一解释而言为假。

让量词化的变量唯一
(14.6)式有个有意思的结果，就是我们总是可以把任何谓词逻辑表达式E 转换成等价表达式，使其没有两个量词使用同一变量，而且没有量词使用在E 中也作为自由变量的变量。这样的表达式称为修正表达式（rectified expression）。
在证明过程中，我们可能从重言式E ≡E 开始，然后利用(14.6)，以E 中未使用过的新变量，依次为右边的E 中各量词化的变量重命名。得到的结果是表达式E ≡E'，其中E' 中所有的量词(QX )都涉及不同的X，而这些X 也不是E 或E' 中的自由变量。根据命题逻辑中等价的传递性，E ≡E' 是重言式，也就是说E 和E' 是等价的表达式。

14.7.2　自由变量的全称量词化

只有在其自由变量全称量词化的相同表达式为重言式时，带有自由变量的表达式才可能是重言式。严格来讲，对所有重言式T 和变量X 而言，(∀X )T 也是重言式。技术上讲，出现在T 中的X 是否自由都是没关系的。

要知道(∀X )T 为什么是重言式，设Y₁、…、Y_k 是T 的自由变量，X 可能是其中一员，也可能不是。首先，假设X=Y₁。我们需要证明，对所有的解释I，(∀X )T 为真。等价地讲，也就是需要证明，对I 的定义域中的每个值v，通过为X 给定值v 而由I 形成的解释J_v 使T 为真。但T 是重言式，所以每种解释都会使其为真。

如果X 是T 的其他自由变量Y_i 中的某一个，那么论证(∀X )T 为重言式的过程本质上讲是相同的。如果X 不是Y_i 中的一员，那么它的值不会对T 的真假产生影响。因此T 对所有的X 都为真，就因为T 是重言式。

14.7.3　闭表达式

一个有意思的结果是，对重言式来说，可以假设不存在自由变量。我们可以利用之前的变形，一次全称量词化一个自由变量。不含自由变量的表达式就叫作闭（closed）表达式。

示例 14.16

我们知道p(X,Y )OR NOT p(X,Y )是重言式。可以为自由变量X和Y加上全称量词，得到重言式

(∀X )(∀Y )(p(X,Y )OR NOT p(X,Y ))

14.7.4　把量词移过`NOT`

存在德摩根律的无限版本，让我们可以用∃替代∀，反之亦然，就像“普通的”德摩根律允许我们在移过NOT的时候，在AND和OR之间切换一样。假设有像

NOT((∀X )p(X ))

这样的表达式。如果定义域值的数量是有限的，比方说是v₁、…、v_n，那么可以把该表达式看作NOT(p(v₁)AND p(v₂)AND…AND p(v_n))。然后，可以应用德摩根律把该表达式重新写为NOT p(v₁)OR NOT p(v₂)OR…OR NOT p(v_n)。在有限定义域的假设之下，这一表达式就等同于(∃X )(NOT p(X ))，也就是说，对某个X 的值，p(X )为假。

事实上，这一变形并不取决于定义域的有限性，它对每种可能的解释来说都是成立的。也就是说，下面的等价对任何表达式E 来说都是重言式。

(NOT((∀X )E ))≡((∃X)(NOT E ))　　　　　　(14.9)

粗略地讲，(14.9)表示，刚好在存在某个X 的值令E 为假时，E 对所有的X 都不为真。

还有一个类似的重言式让我们可以把NOT压入存在量词。

(NOT((∃X )E ))≡((∀X )(NOT E ))　　　　　　(14.10)

粗略地讲就是，刚好当E 对所有X 来说都为假时，不存在X 使E 为真。

示例 14.17

考虑我们根据命题逻辑重言式p OR NOT p，利用替换原则得到的重言式

(∀X )p(X ) OR NOT((∀X )p(X ))　　　　　　(14.11)

可以令(14.9)中的E=p(X )，用(∃X )(NOT p(X ))替换(14.11)中的NOT((∀X )p(X ))，得到重言式

(∀X )p(X )OR(∃X )(NOTp(X ))

也就是说，要么p(X )对所有的X 都为真，要么存在某个X 令p(X )为假。

14.7.5　把量词移过`AND`和`OR`

在从左向右应用法则(14.9)和(14.10)时，可以把量词移到否定之外，并在这样做的过程中“反转”量词，也就是用∀代替∃，用∃代替∀。同样，可以把量词移到AND或OR之外，不过一定要小心，不能改变其中出现的任何变量的约束情况。还有，我们在移过AND或OR时不会反转量词。这些法则的表达式为

(E AND(QX )F)≡(QX )(E AND F )　　　　　　(14.12)

(E OR(QX )F )≡(QX )(E OR F )　　　　　　(14.13)

其中E 和F 是任何表达式，而Q 是任一量词。不过，我们要求X 在E 中不是自由变量。

因为AND和OR都是满足交换律的，所以还可以使用(14.12)和(14.13)移动附加到AND或OR左操作数上的量词。例如，由(14.12)以及AND的交换律可得出如下表达式

((QX )E AND F )≡(QX )(E AND F )

这里，我们要求X 在F 中不是作为自由变量出现的。

示例 14.18

我们来为示例14.17中得出的重言式，也就是

(∀X )p(X )OR(∃X )(NOT p(X ))

变形，使得量词都在表达式之外。首先，需要为两个量词之一所使用的变量重命名。根据法则(14.6)，可以用(∃Y )NOT p(Y )替代(∃X )NOT p(X )，得出重言式

(∀X )p(X )OR(∃Y )(NOT p(Y ))　　　　　　(14.14)

现在可以利用(14.13)的变形，也就是利用量词移到OR运算左操作数上的那个重言式，将∀移到OR之外，得到的表达式就是

(∀X )(p(X )OR(∃Y )(NOT p(Y ))　　　　　　(14.15)

表达式(14.15)与(14.14)只是形式不同，含义却没什么不同。(14.15)表述的是，对所有的X的值，以下两条中至少有一条成立：

1. p(X )为真；

2. 存在某个值Y，使p(Y )为假。

要知道(14.15)为何是重言式，可以考虑对应X 的某个值v。如果所考虑的解释使p(v )为真，那么有p(X )OR(∃Y )(NOT p(X ))为真。如果p(v )为假，那么在这一解释中，(2)肯定成立。特别要说的是，当Y=v 时，NOT p(X )为真，因此(∃Y )(NOT p(Y ))为真。

最后，可以应用(14.13)，将∃Y 移到OR运算之外，得到的表达式就是

(∀X )(∃Y )(p(X )OR NOT p(Y ))

该表达式也一定是重言式。粗略地讲，它所表述的是，对每个X 的值，存在某个Y 的值，使得p(X )OR NOT p(Y )为真。要知道原因，设v 是X 可能的取值之一。如果p(v )在给定解释I 之下为真，那么显然有如下表达式为真，不管Y 是什么。

p(X )OR NOT p(Y )

如果p(v )在解释I中为假，就可以为Y 选择v，这样(∃Y )(p(X )OR NOT p(Y ))就为真。

14.7.6　前束式

法则(14.9)、(14.10)、(14.12)和(14.13)带来的结果是，给定任一涉及量词与逻辑运算符AND、OR和NOT的表达式，可以为其找到量词全部在外部（在表达式树的顶部）的等价表达式。也就是说，可以找到形如

(Q₁X₁)(Q₂X₂)…(Q_kX_k)E　　　　　　(14.16)

的等价表达式，其中Q₁、…、Q_k 各自代表量词∀或∃中的某一个，而且子表达式E 是无量词的。如此则称表达式(14.16)是前束式（prenex form）的。

通过以下两步，就可以把表达式变形为前束式表达式。

1. 修正表达式。也就是说，利用法则(14.6)，使各个量词引用不同的变量，出现在一个量词中的变量既不会出现在另一个量词中，也不会作为表达式的自由变量出现。

2. 然后，根据法则(14.9)和(14.10)把各量词移过NOT，根据法则(14.12)移过AND，并根据(14.13)移过OR。

前束式程序
原则上讲，只要重命名所有局部变量，使它们全都具有不同的变量名，然后将它们的声明移到主程序中，我们也可以把C语言程序表示为前束式程序。不过一般不会这么做，而是会选择在局部声明变量，比方说，这样一来就不必担心为在10个不同函数中用作循环指标的变量i使用各种不同的变量名了。对逻辑表达式来说，通常都有理由将表达式表示为前束式表达式，虽然这一问题超出了本书的范围。

示例 14.19

示例14.17和示例14.18都是这一过程的例子。从给出表达式(∀X )p(X )OR NOT((∀X )p(X ))的示例14.17开始，通过把第二个∀移过NOT，就得到示例14.18中一开始的表达式

(∀X )p(X )OR(∃X )(NOT p(X ))

然后我们为用到的第二个X 重命名，这是一开始就可以完成而且应该完成的。通过把两个量词移过OR运算符，就得到前束式表达式(∀X )(∃Y )(p(X )OR NOT p(Y ))。

请注意，涉及AND、OR和NOT之外的逻辑运算符的表达式也可以变形为前束式表达式。正如我们在第12章中了解到的，每种逻辑运算符都可以用AND、OR和NOT表示出来。例如，E →F 就可以替换为NOT E OR F 。如果把各逻辑运算符都用AND、OR和NOT表示出来，就能够应用刚刚概述过的变形方式找到等价的前束式表达式。

14.7.7　量词的重新排列

最后要介绍的重言式指出了，将全称量词应用于两个变量，排列这两个量词的次序是没关系的。同样，也可以用任一次序排列两个存在量词。严格地讲就是，以下两个表达式是重言式。

(∀X )(∀Y )E≡(∀Y )(∀X)E　　　　　　(14.17)

(∃X )(∃Y )E≡(∃Y )(∃X )E　　　　　　(14.18)

请注意，根据(14.17)，我们能够把任一∀串(∀X₁)(∀X₂)(…)(∀X_k )排列成选定的任意次序。事实上，(14.17)就是∀的交换律。同样的结论对法则(14.18)（即∃的交换律）也是成立的。

14.7.8　习题

1. 将以下表达式变形为修正表达式，也就是说，任两个量词不会共用同一变量的表达式。

(a) (∃X )((NOT p(X ))AND((∃Y )(p(Y ))OR(∃X )(q(X,Z ))))

(b) (∃X )((∃X )p(X )OR(∃X )q(X )OR r (X ))

2. 通过把各自由变量全称量词化，将以下表达式转换为闭表达式。如果需要的话，可以为变量重命名，使两个量词不会使用相同变量。

(a) p(X,Y )AND(∃Y )q(Y )

(b) (∀X )(p(X,Y )OR(∃X )p(Y,X ))

3. * 法则(14.12)是否暗指p(X,Y )NOT(∀X )q(X )与(∀X )(p(X,Y )AND q(X ))是等价的？对自己的回答作出解释。

4. 把习题1中的表达式变形为前束式表达式。

5. * 说明如何把量词移过→运算符。也就是说，如何把表达式((Q₁X )E )→((Q₂Y )F )变形为前束式表达式。大家需要对E 和F 中的自由变量进行什么约束？

6. 我们可以利用重言式(14.9)和(14.10)把NOT移进量词和移出量词。利用这些法则以及德摩根律，可以移动所有的NOT，使它们直接应用到原子公式上。为下列表达式应用这种变形

(a) NOT((∀X )(∃Y )p(X,Y ))

(b) NOT((∀X )(p(X )OR(∃Y )q(X,Y )))

7. * 只要(∃X )E 是重言式，E 就是重言式，这样的说法是否正确？

14.8　谓词逻辑中的证明

在14.8和14.9这两节中将讨论谓词逻辑中的证明。不过，我们不会把12.11节中的分解法扩展到谓词逻辑中，虽然这样也是可行的。事实上，分解对很多使用谓词逻辑的系统来说也是极为重要的。这种证明机制将在12.10节中介绍。回顾一下，在命题逻辑的证明中，给定某些表达式E₁、E₂、…、E_k 作为前提或者说“公理”，并构造一系列表达式（行），使各表达式符合下列条件之一。

1. 为E_i 之一；

2. 根据推理规则，是用之前的0个或更多表达式得到的。

推理规则必须具有以下属性，只要我们因为F₁、F₂、…、F_n 出现在表达式列中，而可以向表达式列中添加F，就有

(F₁ AND F₂ AND…AND F_n)→F

是重言式。

谓词逻辑中的证明基本是相同的。当然，作为前提和证明中各行的表达式都是谓词逻辑表达式，而非命题逻辑表达式。此外，一个表达式的自由变量与另一个表达式中同名的自由变量是不能存在关系的，所以会要求前提和证明中各行都是闭公式。

14.8.1　隐式全称量词

然而，一般约定在书写证明中的表达式时，不会显式给出最外层的全称量词。例如，考虑示例14.3中的表达式

(csg(“CS101”,S,G )AND snap(S,“C.Brown”,A,P ))→answer(G )　　　　　　(14.19)

表达式(14.19)可能是证明的某一前提。在示例14.3中，我们凭直觉将其看作谓词answer 的定义。比方说，我们在answer ("A")，也就是C.Brown的CS101课程得了A的证明中可能用到(14.19)。

在示例14.3中，对(14.19)含义的解释是，对所有的S、G、A 和P 的值，如果说学号为S 的学生CS101课程得到了成绩G，也就是说，如果csg("CS101",S,G )为真，而且学号为S 的学生名叫C.Brown，地址为A，电话号码为P，也就是说，如果snap(S,"C.Brown",A,P)为真，那么G 就是一种答案，即answer (G )为真。在示例14.3的那个例子中，我们还没有正式的量词概念。不过，现在看到，真正想要断言的是

(∀S )(∀G )(∀A )(∀P )(((csg(“CS101”,S,G )AND snap(S,“C.Brown”,A,p ))→answer(G ))

因为经常需要在表达式前引入一串全称量词，所以我们会用简化符号(∀*)E 表示一串全称量词(∀X₁)(∀X₂)…(∀X_k)E，其中X₁、X₂、…、X_k 是表达式E 的自由变量。例如，(14.19)就可以写成

(∀*)((csg("CS101",S,G )AND snap(S,"C.Brown",A,P ))→answer (G ))

不过，我们将继续把E 中的自由变量称为(∀*)E 中的“自由变量”。这样使用术语“自由”严格来讲是不正确的，但是非常实用。

14.8.2　作为推理规则的变量替换

除了第12章中讨论过的对应命题逻辑的推理规则外，比如肯定前件式假言推理，以及在证明的前一行中进行以相等换相等的替换，对谓词逻辑中的证明来说还有一种特别实用的涉及变量替换的推理规则。如果已经断言作为前提或证明中某一行的表达式E，而且E ' 是通过用变量或常量替换E 中某个自由变量形成的表达式，那么E →E ' 是重言式，而且我们可以向证明中添加E ' 这样一行。务必记住，我们不能替换E 的约束变量，只能替换E 的自由变量。

严格地讲，可以用函数sub 作为表达式变量的替换。对E 中各自由变量X 而言，可以定义sub(X )为某个变量或某个常量。如果没有为sub(X )指定值，就要假设想要的是sub(X )=X。如果E 是任一谓词逻辑表达式，表达式sub(E )就是将E 中所有作为自由变量出现的X 用sub(X )替代后得到的。

证明中出现的表达式
请记住，如果在证明中看到表达式E，它其实是(∀*)E 的简略形式。要注意到E≡(∀*)E 一般不是重言式，因此我们显然是在用一个表达式代表一个与之不同的表达式。
还要记住，当证明中出现E 时，并不是在断言(∀*)E 是重言式，而是在断言(∀*)E 是根据前提得出的。也就是说，如果E₁、E₂、…、E_n 是前提，而且正确书写了证明中的行E，则可知
((∀*)E₁AND(∀*)E₂ AND…AND(∀*)E_n)→(∀*)E
是重言式。

变量替换法则说明E →sub(E )是重言式。因此，如果E 是证明中的行，就可以在同一证明中加入sub(E )这一行。

示例 14.20

考虑以表达式(14.19)

(csg(“CS101”,S,G )AND snap(S,“C.Brown”,A,P ))→answer (G )

作为E。可以将一种可能的替换sub 定义为

sub(G )="B "
sub(P )=S

也就是说，这里要用常量B替换变量G，并用变量S 替换变量P。而变量S 和A 保持不变。表达式sub(E )就是

(csg(“CS101”,S“B ”)AND snap(S,“C.Brown”,A,S ))→answer (“B ”)　　　　　　(14.20)

通俗地说，表达式(14.20)的意思是，如果学生S 的CS101课程得了B，该学生的姓名是C.Brown，而且该学生的电话号码和学号是唯一的，那么“B”就是答案。

请注意，(14.19)表达了更具一般性的规则，而(14.20)只是它的一个特例。也就是说，只有在成绩为B，而且C.Brown的学号巧合到与他的电话号码相同时，(14.20)才能推理出正确答案，否则(14.20)不说明任何问题。

示例 14.21

表达式

p(X,Y )OR(∃Y )q(X,Z )　　　　　　(14.21)

中含有自由变量X 和Y，以及约束变量Z。回想一下，从技术上讲，(14.21)其实代表闭表达式(∀*)(p(X,Y ))OR(∃Z )q(X,Z )，而这里的(∀*)代表对自由变量X 和Y 的量化，也就是有

(∀X )(∀Y )(p(X,Y ))OR(∃Z )q(X,Z )

在(14.21)中，可以替换sub(X )＝a和sub(Y )＝b，得到表达式p(a,b )OR(∃Z )q(a,Z )。不难看出，这一不含自由变量（因为我们用常量替换了其中各自由变量）的表达式是(14.21)的一个特例，它陈述了要么p(a,b )为真，要么存在某个Z 的值，使得p(a,Z )为真。正式地讲，

((∀X )(∀Y)(p(X,Y )OR(∃Z)q(X,Z )))→(p(a,b )OR(∃Z )q(a,Z ))

是重言式。

有人可能想知道在用a 和b 替换X 和Y 时(14.21)中隐含的量词会发生什么。答案是，得到的表达式p(a,b )OR(∃Z )q(a,z )中不存在自由变量，隐含的表达式(∀*)(p(a,b )OR(∃Z )q(a,z ))没有全称量词前缀，也就是说

p(a,b )OR(∃Z )q(a,Z )

在这种情况中只代表自身。我们不会把(∀*)替换为(∀a )(∀b )，因为常量不可能被量词化，这样做是行不通的。

替换的特例
示例14.20是一般情况，其中只要我们对表达式E 应用替换sub，得到的就是E 的特例。如果sub 用常量c 替换变量X，那么表达式sub(E )就只适用于X=c 的情况，而不适用于其他情况。如果sub 让两个变量变得相同，那么sub(E )就只适用于两个变量具有相同值的特例。然而，变量的替换往往正是我们进行证明时所需的，因为它们让我们可以在特例中应用一般规则，而且让我们可以将规则组合起来构成其他规则。我们将在14.9节中研究这种形式的证明。

14.8.3　习题

根据前提，利用12.10节中讨论过的推理规则以及刚刚讨论过的变量替换规则，证明以下结论。请注意，大家可以把任何命题或谓词演算的重言式用作证明的某一行。不过，请尽量只使用12.8节、12.9节和14.7节中介绍的重言式。

(a) 根据前提(∀X )p(X )，证明结论(∀X )p(X )OR q(Y )。

(b) 根据前提(∃X )p(X,Y )，证明结论NOT((∀X )(NOT p(X,a )))。

14.9　根据规则和事实的证明

谓词逻辑中形式最简单的证明可能涉及以下两类前提。

1. 事实（fact），它们是基本原子公式。

2. 规则（rule），它们是“如果-那么”形式的表达式。我们在示例14.20中讨论过的有关C.Brown在课程CS101所取得成绩的查询(14.19)就是一个例子

(csg(“CS101”,S,G )AND snap(S,“C.Brown”,A,P ))→answer(G )

规则由蕴涵符号左侧的一个或更多原子公式的AND以及蕴涵符号右侧的一个原子公式组成。假设出现在右部的任何变量也会出现在左部中的某处。

规则的左边（前提）叫作左部（body），而右边叫作右部（head）。左部中的任一原子公式叫作子目标（subgoal）。例如，在上面再次表示出的规则(14.19)中，子目标是csg("CS101",S,G )和snap(S,"C.Brown",A,P )。右部是answer(G )。

规则的一般使用思路是，规则是可以应用于事实的一般原则。我们会试着通过替换规则中的变量，将规则左部的子目标与给定或已经证明的事实匹配起来。如果能这样做，这种替换会使右部成为基本原子公式，因为已经假设右部的各变量都会出现在左部中。我们可以把这一新的基本原子公式添加到自己可支配的事实集中，以作进一步证明之用。

示例 14.22

根据规则和事实的证明有一种简单的应用，就是用于回应第8章讨论的关系模型中的查询。关系对应的是谓词符号，而关系中的元组则对应着基本原子公式，这些基本原子公式具有谓词符号以及依次等同于元组组分的参数。例如，由图8-1中的“课程-学号-成绩”关系，可以得到如下事实

csg(“CS101”,12345,“A”)　　csg(“CS101”, 67890,“B”)
csg(“EE200”,12345,“C”)　　csg(“EE200”, 22222,“B+”)
csg(“CS101”,33333,“A-”)　csg(“PH100”, 67890,“C+”)

同样，由图8-2a中的“学号-姓名-地址-电话”关系，可以得到以下事实

snap(12345,“C.Brown”,“12Apple St.”,555-1234)
snap(67890,“L.Van Pelt”,“34Pear Ave.”,555-5678)
snap(22222,“P.Patty”,“56Grape Blvd.”,555-9999)

对这些事实，可以添加规则(14.19)

(csg(“CS101”,S,G )AND snap(S,“C.Brown”,A,P ))→answer(G )

从而完成前提列表。

假设想要证明answer("A")为真，也就是说，C.Brown的CS101课程得了A。在证明开头部分要列出所有的事实和规则，虽然在这里我们只需要规则、第一条csg 事实和第一条snap 事实即可。证明的前3行就是

(1) (csg(“CS101”,S,G )ANDsnap(S,“C.Brown”,A,P ))→answer(G )

(2) csg(“CS101”,12345,“A”)

(3) snap(12345,“C.Brown”,“12Apple St.”,555-1234)

下一步是利用推理规则（如果E₁和E₂是证明中某两行，则可以把E₁ AND E₂写为证明中的一行）把第二行和第三行结合起来，因此就有了这样一行

(4) csg(“CS101”,12345,“A”)AND

　snap(12345,“C.Brown”,“12Apple St.”,555-1234)

然后，利用自由变量的替换法则特化我们的规则——第(1)行，使它适用于第(4)行中的常量。也就是说，要在第(1)行中进行以下替换

sub(S )=“CS101”
sub(G )=“A”
sub(A )=“12Apple St.”
sub(P )=555-1234

得到如下一行

(5) csg(“CS101”,12345,“A”)AND snap(12345,“C.Brown”,“12Apple St.”,555-1234)→answer (“A”)

最后，对(4)和(5)应用肯定前件式假言推理就得到该证明的第六行也是最后一行

(6) answer (“A”)。

14.9.1　简化的推理规则

如果看过示例14.22中的证明，就可以得出以下根据基本原子公式和逻辑规则构建证明的策略。

1. 选择一条要应用的规则，并选择一种替换，将各个子目标转换成基本原子公式，这些基本原子公式要么是给定的事实，要么是已经证明的内容。在示例14.22中，我们用12345替换了S，等等。得到的结果就如示例14.22的第(4)行所示。

2. 为替换过的各个子目标创建证明中的行，要么因为这些子目标是事实，要么用某种方式推断出它们。这一步是示例14.22中的第(2)行和第(3)行。

3. 创建一行，表示与替换过的各子目标对应的那几行的AND。这一行是替换过规则的左部。在示例14.22中，这一步出现在第(5)行。

4. 利用肯定前件式假言推理、第(3)步替换过的左部，以及第(1)步替换过的规则，推论出替换过的右部。这一步就是示例14.22的第(6)行。

可以按照如下方式把这些步骤结合成一条推理规则。如果在前提中存在规则R，而且存在替换sub 满足在替换过的实例sub(R )中，各子目标都是证明中的行，就可以把sub(R )的右部添加为证明中的一行。

规则的诠释
和所有出现在证明中的表达式一样，规则也是因式全称量词化的。因此可以把(14.19)说成是“对所有的S、G、A 和P，如果csg("CS101",S,G )为真，而且snap(S,"C.Brown",A,P )为真，那么answer (G )为真”。不过，可以将出现在左部中但未出现在右部中的变量，比如S、A 和P，当作左部范围内的存在量词。正式地讲就是(14.19)等价于
(∀G )((∃S )(∃A )(∃P )(csg("CS101",S,G )AND snap(S,"C.Brown",A,P ))→answer(G ))
也就是说，对所有的G，如果存在S、A 和P 满足csg("CS101",S,G )和snap(S,"C.Brown",A,P )都为真，answer (G )就为真。
这种说法更接近我们应用规则的方式。它表示，对右部中出现的变量的各个值，我们应该试着找出只出现在左部中的变量使得左部为真时的值。如果找到这样的值，则右部对所选的右部变量的值而言为真。
要知道为什么可以把只出现在左部中的变量当作存在量词化的变量，首先从形如B→H 这样的规则开始，其中B 是左部，H 是右部。设X 是只出现在B 中的变量。这一规则隐含着如下形式
(∀*)(B→H )
而且根据法则(14.17)，可以让对应X 的量词位于最内侧，将表达式写为(∀*)(∀X )(B→H )。在此，(∀*)包含了除X 之外的所有变量。现在可以利用只使用NOT和OR的等价表达式，即(∀*)(∀X )((NOT B )OR H )来代替蕴涵式了。因为X 没有出现在H 中，所以可以反向应用法则(14.13)，从而让(∀X )只应用于NOT B，得到(∀*)(((∀X )NOT B )OR H )。接下来，利用法则(14.10)把(∀X )移动到否定内，就得出
(∀*)((NOT(∃X )(NOT NOT B ))OR H )
消除双重否定之后就是(∀*)((NOT (∃X )B )OR H )。最后，还原蕴涵就得到(∀*)(((∃X )B )→H )。

示例 14.23

在示例14.22中，规则R是(14.19)，或者说

(csg("CS101",S,G )AND snap(S,"C.Brown",A,P ))→answer (G )

替换sub 就如示例14.22中给出的那样，而且sub(R )的子目标是示例14.22中的第(2)和第(3)行。根据新的推理规则，可以立即写出示例14.22的第(6)行，而不需要第(4)行和第(5)行。其实，只要第(1)行（规则R 本身）是给定的前提，就可以从证明中省略掉它。

示例 14.24

再举个规则在证明中如何应用的例子。考虑一下图8-2b中的“课程-前提”关系，其中的8个事实可以用如下8个具有谓词cp 的基本原子公式表示。

cp(“CS101”,“CS100”)　cp(“EE200”,“EE005”)
cp(“EE200”,“CS100”)　cp(“CS120”,“CS101”)
cp(“CS121”,“CS120”)　cp(“CS205”,“CS101”)
cp(“CS206”,“CS121”)　cp(“CS206”,“CS205”)

我们可能希望另一个谓词before(X,Y )表示在选修课程X 之前必须修完课程Y。课程Y 可能是X 的前提，或是X 前提的前提，诸如此类。可以通过以下描述递归地定义“之前”的概念。

(1) 如果Y 是X 的前提，那么Y 在X 之前。

(2) 如果Z 是X 的前提，而且Y 在Z 之前，那么Y 在X 之前。

规则(1)和(2)可以表示为如下的谓词逻辑规则。

cp(X,Y )→before(X,Y )　　　　　　(14.22)

(cp(X,Z )AND before(Z,Y ))→before(X,Y )　　　　　　(14.23)

现在要来探索一些根据本示例开头部分给出的8条“课程-前提”事实以及规则(14.22)和(14.23)可以证明的before 事实。首先，可以应用规则(14.22)把各条cp 事实转换成相应的before 事实，得到：

before(“CS101”,“CS100”)　before(“EE200”,“EE005”)
before(“EE200”,“CS100”)　before(“CS120”,“CS101”)
before(“CS121”,“CS120”)　before(“CS205”,“CS101”)
before(“CS206”,“CS121”)　before(“CS206”,“CS205”)

例如，可以对(14.22)使用替换

sub₁(X )=“CS101”
sub₁(Y )=“CS100”

得到替换过的规则实例

cp(“CS101”,“CS100”)→before(“CS101”,“CS100”)

这条规则加上前提cp(“CS101”,“CS100”)，就给出了

before(“CS101”,“CS100”)

现在可利用规则(14.23)、前提cp(“CS101”,“CS100”)以及刚证明的事实before(“CS101”,“CS100”)，证明

before(“CS120”,“CS100”)

也就是，对(14.23)应用替换

sub₂(X)=“CS120”
sub₂(Y)=“CS100”
sub₂(Z)=“CS101”

得到规则

(cp(“CS120”,“CS101”） AND before(“CS101”,“CS100”))→before(“CS120”,“CS100”)

然后可以推断出这一替换过的规则的右部，从而证明

before(“CS120”,“CS100”)

同样，可以对基本原子公式

cp(“CS121”,“CS120”)

和before(“CS120”,“CS100”)应用规则(14.23)，证明before(“CS121”,“CS100”)。然后对基本原子公式cp(“CS206”,“CS121”)和before(“CS121”,“CS100”)应用规则(14.23)，证明

before(“CS206”,“CS100”)

还有若干条其他的before 事实也可以通过同样的方式来证明。

图中的路径
示例14.24所处理的，是规则的一种常见形式，它在给定有向图中弧的情况下，定义了图中的路径。把课程当作节点，如果课程b 是课程a 的前提，就存在弧a→b。那么before(a,b )就对应着从a 到b 的某一条长度为1或更长的路径。图14-9展示了基于图8-2b中“课程-前提”信息绘制的有向图。
在图表达是前提时，我们希望它是无环的，因为选修某门课程的前提是修过这门课本身。不过，即便图中含有环路，同类的逻辑规则也仍然用弧定义了路径。可以把这些规则写成
arc(X,Y )→path(X,Y )
也就是说，如果存在从节点X 到节点Y 的弧，就存在从X 到Y 的路径，而且
(arc(X,Z )AND path(Z,Y ))→path(X,Y )
也就是说，如果存在从X 到某节点Z 的弧，而且存在从Z 到Y 的路径，那么存在从X 到Y 的路径。请注意，这些内容与(14.22)和(14.23)表示的是同样的规则，其中用谓词arc 代替了cp，用path 代替了before。

图 14-9　表示成有向图的前提信息

14.9.2　习题

1. * 我们可以按照以下方式证明示例14.24中的谓词before 是谓词cp 的传递闭包。假设存在一系列的课程c₁、c₂、…、c_n，其中n≥2，而且c₁是c₂的前提，c₂是c₃的前提，以此类推，对i=1、2、…、n-1而言，cp(c_i ,c_i+1)是给定的事实。通过对i 的归纳证明对i=2、3、…、n，有before(c₁,c_i )，从而证明c₁在c_n 之前。

2. 利用示例14.24中的规则和事实，证明以下事实。

(a) before(“CS120”,“CS100”)

(b) before(“CS206”,“CS100”)

3. 通过向示例14.24添加规则

(before(X, Z )AND before(Z,Y ))→before(X,Y )，

可以提高处理前提链的速度。也就是说，第一个子目标可以是任一before 事实，而不止是前提事实。利用该规则，为习题2的(b)小题找出更简短的证明。

4. * 示例14.24中有多少before 事实是可以证明的？

5. 设csg是代表图8-1中“课程-学号-成绩”关系的谓词，cdh 是代表图8-2c中课程-日子-时刻关系的谓词，cr 是代表图8-2d中“课程-教室”关系的谓词。并设where(S,D,H,R )是表示学号为S 的学生D 那天H 时在教室R 上课。更精确地讲，学号为S 的学生选修的课程是那个时间在那个教室上课。

(a) 写出用csg、cdh 和cr 定义where 的规则。

(b) 如果对应谓词csg、cdh 和cr 的事实是图8-1和图8-2中给出的，那么可以推导出哪些where 事实？证明两条这样的事实。

14.10　真理和可证性

在为谓词逻辑的讨论收尾时，我们要介绍一个更为微妙的逻辑问题：可证明内容与真实内容之间的区别。前面已经看到过这样一些推理规则，它们允许我们证明命题逻辑或谓词逻辑中的内容，但我们不确定给定的规则集合是否完备，是否允许我们证明每一个真命题。例如，我们断言12.11节中所表示的分解对命题逻辑而言是完备的。分解的一种一般化形式（这里没有涵盖）对谓词逻辑而言也是完备的。

14.10.1　模型

不过，要理解证明策略的完备性，就需要掌握“真理”的概念。要发现“真理”，需要理解模型（model）的概念。每种逻辑对表达式集而言都有模型的概念，这些模型是令表达式为真的解释。

示例 14.25

在命题逻辑中，解释是真值赋值。考虑表达式E₁=p AND q 和E₂= $\overline{p}$ OR r。涉及变量p、q 和r 的表达式有8种真值赋值，我们可以用依次对应各变量真值的3位构成的位串来表示这些真值赋值。

只有真值赋值令p 和q 都为真（即110和111这两种真值赋值）时，它才能令表达式E₁为真。而000、001、010、011、101和111这6种真值赋值可以让表达式E₂为真。因此只有一种对应表达式集{E₁,E₂}的模型，即111，因为只有该模型出现在两个列表中。

示例 14.26

在谓词逻辑中，解释是14.5节中定义过的结构。我们来考虑表达式E

(∀X )(∃Y )p(X,Y )

也就是说，对每个X 的值来说，至少存在一个Y 值，使得p(X,Y )为真。

如果对定义域D 中每个元素a 来说，在D 中存在某个元素b（对各个a 不一定有相同的b），使得“谓词p 的解释”这个关系中具有成员“有序对(a,b )”，就说解释使得E 为真。这些解释就是E 的模型，其他的解释则不是。例如，如果定义域D 是整数，而且当且仅当X< Y 时，谓词p 的解释使得p(X,Y )为真，我们就有了对应表达式E 的模型。不过，定义域D 也是整数，而且p 的解释是当且仅当X=Y ²时p(X,Y )为真，这一解释就不是表达式E 的模型。

14.10.2　蕴涵

在给定表达式集{E₁,E₂,…,E_n}的情况下，就可以陈述表达式E 为真的含义了。如果每个对应{E₁,E₂,…,E_n}的模型M 也是对应E 的模型，就说{E₁,E₂,…,E_n}蕴涵（entail）表达式E。双十字转门（double turnstile）运算符⊧就表示蕴涵，如

E₁，E₂，…，E_n⊧E

我们需要凭直觉意识到每种解释都是一个可能存在的世界。当说E₁，E₂，…，E_n⊧E 时，也就是在说，在使表达式E₁，E₂，…，E_n为真的每个可能存在的世界中，E 都为真。

蕴涵的概念应该是与证明的概念形成对照的。如果我们有某个特定的证明系统，比如说分解证明，那么可以使用单十字转门（single turnstile）运算符⊦用同样的方式表示证明。也就是说，

E₁，E₂，…，E_n⊦E

意味着，对当前所拥有的推理规则集而言，存在从前提E₁，E₂，…，E_n到E 的证明。请注意，⊦运算符对不同的证明系统可能存在不同的含义。还要记住，虽然我们一般乐于使用当且仅当另一者为真时一者为真的证明系统，但是⊧和⊦不一定是相同的关系。

重言式与蕴涵之间有着密切联系。特别要指出的是，假设E₁，E₂，…，E_n⊧E。然后可以声明

(E₁ANDE₂AND…ANDE_n)→E　　　　　　(14.24)

是重言式。若某解释I 使(14.24)左边为真，则I 是{E₁,E₂,…,E_n}的模型。因为E₁，E₂，…，E_n⊧E，所以I 一定也能使E 为真。因此I 使(14.24)为真。

其他的可能就只有I 使(14.24)的左边为假。这样一来，因为当蕴涵的左边为假时它恒为真，可知(14.24)还是为真。因此(14.24)是重言式。

反过来，如果(14.24)是重言式，则可以证明E₁，E₂，…，E_n⊧E。这里把这一证明留作本节习题。

请注意，我们的论证并不取决于涉及的表达式是命题逻辑表达式还是谓词逻辑表达式，或者是我们没有了解的某种其他逻辑的表达式。只需要知道，重言式是指那些所有“解释”都使之为真的表达式，而表达式或表达式集的模型是指令这一或这些表达式为真的某种解释。

14.10.3　可证性与蕴涵的比较

我们想要给定的证明系统允许我们证明所有为真的事物，而且不会证明为假的事物。也就是说，我们希望单十字转门和双十字转门符号表示相同的含义。如果只要某事物可证，它也就被蕴涵，那么该证明系统是相容的（consistent）。也就是说，E₁，E₂，…，E_n⊧E 蕴涵E₁，E₂，…，E_n⊦E。例如，我们在12.10节中讨论过为什么命题逻辑的推理规则是相容的。准确地讲，我们证明了，只要从前提E₁、E₂、…、E_n开始，并在证明中写出一行E，就有(E₁ANDE₂AND…ANDE_n)→E 是重言式。根据上面论证过的，这就等同于表述E₁，E₂，…，E_n⊧E。

我们还希望证明系统是完备的。这样就可以证明所有由前提蕴涵的事物，即便要找到该证明是很难的。事实证明，12.10节给出的推理规则，还有12.11节的分解规则都是完备证明系统。也就是说，如果E₁，E₂，…，E_n⊧E，则E₁，E₂，…，E_n⊦E 也在这些证明系统中。完备的谓词逻辑证明系统是存在的，虽然我们不会介绍它们。

14.10.4　哥德尔不完备性定理

这个现代数学最引人注目的结论之一通常被看作与我们刚说过的谓词逻辑存在完备证明系统是矛盾的。事实上，这一结论并未涉及前面讨论过的谓词逻辑，而是关系到谓词逻辑的一种特殊形式，这种逻辑只谈论整数以及常见的整数运算。特别要说的是，我们必须对谓词逻辑加以修改，从而引入对应算术运算的谓词，比如

1. plus(X,Y,Z )，我们希望当且仅当X+Y=Z 时它才为真，

2. times(X,Y,Z )，只有在X×Y=Z 时为真，以及

3. less(X,Y )，只有在X< Y 时为真。

此外，我们需要对解释中的定义域加以限制，以使这些值都是非负整数。完成这一工作有两种方式。一种是引入由我们断言为真的表达式构成的表达式集。通过恰当地选择这些表达式，任何满足表达式的解释中的定义域都必须“看似”整数，而且像plus 或less 这样的特殊谓词必须具有和同名运算相同的行为。

示例 14.27

我们可以断言像

plus(X,Y,Z )→plus(Y,X,Z )

这样表示加法交换律的表达式，或表示<关系传递性的表达式

(less(X,Y )AND less(Y,Z ))→less(X,Z )

也许理解哥德尔的定理为谓词逻辑带来的限制有种更简单的方式，就是假设这种逻辑只允许一种模型，这种模型的定义域是非负整数，而且为这些特殊的谓词给定了与它们的约定含义对应的关系。例如，我们可以令对应谓词plus的解释为

{(a,b,c ) | a+b=c }

哥德尔的定理说的是，不管选择什么相容的证明系统，总是存在某个为真但不可证明的表达式E!更精确地讲，如果E₁、E₂、…、E_n 是其模型相当于非负整数的这样一些表达式，那么有E₁，E₂，…，E_n⊧E 为真，但E₁，E₂，…，E_n⊦E 为假。也就是说，在我们选定的证明系统中，不可能根据{E₁,E₂,…,E_n}证明E。

对选定的不同证明系统而言，不可证明的表达式E 可能是不同的。事实上，所选的表达式E可被视作把该表达式本身在给定证明系统中不可证明这一事实编码为整数的一种方法。

14.10.5　计算机能完成的工作的限制

哥德尔的理论表明我们回答与数学相关的问题的能力是有限的。如果拥有像整数这样复杂的数学模型，以及我们在本书中已经见识过的，比整数还要复杂得多的数学模型，就不存在将真命题与假命题区分开的机械方式。我们能做到的最多也就是利用某种相容的证明系统以便可以寻找证明。如果找到一种，就算是非常幸运了，而且可以确定被证明的命题为真。不过，这种找寻可能一直继续下去，而永远都找不到证明，即便该命题为真。也就是说，我们定义手头的数学模型时所做的假设蕴涵了该命题。

从哲学的角度讲，这种情况说明了数学永远会是充满乐趣和挑战的。从实践的角度讲，它表明用计算机可以完成的任务是有限的。特别要指出的是，虽然可以编写程序在简单的系统（比如命题逻辑或不含任何特殊谓词或限制的谓词逻辑）中寻找证明，但没法为足够复杂的系统完成这一工作。大家应该看看下文附注栏内容“不可判定性”，这里讨论了一个与哥德尔不完备性定理有关的定理。不可判定性的理论让我们可以指出一些可证明计算机无法解决的具体问题。

不可判定性
逻辑学家阿兰·图灵（Alan Turing）在20世纪30年代就创立了正式的计算理论，这要比根据他的理论构造的电子计算机早出现很久。这一理论最重要的结果就是发现某些问题是不可判定的（undecidable），无论什么计算机都不能解答这些问题。
该理论最重要的特征是图灵机（Turing machine），一种由有限自动机和被分成无限个方格的纸带组成的抽象计算机。在一次移动中，图灵机可以读它的读写头（tape head）看到的那个方格中所含的字符，并根据这个字符以及图灵机的当前状态，用另一个字符代替该字符，改变图灵机的状态，并将读写头左移或右移一格。很明显，所有真实的计算机，以及其他那些研究计算机应该是怎样的数学模型，都刚好能计算图灵机可以计算的内容。因此可以把图灵机当作计算机的标准抽象模型。
不过，我们不必详细了解图灵机是怎样给图灵的理论增色的。只要拿它作为计算机模型，那种读字符输入并且只有两种可能的写语句printf("yes\n")和printf("no\n")的C语言程序，就足够了。此外，在产生任一种输出后，该程序必须终止，这样它才不会随后产生矛盾的输出。要理解，这类程序在接受某些输入后可能既不能回应“yes”也不会回应“no”，而是在循环中一直循环下去。
我们将要证明，不存在像图14-10a所示的“判定器”程序D 这样的程序。假设D 接受上述特殊类型的程序P 作为输入，在给定P 本身作为P 的输入时，若P 说“yes”，则D 说“yes”。而在给定P 作为P 的输入时，若P 说“no”或者P 没法进行任何判定，则D 说“no”。正如我们将要看到的，正是这一要求使得D 可以算出什么时候P 从不会作出使得D 无法写的判定。
不过，假设这样的D 存在，要编写如图14-10b所示“求补器”程序C 就是个简单问题了。C 是根据假设的D，通过把所有打印“no”的语句变成打印“yes”的语句，并把打印“yes”的语句变成打印“no”的语句而形成的程序。
现在可以询问，如图14-10c所示，在把C 本身提供给C 作为输入时，会发生什么？如果C 说“yes”，那么按照图14-10b表示的，C 会断言“C 针对输入C 不会说‘yes’”。如果C 说“no”，那么C 会断言“C 针对输入C 会说‘yes’”。现在就有了类似罗素悖论的矛盾，其中C 没法真实地说出“yes”和“no”。
结论就是，这样的判定器程序D 其实是不存在的。也就是说，D 可以解决的问题，也就是在给定其自身作为输入时类型限制为说“yes”或没法说“yes”（通过说“no”或什么都不说）的C语言程序，是不能由计算机解决的。它是个不可判定的问题。
自图灵最初的结果起，现已发现种类繁多的不可判定问题。例如，某给定输入是否会让给定的C语言程序进入无限循环，或两个C语言程序在接受相同输入时是否会产生相同的输出，都是不可判定的。

图 14-10　图灵构造的一部分

因此，本书并不是要以负面的声音收尾，而是要用不可判定性这一理论提醒我们，和数学一样，计算机科学也注定是挑战最优秀人才的。深入研究这一学科的学生还将了解到避免这种不可判定（而且难以驾驭）的情况所需要的科学与艺术。这些学生之后可能会加入到推进计算机发展的科学家和工程师的队伍之中。

14.10.6　习题

1. 设E₁=p，E₂=q，而且 $E_3=qr+p\overline{r}$ 。描述使{E₁,E₂}为真的模型（命题变量p、q 和r 的真值赋值）。描述E₃的模型。E₁,E₂⊧E₃是否为真？为什么？

2. ** 考虑以下谓词逻辑表达式。

a) E₁=(∀X )p(X,X )

b) E₂=(∀X )(∀Y )(p(X,Y )→p(Y,X ))

c) E₃=(∀X )(∀Y )(∀Z )((p(X,Y )AND p(Y,Z ))→p(X,Z ))

d) E₄=(∀X )(∀Y )(p(X,Y )ORp(Y,X ))

e) E₅=(∀X )(∃Y )p(X,Y )

这5个表达式中哪个表达式是由其他4个表达式蕴涵的？在各情况中，要么给出与所有可能的解释有关的论证以证明这种蕴涵，要么给出可以作为其中4个表达式的模型但不是第5个表达式的模型的某种特定解释。提示：首先可以想象谓词p 表示有向图的弧，并把各表达式看作图的属性。7.10节中的材料应该能提供一些提示，包括如何找到定义域是某图节点而且谓词p 是该图弧的合适模型，或者是如何证明为何一定存在蕴涵。不过请注意，只强调该解释是图，并不足以证明蕴涵。

3. * 设S₁和S₂是两个谓词逻辑（或者是命题逻辑，这都没关系）表达式集合，并设它们对应的模型集合分别是M₁和M₂。

(a) 证明对应表达式集合S₁∪S₂的模型集合是M₁∩M₂。

(b) 对应表达式集合S₁∩S₂的模型集合是否总是M₁∪M₂？

4. * 证明：如果(E₁ANDE₂AND…ANDE_n)→E 是重言式，就有E₁，E₂，…，E_n⊧E。

14.11　小结

大家应该从本章中了解到了如下要点。

谓词逻辑用原子公式（即带参数的谓词）作为原词操作数，并使用命题逻辑运算符以及两个量词“对所有”和“存在”。
谓词逻辑表达式中的变量受量词约束的方式，类似程序中的变量受声明约束的方式。
与命题逻辑中的真值赋值不同，在谓词逻辑中我们有一种名为“解释”的更复杂的结构。解释是由定义域、定义域上对应谓词的关系，以及从定义域对应任何自由变量的值组成的。
使得表达式集为真的解释就是该表达式集的“模型”。
谓词演算的重言式是那些对每种解释而言都能得出TRUE的表达式。尽管很多重言式是通过对命题逻辑重言式进行替换得到的，但也存在一些涉及量词的重要重言式。
每个谓词逻辑表达式都可以表示为“前束式”表达式，它是由无量词表达式最后应用量词运算符构成的。
谓词逻辑中的证明可以通过与构建命题逻辑中的证明类似的方式构建。
在重言式中用常量替换变量可得到另一个重言式，这一推理规则在证明中是很实用的，特别是在处理大量的事实和规则时。
如果表达式集{E₁,…,E_n}的任一模型同时也是表达式E的模型，则该表达式集“蕴涵”表达式E。如果E₁，…，E_n蕴涵E，在给定E₁，…，E_n作为前提时就把E视为“真”。
哥德尔的定义说明了，如果我们用描述数论（即非负整数的算术）的表达式作为前提，那么对任何证明系统而言，都存在一些由前提蕴涵但不能通过前提证明的表达式。
图灵的定理描述了“图灵机”这种正式的计算机模型，并表示存在不能由计算机解决的问题。

14.12　参考文献

12.14节中引用过的介绍逻辑的书籍，包括Enderton [1972]、Mendelson [1987]、Lewis and Papadimitriou [1981]，以及Manna and Waldinger [1990]，也涵盖了有关谓词逻辑的内容。

哥德尔的不完备性定理出现在Gödel [1931]中。图灵有关不可判定性的论文是Turing [1936]。

Gödel, K. [1931]. “Uber formal unentscheidbare satze der Principia Mathematica und verwander systeme,” Monatschefte fur Mathematik und Physik 38, pp. 173–198.

Turing, A. M. [1936]. “On computable numbers with an application to the entscheidungsproblem,” Proc. London Math. Soc. 2:42, pp. 230–265.

第 14 章 谓词逻辑

14.1 本章主要内容

14.2 谓词

14.2.1 原子公式

14.2.2 常量和变量的区分

示例 14.1

14.2.3 习题

14.3 逻辑表达式

14.3.1 文字

示例 14.2

14.3.2 逻辑表达式

示例 14.3

14.3.3 其他术语

14.3.4 习题

14.4 量词

示例 14.4

14.4.1 逻辑表达式的递归定义

14.4.2 运算符的优先级

示例 14.5

示例 14.6

14.4.3 约束变量和自由变量

示例 14.7

示例 14.8

示例 14.9

14.4.4 习题

14.5 解释

示例 14.10

14.5.1 表达式的含义

示例 14.11

示例 14.12

14.5.2 习题

14.6 重言式

示例 14.13

14.6.1 替换原则

14.6.2 表达式的等价