第8章 一阶逻辑

第8章 一阶逻辑

我们注意到世界幸福地拥有着许许多多的对象，对象之间可能存在联系，我们尽力对它们进行推理。

第7章讨论了用基于知识的 agent 表示它所处的世界并推理将要采取的行动。我们把命题逻辑作为表示语言，因为它足以阐述逻辑和基于知识的 agent 的基本概念。不幸的是，命题逻辑是一种表达能力很弱的语言，无法以简洁的方式表示复杂环境的知识。本章考察一阶逻辑 $ ^{1} $，它具有丰富的表达能力，可以表示大量常识知识。它还包含或形成了很多其他表示语言的基础，已经被深入研究了几十年。8.1 节讨论一般的表示语言；8.2 节涵盖了一阶逻辑的语法和语义；8.3 节和8.4 节说明了一阶逻辑在简单表示中的运用。

8.1 重温表示

本节讨论表示语言的本质。我们的讨论将引出一阶逻辑的发展，它是一个比第7章所介绍的命题逻辑表达能力更强的语言。我们将着眼于命题逻辑和其他类型的语言以便了解这些语言能做什么不能做什么。我们的讨论有些粗略，把几个世纪的思想、试验和错误浓缩为几段文字。

程序设计语言（如 C++、Java 或 Lisp）是到目前为止常用的形式语言中最大的一类。程序本身在直接的意义下表示的是计算过程。程序中的数据结构可以表示事实；例如，程序可以用 $ 4 \times 4 $ 数组表示 Wumpus 世界。那么，程序设计语言的语句 World[2,2] ← Pit 是加入断言[2,2]有陷阱的很自然的方式（这样的表示可能被认为是专门的；数据库系统的精确开发提供了一种更通用的、独立于领域的方法来存储和检索事实）。程序设计语言缺乏的是从其他事实推导出其他事实的通用机制；数据结构的每次更新都是通过领域特定的过程来完成，该过程的细节是由程序员根据他或她自己拥有的关于该领域的知识得出的。这种过程性方法可以和命题逻辑的描述性本质相对，知识和推理是分开的，而且推理完全独立于领域。

程序（以及数据库）中的数据结构的第二个缺点是缺乏任何简便的表述方式，例如，“[2,2]或[3,1]中有一个陷阱”或者“如果Wumpus在[1,1]，那么它不在[2,2]中”。程序可以为每个变量保存一个单独的值，而且某些系统中允许该值是“未知的”，但是它们缺乏处理不完全信息所需的表达能力。

命题逻辑是一种描述性语言，因为它的语义是基于语句和可能世界之间的真值关系。它有充分的表达能力，可以采用析取式和否定式来处理不完全信息。命题逻辑所拥有的第

三种特性在表示语言中很受欢迎，即合成性。在合成性语言中，语句的含义是它的各部分含义的一个函数。例如，“ $ S_{1,4} \wedge S_{1,2} $”与“ $ S_{1,4} $”和“ $ S_{1,2} $”的含义有关。如果 $ S_{1,4} $表示[1,4]有臭气， $ S_{1,2} $表示[1,2]有臭气，而 $ S_{1,4} \wedge S_{1,2} $却表示法国和波兰在上周的冰球资格赛中战成1比1，这将是一件非常怪异的事情。显然，非合成性使得推理系统更加困难。

正如第7章所述，命题逻辑缺乏足够的表达能力，因而无法简洁地描述有很多个对象的环境。例如，我们不得不单独为每个方格写一个关于微风和陷阱的规则，如：

$$ B_{1,1}\Leftrightarrow(P_{1,2}\land P_{2,1}) $$

另一方面，用自然语言一劳永逸地表述看来是很容易的，“与陷阱相邻的方格有微风。”自然语言的语法和语义使得其能够简洁地对环境进行描述。

8.1.1 思维语言

自然语言（如英语或西班牙语）确实具有非常强大的表达能力。我们几乎全部用自然语言来写作这整本书，间或使用其他语言（包括逻辑、数学和图表语言）。语言学和语言学中的传统是把自然语言本质上视为一种描述性知识表示语言。如果我们能够总结自然语言的法则，就能够应用在表示和推理系统中，从无数的自然语言描述的内容中获益。

自然语言的现代观点认为它是交流的媒介而不是单纯的表示。当某人指点着说：“看！”听众便明白，比如说，超人最终在屋顶上现身了。我们其实并不认为语句“看！”表示了该事实。所以，语句的含义取决于语句本身以及说出该语句时的上下文。显然，人们无法在知识库中存储诸如“看！”这样的语句，同时期望在没有同时保存上下文的情况下复原它的含义——这就带来了上下文本身如何表示的问题。自然语言存在歧义性的困扰，歧义性是表示语言的一类典型问题。正如Pinker（1995）指出，“当人们考虑Spring时，他们显然没有感到困扰，他们到底是在考虑一个季节还是某个发出啵嘤（弹簧突然弹开或振动时发出的声音）响声的事物——如果一个词语对应于两种含义，那么，这些含义就不能是词语”。

著名的 Sapir-Whorf 假说声称我们所说的语言深刻地影响着人们对世界的理解。Whorf（1956）写道：“我们切开本质，将它组织成概念，归因于意义，这很大程度上是因为我们是协议的一方——在我们的言语通信中贯穿始终的协议，并以我们的语言编制成法典。”显然不同的语言社会以不同的方式分离世界。法语中有两个词“chaise”和“fauteuil”，在英语中只用一个词对应：“chair”。但讲英语的人很容易识别出“fauteuil”并给它一个名字——大概是“open-arm chair”——所以语言当真是不同的吗？Whorf 主要依赖于本能和推断，但是近期我们确实得到了人类学、心理学和神经学研究的真实数据。

例如，你是否记住了8.1节是以下面哪个句子开始的吗？

“本节讨论表示语言的本质……”

“本节将涵盖知识表示语言的主题”

Wanner（1974）做了类似实验发现，受试对象在这种测试中做出正确选择的概率处于随机水平——大约为50%——而记住他们所读内容，准确率可达到90%。这暗示着人们对词语进行处理进而形成某种非言语表示。

更有意思的是语言中完成缺少某个概念。讲澳大利亚土著语言 Guugu Yimithirr 的人没有词语可以表达相对方向，如前、后、左或右。他们使用绝对方向，例如，“我的北胳膊有

点痛”。语言上的不同也导致了行为上的不同：Guugu Yimithirr 人更精于在开放地势中导航，而讲英语的人则擅长将叉子放在盘子的右边。

语言通过一些语法特征，如名词的性，影响到思维。例如，“bridge”是西班牙语中是男性，在德语则是女性。Boroditsky（2003）要求选择英语形容词来描述一幅特定的桥的照片。讲西班牙语的人选择了大的、危险的、强建的和参天的，而讲德语的人则选择了美丽的、优雅的、脆弱的和苗条的。词语像锚点一样影响着我们对世界的感知。Loftus和Palmer（1974）给出了汽车事故的视频实验。问题“车相碰时的车速有多快”的回答平均值是每小时32英里，把“相碰”换成相撞，同样的视频同样的车，回答的平均车速则为每小时41英里。

在使用 CNF 的一阶逻辑推理系统中，可以看出语言形 “﹁(A∨B)” 和 “﹁A∧﹣B” 是相同的，因为两个语句具有相同的 CNF 范式。对人脑能这样做吗？不久之前答案还是“不”，但现在的回答是“可能”。Mitchell 等人（2008）将测试者放入 fMRI（功能磁共振成像）机器，向他们展示一些词语如 “celery”，记录下他们的大脑成像。研究人员因而可以训练计算机程序从大脑成像来猜测测试者看到了什么词语。给出两个选择（如 “celery” 和 “airplane”），系统猜测的准确率为 77%。即使是它从未见过的 fMRI 成像，它猜测的准确率也高于随机水平。这类研究工作还刚刚起步，但 fMRI（和其他成像技术）如颅内电（Sahin 等人，2009）将为我们理解人类知识表示提供更具体的思路。

从形式逻辑的角度看，用两种方法来表示同样的知识应该没有不同；不论从哪种表示出发应该都推导出相同的结论。然而在实践中，一种表示可能要求得出结论的步骤数要少，这意味着资源有限的推理器用一种表示能够导出结论，而另一种不能。对于非推理性任务，如从经验中学习，结论严重依赖于所使用的表示形式。第18章中我们将看到学习算法考虑两种可能的世界理论，两者都与数据相容，打破这种僵局的最常见的方法是选择最简洁的理论——这依赖于表示理论的语言。所以，语言对思维的影响对试图学习的任何agent来言都不可避免。

8.1.2 结合形式语言和自然语言的优势

我们采用命题逻辑的基础——即一种描述式的、上下文无关且无歧义性的合成语义——并在这一基础上，借用自然语言的表达思想，同时避开它的缺点，构造出一种更具表达能力的逻辑。我们观察自然语言的语法，最明显的元素是指代对象的名词和名词短语（方格、陷阱、Wumpus）以及表示对象之间关系的动词和动词短语（是有微风的、相邻、射击）。有些关系是函数——在该关系中，对于给定“输入”，只输出一个“值”。很容易罗列出对象、关系和函数的实例：

对象：人们、房子、数字、理论、Ronald McDonald、颜色、棒球比赛、战争、世纪……

● 关系：可以是一元关系或称属性，诸如：红色的、圆的、伪造的、质数、多楼层的……也可以是更常见的n元关系，诸如：是…的哥哥、比…大、在…里面、是…的一部分、有…颜色、在…之后发生、拥有、在…之间、……。

● 函数：…的父亲、最好的朋友、…的第三局、比…多一个、…的开始、……

实际上，可以认为几乎每条断言都涉及对象和属性或者关系。一些例子如下：

“1加2等于3。”

对象：1、2、3、1加2；关系：等于；函数：加（“1加2”是通过将“加”函数应用于对象“1”和“2”而得到的对象的名称。“3”是这一对象的另一个名称）。

“与 Wumpus 相邻的方格是有臭味的。”

对象：Wumpus、方格；属性：有臭味的；关系：相邻。

“邪恶的 King John 于 1200 年统治英格兰。”

对象：John、英格兰、1200；关系：统治；属性：邪恶的、王。

一阶逻辑语言是围绕对象和关系建立起来的，将在下一节讨论它的语法和语义。它在数学、哲学和人工智能中的地位十分重要，确切原因是这些领域——实际上，人类生活的每一天的大部分——对处理对象以及对象之间的关系是很有用的。一阶逻辑还可以表达关于全域中某些或全部对象的事实。这使得人们可以表示通用规律或者规则，如语句“与Wumpus相邻的方格有臭味”。

