第 14 章 谓词逻辑

第 14 章 谓词逻辑

现在要把注意力转移到一般化的命题逻辑,也就是“谓词”逻辑或者说“一阶”逻辑上。谓词是指返回布尔值的具有0个或更多变量的函数。因此,谓词可能有时为真有时为假,这取决于其参数的值。例如,我们将看到csg (C,S,G )这样的谓词逻辑原子操作数。其中,csg 是谓词名,而CSG 则是参数。可以将该表达式视作图8-1中数据库关系“课程-学号-成绩”的逻辑表示。只要CSG 满足学号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个前提,或者说我们假设为真的表达式:ru(“如果天在下雨,那么乔伊带着伞”)、u\to\overline{w}(“如果乔伊带伞了,那么他不会被淋湿”),以及\overline{r}\to\overline{w}(“如果没有下雨,乔伊不会被淋湿”)。

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

ruJoeu_{joe}\to\overline{w}_{joe}\overline{r}\to\overline{w}_{joe}

如果定义命题uMary 表示玛丽带着她的伞,并定义wMary 表示玛丽被淋湿,那么就有了一组类似的前提:

ruMaryu_{Mary}\to\overline{w}_{Mary}\overline{r}\to\overline{w}_{Mary}

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

ruXu_X\to\overline{w}_X\overline{r}\to\overline{w}_X

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

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

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

1. ru(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 )可以被视作在说:对变量CSG,学号为S 的学生选修了课程C,并得到了成绩G。换句话说,当我们用常量c 代替C,用s 代替S,并用g 代替G 时,当且仅当学号为s 的学生选修了课程c 并取得成绩gcsg (c,s,h)的值为TRUE

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

14.2.3 习题

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

(a) CS205

(b) cs205

(c) 205

(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章中讨论过的ANDORNOT、→和≡运算符,以及其他的逻辑连接符。而在下一节中,我们会介绍“量词”,也就是可以在谓词逻辑中用来构建表达式,但在命题逻辑中没有类比物的运算符。

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

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

示例 14.3

假设有谓词csgsnap,它们分别可以解释为第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"(CSGSNAP))

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

14.4 量词

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

rw (“乔伊”)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 )就表示“对所有的XX 都带着伞”。一般而言,对任何逻辑表达式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 为空(即对所有Xw(X )都为假),要么S 不为空(也就是,存在某个Y 使得w(Y )为真)。

14.4.1 逻辑表达式的递归定义

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

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

归纳。如果EF 是逻辑表达式,那么以下表达式也是逻辑表达式。

1. NOT EE AND FE OR FEFEF。粗略地讲,我们也允许使用NAND这样的其他命题逻辑运算符。

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

14.4.2 运算符的优先级

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

示例 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 )解释为“XY”,那么(∀X)(∃Y)loves(X,Y)就表示“每个人都爱某个人”,也就是说,对每个个体X,至少存在一个个体YX 所爱的。另一方面(∃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 )为真的XY 的取值对。

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,而EF 之外的部分所使用的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 引用了不同的“声明”,而且它们之