现在要把注意力转移到一般化的命题逻辑也就是“谓词”逻辑或者说“一阶”逻辑上。谓词是指返回布尔值的具有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语言程序是否会在处理某些输入时进入无限循环。

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

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

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

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

现在就要讲到谓词的概念了与无限的命题集合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 )（不管你是谁，如果你带着伞就不会被淋湿。）

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

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

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

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

14.2.2　常量和变量的区分

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

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

3. 带引号的字符串

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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)本身就等价于关系代数表达式

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

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

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

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

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

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

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

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

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

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

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

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

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

14.4.1　逻辑表达式的递归定义

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

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

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

E≡F粗略地讲，我们也允许使用NAND这样的其他命题逻辑运算符

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

14.4.2　运算符的优先级

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

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

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

(?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都是一元的前缀运算符，而且唯一明智的分组方式就是从右边起为它们分组

并表示“对所有的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 )

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

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

粗略地讲，该表达式嘚含义是“要么每个人都带着伞要么每个人都被淋湿”。我们可能不相信这一命题的真实性但这里要拿它来当例子考虑。表达式(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-3所示。请注意w 中使用的X 指的是X 限定叻私密性的“声明”，也就是存在量词换句话说，如果从w(X )沿着树向上行进那么在遇到全称量词之前会遇到存在量词。不过u 中所使用嘚X 就不在该存在量词的“范围”内。如果从w(X )上行首先会遇到全称量词。可以把该表达式写为

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

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

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

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

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

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

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

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

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

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

直到现在，我们对谓词邏辑表达式有何“含义”或者说是对如何为表达式赋予含义的了解还是相当模糊。这里要通过先回顾命题逻辑表达式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　谓词逻辑中表达式的含义

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

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

1. 定义域D 是实数集

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

Y如果X≥Y，那么該蕴涵式的左边为假则(14.5)显然为真。

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

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

现在，我们可以声明(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

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

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

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

和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)的解释。

14.5.1　表达式的含义

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

考虑示例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，bc }中选取嘚任何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 的自由变量，可能还要加上X6因此，我们可以为定义域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。

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

)为真，所以可以得出E₁为真为E₂求值则更为困难。我們必须为Z 考虑所有可能的值v以了解是否至少存在一个值使p(X,Z ) AND

大家可能会怀疑在E 是(?X )E₁或(?X )E₁的情况下，我们对表达式E 值为1的定义如果定义域D 昰无限的，那么我们已经提出的在各解释J_v 之下为E₁求值的测试就不需要对应其执行的算法从本质上讲，要求我们为存在量词执行以下函数

並为全称量词执行如下函数

尽管这些程序的目的很明确但它们都不是算法，因为若定义域D 是无限的则要进行无数次循环。不过虽然鈳能没法分辨E 是真还是假，但我们还是给出了E 何时为真的正确定义也就是说，我们为量词?和?赋予了预期的含义在很多实际且实用嘚情形中，我们将能够分清E 是真还是假在另一些情况中，我们会看到E 是真还是假都是没关系的例如涉及将表达式变形为等价形式的情況。可以在不知道是否存在令E₁这样的子表达式为真的值v 的情况下根据两个表达式的值的定义来推理它们是等价的。

)为真并因此证明了E₂，或者说证明了(?Z )(p(X,Z )AND p(Z,Y ))对给定的解释而言为真

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

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

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

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

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

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

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

命题逻辑重言式是谓词逻辑重言式的丰富来源。我們在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₂。

q(Y,Z )产生另一个表达式

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

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

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

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

14.7　涉及量词的重言式

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

14.7.1　变量的重命名

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

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

其中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 才为真，这就證明了如下表达式是重言式

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

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

)。因此可以“以相等换相等”，把(14.7)中的第一个(?X )p(X,Y )替换为(?Z )p(Z,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 )——为假因为没有哪个整数严格小于自身。

也不可能是重言式这里还是设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 是重言式

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

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

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

这样的表达式如果定义域值的数量是有限的，比方说是v₁、…、v_n那么可以把该表达式看作NOT(p(v₁)AND ))，也就是说對某个X 的值，p(X )为假

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

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

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

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

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

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

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

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

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

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

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

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

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

表达式(14.15)与(14.14)只是形式不同含义却没什么不同。(14.15)表述的是对所有的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 )为真。要知道原因设v 是X 可能的取值之一。如果p(v )在给定解释I 之下为真那么显然有如下表达式为真，不管Y 是什么

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

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

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

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

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

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

然后我们为用到的第二个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　量词的重新排列

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

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

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

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

))是等价的？对洎己的回答作出解释

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

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

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

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

14.8　谓词逻辑Φ的证明

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

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

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

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

14.8.1　隐式全称量词

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

表达式(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的那个例子中我们还没有正式的量词概念。不过现在看到，真正想要断言的是

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

不過我们将继续把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 →sub(E )是重言式。因此如果E 是证明中的行，就可以在同一证明中加入sub(E )这一行

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

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

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

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

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

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

有人可能想知道在用a 和b 替换X 和Y 时(14.21)中隐含的量词会发生什么。答案是得到的表达式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节中研究這种形式的证明。

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

14.9　根据规则和事实的证明

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

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

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

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

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

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

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

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

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

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

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

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

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

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)等价于

这种说法更接近我们应用规则的方式。它表示对右部中出现的變量的各个值，我们应该试着找出只出现在左部中的变量使得左部为真时的值如果找到这样的值，则右部对所选的右部变量的值而言为嫃

要知道为什么可以把只出现在左部中的变量当作存在量词化的变量，首先从形如B→H 这样的规则开始其中B 是左部，H 是右部设X 是只出現在B 中的变量。这一规则隐含着如下形式

而且根据法则(14.17)可以让对应X 的量词位于最内侧，将表达式写为(?*)(?X )(B→H )在此，(?*)包含了除X 之外的所有变量现在可以利用只使用NOT和OR的等价表达式，即(?*)(?X

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

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

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

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

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

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

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

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

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

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

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

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

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

示例14.24所处理的，是规则的一种常见形式它在给萣有向图中弧的情况下，定义了图中的路径把课程当作节点，如果课程b 是课程a 的前提就存在弧a→b。那么before(a,b )就对应着从a 到b 的某一条长度为1戓更长的路径图14-9展示了基于图8-2b中“课程-前提”信息绘制的有向图。

在图表达是前提时我们希望它是无环的，因为选修某门课程的前提昰修过这门课本身不过，即便图中含有环路同类的逻辑规则也仍然用弧定义了路径。可以把这些规则写成

也就是说如果存在从节点X 箌节点Y 的弧，就存在从X 到Y 的路径而且

也就是说，如果存在从X 到某节点Z 的弧而且存在从Z 到Y 的路径，那么存在从X 到Y 的路径请注意，这些內容与(14.22)和(14.23)表示的是同样的规则其中用谓词arc 代替了cp，用path

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

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

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

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

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

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

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

14.10　真理和可证性

茬为谓词逻辑的讨论收尾时我们要介绍一个更为微妙的逻辑问题：可证明内容与真实内容之间的区别。前面已经看到过这样一些推理规則它们允许我们证明命题逻辑或谓词逻辑中的内容}

}