命题逻辑和一阶逻辑之间最根本的区别在于每种语言所给出的本体论约定——即关于现实本质的假设不同。从数学上说，这种约定用形式模型的本质来表达，模型中定义的是语句的真值。例如，命题逻辑假定世界中的事实要么成立要么不成立。每个事实只能处于真或假两种状态之一，每个模型对每个命题符号赋值 true 或 false（见 7.4.2 节） $ ^{1} $。一阶逻辑的假设更多；即，世界由对象构成，对象之间的某种关系或者成立或者不成立。相应的形式模型也比命题逻辑的要更加复杂。专用的逻辑需要更进一步的本体论约定；例如，时态逻辑假定，事实在特定时间成立而且时间（可能是时间点或者时间区间）是有序的。因此，专用逻辑给予特定对象（以及关于它们的公理）逻辑中的“头等”状态，而不是在知识库中对它们进行简单定义。高阶逻辑把一阶逻辑中的关系和函数本身也视为对象。这允许人们对所有的关系做出断言——例如，人们可以定义什么样的关系是传递的。与多数专用逻辑不同，高阶逻辑比一阶逻辑表达能力更强，这一点表现在一些高阶逻辑语句无法用有限数目的一阶逻辑语句来表达。

逻辑还具备认识论本质特点——根据事实所允许的知识的可能状态。在命题逻辑和一阶逻辑中，一条语句代表一个事实，agent或是相信语句为真、或是相信其为假，也可以没有任何意见。因此这些逻辑对于任何语句具有三个可能的知识状态。另一方面，采用概率论的系统可以有从0（完全不相信）到1（完全相信）的可信度 $ ^{2} $。例如，概率的Wumpus世界agent相信Wumpus位于[1,3]的概率是0.75。图8.1总结了5种不同逻辑的本体论和认识论的约定：

下一节将深入讨论一阶逻辑。正如一个物理系的学生要熟知数学，研究人工智能的学生要能够处理逻辑表示。另一方面，同样重要的是不要太关注于特定逻辑表示的细节——形式语言的版本太多。要始终关注的是如何使用语言得到简明的表示以及如何利用语义得到可靠的推理过程。

8.2 一阶逻辑的语法和语义

在本节开始详细讨论一阶逻辑表示以反应其在对象和关系上的本体论约定。接着介绍一阶逻辑语言的多种元素及其语义。

8.2.1 一阶逻辑的模型

回顾第7章，逻辑语言的模型是组成可能世界的形式结构。每个模型连接的是逻辑语句的词汇和可能世界中的元素，由此可以确定任一语句的真值。那么，命题逻辑连接的是命题符号和预定义的相应真值。一阶逻辑的模型更有趣。首先，它们包含对象！模型的域是它所包含的对象或域元素的集合。要求域不为空——每个可能世界必须包含至少一个对象。（习题8.7对空世界进行了讨论。）数学上说，这些对象是什么无关紧要——紧要的是在每个特定模型中有多少对象——但出于教学目的我们将举一个具体例子。图8.2显示了一个含有5个对象的模型：1189年到1199年间在位的英格兰国王Richard the Lionheart；他的弟弟，the evil King John从1199年到1215年统治英格兰；Richard和John的左腿；一个王冠（crown）。

模型中的对象可能以多种方式相互关联。图中 Richard 和 John 是兄弟。形式化地说，关系只是相互关联的对象的元组集合（元组是以固定顺序排列并用尖括号括起来的一组对象）。因此模型中的兄弟关系是集合：

{〈Richard the Lionheart, King John〉,〈King John, Richard the Lionheart〉}(8.1)

（这里直接用英文名字来命名对象，如果愿意可以随意替换名称）王冠在 King John 的头上，因此关系 “在…的头上” 只包含一个元组〈the crown，King John〉。“兄弟”（brother）和 “在…头上”（on head）关系都是二元关系——即，这些关系关联一组对象。该模型还包括一元关系，或称属性：Richard 和 John 二者的 “人”（person）属性都为真；只有 John 的 “国王”（king）属性为真（大概是因为在这个时候 Richard 已经死亡）；而且只有王冠的 “王冠”（crown）属性为真。

有些类型的关系最好处理成函数，即，对给定的对象与正好一个对象以这种方式相关联。例如，每个人都有一条左腿，因此模型中的一元“左腿”函数包含如下映射：

$$ \begin{aligned}&\langle Richard~the~Lionheart\rangle\rightarrow Richard 的左腿 \\\ &\langle King~John\rangle\rightarrow John 的左腿 \end{aligned} $$

严格地说，一阶逻辑中的模型要求全函数，即每个输入元组必须有一个结果值。因此，王冠必须有一条左腿，每条左腿也不例外。一种解决这一棘手问题的技术方法是：附加一个“不可见”对象，该对象是每个没有左腿的事物的左腿，包括左腿本身。幸运的是，只要人们不对没有左腿的事物提出任何关于左腿的断言，这种技术性处理就无关紧要了。

至此，我们介绍了一阶逻辑主流模型中的元素。下面讨论模型中的必要部分，即逻辑语句中的词汇和这些元素的链接。

8.2.2 符号和解释

现在考虑语言的语法。心急的读者可以从图8.3中得到一阶逻辑形式语法的完整描述。

一阶逻辑的基本句法元素是表示对象、关系和函数的符号。因此，这些符号分为三类：表示对象的常量符号；表示关系的谓词符号；表示函数的函词。按照惯例将这些符号的起始字母都大写。例如，我们可以采用常量符号 Richard 和 John；谓词符号 Brother、OnHead、Person、King 和 Crown；函词 LeftLeg。而对于命题符号，名称的选择完全取决于用户自己。每个谓词和函词还伴随着确定参数个数的元数。

命题逻辑中，每个模型必须给出足够信息来确定语句的真值为真还是为假。因此，除了对象、关系和函数，每个模型还包括规范这些常量、谓词和函词的解释。上述实例的一个可能解释——我们将称之为预期解释——如下所示：

Richard 指代 Richard the Lionheart, John 指代邪恶 King John.

Brother 指代兄弟关系，即公式（8.1）中给出的对象元组集合；OnHead 指代在王冠和 King John 之间成立的“在…头上”关系；Person、King 和 Crown 分别指代人、国王和王冠的对象集。

LeftLeg 指代 “左腿” 函数，即公式（8.2）给出的映射。

当然，可能的解释有很多。例如，某个解释可以将 Richard 映射到王冠，而 John 映射到 King John 的左腿。模型有 5 个对象，因此仅对常数符号 Richard 和 John 就存在 25 种可

能的解释。请注意并不是所有的对象都必须有名称——如预期解释并没有对王冠和左腿命名。一个对象可能有多个名字；存在一种解释，Richard 和 John 都指代王冠 $ ^{1} $。如果你觉得这点有些困惑，回顾命题逻辑，它可能有这样的模型，在该模型中 Cloudy（多云）和 Sunny（阳光灿烂）同时为真；消除跟我们的知识不相容的模型则是知识库的任务。

总而言之，一阶逻辑的模型包括对象集及其解释，解释将常量符号映射到对象、谓词符号映射到对象之间的关系、函词映射到对象上的函数。正如命题逻辑一样，蕴涵、有效性等都根据所有可能模型来定义。图8.4可以帮助你理解所有可能模型的含义。它说明，模型与它所包含的对象个数——从一个到无穷——以及常量到对象的映射方式相关。如果有两个常量，只有一个对象，那么两个常量都只能映射到此对象；当然，多个对象时同样可以做这样的映射。如果对象数多于常量数，有些对象会没有名字。由于可能模型的数量是无限的，通过枚举所有可能模型以检验蕴涵在一阶逻辑中是不可行的（这不同于命题逻辑）。即使对象数量有限，各种组合的数量仍然可能非常大（参见习题8.5）。图8.4如果有6个或更少的对象，会有137 506 194 466个模型。

8.2.3 项

项是指代对象的逻辑表达式。因此常量符号是项，但是用不同的符号来命名每一个对象有时并不方便。例如，在英语中，我们可能会用“King John's left leg”而不是给他的腿取名字。这就是使用函词的原因：采用 LeftLeg(John) 而不是常量符号。通常情况下，复合项由函词以及紧随其后的参数、被括号括起来的列表项组成。这一点很重要：复合项只是名称复杂。它不是“返回一个值”的“子程序调用”。没有将某个人作为输入并返回一条腿的 LeftLeg 子程序。甚至可以在没有提供 LeftLeg 定义的情况下对左腿进行推理（例如，说明规则“每人都有一条左腿”，那么推导出 John 必然有一条）。这是无法用程序设计语言中的子程序实现的。 $ ^{1} $

项的形式语义很直接。考虑项 $ f(t_1,\cdots,t_n) $。函词 $ f $指代模型中的某个函数（称为 $ F $）；参数项指代论域中的对象（称为 $ d_1,\cdots,d_n $）；作为整体的项指代函数 $ F $应用于 $ d_1,\cdots,d_n $得到的值所对应的对象。例如，假定 $ LeftLeg $函词指代公式(8.2)所示的函数，而 $ John $指代 $ King $ John，那么 $ LeftLeg(John) $指代 $ King $ John的左腿。这样，解释确定了每个项的指代。

8.2.4 原子语句

现在有了指代对象的项以及指代关系的谓词，把它们放在一起可形成陈述事实的原子语句。原子语句由谓词符号以及随后被括号括起来的列表项组成。例如，

$$ Brother(Richard,John) $$

根据前面给出的解释，它表述的意思是 Richard the Lionheart 是 King John 的兄弟 $ ^{2} $。原子语句可以使用复合项作为参数。所以，

$$ Married(Father(Richard),Mother(John)) $$

陈述的是 Richard the Lionheart 的父亲与 King John 的母亲结了婚（再次强调：在合适的解释下）。

如果谓词所指代的关系在参数所指代的对象中成立，那么原子语句在给定模型、给定的解释下为真。

8.2.5 复合语句

和命题演算的语法和语义一样，我们可以用逻辑连接词构造更复杂的语句。由逻辑连接词构成的语句。以下是在前面的解释中，图8.2给出的模型中为真的四个语句：

$$ \neg Brother(Left Leg(Richard),John) $$

Brother(Richard, John)∧Brother(John, Richard)

King(Richard)∨King(John)

¬King(Richard)⇒King(John)

8.2.6 量词

有了允许对象存在的逻辑，那么很自然地想要表达全部对象集合的属性，而不是根据名称列举对象。量词可以让我们达到这一目的。一阶逻辑有两个标准量词，称为全称量词和存在量词。

全称量词（∀）

回顾在第7章中用命题逻辑表示一般规则时遇到的困难。像“与Wumpus相邻的方格都有臭气”和“所有的国王都是人”这样的规则是一阶逻辑的基础。我们将在8.3节中讨论第一条规则。第二条规则“所有的国王都是人”写成一阶逻辑是：

$$ \forall x\;King(x)\Rightarrow Person(x) $$

∀通常读为“对于所有的…”。（请记住，倒置的 A 代表“所有”。）因此，该语句表示“对于所有的 x，如果 x 是国王，那么 x 是人。”符号 x 被称为变量。按照惯例，变量用小写字母表示。变量本身是一个项，同时也可作为函数的参数——例如 $ LeftLeg(x) $。没有变量的项被称为基项（ground term）。

