2023人工智能知识推理和规划

PAGEPAGE407人工智能知识、推理和规划目录TOC\o"1-2"\h\u23111人工智能知识、推理和规划 119112第7章逻辑智能体 3194937.2wumpus世界 75055第8章一阶逻辑 62196988.1回顾表示 63217008.2一阶逻辑的语法和语义 70145298.3使用一阶逻辑 8564968.4一阶逻辑中的知识工程 955357读者服务： 10416502第9章一阶逻辑中的推断 10516382第10章知识表示 1522583910.1本体论工程 1531988610.2类别与对象 157158510.3事件 1662254910.4精神对象和模态逻辑 1721358610.5类别的推理系统 176596510.6用缺省信息推理 18229051第11章自动规划 1892330011.1经典规划的定义 190156711.2经典规划的算法 196764211.3规划的启发式方法 2032328111.4分层规划 2082675511.5非确定性域的规划和行动 2191542111.6时间、调度和资源 2321099611.7规划方法分析 238第7章逻辑智能体来获取关于这个世界的新表示，并使用这种表示来推导下一步该怎么做。人类似乎具有知识，人类的知识能够帮助他们做事。在人工智能中，基于知识的智能体（knowledge-based agent）对知识的内部表（representation）进行推理（reasoning）来确定要采取的动作。第3章和第4章的问题求解智能体具有知识，但这种知识是非常有限且死板的。它们知道可以采取哪些动作，也知道在某个状态采取某个动作将得到哪种结果，但它们不知道一般事实。例如，寻路智能体不知道一条路的长度不可能是负数公里，而8数码智能体也不知道两块瓷砖无法放置在同一个空格当中。问题求解智能体具有的知识对寻找从起点到终点的路径这种问题非常有用，但也仅限于此。问题求解智能体所使用的原子表示也有很大的局限性。例如，在部分可观测的环境中，问题求解智能体表示它对当前状态的了解的唯一选项是列出所有可能的具体状态。我可以让一个人驱车前往一个人口不超过1万的美国小镇，但如果要让问题求解智能体来做这件事，我只能明确地将目标描述为大约1.6万个符合条件的小镇的集合。第6章引入了我们的第一个因子化表示，其中状态被表示为对变量的赋值。这是朝正确方向前进的一步，它能使智能体的某些部分以与领域无关的方式运作，并支持更高效的算法。在本章中，我们将这一步延伸到它的逻辑结论，可以说，我们将逻辑持基于知识的智能体。这些智能体可以组合或重组信息以适应各种用途。它可以与我们当下的需要毫不相关，就像数学家证明定理或天文学家计算地球的预期寿命一样。基于知识的智能体能够接受明确描述的目标作为任务，能够通过主动学习或被告知关于环境的新知识快速地获得完成任务的能力，也能够通过更新相关知识适应环境的变化。我们在7.1节开始介绍智能体的总体设计。7.2节新引入了一个名为wumpus世界的简单环境，以便在不涉及任何技术细节的前提下，阐明基于知识的智能体的运作方式。随后我们在7.3节解释逻辑的一般原理，在7.4节介绍命题逻辑的具体细节。命题逻辑是一种因子化表示，尽管它的表达能力不如一阶逻辑（第8章）却能够阐明逻辑的所有基本概念。命题逻辑还具有丰富的推断方法，我们将在7.5节和7.6节中描述这些内容。最后，7.7节将基于知识的智能体的概念与命题逻辑的技术结合起来，为wumpus世界构建了一个简单的智能体。基于知识的智能体基于知识的智能体的核心部件是它的知识库（knowledge KB）。知识库是一个语句集。（此处“语句”是一个术语。它与英语或其他自然语言的语句类似，但不完全相同。）这些语句用知识表示语言（knowledgerepresentationlanguage）表达，代表了关于世界的某种断言。如果一条语句是直接给出的，而不是从其他语句推导而来的，我们就称它为公理（axiom）。向知识库添加新语句以及从知识库查询已知语句的方法是必不可少的。这些操作的标准名称分别是TELL（告知）和ASK（询问）。这两个操作都可能涉及推断（inference），也就是从原有语句中推导出新语句。推断必须符合以下要求：当向知识库询问（ASK）时，答案应当遵循先前已经告知（TELL）知识库的内容而生成。我们将在本章后续部分仔细讲解何为“遵循”。现在，我们暂且将其理解为在推断过程中不能进行捏造。图7-1展示了基于知识的智能体程序。与所有的智能体一样，基于知识的智能体以一个感知作为输入，返回一个动作。该智能体维护一个知识库KB，这个知识库最初可能包括一些背景知识（backgroundknowledge）。图7-1 通用的基于知识的智能体。给定一个感知，智能体将这一感知添加进知识库，向知识询问最优动作，并告知知识库它已经采取了这一动作每次调用智能体程序时，程序会做3件事。首先，它告知知识库它所感知到的东西。然后，它询问知识库它应当采取什么动作。在回答这一查询时，可能会对关于世界的当前状态、可能的动作序列的执行结果等进行大量推理。最后，智能体程序告知知识库它选择的动作，并返回这一动作以便执行。表示语言的细节隐藏在3个函数中，这3构建了一个语句，断言智能体在给定时间接收到给定的感知。构建了一个语句，询问当前时刻应当采取何种动作。最后，构建了一个语句，断言选定的动作已经执行。推断机制的细节隐藏在与中。后续章节将阐明这些细节。图7-1所示的基于知识的智能体看起来与第2章所述的具有内部状态的智能体非常相似。而由于TELL和ASK的定义，基于知识的智能体并不仅是普通的用来计算动作的程序。它受到位于知识层面（knowledgelevel）的描述的操控，我们只需要在知识层面明确智能体所具有的知识和它的目标，就可以决定它的行为。例如，一辆自动驾驶出租车的任务是将一名乘客从旧金山送往马林县，它或许知道金门大桥是两地间的唯一通路。因此，我们可以猜测出租车将驶过金门大桥，因为它知道这样能达成目标。注意，这一分析与出租车在实现层面（implementation level）的工作原理毫无关系。不它是用链表或点阵图来实现地理知识，还是通过操纵寄存器中的符号串或在神经元网络中传递有噪声的信号来进行推理，都与我们的分析无关。如何在它的环境中运作。我们称之为陈述性（declarative）系统构建方法。相对地，过程性（procedural）方法将所需的行为直接编码为程序代码。在20世纪70年代和80年代，两种方法的提倡者进行了激烈的辩效的过程性代码。我们还可以给基于知识的智能体赋予自主学习的机制，我们将在第19章讲解的这些机制。智能体能够利用这些机制从一系列感知中创建关于环境的一般知识。进行学习的智能体可以是完全自主的。wumpus世界本节我们将描述一个能够体现基于知识的智能体的价值的环境。wumpus世界（wumpus world）是一个洞穴，其中有许多房间，房间间有走廊连接。在洞穴的某处潜伏着可怕的wumpus，这是一只会吃掉任何进入其房间的人的怪兽。智能体可以射杀wumpus，但智能体只有一支箭。一些房间有无底洞，能困住任何漫游到这些房间中的人（wumpus除外，它体型大得无法落入无底洞）。这个阴森环境的唯一回报是可能找到的金块。尽管以现代电子游戏的眼光来看，wumpus世界相当乏味，但它却能展示出智能的一些重要属性。图7-2展示了一个简单的wumpus世界示例。任务环境的精确定义用节所述的PEAS描述法给出。图7-2 一个典型的wumpus世界。智能体位于左下角，面朝东（向右）性能度量：带着金块从洞穴爬出+1000，跌入无底洞或被wumpus吞食−1000，每采取一个动作−1，用尽箭支−10洞穴，游戏结束。环境：一个4×4的房间网格，网格四周环绕着围墙。智能体始终从标为[1,1]的方格开始，面向东方。金块和wumpus的位置是根据均匀分布从除了起始方格的所有方格中随机选定的。另外，除起始方格外的每个方格都可能是无底洞，出现的概率为0.2。执行器：智能体可以向前（Forward）、左转（TurnLeft）90°和右转（TurnRight）90°。如果智能体进入有活着的wumpus或者有无底洞的方格，它将悲惨地死去。（但进入有死掉的wumpus的方格是安全的，尽管气味会很臭。）如果智能体试图前进并撞到墙，则智能体会原地不动。如果智能体与金块在同一个方格，抓取（Grab）捡起金块。射击（Shoot）动作可以用于向智能体面对的方向笔直地发射一支箭，这支箭会一直飞行，直到它命中wumpus（此时wumpus将被杀死）或击中墙壁。智能体只有一支箭，因此只有第一次射击动作有效。最后，攀爬（Climb）动作可以用于爬出洞穴，但智能体仅能从方格[1,1]爬出。传感器：该智能体有5息。❏ 在与wumpus直接（非对角）味（Stench）。[1]wumpus❏ 在与无底洞直接相邻的方格中，智能体会感知到微风（Breeze）。❏在金块所在的方格中，智能体会感知到闪光（Glitter）。❏智能体走向墙壁会感知到碰撞（Bump）。❏ 如果wumpus被杀死，它将发出惨叫（Scream），智能体可以在洞穴的任意位置感知到。感知将以由5个符号组成的列表的形式传给智能体程序。例如，如果有臭味和微风，但没有闪光、碰撞和惨叫，智能体程序将收到[Stench,Breeze,None,None,None]。我们可以在第2章所述的多个维度上描述wumpus环境。显然，它是确定性的、离散的、静态的且单智能体的。（好在wumpus不移动。）它是序贯的，因为只有采取很多动作后才可能得到奖励。它是部分可观测的，因为状态的一些方面是无法直接感知到的，如智能体的位置、wumpus的健康状况以及是否还有箭支可用。对于无底洞和wumpus的位置，我们可以将其看作状态中没有观测到的部分，在这种情况下，环境的转移模型是完全已知的，找出无底洞和wumpus的位置就能补全智能体对状态的知识；抑或，我们也可以说转移模型本身是未知的，因为智能体不知道哪些向前动作是致命的，在这种情况下，找出无底洞和wumpus的位置能够补全智能体对于转移模型的知识。对于环境中的智能体，主要的挑战是它起初并不知道环境的配置。克服这种无知似乎需要逻辑推理。在wumpus世界的大多数情况中，智能体是有可能安全地拾取金块的。但智能体偶尔也需要在空手而归和冒死寻宝之间做出选择。大约21%的环境是极不公平的，因为这时金块位于无底洞中，或被无底洞包围。我们来看一个基于知识的智能体是如何探索图7-2所示的wumpus世界的环境的。此处使用一种非形式化的知识表示语言，在网格中写下符号来表示（如图7-3和图7-4所示）。图7-3 智能体在wumpus世界迈出的第一步。（a）在感知到[None,None,None,None,None]后的初始状态。（b）在移动到[2,1]后感知到[None,Breeze,None,None,None]智能体的初始知识库包括前述的环境规则。具体来说，智能体知道自己位于[1,1]且[1,1]是安全的方格。我们在方格[1,1]中用“A”和“OK”分别进行表示。第一个感知是[None,None,None,None,None]，据此智能体可以认定它的相邻方格[1,2]和[2,1]是安全的——它们是“OK”的。图7-3a展示了此时智能体的知识状态。图7-4 智能体运作时的两个后续状态。（a）回到[1,1]再移动到[1,2]后，感知到[Stench,None,None,None,None]。（b）来到[2,2]再移动到[2,3]，感知到[Stench,Breeze,Glitter,None,None]一个谨慎的智能体只会移动到它所知的OK方格。我们假设智能体决定前进到[2,1]。这个智能体在[2,1]感受到微风（用“B”表示），因此在相邻方格中必然存在无底洞。根据游戏规则，无底洞不可能在[1,1]，因此[2, 2]和[3, 1]其中之一必然有无底洞或二者都有。图7-3b中的记号“P?”表示这些方格中可能存在无底洞。此时，仅有一个已知的且未访问过的“OK”方格。因此这个心思缜密的智能体将扭头，回到[1, 1]，后移步[1,2]。智能体在[1,2]感知到臭味，导致知识状态变为图7-4a[1,2]有臭味表明附近肯定有wumpus。但根据游戏规则wumpus不可能在[1,1]，也不在[2,2]（否则智能体先前在[2,1]时会探测到臭味）。因此，智能体可以推断出wumpus在[1,3]。记号“W!”表示这一推断。而[1,2]没有微风表明[2,2]没有无底洞。考虑到智能体先前已经推断出[2,2]或[3,1]中必然有无底洞，因此无底洞必然位于[3,1]。这是一次相当复杂的推断，因为它结合了在不同时间、不同地点获取的信息，并在缺乏感知的情况下迈出了关键的一步。现在智能体已经证明了[2,2]中既没有无底洞也没有wumpus，因此可以移动到那里。我们没有展示智能体在[2,2]能体转向并移动到[2,3]，形成了图7-4b所示的情况。在[2,3]探测到闪光，因此它应该抓取金块然后回家。注意，在智能体从可用信息中得出结论的每个情形下，如果可用信息是正确的，则可以保证结论都是正确的。这是逻辑推理的一个重要性质。本章剩余部分将描述如何构建能够表示信息并得出类似前述的结论的逻辑智能体。逻辑本节综述逻辑表示和推理的基本概念。这些漂亮的想法独立于逻辑的具体形式。因此，我们将形式的技术细节推后到7.4节介绍，本节代之以熟悉的普通算术问题作为示例。在7.1节，我们说过知识库由语句组成。这些语句是根据表示语言的语法（syntax）表达的，语法规定了所有的合规语句。用简单的算术就能清晰地说明语法这个概念：“x+y=4”是合规的语句，而“x4y+=”不是。一种逻辑还必须定义语句的语义，或者说语句的含义。语义定义每条语句在每个可能世界中的真值。例如，算术的语义指明“x+y=4”一个x为2且y为2的世界为真，但在一个x为1且y为1的世界中为假。在标准的逻辑学中，每个可能世界中的每条语句要么为真，要么为假——没有中间地带。[2]第13章讨论的模糊逻辑（fuzzylogic）允许存在不同程度的真值。当需要精确描述时，我们用模型来代替“可能世界”。可能世界可以被认为是（潜在的）是数学抽象，对于每个相关的语句，每个模型都有固定的真值（真或假）。非正式地举个例子：我们可以认为一个可能世界是让x个男士和y个女士坐在一张桌子边上玩桥牌，如果总共有4个人，则语句x+y=4为真。正式地说，可能的模型是对变量x和y进行非负整数赋值的所有可能。每个这样的赋值都确定了任何一个变量为x和y的算术语句的真值。如果语句在模型m中为真，我们说m满足，有时也可以说m是的一个模型。我们使用记号来代表的所有模型的集合。有了真值的概念，我们就可以讨论逻辑推理了。这涉及语句之间的逻辑蕴含（entailment），即一个语句逻辑上引发另一语句。数学上，我们用来表示语句蕴含语句。蕴含的形式化定义是：当且仅当在为真的每个模型中也为真。用刚才介绍的记法，我们可以将其写作当且仅当（注意此处⊆的方向：若，则是比更强的断言，它排除了更多的可能世界。）易理解语句x=0蕴含语句xy=0。显然，在任一x为0的模型中，xy也必然为0（而无论y的值是多少）。我们可以将同样的分析应用于7.2节所述的wumpus世界推理的例子。考虑图7-3b所示的情形：智能体在[1,1]中什么都没有探测到，在[2,1]中探测到微风。这些感知与智能体所具有的wumpus世界规则的知识一同构成了知识库。智能体所感兴趣的是相邻的方格[1,2]、[2,2]和[3,1]是否有无底洞。这3个方格中的每一个都可能有或没有无底洞，因此（暂且忽略这个世界的其他方面），总共有23=8个可能的模型。图7-5展示了这8个模型。[3]尽管该图用部分wumpus世界来表示模型，但模型实际上只是对类似“[1, 中有无底洞”的语句进行真或假的赋值。从数学的角度来看，模型中并不需要有可怕的长毛wumpus。图7-5 方格[1,2]、[2,2]和[3,1]中无底洞存在性的可能的模型。在[1,1]中没有观测到任何东西且在[2,1]中观测到微风的知识库用实线表示。（a）虚线表示的模型（[1,2]中没有无底洞）。（b）虚线表示的模型（[2,2]中没有无底洞）KB可以理解为一个语句的集合，或断言了所有单个语句的单个语句。在与智能体已知相矛盾的模型中，KB为假。例如，在所有[1, 2]有无底洞的模型中，KB都为假，因为[1, 1]中没有微风。实际上，使KB为真的模型只有3个，这些模型在图7-5中用实线包围。我们现在考虑两个可能的结论：=“[1,2]中没有无底洞” =“[2,2]中没有无底洞”在图7-5a和图7-5b中分别用虚线包围了和的模型。仔细观察后，我们可以得出在所有KB为真的模型中，也为真因此，，即[1,2]中没有无底洞。我们还可以得在一些KB为真的模型中，为假因此，KB不蕴含，即智能体无法断定[2,2]中没有无底洞。（也无法断定[2,2]中有无底洞。）[4]智能体可以计算[2,2]中有无底洞的概率，第12章将介绍如何计算。前述的例子不仅阐明了什么是蕴含，还展示了如何用蕴含的定义来推导出结论，即进行逻辑推断。图7-5所示的推断算法被称为模型检验，因为这个示例枚举了所有可能的模型来检验在所有KB为真的模型中都为真，即。将KB的所有推论的集合比作干草堆而将比做一根针或许有助于理解蕴含和推断。蕴含正如草堆中的针一样，而推断就像找到这根针的过程。一些形式化记法体现了这种区别：如果一个推断算法i可以从KB中推导出，则记为读作“是由i从KB中推得的”或“i从KB推得”。一个仅推导蕴含语句的推断算法被称为是可靠的或保真的。可靠性是极为重要的属性。一个不可靠的推断过程在运作时本质上会编造事实——它会声称发现了并不存在的针。我们很容易看出，模型检验在适用时[5]是一个可靠的程序。如果模型空间是有限的，则模型检验是有效的，例如，在固定大小的wumpusx+y=4中x和y的值也是有无限多对的。完备性也是很重要的属性：如果一个推断算法能够推导出所有蕴含的语句，则它是完备的。真正的草堆大小是有限的，对其进行全面仔细的检查就一定能确定针在不在草堆里，这似乎是很显然的道理。然而，对许多知识库来说，推论的草堆是无限的，因而完备性就成了一个重大问题。[6]幸运的是，逻辑学中有完备的推断过程，其表达能力足以处理许多知识库。比如说，在第3章的无限搜索空间的情形中，深度优先搜索就是不完备的。我们已经描述了一个推理过程，在前提为真的任何世界中都保证结论为真。具体来说，如果KB在真实世界中为真，则用可靠的推断过程从KB中推出的所有语句在真实世界中也为真。因此，当推断过程在“语法”（例如，寄存器中的位或大脑中的电信号模式这样的内部物理结构）上进行操作时，这个过程对应于一个真实世界的关系，即真实世界的某个部分为真是因为真实世界的其他一些部分为真。[7]这种世界与表示的对应如图7-6所示。正如路德维希•维特根斯坦（Ludwig Wittgenstein）在其著名的《逻辑哲学论》（Tractatus）（Wittgenstein,1922）中所述：“世界就是所有为真的一切。”最后要考虑的问题是落地，也就是逻辑推理过程与智能体所存在的真实环境的联系。尤其是，我们如何知道KB在真实世界中为真？（毕竟KB只是存在于智能体头脑中的“语法”。）这是一个哲学问题，众多的书籍都对此进行了讨论（见第27章）。一个简单的回答是，智能体的传感器创建了这个联系。例如，我们的wumpus世界智能体有嗅觉传感器。一旦有气味，智能体程序就会创建一条合适的语句。因此，一旦这条语句被包含在知识库中，就意味着它在真实世界中也为真。这样，感知语句的含义和真值就是由产生这些语句的感知过程和语句构建过程定义的。那么智能体知识的其他部分呢？例如，它对于“wumpus相邻的方格有臭味”这件事的信念呢？这不是单个感知的直接表示，而是一项一般规则，它可能是从感知的经验推导出的，却与经验陈述并不完全相同。这种一般规则是通过被称为学习部分的主题。学习是难免会出错的。一种可能的情况是，wumpus有臭味但闰年2月29日这一天除外，因为这一天它要洗澡。因此，KB在真实世界中可能并不为真，但因为有很好的学习过程，我们对此就有理由乐观。图7-6 语句是智能体的物理结构，而推理是从旧结构构建新结构的过程。逻辑推理应当确保结构所表示的部分世界确实能够从旧结构所表示的部分世界推得命题逻辑：一种非常简单的逻辑本节讲解命题逻辑（propositionallogic）。我们将阐述其语法（即语句的结构）和语义（确定语句真值的方法）。由此，我们将推导出一个简单的、语法的逻辑推断算法，它能够实现蕴含的语义概念。当然，这一切都仍将发生在wumpus世界中。语法命题逻辑的语法定义合法的语句。原子语句（atomic sentence）单个命题符号（propositionsymbol）构成。每个这样的符号代表一个为真或假的命题。我们使用以大写字母开头的、可能包含其他字母或下标的符号来表示，例如P、Q、R、W1,3以及FacingEast等。我们可以任意地进行命名，但通常选择一些有助记功能的名字，例如，使用W1,3代表“wumpus位于[1, 3]”。请记住，像W1,3这样的符号是原子的，也就说分开的W、1、3并非符号的有意义的部分。）有两个命题符号有固定的含义：True是永真命题，False是永假命题。使用括号和被称作逻辑联结词（logical connective）的运算符可以将简单语句构造成复合语句（complexsentence）。常用的联结词有5个。）。类似这样的语句称为W1,3的否定。一个文字要是原子语句，即正文字，要么是原子语句的否定，即负文字。∧（与）。主要联结词是∧的语句称为合取式，例其各部分称为合取子句。（∧看起来像是“And”中的“A”。）∨（或）。主要联结词是∨的语句称为析取式，例如，其各部分为析取子句，本例中分别为和W2,2。涵）。如这样的语句称为蕴涵式（implication）或条件式，其前提（premise）或前件（antecedent）是，其结论（conclusion）或后件（consequent）。蕴涵式也被称为规则（rule）或if-then声明。有时，蕴涵符号在一些书籍中写作或。且仅当）。语句是双向蕴涵式（biconditional）。图7-7给出了命题逻辑的形式文法。［附录B将会介绍巴克斯-诺尔范式（Backus-Naur 的概念。］我们在BNF文法上附加了运算符优先级，以避免在使用多个运算符时出现歧义。“非”运算符的优先级最高，这意味着在语句中，的结合力更强，因此它等价于而不是。（这与普通算术一样：−2+4等于2而不是−6。）我们也会适时地使用圆括号和方括号来明确语句结构，以改善可读性。图7-7 命题逻辑中语句的BNF文法以及从高到低排列的运算符优先级语义了解了命题逻辑的语法后，我们来说明其语义。语义定义了用于判定特定模型中语句真值的规则。命题逻辑中，模型就是对每个命题符号设定真值，即真（true）或假（false）。例如，如果知识库中的语句使用了命题符号P1,2、P2,2和P3,1，则一个可能模型为由于含有3个命题符号，因此有23=8种可能的模型，与图7-5所示的完全相同。但要注意，这些模型是纯粹的数学对象，不必与wumpus世界有关。P1,2只是符号，它可能代表“[1,2]中有无底洞”，也可能代表“我今天和明天都在巴黎”。命题逻辑的语义必须指定在给定模型下如何计算任一语句的真值。这是以递归的方式实现的。所有语句都是由原子语句和5个联结词构建的。因此，我们需要指定如何计算原子语句的真值和用5个联结词构建的语句的真值。对原子语句来说这很简单。true在每个模型里都为真，false在每个模型里都为假。的模型m1中，P1,2为假。对于复合语句，有5条规则，它们对任一模型m中的任一子句P和Q（原子语句或复合语句）都成立。为真，当且仅当在m中P为假。●为真，当且仅当在m中P和Q都为真。●为真，当且仅当在m中P或Q中至少一个为真。●为真，除非在m中P为真而Q为假。●为真，当且仅当在m中P和Q都为真或都为假。这些规则也可以用真值表表示。真值表指明在对复合语句的组成部分进行每种可能的真值赋值后，该复合语句的真值。图7-8给出了5个联结词的真值表。任一语句s关于任一模型m的真值都可以用简单的递归求值来计算。例如，在模型m1中求语句 的值，得到。习题7.TRUV要求写出算法,，用于计算命题逻辑语句在模型中的真值。图7-85个逻辑联结词的真值表。若要使用真值表计算在P为真、Q为假时的值，首先而Q为false的行（第3行），然后找到该行位于列处的值，得到结果true“与”“或”“非”的真值表与我们对这些词的直观认识非常接近。可能会混淆的关键点是当P为真或Q为真，或者二者同时为真时，为真。而另一个联结词“排他或”（简称“异或”）。[8]排他或没有公认的符号，有些人选择使、或者⊕。在拉丁语中，“或”用两个词表示：“vel”是相容或，“aut”是排他或。⇒的真值表可能不太符合人们对“P蕴涵Q”或“若P则Q”的直观理解。一种解释是，命题逻辑并不要求P和Q之间有任何因果关系或相关性。（在一般的理解下）语句“5是奇数蕴涵东京是日本的首都”逻辑中的真语句，尽管这句话相当奇怪。另一个容易混淆之处在于前件为假的所有蕴涵式都为真。例如，“5是偶数蕴涵Sam很聪明”是否聪明。这似乎很怪异，但如果你将”当作“如果P为真，则我可以断言Q为真，否则我无法断言”的话，就可以理解了。这条语句为假的唯一情形是当P为真而Q为假时。当与均为真时，双向蕴涵式为真，英语中常写作“PifandonlyifQ”（P当且仅当Q）。wumpus世界的大部分规则都可以用很好地表示。例如，当一个方格的相邻方格中有无底洞，该方格有微风，而且，仅当一个方格的某个相邻方格中有无底洞，该方格有微风。因此，我们需要使用双向蕴涵式其中B1,1代表[1,1]有微风。一个简单的知识库我们已经定义了命题逻辑的语义，现在可以为wumpus世界构建一个知识库了。首先关注wumpus世界的不变部分，后面章节再处理其可变部分。对于每个位置[x,y]，需要用到下列符号：当[x,y]有无底洞，Px,y为真。当wumpus在[x,y]，不论其死活Wx,y都为真。当[x,y]有微风，Bx,y为真。当[x,y]处有臭味，Sx,y为真。当智能体位于位置[x,y]，Lx,y为真。我们写下的语句将足以推得（[1, 2]中没有无底洞），正如7.3节用非形式化的方法所做的那样。我们用Ri代表每个语句，以便推导。[1,1]中没有无底洞：方格都进行这样的表示，在此我们只写出相关方格的表示：上述语句在所有wumpus个特定世界中已访问过的前两个方格引入微风感知，以形成图7-3b所示的情形：一个简单的推断过程我们现在的目标是确定对于一些语句，是否成立。例如，我们的KB是否蕴含？我们的第一个推理算法是模型检验方法，它直接实现了蕴含的定义：枚举所有模型，检验在KB为真的每个模型中是否为真。模型是对每个命题符号进行真或假的赋值。回到例子中的wumpus世界，它涉及的命题符号是B1,1、B2,1、P1,1、P1,2、P2,1、P2,21。在有7个符号的情况下，总共有27=128个可能的模型，KB在中3个模型中为真（如图7-9所示）。在这3个模型中，为真，因此[1, 2]中没有无底洞。但是，在3个模型中，P2, 2在其中两个模型中为真，在另一个模型中为假，因此我们还无法确定[2,2]中是否有无底洞。图7-9以更准确的形式再现了图7-5所示的推理。图7-10描述了一个确定命题逻辑中蕴含关系的通用算法。与6.3节所示的BACKTRACKING-SEARCH算法类似，TT-ENTAILS?在符号赋值的有限空间中进行递归枚举。这个算法是可靠的，因为它直接实现了蕴含的定义；这个算法也是完备的，因为它对所有KB和都适用，并且算法最后都会终止——因为需要检验的模型数量是有限的。图7-9 根据文中所述的知识库构建的真值表。如果从R1到R5都为true，则KB为true。这种情况在全部128行中只出现了3次（在最右侧的列中用下划线标出）。在这3行中，P1,2均为false，此[1,2]中没有无底洞。但是，[2,2]中可能有（也可能没有）无底洞图7-10 用于确定命题蕴含的真值表枚举算法（TT代表真值表）。当语句在一个模型中成立，PL-TRUE?返回true。变量model代表部分模型——对于部分符号的赋值。此处的关键字and不是命题逻辑中的运算符，而是伪代码编程语言中的中缀；如果其两个参数中的任意一个为true，则回true当然，“有限数量”并不总是等同于“少量”。如果KB和总共含有n个符号，那么就会有2n个模型。这样，算法的时间复杂性就会达到O(2n)。（空间复杂性仅为O(n)，因为枚举是深度优先的。）在本章稍后部分，我们将展示一个在大多数情况下更高效的算法。遗憾的是，命题蕴含是余NP完全的（即很可能不比NP完全简单，见附录A），因此命题逻辑所有已知推断算法的最坏情况复杂性都是输入规模的指数量级。命题定理证明至此，我们已经展示了如何用模型检验判定蕴含关系：枚举模型，并验证语句在所有模型中必须成立。本节将展示如何通过定理证明找出蕴含关系。定理证明对知识库中的语句直接应用推断规则，它能够在不检验模型的情况下，构建对所需语句的证明。如果模型的数量很多，但其证明很短，则定理证明会比模型检验更为高效。在深入定理证明算法的细节之前，我们还需要了解一些与蕴含相关的概念。第一个概念是逻辑等价（logicalequivalence）：如果两个语句和在相同的模型集合中都为真，则这两个语句逻辑等价，可以写作。（注意，用于对语句进行声明，而则用作语句的一部分。）例如，我们可以很容易地（用真值表）证明与是逻辑等的。其他逻辑等价见图7-11恒等式在普通数学中的角色非常相似。等价的另一种定义为“任意两条语句和是等价的，当且仅当它们互相蕴含”：当且仅当且第二个概念是有效性（validity）。如果一条语句在所有真，则这条语句是有效的。例如，语句是有效的。有效的语句也被称为重言式（tautology）——它们必然为真。由于语句True在所有模型中都为真，所有有效的语句都逻辑等价于True。有效语句有什么用？从蕴含的定义可以推导出古希腊人早已懂得的演绎定理（deductiontheorem）：对于任意语句和，当且仅当语句是有效的。（习题7.DEDU要求对其进行证明。）因此，可以像图7-10推断算法那样，通过检验是否在每个模型中为真来确定是否成立，或者通过证明等价于True来确定是否成立。反过来，演绎定理表明每条有效的蕴涵语句都描述一个合法的推断。图7-11 标准的逻辑等价。符号、、代表任意命题逻辑语句最后一个概念是可满足性（satisfiability）。如果一条语句在某些模型中为真或能够被满足，则这条语句是可满足的。例如，前述的知识库中，是可满足的，因为如图7-9所示，它在3模型中为真。可以通过枚举可能的模型，直到找出满足语句的模型来验证可满足性。在命题逻辑中确定语句的可满足性的问题——SAT问题——是第一个被证明为NP完全的问题。计算机科学中的许多问题实际上都是可满足性问题。例如，第6可以通过某种赋值来满足。有效性和可满足性当然是有联系的：是有效的，当且仅当是不得出下述非常有用的结论：当且仅当语句是不可满足的通过检验的不可满足性，可以从证明，这正是数学证明方法中标准的归谬法（reductio ad absurdum，意为“归结为荒谬物”）。它也被称为反证法或矛盾法。假为假，并证明这会导致与已知公理矛盾，这个矛盾的含义与声明语句是不可满足的完全相同。推断与证明本节介绍可以用于推导证明的推断规则。证明是一系列可以引向所需目标的结论。最著名的规则是肯定前件（ModusPonens，modethataffirms的拉丁语），写作它的意思是，当给出和具有形式的语句时，可以推导出语句。例如，如果给出，并且已知，可以推导出Shoot。另一个有用的推断规则是合取消去（and-elimination），即可以从一个合取式推导出任一合取子句：例如，由，可推导出WumpusAlive。通过考虑和的可能真值，可以证明肯定前件和合取消去是可靠靠的推断。图7-11所示的所有逻辑等价都可以用作推断规则。例如，等价消去可以产生两条推断规则：肯定前件规则，从得出和。让我们来看看这些推断规则和等价关系是如何应用于wumpus世界的。我们从含有R1到R5的知识库开始，演示如何证明 ，即证明[1,2]中没有无底洞。假言易位逻辑等价关系得到对R8和感知R4（即 ）使用肯定前件，得到使用德摩根律，得到结论也就是，[1,2]和[2,1]都没有无底洞。应用第3章的任意搜索算法都可以找到构成这种证明的一系列步骤。只需要定义如下的证明问题。初始状态（L）：最初的知识库。动作（）：合上半部分推断规则的语句。结果（）：例加入知识库。目标（）：目标是含有我们试图证明的语句的状态。这样，搜索证明就可以替代枚举模型。在许多实际案例中，找出某有多少。例如，刚才给出的，得出的证明并没有提及命题B2,1、P1,1、P2,2或P3,1。由于目标命题P2,1只出现于语句R2，因此可以忽略它们；而R2中的其他命题只出现在R4和R2中，因此R1、R3和R5与证明单的真值表算法将无法承受这种模型的指数级爆炸式增长。逻辑系统的最后一个属性是单调性信息被加入知识库而增长。[9]对于任意语句，违反单调性的非单调逻辑刻画了人类推理的常见性质：改变想法。我们将在10.6行讨论。如果 ，则例如，假设知识库含有额外的断言，它表明世界中恰好有8个无洞。这条知识可能有助于智能体得出额外的结论，但它不能使任何已经得出的结论失效，例如[1,2]中没有无底洞这样的结论。单调性意味着只要在知识库中找到合适的前提，就可以使用推断规则——规则的结论必然是合理的，不论知识库中还有什么东西。通过归结证明我们已经论证了目前所说的推断规则是可靠的，但还没讨论过使用这些规则的推断算法的完备性问题。像迭代加深搜索（3.4.4节）这样的搜索算法能够找到任意的可达目标，从这种意义上说它是完备的；但如果可用的推断规则不充分，则目标是不可达的——仅使用这些推断规则的证明是不存在的。例如，如果去掉等价消去规则，7.5.1节所述的证明就行不通了。本节我们只介绍一个推断规则——归结（resolution），当它与任意完备的搜索算法结合后，可以产生一个完备的推断算法。我们从在wumpus世界使用简单的归结规则入手。考虑导致图7-4a所示状态的步骤开始：智能体从[2,1]返回到[1,1]，然后走到[1,2]此处感知到臭味，但没有微风。我们将如下事实添加到知识库中：用先前推得R10时使用的相同步骤，可以推出[2,2]和[1,3]中没有无底洞（别忘了已知[1,1]中没有无底洞）：还可以对R3使用等价消去，然后对R5使用肯定前件，以得到[1,1]、[2,2]或[3,1]中有无底洞的事实：现在我们首次运用归结规则：R13中的文字与R15中的文字归结，得到归结句（resolvent）用自然语言描述：如果[1,1]、[2,2]或[3,1]中必有无底洞，而[2,2]中没有无底洞，则无底洞在[1, 1]或[3, 中的文与R16中的文字P1,1归结，得到用自然语言描述：如果[1,1]或[3,1]中有无底洞，无底洞又不在[1,1]中，则它在[3,1]中。最后两步推断采用了单元归结（unitresolution）规则其中每个都是文字，而和m是互补文字（即各自是对方的否定）。这样，单元归结推断规则使用一个子句（文字的析取式）以及一个文字，生成一个新的子句。注意，单个文字可看作是一个文字的析取式，也被称为单元子句。单元归结规则可以推广为全归结规则其中，li和mj是互补文字。这表明归结使用两个子句并产生一个新的子句，该新子句包含除一对互补文字以外的原始子句的所有文字，例如，我们有可以一次只归结一对互补文字。例如，可以归结P和 推得但不能同时归结P和Q来推得R子句只能含有每个文字的一个副本。[10]去除文字的多个副本被称为因子提取。例如，如果我们归，得，通过因子提取简化为A。如果一个子句被视作文字的集合，则这条限制自然地适用。对子句使用集合的概念可以通过对文字和另一个子句中的互补文字mj的讨论，我们可以很易理解归结规则的可靠性。如果为真，则mj为假，因此必然为真，因为已知。如果为假，则必为真，因为已知。现无为真还是为假，结论必然成立，这与归结法则所述的完全相同。础。基于归结的定理证明器可以对命题逻辑中的任意语句和确定是否成立。接下来的“合取范式”和“归结算法”两小节将解释归结是如何完成这项任务的。合取范式归结规则仅适用于子句（也就是文字的析取式），因此它似乎只能用于含有子句的知识库和查询。那么对于所有命题逻辑，它如何实现完备的推断过程？答案是，命题逻辑的所有语句逻辑上都等价于子句合取式。形式为子句合取式的语句被称为合取范式（conjunctive normalform）或CNF（见图7-12）。下面介绍把语句转换为CNF的过程。我们通过将语句转换为CNF来阐明这一过程。转换的步如下。消去，将替换为：消去，将替换为CNF要求只能在文字前出现，因此我们反复应用图7-11下等价关系“将内移”：（双重否定律）（德摩根律（德摩根律本例中，我们只需运用最后一条规则一次：语句。运用图7-11的分配律，尽可能地对∧分配∨：原始语句现在已经成为CNF，是3个子句的合取式。它读起来难了很多，但它可以作为归结过程的输入。图7-12 合取范式、霍恩子句、确定子句、目标子句的文法。形式如这样的CNF子句可以写成确定子句归结算法基于归结的推断过程使用7.5.1节介绍的反证法来进行证明。也就是说，为了证明，我们要证明是不可满足的。我们通证明矛盾来做到这一点。图7-13展示了一个归结算法。首先，被转换为CNF。然持续，直到发生下述的两件事情之一。没有可供添加的新子句，此时KB不蕴含；两个子句归结为空子句，此时KB蕴含。图7-13 单的命题逻辑归结算法。PL-RESOLVE返回对其两个输入进行归结得到的所有可能子句集合空子句是一个没有析取子句的析取式，它等价于False，因为仅当至少一个析取子句为真时析取式为真。另外，空子句仅在归结两个矛的单元子句（如P和 ）时出现。我们可以将归结过程用在wumpus世界中一个很简单的推断中。当智能体位于[1,1]时，该处没有微风，因此相邻的方格没有无底洞。相关的知识库是我们要证明，即。如果将转换为CNF，我们就能得到在图7-14顶部所示的子句。该图的第二行列出了归结第一行后的句。随后，当P1,2与 归结后，我们得到了空子句，用小方块表示。观察图7-14，可以发现许多归结是毫无意义的。例如，子句等价于，进而等价于True。推出True为真并有什么用处。因此，我们可以忽略所有含有两个互补文字的子句。图7-14 界的一个简单推断部分运用PL-RESOLUTION来证明查。顶行最左侧的4个子句的每一个与其他3个都互相成对，运用归结规则产生底行的子句。顶行的第3个和第4个句结合生成 ，它继而与P1,2归结，生成空子句，表明查询被证明归结的完备性作为对归结的讨论的总结，现在来了解为何PL-RESOLUTION是完备的。为此，我们引入子句集合S的归结闭包（resolutionclosure）RC(S)，即对S中子句及其生成子句反复使用归结规则可推得的所有子句的集合。归结闭包就是RL-RESOLUTION计算所得的变量clauses的最终值。易知RC(S)必然是有限的：得益于因子提取，由S中出现的符号P1,…,Pk得出的子句数量是有限的。因此，总是能够终止。命题逻辑中归结的完备性定理被称为基本归结定理（groundresolutiontheorem）：如果一个子句集是不可满足的，则这些子句的归结闭包含有空子句。定理的证明是通过其假言易位进行的：如果闭包RC(S)不含有空子句，则S可满足。实际上，可以为S构建一个在P1,…,Pk上有适当真值的模型。构建过程如下：对于i从1到k，如果RC(S)中的子句含有文字 且所有其他文字在对P1,…,Pi−1选定的赋值下为假，则对Pi赋值为false；否则，对Pi赋值为true。对P1,…,Pk的赋值是S反面——在序列中的某处i，对符号Pi赋值使得某个子句C为假。此时，情况必然是C中所有其他文字都已经被对P1,…,Pi−1，C的形式必然类或。如果只有其中一个在RC(S)中，则算法将对Pi赋适当的值以使C为真，因此仅在这两个子句都在RC(S)中时，C才会为假。现在，由于RC(S)在归结时是闭的，它会含有这两个子句的归结句，且这个归结句的所有文字已经被对P1,…,Pi−1的赋值定为假。这与我们的假设，即第一个为假的子句出现在i处矛盾。因此，我们证明了这种构建永远无法使RC(S)中的子句为假，也就是说它创建了一个RC(S)的模型。最后，由于S包含在RC(S)中，因此任意RC(S)的模型也是S本身的模型。霍恩子句与确定子句归结的完备性使其成为一种非常重要的推断方法。而许多实际情形并不需要用到归结的全部能力。一些真实世界的知识库中的语句满足某些限制，这使得它们可以使用更为受限而更高效的推断算法。其中一种受限形式是确定子句（definiteclause），它是文字的析取式，其中只有一个为正文字。例如，子句是确定子句而不是，因为它含有两个正文字。更一般性的是霍恩子句（Hornclause），它是文字的析取式，其中最多只有一个为正文字。因此所有的确定子句都是霍恩子句，没有正文字的子句也是霍恩子句——也被称为目标子句（goalclause）。霍恩子句在归结时是闭的：如果归结两个霍恩子句，仍然会得到霍恩子句。还有一种类型是k-CNF语句，它是每个子句最多含有k个文字的CNF语句。仅含有确定子句的知识库很有意义，原因有3个。式，结论是一个正文字。（见习题7.DISJ。）例如，确定子句可以写成蕴涵式。蕴涵形式的语句更容易理解：它说明如果智能体位于[1, 1]，且感知到微风，[1, 1]有微风。在霍恩形式中，前提被称为体（body）而结论被称为头（head）。由单个正文字构成的语句，例如L1,1，被称为事实（fact）。它也可以写成 形式的蕴涵式，但只写成L1,1更为简洁。用霍恩子句进行推断可以通过前向链接（forward-chaining）算法和反向链接（backward-chaining）算法完成，我们稍后会介绍。这些算法都很自然，因为它们的推断步骤很直观，便于人类理解。这类推断是逻辑编程（logicprogramming）的基础，我们将在第9章进行讨论。系，这格外令人满意。前向链接与反向链接前向链接算法PL-FC-ENTAILS?(KB,q)确定单个命题符号q（即查询）是否被确定子句的知识库所蕴含。它从知识库中的已知事实（正文字）开始。如果一个蕴涵式的所有前提都已知，则将其结论添加到已知事实的集合中。例如，如果L1,1和Breeze已知，且 在知识库中，则在知识库中添加B1,1。这一过程持续进行，直到查询q被添加，直到无法进一步进行推断。这一算法在图7-15中展示，我们要记住的要点是它的运行时间是线性的。用图和示例来理解算法是最好的办法。图7-16a展示了一个简单的霍恩子句知识库，其中有A和B两个已知事实。图7-16b展示了绘制为与或图（见第4章）的同一个知识库。在与或图中，用曲线连接的多个边表示一个合取式，每个边都要证明；而没有曲线连接的多个边表示一个析取式，证明任一边即可。图上很容易看懂前向链接是如何运作的。已知的叶节点（此处为A和B）具有真值之后，推断就会沿着图尽可能远地向上传递。当出现合取式时，传递过程开始等待，直到所有合取子句都已知。我们鼓励读者细致地研究这个示例。图7-15 命题逻辑的前向链接算法。queue记录了已知为真但还没“处理过”的符号。表count记录每个蕴涵式尚未证明的前提数量。一旦queue中的新符号p被处理，count就会为每个前提中出现p的蕴涵式减1（使用合适的索引方法，很容易在常数时间内完成）。如果count为0，则蕴涵式的所有前提都已知，因此其结论可以添加到queue。最后，我们还需要记录哪个符号已经被处过，如此在已推断符号集inferred中的符号就无需被再次加入queue。这避免了重复的工作，也避免了由类似P⇒Q和Q⇒P这样的蕴涵式引起的循环图7-16 （a）一个霍恩子句集。（b）相应的与或图显然，前向链接是可靠的：每个推断实际上都是对肯定前件的运用。前向链接也是完备的一点，最简单的方法是考虑（在算法到达不动点，无法产生新推断的时候）inferred表格的最终状态。该表中每个推得的符号都为真，所有其他符号都为假。我们可以将这个表看作一个逻辑模型，且原始KB的每条确定子句在这个模型中都为真。为理解这一点，可以假设其反面，即存在子句在模型中为假。则在模型中必然为真，且b在模型中必然为假。这与我们假设的算法已经到达不动点相矛盾，因为我们此时可以将b加入始知识库的模型。更进一步地，知识库蕴含的任意原子语句q必然在其语句q必然会被算法推得。前向链接是数据驱动（data-driven）推理这一更广泛概念的例子，也就是其注意力开始集中在已知数据的推理。它可以用于智能体，以便从收到的感知推导出结论，且常常是在没有特定查询的情况下。例如，wumpus世界的智能体可以用递增前向链接算法（即新的事实可以被加入队列来启动新的推断）将它的感知告知知识库。对人类来说，当获取新信息后会出现一定数量的数据驱动推理。例如，如果我在屋子里听到外面开始下雨，则我可能会想到取消野餐；但是，我大概不会想到邻居花园里最大的一朵玫瑰的第17片花瓣会淋湿——人类会对前向链接进行精心地控制，以免被无关的结果淹没。反向链接算法如其名称所示，从查询开始反向运作。如果查询q已知为真，则不需要做任何操作。否则，算法将在知识库中找寻结论为q的蕴涵式。如果这些蕴涵式的所有前提都可以（用反向链接）证明为真，则q为真。将反向链接算法用于图7-16的查询Q下方运行，直到到达构成证明基础的已知事实集，即A和B。算法实质上与图411的算法完全相同。与前向链接一样，它的高效实现的时间复杂性是线性的。反向链接是一种目标导向推理（goal-directed reasoning）。它对回答类似“我现在该做什么？”和“我的钥匙在哪里？”这样的特定问题非常有用。通常，反向链接的代价远小于知识库规模的线性变化，因为这个过程仅涉及相关的事实。高效命题模型检验本节，我们介绍两种高效的、基于模型检验的一般命题推断的算法是命题逻辑的“技术”部分。首次阅读本章时可以略过本节内容。我们描述的算法是用于可满足性检验的，即SAT问题。（如7.5述，可以通过检验的不可满足性来检验蕴含。）我们在7.5节中提到过找到满足逻辑语句的模型与找到约束满足问题的解的关系，因此这两种命题可满足性算法与6.3节的回溯算法和6.4节的局部搜索算法非常相似并不令人意外。尽管如此，这些算法本身还是极为重要的，因为许多计算机科学中的组合问题都可以被归为检验命题语句的可满足性。对可满足性算法的任何改进对于我们处理复杂性的能力都有巨大的作用。完备的回溯算法我们要探讨的第一个算法常称为戴维斯-普特南算法（Davis-Putnamalgorithm），得名于马丁·戴维斯（MartinDavis）和希拉里·普特南（HilaryPutnam）的重要论文（DavisandPutnam,1960）。这个算法实际上采用的是戴维斯、洛吉曼和洛夫兰所描述的版本（Davis,Logemann,andLoveland,1962），因此我们用所有4位作者姓氏的首字母DPLL命名这个算法。DPLL使用一个合取范式形式（即一个子句集）的语句作为输入。类似于和，它本质上是递归地、深度优先地枚举可能的模型。它在的基础上进行了3项改进。提前终止：或为假。如果任一文字为真则子句为真，即使其他文字还没有真值；这样，整条语句在模型完成之前就可以断定其真值。例如，若A为真则语句为真，无论B和C的值是什么。类似地，若任一子句为假，即其所有文字为假，则语句为假。同样，这种情形可能会在模型完成前很久就发生。提前终止避免了在搜索空间中检查全部子树。纯符号启发式方法：纯符号是指在所有子句中“符号位”符号。例如，在3个子句、和中，A是纯符号，因为它只以正文字的形式出现；B也是纯符号，因为它总以负文字的形式出现。而C是不纯的。易知如果一条语句有模型，则存在一个模型对纯符号的赋值使其文字为真，因为这样做不会使子句为假。注意，在确定符号是否为纯时，算法可以忽略当前已构建的模型中已知为真的果上述模型含有B=false，则子已经为真，且在剩余子句中C仅作为正文字出现，因此C变为纯符号。单元子句启发式方法：之前对单元子句的定义是只有一个文字子句。在DPLL中，它也指那些除了一个文字外，其余文字都被模型赋值为false的子句。例如，如果模型含有B = 简化为，这是一个单元子句。显然，要使这个子句为真，C必须赋值为false。单元子句启发式方法在余下的部分出现分支前对所有这样的符号赋值。这种启发式的一个重要结果是，所有对知识库中的已有文字进行的证明（通过反证法）将立刻得证（见习题7. KNOW）。还要注意的是，对一个单元子句赋值可能会创建另一个单元子句，例如，当C被置为假，也变成了单元子句，使得A被赋值为真。这种强制赋值的“级联”被称为单元传播（unit propagation）。这类似于确定子句的向链接。实际上，如果CNF表达式仅含有确定子句，则DPLL本质上复制了前向链接。（见习题7.DPLL。）DPLL算法如图7-17所示，它给出了搜索程序的主要结构，但并未实现其细节。图7-17 用于检验命题逻辑语句可满足性的DPLL算法。FIND-PURE-SYMBOL和FIND-UNIT-CLAUSE背后的思路在正文中进行了介绍。这两个函数都返回一个符号（或返回空）以及要赋给这个符号的值。和TT-ENTAILS?一样，DPLL在部分模型上运行图7-17没有展示使SAT求解器能够用于大规模问题的技巧。有趣的是，这些技巧实际上都很寻常，我们之前已经见过它们的其他形式。分量分析（如CSP中的塔斯马尼亚岛问题所见）：当DPLL为变量赋真值时，子句集可能会被分割成不相交的子集，我们称之为分量求解器就可以通过对每个分量独立求解来加快速度。变量排序与值排序（如在6.3.1节的CSP中所见）：我们对DPLL的简单实现使用任意的变量顺序，并在赋值时总是先尝试赋真再尝试赋假。度启发式算法（6.3.1节）常出现的变量。智能回溯（如在6.3.3节的CSP中所见）：许多用按时序回溯关点上，那么问题可以在几秒内求解。所有运用智能回溯的SAT求解器都使用冲突子句学习的某种形式来记录冲突，以避免在后续的搜索中重复出现。通常只保留有限大小的冲突集，丢弃极少使用的冲突。随机重启（在4.1.1节用于爬山法）：有时单次运行似乎无法索。重启后（对变量和值选取）并不保证能更快地找到解，但它能够减小求解时间的方差。聪明索引（在许多算法中可以见到）：DPLL器用到的加速方法需要快速索引“Xi作为正文字出现的子句集合”。这一任务相当复杂，因为算法所感兴趣的只是先前的变量赋值尚未满足的子句，因此索引结构必须在计算过程中动态更新。有了这些改进，现代求解器可以处理有数千万个变量的问题。它们为诸如硬件验证和安全协议验证这样的领域带来革命性的变化。在此之前，这些领域需要十分费力的、手动证明。局部搜索算法我们已经在本书中见过了一些局部搜索算法，包括HILL-CLIMBING（4.1.1节）和SIMULATED-ANNEALING（4.1.2节）。只要我们选择了正确的评价函数，这些算法可就以被直接用于可满足性问题。由于目标是找出满足所有子句的赋值，一个对未满足的子句进行计数的评价函数就可以胜任这项工作。实际上，这正是用于CSP的MIN-CONFLICT算法所使用的量度（见6.4节）。这些算法都在完全赋值的空间采取动作，每次只翻转一个符号的真值。这个空间通常含有许多局部极小值，要跳出这些极小值，需要各种形式的随机方法。近年来，人们进行了大量实验，试图在贪婪性与随机性之间找到一个良好的平衡。这些算法中最为简单和有效的算法之一是（如图718所示）。算法每次循环都选择一个未满足的子句，并在该子句中选择一个符号来翻转。选择要翻转的符号的方法有两种：（1）最小化新状态中未满足子句的数量的“最小冲突”方法；（2）随机挑选一个符号的“随机游走”方法。算法随机选取一种。图7-18 通过随机翻转变量的值来检验可满足性的WALKSAT算法。这个算法有很多版本当返回一个模型时，输入语句就是可满足的。但当它返回failure时，则有两种可能的原因：语句不可满足，或我们需要多给算法一些时间。如果我们设定且p 0，最终将返回个模型（如果存在的话），因为随机游走步骤终将遇到一个解。如果max_flips为无穷大，而语句不可满足，则算法永远不会终止！因此，当我们预计问题有解的时候，WALKSAT最为有用。例如，第3章和第6章讨论过的问题通常有解。但是，WALKSAT并不总是能检测到不可满足性，而对判定蕴含来说这是必备的。例如，wumpus世界中，一个智能体不能使用WALKSAT来可靠地证明一个方格是安全的。不过，它可以说：“我思考了一小时，都想不出存在一种这个方格不安全的可能世界。”这也许是个不错的经验性指示，表明方格是安全的，但它绝对不是一种证明。随机SAT问题概览某些SAT问题比其他要难。简单的问题可以用任意老算法求解，但由于我们知道SAT是NP完全的，至少有一些问题必须需要指数级的运行时间。在第6章中，我们见过一些针对某种问题的惊人发现。例如，对于回溯搜索算法，n皇后问题被认为是相当困难的，而对于局部搜索方法，如最小冲突法，求解这一问题却非常容易。这是由于在赋值空间中，解的分布非常密集，任意初始赋值都能保证在其附近存在解。因此，n皇后问题很简单，因为它是欠约束的（underconstrained）。当我们考虑合取范式的可满足性问题时，一个欠约束的问题是约束变量的子句非常少的情形。例如，下面是一条随机生成的3-CNF语句，它有5个符号和5个子句：在32个可能的赋值中，有16个是这条语句的模型。因此，平均而束问题一样，这是一个简单的可满足性问题。但是，一个过约束法逃离的死胡同。要超越这些基本的直观理解，我们必须明确定义如何生成随机语句。记法CNFk(m, n)表示一个有m个子句、n个符号的k-CNF语句，其子句是均匀地、独立地、无放回地从所有有k个文字的子句中选取的，文字的正负也是随机的。（一个符号在子句中不能多次出现，一个子句也不能在语句中多次出现。）给定一个随机语句源，我们就可以测量可满足性的概率。图7-19a绘制了CNF3(m, 50)的概率，也就是有50个变量、每条子句有3个文字语句，这一概率被绘制为子句/符号，即m/n的函数。如我们预期，对于较小的m/n，可满足性的概率接近0，而在较大的m/n处这一概率接近0。概率在m/n=4.3左右急剧下降。经验上，我们发现这一“峭壁”致相同的位置（对于k3），并随着n的增长越来越陡峭。理论上，可满足性阈值猜想（satisfiabilitythresholdconjecture）表明对所有，存在一个阈值比rk，使得当n接近无穷时CNFk(rn, n)满足的概率对于所有低于阈值的r接近于1，对于所有高于阈值的r接近于0。即便对于如k=3这样的特例，这一猜想仍未被证明。不论这是是一个定理，这样的阈值效应在可满足性问题和其他类型的NP困难问题中都是相当寻常的。现在我们对可满足和不可满足问题分别会出现在什么地方有了很好的了解，接下来的问题是，困难的问题会出现在什么地方？其实它们也经常位于阈值处。图7-19b显示，阈值4.3处的50个符号的问题比阈值3.3处的相同问题大约难20倍。欠约束问题很好求解（因为很容易就能猜到一个解），而过约束问题不如欠约束问题简单，却仍然比恰好在阈值处的问题简单得多。图7-19 （a）有n个符号的随机3-CNF语句的可满足概率图，概率是子句/符号比m/n的函数。（b）DPLL和WALKSAT在随机3-CNF语句上的（多次运行后测量的）运行时间中位数图。最为困难的问题的子句/符号比约为4.3基于命题逻辑的智能体本节我们将目前所学的内容结合起来构建使用命题逻辑的wumpus世界智能体。首先我们要使智能体能够根据其历史感知对世界的状态尽可能地进行推导。这需要写出动作效果的完整逻辑模型。随后我们介绍智能体在wumpus世界中如何使用逻辑推断。我们还会介绍智能体如何在不查看每次推断的历史感知的情况下有效地跟踪世界的变化。最后，我们介绍在已知其知识库在实际世界中为真的情况下，智能体如何使用逻辑推断来构建能确保达到目标的规划。世界的当前状态如本章开头所述，逻辑智能体通过用关于世界的语句知识库推导接下来的动作来运作。知识库由公理（也就是关于世界如何运行的一般知识）和从智能体在某个特定世界获得的感知语句构成。本节，我们聚焦于推导wumpus世界的当前状态这一问题，如我在哪里、方格是否安全等。我们从7.4.3节开始收集公理。智能体知道起始方格没有无底洞（）也没有wumpus（）。此外，对于每个方格，它知道当且仅相邻方格有wumpus，该方格有臭味。由此，我们引入了具有如下形式的大量语句：智能体还知道恰恰只有一个wumpus。我们用两部分表示。首先，我们说至少有一个wumpus：然后我们必须说最多只有一个wumpus。我们对每对方格添加一个语句，来表明其中至少一个方格没有wumpus：到目前为止都还不错。现在让我们考虑智能体的感知。我们使用了S1,1来表示[1,1]有臭味，那么我们可以只用一个命题Stench来表示智能体感知到臭味吗？遗憾的是，不行。如果在之前的时间步中没有臭味，就已经被断言，那么新的断言将与之矛盾。我们发现，如果感时间步（与输入图71中的一样）是4，则我们在知识库这样就能轻松地避免与矛盾。对微风、碰撞、闪光和惨叫等感知也同样处理。间变化的部分。例如，最初知识库中有——智能体在时刻0位于[1,1]，以及FacingEast0、HaveArrow0和WumpusAlive0。我们使用流（fluent，源于拉丁语fluens，意为流动）来表示世界随时间变化的部分。“流”与2.4.7节所述的对因子化表示的讨论中的“状态变量”同义。与世界的不变部分相关的符号不需要时间上标，它们有时被称为非时序变量（atemporalvariable）。我们可以将微风和臭味直接与体验到这些感知的方格的属性连接。[11]对任意时间步t和任意方格[x,y]，我们断言7.4.3节出于简便考虑，隐藏了这项要求。当然，现在我们需要能够使智能体跟进像这样的流的公理。智能体采取动作会改变这些流，因此，用第3章的术语来说，我们需要将wumpus世界的转移模型写成逻辑语句的集合。首先我们需要表示发生动作的命题符号。与感知一样，这些符号用时间索引。因此Forward0表示智能体在时刻0执行前进动作。习惯上，给定时间步的感知先发生，然后是这个时间步上的动作，然后是到下一个时间步的转移。为描述世界如何变化，我们可以试着写出指明动作在下一个时间步产生的结果的效应公理（effectaxiom）。例如，如果智能体位于[1,1]，在时刻0时面朝东并向前走，结果是智能体位于方格[2,1][1,1]：（7-1）对每个可能的时间步、16个方格中的每一个方格、4个方向中的每一个方向我们都需要类似这样的语句。对于其他动作，即抓取、射击、攀爬、左转、右转我们也需要类似的语句。假设智能体在时刻0决定向前移动，并在其知识库对此进行了断言。给定式（7-1）的效应公理，结合时刻0体可以推得它位于2,1。也就是，K。到目前为止，切还好。遗憾的是，如果我们, ao1，答案会是假，也就是智能体无法证明它仍然有箭，它也无法证明它没有箭！信息丢失了，因为效应公理没有说明动作的结果未改变哪些状态。对这项功能的需求引出了框架问题。[12]框架问题的一个可能的求解办法是明确地添加断言所有不变命题的框架公理。例如，对于每个时刻t，我们有“框架问题”（frameproblem）的名字来源于物理学中的参照系（frameofreference），也（frame）也借用了它的含义，其中前景变化时，大部分背景保持静止。其中明确地提到了在采取前进动作时所有从时刻t到时刻t+1维持不变状态的命题。尽管智能体现在已经知道它在前进后仍然有箭，且wumpus没有死去或复活，但激增的框架公理似乎相当低效。在有m个不同动作和n个流的世界，框架公理集的大小为O(mn)。这种框架问题被称作表示框架问题。这个问题在人工智能史上扮演过重要的角色，我们在本章最后的参考文献与历史注释中将进行进一步探索。表示框架问题很重要，因为即便保守来说，真实世界中的流也很多。幸运的是，对我们人类来说，每个动作改变的流通常不多于k个（k是某个较小的值），也就是说世界具有局部性定义公理集大小为O(mk)而非O(mn)的转移模型。还有一个问题是推断框架问题：将t步动作规划的结果在O(kt)时间而非O(nt)时间内前向推进的问题。问题的解是关注于写出关于流而非动作的公理。这样的话，对于每个流F，以时刻t时的所有流（包括F本身）和时刻t时可能发生的动作来定义Ft+1的真值的公理。现在，Ft+1的真值可以用两种方法之一来确定：一种是时刻t的动作导致F在t+1为真，另一种是F在时刻t已经为真而时刻t的动作没有导致它为假。这种形式的公理叫作后继状态公理（successor-stateaxiom），具有如下形式：有箭（HaveArrow）新装填箭支的行动，ActionCausesFt部分可以去掉，所以我们有（7-2）对智能体的位置来说，后继状态公理要更为复杂。例如，如果（a）智能体在面向南方时从[1,2]，或面向西方时从[2,1]向前移动，或者（b）已经为真且动作未产生移动（因为动作不是向前或动作导撞墙），则为真。用命题逻辑写出，就是（7-3）习题7.SSAX要求写出剩余的wumpus世界的流的公理。够询问和回答世界当前状态的所有可解答问题。例如，在7.2节，感知和动作的初始序列是此时，有K，因此智能体知道它在什么位置。而且，K和，因此智能体已经找到了wumpus进入，也就是这个方格是否没有无底洞也没有wumpus很容易，形式如下：最后，K，因此方格2, 2可以安全进入。实上，给定一个如DPLL的可靠且完备的推断算法，智能体可以回答关于哪个方格安全的任意可解答问题，而且对于小型到中型的wumpus世界可以在几毫秒内完成回答。求解表示框架问题和推断框架问题是一步重大的前进，但仍有一个亟待解决的问题：我们需要确认一个动作的所有必要的前提都成立才能保证结果效应。我们说过向前动作使智能体向前方移动，除非前方有墙，但也有许多其他意外会导致动作失败：智能体可能会被绊倒，会犯心脏病，会被巨型蝙蝠抓走，诸如此类。明确所有这些意外被称为资格问题（qualification problem）。它在逻辑学的范畴内没有完备的解，决定要多么详细地明确模型以及要忽略哪些细节时，系统设计者必须做出很好的判断。我们将在第12章中看到，概率论允许以非显式的方式总结所有意外。混合智能体推导世界状态的多个方面的能力可以直接与条件-动作规则（见2.4.2节）以及第3章和第4章的问题求解算法结合，产生一个wump