直观地看，语句 $ \forall x\ P $，其中 $ P $为任意逻辑表达式，表示对每个对象 $ x $， $ P $为真。更精确地说，如果 $ P $在根据给定解释构成的所有可能扩展解释下为真，则 $ \forall x\ P $在给定解释下的给定模型中为真，其中每个扩展解释给出了 $ x $所指代的域元素。

这听起来很复杂，但是它严谨地陈述了全称量词的直观含义。考虑图8.2所示的模型及相应的预期解释。我们可以有5种扩展该解释的方式：

$$ \begin{aligned}&x\rightarrow Richard the Lionheart\\&x\rightarrow King John\\&x\rightarrow Richard 的左腿 \\&x\rightarrow John 的左腿 \\&x\rightarrow 王冠 \end{aligned} $$

如果 $ King(x) \Rightarrow Person(x) $ 在 5 种扩展解释下都为真，那么在原有模型中全称量化语句 $ \forall x\, King(x) \Rightarrow Person(x) $ 为真。即，全称量化语句等价于下列 5 个断言：

$$ Richard the Lionheart 是国王 \Rightarrow Richard the Lionheart 是人 $$

$$ King\ John\ 是国王 \ \Rightarrow\ King\ John\ 是人 $$

$$ Richard 的左腿是国王 \Rightarrow Richard 的左腿是人 $$

$$ John 的左腿是国王 \Rightarrow John 的左腿是人 $$

$$ 王冠是国王 \Rightarrow 王冠是人 $$

仔细研究这个断言集，由于在模型中 King John 是唯一的国王，那么第二个语句可以断言他是人，正如所期望的。但是另外四个语句呢？它们看来对腿和王冠进行了断言。这是否是“所有国王都是人”的含义的一部分？实际上，其余四条断言在模型中都为真，但

是没有腿、王冠或者甚至 Richard 作为人的资格的断言。这是因为这些对象中都不是国王。查阅 $ \Rightarrow $的真值表（图 7.8）可以看到，只要前提为假，表达式就为真——与结论的真值无关。因此，断言全称量化语句等价于断言各蕴含句组成的整个列表，归根结底就是只需对于前提为真的对象，断言规则的结论，而对于那些前提为假的对象，无需任何断言。因此，用全称量词书写一般规则， $ \Rightarrow $的真值表定义是完美的选择。

即使是多次阅读这一段落的读者也可能会犯的常见错误是，用合取词代替蕴含词。语句

$$ \forall x\;King(x)\land Person(x) $$

等价于断言

Richard the Lionheart 是国王 ∧ Richard the Lionheart 是人

King John 是国王 ∧ King John 是人

Richard 的左腿是国王 ∧ Richard 的左腿是人

等等。显然，这并不是我们要表达的。

存在量词（3）

全称量词对每一个对象进行陈述。类似地，我们可以通过使用存在量词对论域中的某些对象进行陈述而无须对它们命名。例如，表示有王冠在 King John 的头上，可以写为：

$$ \exists x\;Crown(x)\land OnHead(x,John) $$

$ \exists x $ 读为“存在 x，使得…” 或 “对于某个 $ x\cdots $”。

直观地，语句 $ \exists x $ P表示至少存在一个对象x，使得P为真。更精确地说，如果至少一个x赋给某个论域元素的扩展解释时P为真，那么 $ \exists x $P在该解释下的给定模型中为真。这就是说下列语句至少有一个为真：

Richard the Lionheart 是王冠 ∧ Richard the Lionheart 在 John 的头上

King John 是王冠 ∧ King John 在 John 的头上

Richard 的左腿是王冠 $ \wedge $ Richard 的左腿在 John 的头上

John 的左腿是王冠 ∧ John 的左腿在 John 的头上

王冠是王冠 ∧ 王冠在 John 的头上

第5条断言在模型中为真，因此原先的存在量化语句在模型中为真。需要注意的是，根据定义，在King John戴着两个王冠的模型中该语句也为真。这和原始语句“King John的头上有一个王冠”是相容的。 $ ^{1} $

正如⇒看来是在使用∀时的自然连接词，∧是使用∃时的自然连接词。在前一节的实例中，将∧作为∀的主连接词使得陈述过强；而在∃句中使用⇒通常会使陈述过弱。考虑下述语句：

$$ \exists x\;Crown(x)\Rightarrow OnHead(x,John) $$

表面上，这看起来很像是语句的一个合理翻译。对其赋予语义，在下列断言中至少有一个为真：

Richard the Lionheart 是王冠 $ \Rightarrow $ Richard the Lionheart 在 John 的头上

$$ King\ John\ 是 王冠 \ \Rightarrow\ King\ John\ 在 \ John\ 的 头 上 $$

$$ Richard 的左腿是王冠 \Rightarrow Richard 的左腿在 John 的头上 $$

等等。现在如果前提和结论都为真，或者如果它的前提为假，那么整个蕴含式为真。因此，由于 Richard 不是王冠，所以第一条断言为真，从而该存在量化语句得到了满足。所以，如果某个对象不能满足前提，存在量化蕴含语句就为真；因此这样的句子并没有真正表述信息。

嵌套量词

采用多个量词可以表示更复杂的语句。最简单的情况是同一种量词。例如，“兄弟是同胞”可表示为：

$$ \forall x\;\forall y\;Brother(x,y)\Rightarrow Sibling(x,y) $$

同一种多个连续量词可以写成有几个变量的单个量词。例如，为了说明同胞关系是对称关系，我们可以写出：

$$ \forall x,y{S i b l i n}g(x,y)\leftrightarrow{S i b l i n}g(y,x) $$

其他情况中可能会有混合量词。“每个人都会爱上某人”的意思是，对于每个人，都会存在此人爱的人：

$$ \forall x\exists y~L o v e s(x,y) $$

另一方面，要说“存在某人被每个人爱”，我们写为：

$$ \exists y\,\forall x~Loves(x,y) $$

由此看出量词的顺序很重要。使用括号将更加明确。 $ \forall x $ ( $ \exists y $ Loves(x, y))表示每个人有一个特殊属性，即爱某人的属性。另一方面， $ \exists y $ ( $ \forall x $ Loves(x, y))表示世界上某人有一个特殊属性，即他被每个人喜爱的属性。

有时两个量词会采用相同的变量名称，这会产生某些混淆。考虑如下语句：

$$ \forall x\;[Crown(x)\;\lor\;(\exists x\;Brother(Richard,x))] $$

在此，Brother(Richard, x)中的x是被存在量化的。规则是变量属于引用该变量的最内层的量词；且不再属于其他任何量词。另一种考虑方式是： $ \exists x $ Brother(Richard, x)是关于Richard（他有一个兄弟）而不是关于x的语句；因而将 $ \forall x $置于该语句外层没有作用。该语句的一个完全等价的写法是 $ \exists z $ Brother(Richard, z)。由于这是造成混淆的源头，因此在嵌套量词中总是采用不同的变量。

$ \forall $和 $ \exists $之间的关联

∀和∃两个量词通过否定词紧密相关。断言每个人都不喜欢欧洲防风草等同于断言不存在某个喜欢欧洲防风草的人；反之亦然：

$$ \forall x\neg Likes(x,Parsnips)\qquad 等价于 \qquad\neg\exists x~Likes(x,Parsnips) $$

我们可以更进一步，“每个人都喜欢冰淇淋”意味着没有人不喜欢冰淇淋：

$$ \forall x~Likes(x,IceCream)\qquad 等价于 \qquad\neg\exists x\neg Likes(x,IceCream) $$

因为 $ \forall $实际是论域上所有对象的合取式，而 $ \exists $是析取式，所以它们遵循 De Morgan 定律就不奇怪了。用于量化语句和非量化语句的 De Morgan 定律如下所示：

$$ \begin{array}{r l r}{\forall x\neg P}&{{}\equiv}&{\neg\exists x\;P}\\ {\neg\forall x\;P}&{{}\equiv}&{\exists x\neg P}\end{array}\quad\begin{array}{r l}{\neg(P\lor Q)}&{\equiv\neg P\land\neg Q}\\ {\neg(P\land Q)}&{\equiv\neg P\lor\neg Q}\end{array} $$

$$ \begin{array}{r l r l r l}{\forall x\;P\;}&{{}\;\equiv\;}&{\neg\exists x\;\neg P\;}&{{}\;}&{P\land Q\;}&{{}\;\equiv\;\;\neg(\neg P\lor\neg Q)}\\ {\exists x\;P\;}&{{}\;\equiv\;}&{\neg\forall x\;\neg P\;}&{{}\;}&{P\lor Q\;}&{{}\;\equiv\;\;\neg(\neg P\land\neg Q)}\end{array} $$

因此，并不是真的同时需要 $ \forall $和 $ \exists $，正如我们并不是同时需要 $ \lor $和 $ \land $。尽管如此，语句的可读性比精简更重要，所以我们保留这两个量词。

8.2.7 等词

除了前面描述的使用谓词和项产生原子语句之外，一阶逻辑还有另一种构造原子语句的方式。可以使用等词来声明两个项指代同一个对象。例如：

$$ Father(John)=Henry $$

说明 Father(John) 指代的对象和 Henry 所指代的对象是相同的。因为解释固定了项的指代，判定等词语句的真值是个简单问题，通过检验两个项的指代是否是同一对象即可实现。

等词可以用来表述关于给定函数的事实，如同上面例子中的 Father 符号。它还可以和否定词同时使用以强调两个项不是同一对象。为了说明 Richard 至少有两个兄弟，可写为：

$$ \exists x,y\;Brother(x,Richard)\land Brother(y,Richard)\land\neg(x=y) $$

语句

$$ \exists x,y\;Brother(x,Richard)\land Brother(y,Richard) $$

则没有上述含义。特别是在图 8.2 的模型中它为真，图中 Richard 只有一个兄弟。为了理解这一点，考虑 x 和 y 都被指派为 King John 的解释。附加的 $ -(x = y) $ 排除了这样的模型。有时候用 $ x \neq y $ 作为 $ -(x = y) $ 的缩写。

8.2.8 另一种语义

继续讨论上一节的例子，假设我们相信 Richard 有两个兄弟 John 和 Geoffrey。 $ ^{1} $加入以下断言能得到这个状态吗：

$$ Brother(John,~Richard)\land Brother(Geoffrey,~Richard)? $$

不一定。首先，这个断言在 Richard 只有一个兄弟的模型中为真——还需加入 John≠ Geoffrey。其次，该语句没有排除 Richard 除了 John 和 Geoffrey 还有更多兄弟的模型。那么，“Richard 有两个兄弟 John 和 Geoffrey”的正确翻译如下：

$$ Brother(John,Richard)\land Brother(Geoffrey,Richard)\land John\not=Geoffrey $$

$$ \land\forall x~Brother(x,Richard)\Rightarrow(x=John\lor x=Geoffrey) $$

这跟相应的自然语言表述相比要累赘很多。在将知识翻译成一阶逻辑的时候直观上也很容易出错。我们能否设计一种语义使得逻辑表达更直接呢？

一种做法是数据库系统中的常见方法。首先，坚持每个常量符号指代一个确定对象——称为关键字假设。其次，假设我们不知道的所有原子语句事实上都为假——封闭世界假设。最后，使用论域闭包，指的是每个模型只包括常量符号指代的对象。在上述数据库语义下，区分于标准的一阶逻辑语义，公式8.3确实表达了Richard有两个兄弟是John和Geoffrey。

数据库语义也用于逻辑程序设计系统中，这点将在9.4.5节讨论。

对图8.4的同样情况考虑其数据库语义下的所有可能模型具有指导性。图8.5给出了一些模型，从模型中没有元组满足关系到模型中的所有元组都满足关系。两个对象有四种可能的二元组，所以满足关系的可能元组子集有 $ 2^{4}=16 $个。因此，共有16种可能模型——远比标准一阶逻辑语义的无穷模型要少很多。另一方面，数据库语义要求世界中包含的知识是有限的。

这个例子带来很重要的信息：对逻辑而言不存在“正确的”语义。上面讨论的各种语义的用处依赖于它们对我们知识的表达是否具体和直观，相应的规则推理是否简洁和自然。当明确知识库中的所有对象和事实时数据库语义很有用；而在其他情况中，这很怪异。本章中余下的部分，假设选择这种标准语义会使得表达理复杂。

8.3 运用一阶逻辑

前面已经定义了这种富于表达力的逻辑语言，现在学习如何使用它。最好是通过实例来学习。我们已经通过一些简单实例展示了逻辑语法的各个方面；本节将提供某些简单论域的更多系统化表示。在知识表示中，一个论域只是我们希望表达知识的部分世界。

从简单描述一阶知识库的 TELL/ASK 接口开始。接着讨论家庭关系、数字、集合、列表和 Wumpus 世界的论域。下节包括了一个更真实的实例（电路），第 12 章将讨论所有内容。

8.3.1 一阶逻辑的断言和查询

与命题逻辑一样，TELL 将语句添加到知识库中。这样的语句被称为断言。例如，可以断言 John 是国王，而且国王都是人：

TELL(KB, King(John))

TELL(KB, Person(Richard))

TELL(KB, $ \forall x $ King(x) $ \Rightarrow $ Person(x))

用 ASK 向知识库询问问题。例如

ASK(KB, King(John))

返回 true。用 ASK 提出的问题称为查询或目标。一般而言，被知识库逻辑蕴涵的任何查询都肯定可以得到回答。例如，已知上一段的两条断言，查询

ASK(KB, Person(John))

也应该返回 true。可以提出量化查询，如

$$ ASK(KB,\exists x Person(x)) $$

此查询的答案是 true，但是这不像我们喜欢的那样有用。这就像有人问“你是否可以告诉我现在的时间？”而你只回答“是”。如果想知道什么样的 x 使得语句为真，则需要一个不同的函数 ASKVARS，这样可以询问

$$ ASKVARS(KB,Person(x)) $$

可能得到一个答案流。在这个例子中有两个答案：{x/John}和{x/Richard}。这样的答案被称为置换或绑定表。ASKVARS 通常在只含有 Horn 子句的知识库中保留，因为在这样的知识库中查询会使变量绑定到特定的值。这不是一阶逻辑；如果知识库被告知 King(John)∨King(Richard)，对查询∃x King(x)则不存在 x 的绑定，尽管查询返回的是 true。

8.3.2 亲属关系论域

第一个实例是家庭关系论域。论域中包括诸如“Elizabeth是Charles的母亲”和“Charles是William的父亲”的事实，还包括诸如“祖母是其家长的母亲”的规则。

显然，在我们的论域对象是人。有两个一元谓词：Male 和 Female。亲属关系——家长关系、兄弟关系、婚姻关系等——用二元谓词表示：Parent、Sibling、Brother、Sister、Child、Daughter、Son、Spouse、Wife、Husband、Grandparent、Grandchild、Cousin、Aunt、Uncle。用函数来表示 Mother 和 Father，因为每个人只能有一个父亲/母亲（至少大自然是这样设计的）。

考察每个函数和谓词，按照符号定义写出我们所知道的知识。例如，母亲是指女性家长：

$$ \forall m,c{~M o t h e r}(c)=m\Leftrightarrow F e m a l e(m)\land P a r e n t(m,c) $$

丈夫则是指某人的男性配偶：

$$ \forall w,h{H u s b a n d}(h,w)\Leftrightarrow{M a l e}(h)\land{S p o u s e}(h,w) $$

女性和男性是两个不相交的集合：

$$ \forall x\;Male(x)\Leftrightarrow\neg Female(x) $$

家长和孩子是反关系：

$$ \forall p,c P a r e n t(p,c)\Leftrightarrow C h i l d(c,p) $$

祖父母是家长的家长：

$$ \forall g,c{~G r a n d p a r e n t}(g,c)\leftrightarrow\exists p{~P a r e n t}(g,p)\land{P a r e n t}(p,c) $$

同胞是某人家长的另一个孩子：

$$ \forall x,y{S i b l i n g}(x,y)\Leftrightarrow x\neq y\land\exists p{P a r e n t}(p,x)\land{P a r e n t}(p,y) $$

这样可以列出好几页，习题8.14要求你来做这项工作。

正如 7.1 节指出，每个语句都可以看作是亲属关系论域上的公理。公理通常和纯数学域联系在一起——我们很快将了解数域的一些公理——但是所有论域都需要它们。它们提供基本的事实信息，由这些信息推导出有用的结论。我们的亲属关系公理也是定义；它们形如 $ \forall x, y \, P(x, y) \Leftrightarrow \cdots \cdots $ 公理根据其他谓词，可以定义 Mother 函数以及 Husband、Male、Parent、Grandparent 和 Sibling 谓词。定义从基本谓词集合（Child, Spouse, Female）发展而

来，其他谓词根据这个基本集合进行定义。这是构造表示的一种非常自然的方法，这与通过库函数设计子程序构造软件模块的过程类似。需要注意的是，基本谓词集合不是唯一的；用 Parent、Spouse 和 Male 同样可以实现。以后会看到，在某些论域中，不存在可明确区别的基本谓词集合。

不是所有关于论域的逻辑语句都是公理。有些是定理——即，它们通过公理推导而来。例如，考虑对称的同胞关系的断言：

$$ \forall x,y\;Sibling(x,y)\leftrightarrow Sibling(y,x) $$

它是公理还是定理？实际上，它是根据定义同胞关系的公理得出的定理。如果 ASK 知识库这个语句，它应该返回 true。

从纯逻辑的观点来看，知识库只需包括公理，无需包括定理，因为定理并不增加根据知识库得出的结论集。从实用观点来看，定理可以降低生成新语句的计算成本。如果没有它们，推理系统每次都要从基本原理开始，这就像物理学家对每个新问题都要重新推导微积分规则。

不是所有的公理都是定义。有些公理提供关于谓词的更一般信息，并没有构成定义。确实，有些谓词没有完整定义，是因为我们具备的知识还不足以完全刻划它们。例如，没有显而易见的方法来完成以下语句：

$$ \forall x\;Person(x)\Leftrightarrow\cdots $$

幸运的是，一阶逻辑允许利用 Person 谓词而无需完整定义它。反而支持我们写出每个人都具有的属性或哪些属性使其成为一个人：

$$ \begin{aligned}&\forall x~Person(x)\Rightarrow\cdots\\&\forall x~\cdots\Rightarrow Person(x)\\ \end{aligned} $$

公理还可以是“普通事实”，如 Male(Jim)和 Spouse(Jim, Laura)。这样的事实构成了特定问题实例的描述，使得特定问题能够得到求解。这些问题的回答就成为由公理推导出的定理。通常，人们发现期望的答案并不是现成的——例如，从 Male(George)和 Spouse(George, Laura)，希望能够推导出 Female(Laura)；但是这无法由先前已知的公理推导得到。这表明公理不充分。习题8.8要求你提出这一公理。

8.3.3 数、集合和表

数字可能是从很小的公理内核构建出大型理论的最生动实例。这里描述自然数或非负整数的理论。用谓词 NatNum 表示是否为自然数；需要常数符号 0；还需要函词 S（后继）。Peano 公理定义了自然数和加法。 $ ^{1} $自然数的递归定义：

$$ \begin{aligned}&NatNum(0)\\&\forall n NatNum(n)\Rightarrow NatNum(S(n))\end{aligned} $$

即，0 是自然数，而且对于每个对象 n，如果 n 是自然数，那么 $ S(n) $ 是自然数。因此，自然数包括 0、 $ S(0) $、 $ S(S(0)) $ 等（读完 8.2.8 节后，你会发现这些公理还允许其他自然数；见练习 8.12），还需要一些公理来约束后继函数：

$$ \forall n\;0\ne S(n) $$

$$ \forall m,n\;m\neq n\Rightarrow S(m)\neq S(n) $$

现在用后继函数来定义加法：

$$ \forall m\ N a t N u m(m)\Longrightarrow+(0,m)=m $$

$$ \forall m,n \;N a t N u m(m)\land N a t N u m(n)\Longrightarrow+(S(m),n)=S(+(m,n)) $$

以上第一条公理表明，0加上任何自然数m得到m本身。注意二元函词+在项+（m，0）中的用法；在普通数学中，该项应该用中辍表示法写成 $ m+0 $（在一阶逻辑中采用的表示法称为前缀）。为了使这些与数字有关的语句更易于阅读，允许使用中辍表示法。也可以把 $ S(n) $写成 $ n+1 $，因此第二条公理变成：

$$ \forall m,n \;N a t N u m(m)\land N a t N u m(n)\Rightarrow(m+1)+n=(m+n)+1 $$

此公理把加法简化为反复应用后继函数。

中缀表示法的使用是含糖语法的实例。含糖语法是标准语法的扩展或缩写，它不改变语句的语义。任何使用含糖语法的语句可以“脱糖”，生成一个普通一阶逻辑的等价语句。

一旦有了加法，就可以直接定义乘法为重复做加法、定义求幂为重复做乘法、定义整数除法和余数、质数等等。因此，整个数论（包括密码学）可以从一个常数、一个函数、一个谓词和四条公理开始建立。

集合论对于数学以及常识推理也是基础（事实上，通过集合论建立数论是可能的）。我们希望能够表示单个集合，包括空集。我们需要一种方法，它可以通过把元素添加到集合中或者对集合进行合并或求交集等操作得到新集合。我们希望知道一个元素是否属于某个集合，而且能够将集合中与不在集合中的对象区分开。

使用集合论的常用词汇形成含糖语法。空集是常量，用{}表示。一元谓词 Set 判断对象是否为集合。二元谓词为 $ x \in s $（ $ x $ 是集合 $ s $ 中的一个元素）和 $ s_1 \subseteq s_2 $（集合 $ s_1 $ 是集合 $ s_2 $ 的子集，不一定是真子集）。二元函词为 $ s_1 \cap s_2 $（两个集合的交）、 $ s_1 \cup s_2 $（两个集合的并）和 $ \{x \mid s\} $（把元素 $ x $ 添加到集合 $ s $ 而产生的集合）。可能的公理集如下：

（1）集合是空集或通过将一些元素添加到集合中而构成。

$$ \forall s\;S e t(s)\Leftrightarrow(s=\{\;\}).)\lor(\exists x,s_{2}\;S e t(s_{2})\land s=\{x\mid s_{2}\}) $$

（2）空集中没有任何元素，即，空集无法再分解为更小的集合和元素。

$$ \neg\exists x,s\setminus\{x\mid s\}=\{\quad\} $$

（3）将已经存在于集合中的元素添加到该集合中，该集合无任何变化。

$$ \forall x,s x\in s\Leftrightarrow s=\{x\mid s\} $$

（4）集合的元素是那些被添加到集合中的元素。采用递归的方式来表示：x 是集合 s 的元素，当且仅当 s 等价于包含元素 y 的集合 $ s_2 $，其中 y 与 x 相同或者 x 是 $ s_2 $ 的元素。

$$ \forall x,s\;x\in s\Leftrightarrow\exists y,s_{2}\;(s=\{y\mid s_{2}\}\land(x=y\lor x\in s_{2})) $$

（5）一个集合是另一个集合的子集，当且仅当第一个集合的所有元素都是第二个集合的元素。

$$ \forall s_{1},s_{2}\;s_{1}\subseteq s_{2}\Leftrightarrow(\forall x\;x\in s_{1}\Rightarrow x\in s_{2}) $$

（6）两个集合相等当且仅当它们互为子集。

$$ \forall s_{1},s_{2}\left(s_{1}=s_{2}\right)\Leftrightarrow\left(s_{1}\subseteq s_{2}\land s_{2}\subseteq s_{1}\right) $$

（7）一个对象属于两个集合的交集，当且仅当它同时是这两个集合中的元素。

$$ \forall x,s_{1},s_{2}\quad x\in(s_{1}\cap s_{2})\quad\Leftrightarrow\quad(x\in s_{1}\;\land\;\;x\in s_{2}) $$

（8）一个对象属于两个集合的并集，当且仅当它是其中任一集合的元素。

$$ \forall x,s_{1},s_{2}\quad x\in(s_{1}\cup s_{2})\quad\Leftrightarrow\quad(x\in s_{1}\lor x\in s_{2}) $$

表与集合相似，它们的差别在于表中元素是有序的，同一个元素在表中出现不止一次。可以采用 Lisp 语言的词汇：Nil 是没有元素的表常量；Cons、Append、First 和 Rest 都是函词；Find 是谓词，在表中的功能与 Member 在集合中的类似。List? 为谓词，判断对象是否为表。和集合一样，在涉及表的逻辑语句中也经常使用含糖语法。空表用[]表示。项 Cons(x, y)写成[x | y]，其中，y 为非空表。项 Cons(x, Nil)（即只包含元素 x 的表）用[x]表示。有多个元素的列表，诸如[A, B, C]相当于嵌套项 Cons(A, Cons(B, Cons(C, Nil)))。习题 8.16 要求你列出表公理。

8.3.4 Wumpus 世界

第7章中给出了 Wumpus 世界的一些命题逻辑公理。本节介绍的一阶逻辑公理相对而言更加简洁，以更自然的方式来表达知识。

回顾 Wumpus agent 可以接收到有 5 个感知向量的情况。存储在知识库中的相应的一阶逻辑语句应同时包括感知信息以及感知时间；否则 agent 将分不清它在何时感知到了什么。我们将用整数表示时间步。一条典型的感知语句如下所示：

$$ Percept([S t e n c h,B r e e z e,G l i t t e r,N o n e,N o n e],5) $$

其中，Percept 是二元谓词，Stench 等是放在表中的常量。Wumpus 世界中的行动可以用逻辑项表示：

$$ Turn(Right),Turn(Left),Forward,Shoot,Grab,Climb $$

为了决策采取哪个行动，agent程序执行如下查询：

$$ ASKVARS(\exists{a~BestAction}(a,5)) $$

返回一个置换，如 $ \{a/Grab\} $。agent 程序把 Grab 作为将要采取的行动。原始感知数据暗示着当前状态的某些事实。例如：

$$ \begin{aligned}&\forall t,s,g,m,c~Percept([s,Breeze,g,m,c],t)\Rightarrow Breeze(t)\\&\forall t,s,b,m,c~Percept([s,b,Glitter,m,c],t)\Rightarrow Glitter(t)\\ \end{aligned} $$

等等。上述规则展示了推理过程的琐碎形式，这就是感知，将在第24章中深入讨论。注意对时间t的量化。在命题逻辑中，必须在每个时间步上都保留语句的副本。

简单的“反射”行为也可以由量化蕴含式来实现。例如，有

$$ \forall t{G l i t t e r}(t)\Rightarrow{B e s t A c t i o n}({G r a b},t) $$

根据前面给出的感知信息和规则，将得到结论 BestAction(Grab, 5)——即，需要做的行动是 Grab。

我们表示了感知和行动；现在要做的是表示环境自身。首先从对象开始。显然对象候选有方格、陷阱和 Wumpus。可以给每个方格命名——像 $ Square_{1,2} $ 等——但如果这样， $ Square_{1,2} $ 和 $ Square_{1,3} $ 相邻则成为一个要“额外”表达的事实，而每组相邻方格都需要表达事实。更好的方法是采用复合项，方格的行标和列标都用整数值表示；例如，可以用[1,2]表示 $ Square_{1,2} $。任何两个方格的相邻可以定义为：

$$ \forall x,y,a,b\quad Adjacent([x,y],[a,b])\iff $$

$$ (x=a\;\land\;\left(y=b-1\lor y=b+1\right))\;\lor\;\left(y=b\;\land\;\left(x=a-1\;\lor\;x=a+1\right)\right). $$

可以给每个陷阱命名，但是它跟方格不尽相同，这样做并不合适：没有必要去区分陷阱的不同 $ ^{1} $。简单的方法是定义一元谓词 Pit，如果方格包含陷阱，则它为真。最后，由于仅有一只 Wumpus，常量 Wumpus 和一元谓词一样好（从 Wumpus 世界的观点而言，后者可能更有价值）。

agent 的位置不断变化，我们用 At(Agent, s, t) 表示 agent 在时间 t 位于方格 s。Wumpus 的位置可以用 $ \forall t $ At(Wumpus, [2, 2], t) 表示。我们还可以声明一个对象在一个时间只能处于一个位置：

$$ \forall x,s_{1},s_{2},t\ A t(x,s_{1},t)\land A t(x,s_{2},t)\Rightarrow s_{1}=s_{2} $$

已知 agent 的当前位置，agent 可以根据当前的感知信息推导出方格的一些属性。例如，如果 agent 处于某个方格并感觉到微风，那么该方格有微风：

$$ \forall s,t\;A t(A g e n t,s,t)\;\land\;B r e e z e(t)\;\Rightarrow\;B r e e z y(s) $$

知道某个方格有微风非常有用，因为我们知道陷阱无法四处移动。请注意 Breezy 没有时间参数。

在发现哪些位置有微风（或者臭气），很重要的是发现哪些位置没有微风（或没有臭气）之后，agent 就可能推导出陷阱的位置（和 Wumpus 的位置）。在命题逻辑中每个方格都需要公理来说明这点，同样还需要公理来表明世界中的方格位置，而一阶逻辑只需一条公理：

$$ \forall s{~}B r e e z y(s)\leftrightarrow\exists r{~}A d j a c e n t(r,s){\wedge}P i t(r) $$

相似地，一阶逻辑可以对时间进行量化，因此对每个谓词只需要一个后继状态公理，无需在每个时间步都保留副本。例如，关于射箭的公理（公式7.2）变为

$$ \forall t\;HaveArrow(t+1)\Leftrightarrow(HaveArrow(t)\land\neg Action(Shoot,t)) $$

从这两个例子可以看出，一阶逻辑公式的简洁性不亚于第7章给出的自然语言描述。读者可以为agent的位置和朝向构建与此类似的公理；在这些情况中，公理的量化包括空间和时间。类似命题状态的评估，agent可以使用公理的逻辑推理跟踪那些不能直接观察到的世界轨迹。第10章将深入讨论一阶逻辑后继状态公理及其在构建规划中的应用。

8.4 一阶逻辑的知识工程

上一节举例说明了一阶逻辑在知识表示方面的应用。本节介绍知识库构造的一般过程——这被称为知识工程。知识工程师对特定领域进行调研，总结出在该领域的重要概念，构建该领域的对象和关系的形式化表示。我们以相当熟悉的电路领域为例阐述知识工程的过程，这使我们可以专注于相关的表示问题。我们所采用的方法适合于开发专用数据库，预先仔细限定了它的域，查询范围也已事先知道。而通用知识库涵盖了整个人类知识范围，它支持诸如自然语言理解等的任务，将在第10章中讨论。

8.4.1 知识工程的过程

知识工程项目在内容、范围和难度方面变化比较大，但是这些项目都包括以下步骤：

（1）确定任务。知识工程师必须刻画出知识库支持哪些问题查询，以及对于每个特定的问题可以采用哪些种类的事实。例如，Wumpus 知识库是否需要选择行动，或者它是否只需回答跟环境相关的问题？传感器事实是否需要包括当前位置？任务将决定必须表示哪些知识，从而可以将问题和解答联系起来。这一步与第2章中设计agent的PEAS过程类似。

（2）搜集相关知识。知识工程师可能是该领域的专家，或者还需要和真正的专家沟通合作以便提取专家的知识——这一过程称为知识获取。在这一阶段，还未对知识进行形式化。这一步的思路是由任务确定知识库范围，并了解该领域的工作模式。

对于由人造规则集定义的 Wumpus 世界，确定它的相关知识相对容易（然而要注意的是，Wumpus 世界的规则并没有显式给出相邻关系的定义）。对于现实领域，相关性问题可能非常难——例如，仿真 VLSI 设计的系统可能需要，也可能不需要考虑寄生电容和集肤效应。

（3）确定词汇表，包括谓词、函词和常量。也就是把重要的领域概念转换为逻辑名称。这涉及知识工程风格的很多问题。与程序设计风格一样，知识工程的风格对项目最终的成败有重大影响。例如，陷阱是表示为对象还是一元谓词？agent的朝向应该是函数或谓词吗？Wumpus的位置是否与时间相关？一旦做出了选择，它的结果就是被称为域的本体论的领域词汇表。本体论是关于存在或实体的本质的理论。本体论决定哪种事物是存在的，但并不确定它们的特定属性和相互关系。

（4）对领域通用知识编码。知识工程师对所有词汇项写出公理。（尽可能）明确给出项的含义，使得专家可以对内容进行检查。此步骤通常可以检查词汇表中的误解或者缺陷，这需要返回步骤3并迭代执行整个过程来进行修正。

（5）对特定问题实例描述编码。如果本体设计良好，那么这一步骤将容易实现。它涉及写出已经是本体的一部分的概念实例的简单原子语句。逻辑 agent 的问题实例由传感器提供，而在“不具形体的”知识库中，问题实例是由附加语句按照传统程序中输入数据的同样方式来得到。

（6）把查询提交给推理过程并获取答案。这是回报：通过推理过程对公理和与问题相关的事实进行操作，从而得出我们感兴趣的结论。

（7）知识库调试。遗憾的是查询的结果很少在第一次尝试的时候就正确。更准确地说，假定推理过程是可靠的，那么结论对于知识库的内容来说是正确的，但它可能不是用户所期望的结果。例如，如果缺少一条公理，那么有些查询可能是得不到回答的。所以需要合理的调试过程。通过调试过程关注推理链意外中止的地方，可以确定那些缺失或者描述过弱的公理。例如，如果知识库包括寻找 Wumpus 的诊断规则（见习题 8.13）：

$$ \forall s\;Smelly(s)\Rightarrow Adjacent(Home(Wumpus),s) $$

这里用的不是等价词，agent 永远也无法证明 Wumpus 的不存在。很容易识别错误的公理，因为它对世界做出了错误的陈述。例如，语句

$$ \forall x{\sf N u m O f L e g s}\;(x,4)\Rightarrow{\sf M a m m a l}(x) $$

上述语句对于爬行动物、两栖动物以及更重要的，如桌子，均不成立。可以独立于知识库中的其余内容来判断这个语句是错误的。相反，程序中的一个典型错误如下所示：

$$ offset~=position~+~1 $$

不查看余下程序而判断这条语句的正确性是不可能的，如 offset 被用于指代当前位置或当前位置之后的位置，或者 position 的值被另一个语句改变从而导致 offset 也应该被改变。

为了更好地理解这七步过程，我们以电路领域为例详细讨论实现。

8.4.2 电路领域

我们将开发本体和知识库，以便对图8.6所示的数字电路进行推理。我们将遵循知识工程的七步过程。

确定任务

有很多与数字电路相关的推理任务。最高层次是分析电路的功能。例如，图8.4的电路是否能正确地完成加法？如果所有的输入都是高位，那么门 $ A_{2} $的输出是什么？同样是感兴趣的是电路结构问题。例如，所有的门都和第一个输入端相连，得到的是什么？电路是否包含反馈回路？这些都是在这一步骤中的任务。还存在更详细的分析层次，包括定时延迟、电路面积、功耗、生产开销等相关的内容。每一层次都需要补充额外的知识。

组织相关知识

我们知道的数字电路到底是什么？就我们的目标而言，它由导线和门构成。信号从导线流到门的输入端，流经另一段导线在输出端生成一个信号。为了判断这些信号，我们需要知道门电路如何变换它的输入信号。有四种类型的门：与门、或门和异或门有两个输入端，非门则只有一个输入端。所有的门都有一个输出端。电路，跟门一样，都有输入和输出端。

对电路功能和连通性进行推理，无需讨论导线本身、布设导线的路径或者两条导线相

遇的交叉点。要考虑的是端之间的连接——可以说输出端和另一个输入端直接连接，不关注两者间实际是如何连接的。这个领域中的很多其他因素和我们的分析无关，诸如大小、形状、颜色或不同部件的成本。

如果目的不是对门级的设计进行校验，那么本体就会不同。例如，如果是调试有问题的电路，那么本体中最好把导线包括进来，因为有问题的导线会破坏流经它的信号。如果感兴趣的是解决定时错误，我们需要把门延迟加进本体。如果我们对设计出一种有利可图的产品感兴趣，那么电路的成本以及它相对于市场上其他产品的速度都将是重点要考虑的。

确定词汇表

现在要讨论的是电路、端、信号和门。下一步则是选择函词、谓词和常量来表示它们。首先，需要能够把某个门和其他门、对象区分开。每个门表示成有名字的常量对象，如用 Gate( $ X_{1} $)表示。门的行为跟它的类型有关：与门、或门、异或门和非门常量。由于每个门都只能有一种类型，可以使用函词来表示：Type( $ X_{1} $) = XOR。而电路由用谓词来表示：Circuit( $ C_{1} $)。

下一步考虑端，使用谓词 Terminal(x)。门或者电路可以有一个或多个输入端以及一个或多个输出端。用函词 $ In(1, X_1) $ 表示门 $ X_1 $ 的第一个输入端。类似的用函词 Out 表示输出端。函词 Arity(c,ij) 表示电路 c 有 i 个输入端和 j 个输出端。门之间的连接用谓词 Connected 表示，它以两个端作为参数，如 Connected(Out(1, X_1), In(1, X_2))。

最后，需要知道信号是接通的还是断开的。一种可能是用一元谓词 $ On(t) $，当某个端的信号接通时为真。然而，这样做不好回答诸如“电路 $ C_{1} $ 输出端的所有可能信号值是什么？”因此我们把两个“信号值”1和0作为对象引入，用函词 $ Signal(t) $ 表示端 t 的信号值。

对电路领域的通用知识进行编码

我们拥有好的本体的标志是：只需说明少量的通用规则，就能得到清晰简洁的知识表示。需要的所有公理如下所示：

（1）如果两个端是连通的，那么它们信号相同：

$$ \forall t_{1},t_{2}{~T e r m i n a l}(t_{1})\land{T e r m i n a l}(t_{2})\land{C o n n e c t e d}(t_{1},t_{2})\Rightarrow{S i g n a l}(t_{1})={S i g n a l}(t_{2}) $$

（2）每个端的信号不是1就是0：

$$ \forall t{\mathrm{~T e r m i n a l}}(t)\Rightarrow{\mathrm{S i g n a l}}(t)=1\;\lor\;\mathrm{S i g n a l}(t)=0 $$

（3）Connected 是对称的：

$$ \forall t_{1},t_{2}\quad C o n n e c t e d(t_{1},t_{2})\lefleftleftrightarrow C o n n e c t e d(t_{2},t_{1}) $$

（4）存在有四种类型的门：

$$ \forall g\;Gate(g)\land k=Type(g)\Rightarrow k=AND\;\lor\;k=OR\;\lor\;k=XOR\;\lor\;k=NOT $$

（5）与门的输出为0，当且仅当它的任一输入为0：

$$ \begin{aligned}\forall g\quad&Gate(g)\land Type\left(g\right)=AND\Rightarrow\\&Signal(Out(1,g))=0\Leftrightarrow\exists n~Signal(In(n,g))=0\end{aligned} $$

（6）或门的输出为1，当且仅当它的任一输入为1：

$$ \begin{aligned}\forall g\quad&Gate(g)\land Type\left(g\right)=OR\quad\Rightarrow\\&Signal(Out(1,g))=1\Leftrightarrow\exists n~Signal(In(n,g))=1\end{aligned} $$

（7）异或门的输出为1，当且仅当它的输入不相等：

$$ \begin{aligned}\forall g\quad&Gate(g)\land Type\left(g\right)=XOR\quad\Rightarrow\\&Signal(Out(1,g))=1\Leftrightarrow Signal(In(1,g))\neq Signal(In(2,g))\end{aligned} $$

（8）非门的输出与它的输入相反：

$$ \forall g\quad G a t e(g)\land(T y p e\left(g\right)=N O T)\Rightarrow S i g n a l(O u t(1,g))\neq S i g n a l(I n(1,g)) $$

（9）门（除了非门）有两个输入和一个输出：

$$ \forall g{G a t e}(g)\land{T y p e}(g)={N O T}\Rightarrow{A r i t y}(g,1,1) $$

$$ \forall g{G a t e}(g)\land k={T y p e}(g)\land(k={A N D}~\lor~k={O R}~\lor~k={X O R})\Rightarrow{A r i t y}(g,2,1) $$

（10）门电路有多个端，输入端和输出端都不能超出它的维数：

$$ \forall c,i,j{~C i r c u i t}(c)\land{A r i t y}(c,i,j)\Rightarrow $$

$$ \forall n\ (n{\leqslant}i{\Rightarrow}Terminal(In(c,n)))\land(n>i{\Rightarrow}In(c,n)=Nothing)\ \land $$

$$ \forall n\,(n{\leqslant}j\Rightarrow Terminal(Out(c,n)))\land(n{>}j\Rightarrow Out(c,n)=Nothing) $$

（11）门、端、信号、门的类型和空是互不相同的。

$$ \forall g,t{G a t e}(g)\land{T e r m i n a l}(t)\Rightarrow $$

$$ g\ne t\ne1\ne0\ne OR\ne AND\ne XOR\ne NOT\ne Nothing $$

（12）门是电路。

$$ \forall g\;Gate(g)\Rightarrow Circuit(g) $$

问题实例编码

对图8.6的电路 $ C_{1} $进行编码。首先，我们对电路和组成它的门加以分类：

$$ {C i r c u i t}(C_{1})\;\land\;{A r i t y}(C_{1},\;3,\;2) $$

$$ Gate(X_{1})\ \land\ Type(X_{1})=XOR $$

$$ Gate(X_{2})\ \land\ Type(X_{2})=XOR $$

$$ Gate(A_{1})\ \land\ Type(A_{1})=AND $$

$$ Gate(A_{2})\land Type(A_{2})=AND $$

$$ Gate(O_{1})\land Type(O_{1})=OR $$

接着说明它们之间的连接：

$$ Connected(Out(1,X_{1}),In(1,X_{2}))\qquad Connected(In(1,C_{1}),In(1,X_{1})) $$

$$ Connected(Out(1,X_{1}),In(2,A_{2}))\qquad Connected(In(1,C_{1}),In(1,A_{1})) $$

$$ \mathrm{C o n n e c t e d}({O u t}(1,A_{2}),{I n}(1,O_{1}))\qquad\mathrm{C o n n e c t e d}({I n}(2,C_{1}),{I n}(2,X_{1})) $$

$$ Connected(In(2,C_{1}),In(2,A_{1})) $$

$$ Connected(Out(1,X_{2}),Out(1,C_{1}))\qquad Connected(In(3,C_{1}),In(2,X_{2})) $$

$$ Connected(Out(1,O_{1}),Out(2,C_{1}))\qquad Connected(In(3,C_{1}),In(1,A_{2})) $$

向推理过程提交查询

哪种输入组合可以使得 $ C_{1} $ 的第一个输出（和位）为 0，而 $ C_{1} $ 的第二个输出（进位）为 1?

$$ \exists i_{1},i_{2},i_{3}\quad Signal(In(1,C_{1}))=i_{1}\land Signal(In(2,C_{1}))=i_{2}\land Signal(In(3,C_{1}))=i_{3} $$

$$ \land~Signal(Out(1,C_{1}))=0\land~Signal(Out(2,C_{1}))=1 $$

回答则是变量 $ i_{1} $、 $ i_{2} $ 和 $ i_{3} $ 的置换，其结果语句被知识库蕴涵。这样的置换有三个：

$$ \{i_{1}/1,i_{2}/1,i_{3}/0\}\qquad\{i_{1}/1,i_{2}/0,i_{3}/1\}\qquad\{i_{1}/0,i_{2}/1,i_{3}/1\} $$

加法器电路所有端的可能值的集合是什么？

$$ \exists i_{1},i_{2},i_{3},o_{1},o_{2}\quad Signal(In(1,C_{1}))=i_{1}\land Signal(In(2,C_{1}))=i_{2} $$

$$ \land~Signal(In(3,C_{1}))=i_{3}\land~Signal(Out(1,C_{1}))=o_{1}\land~Signal(Out(2,C_{1}))=o_{2} $$

最后的这个查询将返回一个完整的输入输出对应表，可以用于检验该加法器是否正确地对其输入进行了加法运算。这是电路验证的一个简单实例。可以根据电路的定义来建立更大的数字系统，对它们采用相同的验证过程（见习题8.26）。很多领域都接受同样的结构化知识库的开发过程，从简单概念出发定义更复杂的概念。

调试知识库

可以用很多方法来干扰知识库以便了解知识库可能的错误行为。例如，假设我们没有阅读第8.2.8节，从而漏掉了断言 $ 1 \neq 0 $。除了输入000和110的情况，系统无法证明电路的任一输出。可以通过检查每个门的输出来查明问题。例如，可以提问：

$$ \exists i_{1},i_{2},o\quad Signal(In(1,C_{1}))=i_{1}\land Signal(In(2,C_{1}))=i_{2}\land Signal(Out(1,X_{1})) $$

它表明除了输入 10 和 01 的情况， $ X_{1} $ 的输出都是未知的。接着我们观察异或门的公理，把它应用于 $ X_{1} $:

$$ Signal(Out(1,X_{1}))=1\Leftrightarrow Signal(In(1,X_{1}))\neq Signal(In(2,X_{1})) $$

如果输入已知，假设为1和0，那么上式变化为：

$$ Signal(Out(1,X_{1}))=1\Leftrightarrow1\neq0 $$

这时问题已经很明显：系统无法推断出 $ \mathrm{Signal}(Out(1,X_{1}))=1 $，所以我们需要告诉它 $ 1\neq0 $。

8.5 本章小结

本章介绍了一阶逻辑表示语言，它比命题逻辑表达能力更强。本章的要点如下：

● 知识表示语言应该是陈述性的、可合成的、有表达力的、上下文无关的以及无歧义的。

逻辑学在本体论约定和知识论约定上存在着不同。命题逻辑只是对事实的存在进行限定，而一阶逻辑对于对象和关系的存在进行限定，因此有更强的表达力。

一阶逻辑的语法建立在命题逻辑的基础上。它增加了项来表示对象，并且使用全称量词和存在量词对变元进行量化来构建断言。

一阶逻辑的可能世界或模型包括通过对象集和解释，解释把常量符号映射到对象，谓词符号映射成对象之间的关系，函词映射成对象上的函数。

原子语句仅在谓词所表示的关系在项所指代的对象上成立时为真。扩展解释将量化的变元映射到对象上，定义了量化语句的真值表。

用一阶逻辑开发知识库是一个细致的过程，包括对领域进行分析、选定词汇表、对推理结论必不可少的公理进行编码。

参考文献与历史注释

尽管 Aristotle 的逻辑处理对象的形式化，它和一阶逻辑的表达力还差得很远。主要的障碍在于它关注一元谓词，而排斥二元关系谓词。第一个系统对待关系的是 Augustus De Morgan（1864），他给出了 Aristotle 的逻辑无法处理的实例：“所有马都是动物；所以，一匹马的头是一个动物的头。” Aristotle 无法推理，因为这个语句分析必须使用二元谓词“x 是 y 的头”。Charles Sanders Peirce（1870，2004）深入讨论了关系逻辑。

真正一阶逻辑的诞生应该从 Gottlob Frege（1879）的“Begriffschrift”（“概念书写”或“概念表示”）中引入量词开始。Peirce（1883）也独立开发了一阶逻辑系统，尽管在时间上落后于Frege。Frege的逻辑系统使用了嵌套量词，向前迈进了一大步，但他采用的表示很笨拙。一阶逻辑现有的符号表示实际应归功于Giuseppe Peano（1889），但是其语义实质上与Frege提出的语义相同。奇怪的是，Peano公理在很大程度上归功于Grassmann（1861）和Dedekind（1888）。

Leopold Löwenheim（1915）系统地给出了一阶逻辑模型论，对等词给出了合适的处理。Thoralf Skolem（1920）进一步扩展了 Löwenheim 的结果。Alfred Tarski（1935，1956）用集合论给出了一阶逻辑中的真值和模型论的显式定义。

McCarthy（1958）的贡献在于把一阶逻辑作为构建 AI 系统的工具。Robinson（1965）对归结的发现极大地推进了逻辑主义 AI 的发展，我们在第 9 章描述了用于一阶逻辑推理的完整过程。AI 的逻辑主义学派发源于斯坦福大学。Cordell Green（1969a，1969b）开发出一阶逻辑推理系统 QA3，这引发了 SRI 首次尝试建造有逻辑能力的机器人（Fikes 和 Nilsson，1971）。Zohar Manna 和 Richard Waldinger（1971）把一阶逻辑应用于对程序的推理，Michael Genesereth（1984）把它应用于电路的推理。在欧洲，逻辑程序设计（一阶逻辑推理的一种受限形式）应用于语言学分析（Colmerauer 等，1973）和通用断言系统（Kowalski，1974）。计算逻辑通过 LCF（Logic for Computable Functions，可计算函数逻辑）计划（Gordon 等人，1979）在 Edinburgh 扎根。这些在第 9 章和第 10 章中会进一步讨论。

一阶逻辑的实际应用包括电子产品生产需求评价系统（Mannion，2002），它可以对政策文件进行推理和数字版权管理（Halpern and Weissman，2008）。一阶逻辑的实际应用还有Web服务自动集成系统（McIlraith和Zeng，2001）。

Whorf 假设（Whorf，1956）以及语言和思维的一般问题在最近的一些书中有讨论（Gumperz 和 Levinson，1996；Bowerman 和 Levinson，2001；Pinker，2003；Gentner 和 Goldin-Meadow，2003）。“theory”理论（Gopnik 和 Glymour，2002；Tenenbaum 等人，2007）认为儿童认识世界与构建科学理论是一回事。正好机器学习算法的预测强烈依赖于提供给它的词汇表一样，儿童的理论学习依赖于学习发生时的语言学环境。

一阶逻辑的入门教材有很多，其中有些是由逻辑学大师编写的：Alfred Tarski（1941）、Alonzo Church（1956）和Quine（1982）（此教材是最具可读性的教材之一）。Enderton（1972）的书数学倾向性更强。Bell和Machover（1977）给出了一阶逻辑的高度形式化的处理，同时讨论了逻辑中的很多高级论题。Manna和Waldinger（1985）从计算机科学的角度通俗地

介绍了逻辑，Huth 和 Ryan（2004）也做了这项工作，同时关注了程序验证。Barwise 和 Etchemendy （2002）也同样使用了这里介绍的方法。Smullyan（1995）使用表格格式使结果更简洁。Gallier（1986）为一阶逻辑提供了极端严格的数学说明，给出了大量关于它在自动推理中应用的材料。《人工智能的逻辑基础》（Logical Foundations of Artificial Intelligence）（Genesereth 和 Nilsson，1987）既系统地介绍了逻辑基础，同时首次系统地对具有感知和动作的逻辑 agent 进行了讨论，还有两个很好的手册：van Bentham 和 ter Meulen（1997），Robinson 和 Voronkov （2001）。纯粹的数学逻辑期刊为“符号逻辑杂志”（Journal of Symbolic Logic），而“应用逻辑杂志”（Journal of Applied Logic）则更接近人工智能。

习题

8.1 逻辑知识库使用没有显式结构的语句集来表示世界。而类推表示具有直接与被表示的事物的结构相对应的物理结构。把你所在国家的道路交通图看作该国家事实的一种类推表示——它用地图语言表示。地图的二维结构对应于该地区的二维地表。

a. 给出5个地图语言符号的例子。

b. 显式语句是指由表示的创建者明确写出的语句。隐含语句是由于类推表示的属性而从显式语句得出的语句。用地图语言分别给出三个隐含语句和显式语句的例子。

c. 给出三个关于你所在国家的物理结构的事实，这些例子无法用地图语言表示。

d. 给出两个事实，它们用地图语言来表示比用一阶逻辑更容易。

e. 举出两个例子说明类推表示的另外两个例子。这些语言的优缺点各是什么？

8.2 考虑某知识库只包括两条语句 $ P(a) $ 和 $ P(b) $。此知识库是否蕴涵 $ \forall x \quad P(x) $？请用模型解释你的答案。

8.3 语句 $ \exists x, y \quad x = y $ 是否有效？请解释。

8.4 写出一个逻辑语句，使它为真的所有世界刚好只包括一个对象。

8.5 考虑一个符号词汇表，它包括 $c$ 个常量符号，对满足 $1 \leq k \leq A$ 的每个 $k$，有 $p_k$ 个谓词和 $f_k$ 个函词。设域的大小恒为 $D$。对于每个给定模型，每个谓词或函词分别映射为相同元数的关系或函数。你可以假设模型中的函数允许某些输入元组在该函数中无值（也就是，它的值为不可见的对象）。推导一个公式用于计算具有 $D$ 个元素的论域上的可能的解释-模型组合的个数。无需考虑消除冗余组合。

8.6 下列语句中哪些是有效的？

a. $ (\exists x x=x) \Rightarrow (\forall y \exists z y=z) $

b. $ \forall x\, P(x) \lor \neg P(x) $

c. $ \forall x \operatorname{Smart}(x) \vee (x=x) $

8.7 考虑一阶逻辑语义的一个版本，其中的模型允许空的论域。请给出至少两个语句，它们在标准逻辑下是有效的，但在这种新语义下不是的。请讨论对你的例子哪种语义更合理。

8.8 能否从事实 Jim ≠ George 和 Spouse(Jim, Laura) 得出事实 – Spouse(George, Laura)? 如果能，请给出证明；否则，请提供需要的附加公理。如果把 Spouse 作为一元函词而不

是二元谓词处理呢？

8.9 本题使用函词 MapColor 和谓词 $ In(x,y) $、Borders(x,y)、Country(x) $，参数都是用常量表示的地理区域。下列每个英语句子都给出了多个逻辑表示。对每一逻辑表示，说明（1）它是否真实表达了英语语句的含义；（2）是否不合法法并因此无任何意义；（3）是否符合语法但并未表达出英语语句的含义。$

a. Paris and Marseilles are both in France

(i) In(Paris ∧ Marseilles, France)

(ii) In(Paris, France) ∧ In(Marseilles, France)

(iii) In(Paris, France) ∨ In(Marseilles, France)

b. There is a country that borders both Iraq and Pakistan

(i) ∃c Country(c) ∧ Border(c, Iraq) ∧ Border(c, Pakistan)

(ii) ∃c Country(c) ⇒ [Border(c, Iraq) ∧ Border(c, Pakistan)]

(iii) [∃c Country(c)] ⇒ [Border(c, Iraq) ∧ Border(c, Pakistan)]

(iv) ∃c Border(Country(c), Iraq ∧ Pakistan)

c. All countries that border Ecuador are in South America

(i) ∀c Country(c) ∧ Border(c, Ecuador) ⇒ In(c, South America)

(ii) ∀c Country(c) ⇒ [Border(c, Ecuador) ∞ In(c, South America)]

(iii) ∀c [Country(c) ⇒ Border(c, Ecuador)] ⇒ In(c, South America)

(iv) ∀c Country(c) ∧ Border(c, Ecuador) ∧ In(c, South America)

d. No region in South America borders any region in Europe

(i) ¬[∃c,d In(c, South America) ∧ In(d, Europe) ∧ Borders(c, d)]

(ii) ∀c,d [In(c, South America) ∧ In(d, Europe)] ⇒ ¬Borders(c, d)

(iii) ¬∀c In(c, South America) ⇒ ∃d In(d, Europe) ∧ ¬Borders(c, d)

(iv) ∀c In(c, South America) ⇒ ∀d In(d, Europe) ⇒ ¬Borders(c, d)

e. No two adjacent countries have the same map color

(i) ∀x,y ¬Country(x) ∨ ¬Country(y) ∨ ¬Borders(x,y) ∨ ¬(MapColor(x) = MapColor(y))

(ii) ∀x,y (Country(x) ∧ Country(y) ∧ Borders(x,y) ∧ ¬(x=y)) ⇒ ¬(MapColor(x))

MapColor(y)

(iii) ∀x,y Country(x) ∧ Country(y) ∧ Borders(x,y) ∧ ¬(MapColor(x) = MapColor(y))

(iv) ∀x,y (Country(x) ∧ Country(y) ∧ Borders(x,y)) ⇒ MapColor(x ≠ y)

词汇表中有如下符号：

Occupation(p, o)：谓词，p 的职业为 o

Customer(p1, p2)：谓词，p1 是 p2 的客户

Boss(p1, p2)：谓词，p1 是 p2 的老板

Doctor, Surgeon, Lawyer, Actor：表示职业的常量

Emily, Joe：表示人的常量

请使用上述符号写出下列语句的一阶逻辑表示：

a. Emily 要么是外科医生，要么是律师。

b. Joe 是个演员，但他还有另外一个工作。

c. 所有外科医生都是医生。

d. Joe 没有律师（即，他不是任何律师的客户）。

e. Emily 的老板是个律师。

f. 有个律师的客户全都是医生。

g. 每个外科医生都有律师。

8.11 完成下列逻辑语句练习：

a. 将下述逻辑语句翻译成自然的好的英语表示：

$ \forall x,y,l \text{ Speaks Language}(x,l) \land \text{Speaks Language}(y,l) $

$ \Rightarrow \text{Understands}(x,y) \land \text{Understands}(y,x) $

b. 解释为何由 a 可推导出下述语句：

$ \forall x,y,l \text{ Speaks Language}(x,l) \land \text{Speaks Language}(y,l) \Rightarrow \text{Understands}(x,y) $

c. 用一阶逻辑翻译下列语句：

（i）Understanding leads to friendship

（ii）Friendship is transitive

请定义你用的所有谓词、函词和常量。

8.12 重写 8.3.3 节的前两个 Peano 公理为定义 $ \text{NatNum}(x) $ 的一条公理。

8.13 公式 8.4 定义了方格中有微风的条件。这里可以考虑另外两种方法来描述 Wumpus 世界的这一特点。

a. 可以定义诊断规则，从观察到的事实来推导背后可能的原因。为了找出陷阱，显然诊断规则表明如果方格中有微风，那么邻近的某些方格中一定有陷阱；如果方格中没有微风，那么邻近的方格中没有一个有陷阱。用一阶逻辑写出这两条规则，并说明这两条语句的合取在逻辑上等价于公式 8.4。

b. 我们可以定义因果规则，从原因导出结果。一个显然的因果规则就是陷阱会导致邻近的方格有微风。用一阶逻辑写出这条语句，解释与公式 8.4 相比为什么这条语句不完全，并提供缺失的公理。

8.14 写出描述谓词 GrandChild、GreatGrandparent、Ancestor、Brother、Sister、Daughter、Son、FirstCousin、BrotherInLaw、SisterInLaw、Aunt 和 Uncle 的公理。找出隔了 n 代的第 m 代姑表亲的合适定义，并用一阶逻辑写出该定义。现在写出图 8.7 中所示的家族树的基本事实。采用适当的逻辑推理系统，把你已经写出的所有语句 TELL 系统，并 ASK 系统：谁是 Elizabeth 的孙辈，Diana 的姐夫/妹夫，Zara 的曾祖父母和 Eugenie 的祖先？

8.15 请解释下面给出的集合隶属谓词∈的定义存在什么问题：

$ \forall x, s \quad x \in \{x \mid s\} $

$ \forall x, s \quad x \in s \Rightarrow \forall y \quad x \in \{y \mid s\} $

8.16 以集合公理为例，写出表的公理，包括本章所提及的所有常量、函数和谓词。

8.17 解释下面给出的 Wumpus 世界中相邻方格的定义存在什么问题：

$ \forall x, y $ Adjacent([x, y], [x + 1, y]) $ \land $ Adjacent([x, y], [x, y + 1])

8.18 用常量符号 Wumpus 和二元谓词 At(Wumpus, Location)，写出推理 Wumpus 的位置所需的公理。记住 Wumpus 只有一个。

8.19 假设谓词 $ Parent(p, q) $ 和 $ Female(p) $ 以及常量 $ Joan $ 和 $ Kevin $，字面的意思是显然的，用一阶逻辑表示下列语句。（可以用 $ \exists^{1} $ 表示恰有一个）

a. Joan 有女儿（可能有多个，也可能还有儿子）。

b. Joan 只有一个女儿（可能还有多个儿子）。

c. Joan 只有一个孩子，是女儿。

d. Joan 和 Kevin 只有一个孩子。

e. Joan 和 Kevin 只有一个孩子，但和其他人还有孩子。

8.20 用一阶逻辑书写算术断言，使用谓词符号<、函词+和×、常量0和1。

a. 表示属性“x是个偶数”。

b. 表示属性“x是素数”。

c. Goldbach猜想是个猜想（尚未得到证实）：每个偶数都可以表示成两个素数之和。写出它对应的逻辑语句。

8.21 第6章中，使用了等号来表示变量和值的关系。例如，写WA=red表示西澳是红色。把它用一阶逻辑表示出来就得写冗长的ColorOf(WA)=red。直接将WA=red作为逻辑断言会带来什么样的推理错误？

8.22 用一阶逻辑写出断言：每把钥匙和每双袜子中的至少一只会最终永远丢失，使用的词汇表如：Key(x)，x 是钥匙；Sock(x)，x 是袜子；Pair(x,y)，x 和 y 是一对；Now，当前时间；Before( $ t_{1} $, $ t_{2} $)，时间 $ t_{1} $ 在 $ t_{2} $ 之前；Lost(x,t)，对象 x 在时刻 t 丢失。

8.23 对如下英语语句，判断它的一阶逻辑翻译是否是好的翻译。如果不是，请解释原因并改正。（有些语句有多个错误！）

a. No two people have the same social security number.

$\neg\exists x, y, n\, Person(x) \land Person(y) \Rightarrow [HasSS\#(x, n) \land HasSS\#(y, n)]$

b. John's social security number is the same as Mary's

$\exists n\,HasSS\#(John, n) \land HasSS\#(Mary, n)$

c. Everyone's social security number has nine digits

$\forall x, n\,Person(x) \Rightarrow [HasSS\#(x, n) \land Digits(n, 9)]$

d. 使用函词 SS#而不是谓词 HasSS#重写上述（不正确）语句。

8.24 用一个相容的词汇表（需要你自己定义）在一阶逻辑中表示下列语句：

a. 某些学生在2001年春季学期上法语课。

b. 上法语课的每个学生都通过了考试。

c. 只有一个学生在2001年春季学期上希腊语课。

d. 希腊语课的最好成绩总是比法语课的最好成绩高。

e. 每个买保险的人都是聪明的。

f. 没有人会买昂贵的保险。

g. 有一个代理，他只卖保险给那些没有投保的人。

h. 镇上有一个理发师，他给所有不自己刮胡子的人刮胡子。

i. 在英国出生的人，如果其双亲都是英国公民或永久居住者，那么此人生来就是一个英国公民。

j. 在英国以外的地方出生的人，如果其双亲生来就是英国公民，那么此人血统上是一个英国公民。

k. 政治家可以一直愚弄某些人，也可以在某个时候愚弄所有人，但是他们无法一直愚弄所有的人。

1. 所有希腊人讲同样的语言。（使用 Speaks(x, I) 表示 x 讲语言 I）

8.25 写出一个事实和公理的通用集合，用它来表示断言 “Wellington 听说了 Napoleon 死亡的消息”，并正确地回答问题 “Napoleon 听说了 Wellington 死亡的消息吗？”

8.26 扩展第8.4节的词汇表以定义n位二进制数的加法。然后对图8.8的四位加法器的描述进行编码，提出验证其正确性所需的查询。

8.27 获取一份你所在国家的护照申请书，确认获取护照的规则，并按照第8.4节的步骤将它们转换为一阶逻辑表示。

8 考虑一阶逻辑的知识库，知识库中包括人、歌曲、专辑和 CD。词汇表包括符号：

$ \text{CopyOf}(d, a) $: 谓词。盘 d 是专辑 a 的拷贝。

Owns(p, d): 谓词。p 拥有盘 d。

Sings(p, s, a): 专辑 a 中收录了 p 唱的 s。

Wrote(p, s): p 创作了歌曲 s。

McCartney, Gershwin, B Holiday, Joe, Eleanor Rigby, The Man I Love, Revolver: 常量，按字面意思。

用一阶逻辑表示下列语句：

a. Gershwin 创作了歌曲 “The Man I Love”。

b. Gershwin 没有创作 “Eleanor Rigby”。

c. 是 Gershwin 或者 McCartney 创作了 “The Man I Love”。

d. Joe 至少创作了一首歌曲。

e. Joe 有 Revolver 的拷贝。

f. 专辑 Revolver 中 McCartney 唱的每首歌都是 McCartney 自己创作的。

g. Gershwin 没为 Revolver 写过歌。

h. Gershwin 创作的每一首歌都被一些专辑收录（可能不同的歌收录在不同的专辑中）。

i. 有一个专辑中收录了 Joe 写的每一首歌。

j. Joe 拥有一个专辑拷贝，里面有 Billie Holiday 唱的 “The Man I Love”。

k. 只要某专辑中有 McCartney 唱的歌，Joe 就有这个专辑的拷贝（当然，不同的专辑有不同的物理 CD 盘）。

1. 只要某专辑中的所有歌都是 Billie Holiday 唱的，Joe 就拥有该专辑的拷贝。