Artificial Intelligence Notes

第二章 知识表示

2.1 知识与知识表示基本概念

• 知识的获取、知识的表示和运用知识进行推理是人工智能学科研究的3个主要问题

2.1.1 知识的含义和结构

• 知识、信息与数据（三个层次的概念）
  • 数据：是记录信息的符号，是信息的载体和表示
  • 信息：是对数据的解释，是数据在具体的场合下具体的含义
  • 知识：把有关信息关联在一起所形成的信息结构

2.1.2 知识的种类与特性

2.1.4 知识表示

• 面向计算机的知识描述或表达的形式和方法
• 知识表示的过程就是把知识编码成某种数据结构的过程

2.2 一阶谓词逻辑表示法

• 个体域 ：个体变元的变化范围

2.2.1 谓词、函数、量词

• n元谓词 ：$P(x_1, x_2, \cdots, x_n)$ 。$P$ 为谓词符号(大写)，$x_i$ 为参量(项/个体)

• n元个体函数(函数)：$f(x_1,x_2,\cdots,x_n)$ 表达个体之间的对应关系。$f$ 函数符号(小写)， $x_i$个体变元

• 量词：

  • 全称量词$\forall x$：“所有”，“一切”，“任一”，“全体”，“凡是”
  • 存在量词$\exist x$ : “存在” “有些” “至少有一个” “有的“

• e.g.

  • (1)所有的人都是要死的

    (2)有的人活到100岁以上

  • 在个体域D为人类集合时，可符号化为：(1)$(\forall x)P(x)$，$P(x)$ 表示$x$是要死的。(2)$(\exist x)Q(x)$， $Q(x)$表示$x$活到100岁以上

2.2.2 谓词公式

用谓词联接符号将一些谓词联接起来所形成的公式

• 联结符号：优先级从高到低： $\neg$ 否定(非) | $\wedge$ 合取(与) | $\vee$ 析取(或) | $\rightarrow$ 蕴含 (IF…THEN) | $\leftrightarrow$ 等价(当且仅当)
  • e.g. “机器人不在2号房间”：$\neg INROOM(Robot, R2)$
  • 2.g. “如果小王跑得最快，那么他获得冠军“：$RUN(Wang, Fastest)\rightarrow WIN(Wang, CHampion)$
• 辖域：紧接于量词之后被量词作用(即说明)的谓词公式称为该量词的辖域
  • 全称量词辖域
  • 存在量词辖域
• 指导变元：量词后面的变元
• 约束变元：在一个量词的辖域中的与该量词的指导变元相同的变元
• 自由变元：其他的变元
• 改名规则 ：一个变元在一个谓词公式中既可约束出现，又可自由 出现，为了避免混淆，通常通过改名规则，使得一个谓词 公式中一个变元仅以一种形式出现。如对于$\exist xP(x)\wedge B(x)$
  • 换名规则：将某个约束变元及其对应的指导变元改为本辖域内没有出现过的个体变元符号。$\exist uP(u)\wedge B(x)$
  • 代替规则：将某量词辖域中出现的某个自由变元的所有出现改为本辖域内没有出现过的个体变元符号。$\exist xP(x)\wedge B(u)$

2.2.5 谓词逻辑表示法的特点

• 主要优点：
  • 严密性。可以保证其演绎推理结果的正确性， 可以较精确的表达知识
  • 自然性。谓词逻辑是一种接近于自然语言的形 式语言。
  • 通用性。拥有通用的逻辑演算方法和推理的规则。
  • 易于实现。用它表示的知识易于模块化，便于知识的增删及修改，便于在计算机上实现
• 主要缺点：
  • 知识表示能力差。不便于表达和加入非确定性、 启发性知识等
  • 组合爆炸。在其推理过程中，随着事实数目的增大及盲目的使用推例规则，有可能形成组合爆炸
  • 效率低。由于推理是根据形式逻辑进行的，把推 理演算与知识含义截然分开，抛弃了表达内容中所含有的语义信息，往往使推理过程太冗长，降低了系统的效率。

2.3 产生式表示法

适合表示事实性知识和规则性知识

2.3.1 知识的产生式表示方法

• 事实的表示：

  • 事实：断言一个语言变量的值或断言多个语言变量之间关系的陈述句。

    • “雪是白的”，“王峰热爱祖国”

  • 事实的表示：

    • 确定性知识：（对象，属性，值）：(snow, color, white） (关系，对象1，对象2)：(love, Wang Feng, country)
    • 非确定性知识：（对象，属性，值，可信度因子）[0,1]

• 规则的表示（产生式/规则）

  • 产生式的基本形式： $P\rightarrow Q$ 或者$IF\ P\ THEN\ Q$ 其中$P$ 是前提（可用的条件/前件），$Q$是结论（应该执行的操作/后件）

  • “如果王宏是计算机系学生，则王宏会编程序”

    IF 该学生是计算机专业THEN 该学生会编程序

2.3.5 产生式系统的特点

• 主要优点：
  • 自然性:采用”如果……，则……”的形式，人类的判断性知识基本一致
  • 模块性: 每条产生式规则都是一个独立的的知识单元，各规则之间不存在相 互调用关系，这就大大增加了规则的模块性
  • 有效性:产生式知识表示法既可以表示确定性知识，又可以表示不确定性 知识。
• 主要缺点：
  • 效率较低: 各规则之间的联系必须以综合数据库为媒介。并且，其求解过 程是一种反复进行的”匹配一冲突消解一执行”过程。这样的执行方式将导致 执行的低效率。
  • 不便于表示结构性知识：由于产生式表示中的知识具有一致格式，且规则 之间不能相互调用，因此那种具有结构关系或层次关系的知识则很难以自 然的方式来表示

2.4 语义网络表示法

2.4.1 概述

• 概念：通过概念及语义关系来表示知识的一种网络图，它是一个带标注的有向图
  • 图中的各个节点表示各种概念、事物、对象、 行为、状态等
  • 图中的有向弧表示节点间的联系或关系
• 基本表示：由最基本的语义单元（语义基元）组成，可用(节点1，弧，节点2) 的三元组表示，或有向图表示
• 语义网络：把多个基本网元用相应的语义联系关联在一起的到；其节点还可以是一个语义子网络，因此，语义网络实质上是一种多层次的嵌套结构。

2.4.2 基本语义关系

1. 实例关系：ISA（具体与抽象，“是一个”，表示一个事物是另一个事物的实例）

   张三 ISA 人

2. 分类关系：AKO（子类与超类，“是一种”，表示一个事物是另一个事物的一种类型）

   鸵鸟 AKO 鸟类

3. 成员关系：A-Member-of （个体与集体，“是一员”， 表示一个事物是另一个事物的一个成员）

   希拉里 A-Member-of 民主党

   1～3具有属性的继承性

4. 包含关系：Part-of （部分与整体，”是一部分“，表示一个事物是另一个事物的一部分）不具备属性的继承性

   两只手 Part-of 人体

5. 属性关系：Have （“有”，表示一个节点具有另一个节点所描述的属性）Can （“会”，表示一个节点能做另一个节点的事情）

   鸟 Have 翅膀

   张强 Age 18

6. 时间关系 （不同事件在发生时间方面的先后次序关系）Before After

   张三入学 Before 李四入学

   上海世博会 After 北京奥运会

7. 位置关系（不同事物在位置方面的关系）Located-on, Located-under, Located-at, Located-inside, Located-outside

   加油站 Located-at 北京路

8. 相近关系 Similar-to, Near-to

   猫 Similar-to 虎

2.4.3 事物和概念的表示

• 一元关系：可以用一元谓词P(x)表示的关系，谓词P说明实体的性质、属性等，常用:“是”、”有”、”会”、”能”等语义关系来说明。

  动物能运动、会吃

• 二元关系：指可用二元谓词P(x，y)表示的关系。其中， x，y为实体， P为实体之间的关系

  动物能运动、会吃。鸟是一种动物，鸟有翅膀、会飞。鱼是一种动物，鱼生活在水中、 会游泳。

  

• 多元关系: 可用多元谓词P(x1 , x2, ……)表示的关系。其中， x1 , x2, ……为实 体，谓词P说明这些实体之间的关系

2.4.4 情况和动作的表示

1. 情况的表示

增加情况和动作结点的描述方法

• 小燕子这只燕子从春天到秋天占有一个巢

  

2. 事件和动作的表示

需要设立一个事件节点或动作结点。其中，事件节点由一些向外引出的弧来指出事件行为及发出者与接受者。 动作结点由一些向外引出的孤来指出动作的主体与客体。

• 常河给江涛一个优盘

  

  • 用事件节点表示

  

  • 用动作节点表示

2.4.5 基于语义网络的推理

语义网络的推理过程主要有两种，一种是继承，另一种是匹配

• 继承 ：把对事物的描述从抽象结点传递到实例结点。通过继承可以得到所需 结点的一些属性值，它通常是沿着ISA、AKO等继承弧进行的

  用语义网络表示: 动物能运动、会吃。 鸟是一种动物，鸟有翅膀、会飞。 麻雀有爪子，麻雀是一种鸟。 小麻雀是一只麻雀。

  推理:小麻雀有哪些属性?

• 匹配 ：在知识库的语义网络中寻找与待求解问题相符的语义网络模式

  设在语义网络系统的知识库中存在以下事实的语义网络:哈尔滨工业大学是一所学校，位于哈尔滨市，成立于1920年。

  用语义网络进行推理求解哈尔滨工业大学位于哪个城市?

2.4.6 语义网络表示法的特点

• 主要优点：
  • 结构性:采用把事物的属性以及事物间的各种语义联系显式地表示出来，是一种 结构化的知识表示方法。
  • 联想性: 本来是作为人类联想记忆模型提出来的，它着重强调事物间的语义联系， 体现了人类的联想思维过程。
  • 自索引性: 把各接点之间的联系以明确、简洁的方式表示出来，通过与某一结点 连结的弧可以很容易的找出与该结点有关的信息，而不必查找整个知识库。这 种自索引能力有效的避免搜索时所遇到的组合爆炸问题
• 主要缺点：
  • 非严格性:没有象谓词那样严格的形式表示体系，一个给定语义网络的含义完全 依赖于处理程序对它所进行的解释，通过语义网络所实现的推理不能保证其正 确性。
  • 复杂性:语义网络表示知识的手段是多种多样的，这虽然对其表示带来了灵活性， 但同时也由于表示形式的不一致，使得它的处理增加了复杂性。

2.5 框架表示法

2.5.1 框架表示法概述

• 框架 ：人们认识事物的一种通用的数据结构形式。即当新情况发生时， 人们只要把新的数据加入到该通用数据结构中，便可形成一个具体的 实体(类)，这样的通用数据结构就称为框架。
• 实例框架 ：对于一个框架，当人们才把观察或认识到的具体细节填入后， 就得到了该框架的一个具体实例，框架的这种具体实例被称为实例框 架.
• 框架系统 ：在框架理论中，框架是知识的基本单位，把一组有关的框架连 结起来使可形成一个框架系统
• 框架系统推理：由框架之间的协调来完成

2.5.2 框架的组成

• 组成：一个框架由若干个槽 组成，每个槽划分为若干个侧面。由框架名、槽名、侧面、值组成

  • 槽：描述对象的一个方面属性
  • 侧面：描述相应属性的一个方面

• 一个框架结构：

  

2.5.3 框架系统

1. 特性继承：通过ISA 、AKO链来实现，系统沿ISA和AKO链追溯到具有相同槽的类或超类框架
2. 匹配和填槽：框架的匹配实际上是通过对相应槽的槽名和槽值逐个进行比较，并利用继承关系来实现的。

2.5.5 框架表示法的特征

• 主要优点
  • 结构性:最突出特点是善于表示结构性知识，它能够把知识的内部结构关系以及知识问的特殊联 系表示出来。
  • 深层性:框架表示法不仅可以从多个方面、多重属性表示知识，而且还可以通过ISA 、AKO等槽以嵌套结构分层地对知识进行表示，因此能用来表达事物间复杂的深层联系。
  • 继承性:在框架系统中，下层框架可以继承上层框架的槽值，也可以进行补充和修改，这样既减 少知识冗余，又较好地保证了知识的一致性。
  • 自然性:框架能把与某个实体或实体集相关特性都集中在一起，从而高度模拟了人脑对实体多方面、多层次的存储结构，直观，自然，易于理解
• 主要缺点：
  • 缺乏框架的形式理论:至今，还没有建立框架的形式理论。
  • 缺乏过程性知识表示:框架系统不使于表示过程性知识，缺乏如何使用框架中知识的描述能力。 框架推理过程需要用到一些与领域无关的推理规则，而这些规则在框架系统中又很难表达。
  • 清晰性难以保证:由于各框架本身的数据结构不一定相同，从而框架系统的清晰性很难保证

第三章 确定性推理

3.1 概述

3.1.1 推理的基本概念

• 推理：按照某种策略从已有事实和知识推出结论的过程
  • 从结构的角度：推理由两个以上的判断所组成，把判断定义为对客观事物做出肯定或否 定的思维活动;认为判断是在概念的基础上进行的，所揭示的是概念之间联系和关系。
  • 从过程的角度：认为推理是在给定信息和已有知识的基础上的一系列加工操作，提出了如下人类推理的公式：$y=F(x,k)$, 其中$x$为推理时给出的信息，$k$为推理时可用的领域知识和特殊事例，$F$为可用的一系列操作，$y$为推理过程所得到的结论。

3.1.2 推理的分类

1. 按推理的逻辑基础分类

• 演绎推理：从已知的一般性知识出发，推理出适合于某种个别情况的结论过程

  • 从一般到特别的推理，常用形式：三段论法（大前提、小前提、结论）

  • 1 音乐系的学生至少会演奏一种乐器；（大前提）

    2 李聪是音乐系的一名学生；（小前提）

    3 李聪至少会演奏一种乐器。（结论）

  • 不能增殖新知识。

• 归纳推理：从大量特殊事例出发，归纳出一般性结论的推理过程

  • 从个别到一般的过程，是增殖新知识的过程。
  • 根据特殊事例考察范围：
    • 完全推理
    • 不完全推理
  • 根据推理使用方法：
    • 枚举归纳推理
    • 类比归纳推理

• 一位计算机维修员，从书本知识，到通过大量实例积累经验，是一种归纳推理方式。运用这些一般性知识 知识去维修计算机的过程则是演绎推理

2. 按所用知识的确定性分类

• 确定性推理：推理时所有用的知识和证据都是确定的，推出的结论也是确定的，其真值或者为真或者为假， 没有第三种情况出现
• 不确定性推理：推理时所用的知识和证据不都是确定的，推出 的结论也不确定的

3. 按推理中所用知识是否具有启发性分类

• 启发式推理：推理过程中应用与问题有关的启发性知识，即解决问题的的策略、技巧及经验，以加快推理过程，提高搜索效率
• 非启发式推理：在推理过程中，不运用启发性知识，只按照一 般的控制逻辑进行推理。这种方法缺乏对求解问题的针对性，所以推理效率较低，容易出现 “组合爆炸”问题

3.1.3 推理的控制策略及其分类

推理过程不仅依赖于所用的推理方法，同时也依赖于推理的控制策略

• 推理的控制策略：如何使用领域知识使推理过程尽快达到目标的策略
• 控制策略的分类 ：推理策略和搜索策略。
  • 推理策略：
    • 推理方向控制策略用于确定推理的控制方向，可分为正向推理、逆向推理、混合推理及双向推理。
    • 求解策略是指仅求一个解，还是求所有解或最优解等。
    • 限制策略是指对推理的深度、宽度、时间、空间等进行的限制。
    • 冲突消解策略是指当推理过程有多条知识可用时，如何从这多条可用知识中选出一条最佳知识用 于推理的策略
  • 搜索策略：主要解决推理线路、推理效果、推理效率等问题

3.2 产生式系统

3.2.1 产生式系统的基本结构

• 综合数据库DB(Data Base)
  • 存放推理过程的各种当前信息，如问题的初始状态、输入的事实、中间结论及最终结论
  • 作为推理过程选择可用规则的依据。推理过程中某条规则是否可用，是通过该规则的前提与DB中的已知事实的匹配来确定的
• 规则库RB(Rule Base)/知识库KB(Knowledge Base)：
  • 作用：用于存放推理所需要的所有规则，是整个产生式系统的知识集。 是产生式系统能够进行推理的根本
  • 要求：知识的完整性、一致性、准确性、灵 活性和可组织性
• 控制系统(Control system)
  • 主要作用：用于控制整个产生式系统的运行，决定问题求解过程的推理线路
  • 主要任务：选择匹配、冲突消解、执行操作、终止推理、路径解释

3.2.2 产生式系统的推理过程

正向推理

从已知事实出发、正向使用规则，亦称为数据驱动推理或前向链推理。

假设知识库中包含有以下2条规则: r1 :IF B THEN C r2 :IF A THEN B 已知初始证据A，求证目标C

• 正向推理的特性:主要优点是比较直观，主要缺点是推理无明确的目标，求解问题时可能会执行许多与解无关的操作，导致推理效率较低

逆向推理

某个假设目标出发，逆向使用规则，亦称为目标驱动推理或逆向链推理

设有以下两条规则：r1: IF 动物有羽毛 THEN 动物是鸟，r2: IF 动物是鸟AND动物善飞 THEN动物是信天翁，假设已知有如下事实：动物有羽毛，动物善飞。求满足以上事实的动物是何种动物。

• 逆向推理的特性: 逆向推理的主要优点是不必寻找和使用那些与假设目标无关的信息和规则，推理过程的目标明确，主要缺点是当用户对解的情况认识不清时，由系统自主选择假设 目标的盲目性比较大，若选择不好，会影响系统效率
• 双向推理法
• 推理过程的不唯一性 ：无论是正向推理还是逆向推理，当可用规则集中有 多条规则可用时，不同的冲突消解策略将导致不同的规则使用顺序， 因此其推理过 程是不唯一的。

3.3 自然演绎推理

3.3.1 自然演绎推理的逻辑基础

• 定义1 谓词公式的解释：设D是谓词公式P的非空个体域，若 对P中的常量，函数和谓词按如下规定赋值

  • 为每个个体常量指派D中的一个元素
  • 为每个n元函数指派一个从$D^n$到D的一个映射,$D^n = {(x_1,x_2,\cdots,x_n)|x_1,x_2,\cdots,x_n\in D}$
  • 为每个n元谓词指派一个从$D^n$到{F,T}的映射，称这些指派为P在D上的一个解释

• 定义2 谓词公式的永真性

• 定义3 谓词公式的可满足性 ：对于谓词公式P，若至少存在D上一个解释使得P在此解释下的真值为T，则称P是可满足的

• 定义4 谓词公式的永假性

• 定义5 谓词公式的等价性 $P \Leftrightarrow Q$

  • 双重否定率；交换律；结合律；分配律；吸收率；补余率；
  • 摩根定律$\neg(P\vee Q)\Leftrightarrow \neg P\wedge \neg Q$；
  • 连词化归率$P\rightarrow Q\Leftrightarrow \neg P\vee Q$, $P\leftrightarrow Q\Leftrightarrow (P\rightarrow Q)\wedge(Q\rightarrow P)$, $P\leftrightarrow Q\Leftrightarrow (P\wedge Q)\vee(\neg Q\wedge \neg P)$；
  • 量词转换率$\neg(\exists x)P\Leftrightarrow (\forall x)(\neg P)$, $\neg(\forall x)P\Leftrightarrow (\exist x)(\neg P)$
  • 量词分配率$(\forall x)(P\wedge Q)\Leftrightarrow (\forall x)P\wedge (\forall x)Q$, $(\exist x)(P\vee Q)\Leftrightarrow (\exist x)P\vee (\exist x)Q$

• 定义6 永真蕴含式：$P\Rightarrow Q$

  • 化简式 $P\wedge Q\Rightarrow P, P\wedge Q\Rightarrow Q$
  • 附加式 $P\Rightarrow P\vee Q, Q\Rightarrow P\vee Q$
  • 析取三段论 $\neg P, P\vee Q\Rightarrow Q$
  • 假言推理 $P,P\rightarrow Q\Rightarrow Q$
  • 拒取式 $\neg Q, P\rightarrow Q\Rightarrow\neg P$
  • 假言三段论 $P\rightarrow Q, Q\rightarrow R\Rightarrow P\rightarrow R$
  • 二难推理 $P\vee Q, P\rightarrow R, Q\rightarrow R\Rightarrow R$
  • 全称固化 $(\forall x)P(x)\Rightarrow P(y)$， y是个体域中任一个体
  • 存在固化 $(\exist x)P(x)\Rightarrow P(y)$，y是个体域中某一个可以使P(y)为真的个体

• 置换与合一

  • 在不同谓词公式中，往往会出现谓词名相同但其个体不同的情况，此时推理 过程是不能直接进行匹配的，需要先进行置换。

  • $W(a)$和$W(x)\rightarrow Q(x)$中，谓词名虽然相同，但个体域不同，不能进行直接推理

  • 置换

    • ${t_1/x_1, t_2/x_2, \cdots,t_n/x_n}$，其中$t_1,t_2,\cdots,t_n$是项，$x_1,x_2,\cdots,x_n$是互不相同的变元，$t_i/x_i$表示用$t_i$替换$x_i$。要求二者不能相同，$x_i$不能循环地出现在另一个$t_i$中

    • ${a/x,c/y,f(b)/z}$是一个置换

      ${g(z)/x,f(x)/z}$不是一个置换，循环置换现象

    • 定义8 设$\theta={t_1/x_1, t_2/x_2, \cdots,t_n/x_n}$是一个置换，$F$是一个谓词公式，把所有$x_i$换成$t_i(i=1,2,…,n)$，得到一个新的公式$G$，称$G$为$F$在置换$\theta$下的例示，记作$G=F\theta$

    • 置换的合成 设$\theta={t_1/x_1, t_2/x_2, L,t_n/x_n}, \lambda={u_1/y_1, u_2/y_2, L,u_n/y_n}$是两个置换，则将集合${t_1\lambda/x_1,t_2\lambda/x_2,L,t_n\lambda/x_n,u_1/y_1,u_2/y_2, L,u_n/y_n}$中符合条件(1)$t_i\lambda/x_i$，当$t_i\lambda=x_i$；(2)$u_i/y_i$当$y_i\in{x_1,x_2,\cdots,x_n}$；的元素删除，得到的集合仍然是个置换，该置换称为$\theta$与$\lambda$的合成，记作$\theta\cdot \lambda$

  • 合一 寻找相对应变量的置换，使两个或多个谓词公式一致

    • 定义9 设有公式集$F={F_1,F_2,\dots,F_n}$，若存在一个置换$\theta$，可使$F_1\theta=F_2\theta=\dots=F_n\theta$，则称$\theta$是$F$的一个合一。

    • 对于公式集$F={P(x,y,f(y)),P(a,g(x),z)}$，则$\lambda={a/x,g(a)/y,f(g(a))/z}$是它的一个合一

    • 一般情况下，一个公式集的合一不是唯一的

3.3.2 自然演绎推理方法

从一组已知为真的事实出发，直接运用命题 逻辑或谓词逻辑中的推理规则推出结论的过程

最基本的推理规则有：

• 假言三段论

  如果一个人大学毕业，则他就具有独立生活的能力

  如果一个人具有独立生活的能力，则他就可以离开父母

  $P\rightarrow Q, Q\rightarrow R\Rightarrow P\rightarrow R$

  $\Rightarrow$ 如果一个人大学毕业，则他就可以离开父母

• 假言推理

  如果S音乐系学生，则S至少会演奏一样乐器。

  张艺是音乐系学生。

  $P,P\rightarrow Q\Rightarrow Q$

  $\Rightarrow$张艺至少会演奏一样乐器

• 拒取式

  如果S音乐系学生，则S至少会演奏一样乐器。

  张艺不会演奏任何乐器

  $\neg Q, P\rightarrow Q\Rightarrow\neg P$

  $\Rightarrow$张艺不是音乐系学生。

• T规则

• P规则

3.4 归结演绎推理

“反证法”，要证明P→Q永真，只要能够证明P∧$\neg$Q是不可满足的就可以了(原因是$\neg$(P→Q) ⇔$\neg$($\neg$P∨Q) ⇔(P∧$\neg$Q)

3.4.1 谓词公式的范式

范式是谓词公式的标准形式

• 前束范式：设F是一个谓词公式，如果其中的所有量词均非否定出现在公式的最前面，而它们的辖域为整个公式，则称F为前束范式。

  • $(Q_1x_1)(Q_2x_2)\cdots(Q_nx_n)M(x_1,x_2,\cdots,x_n)$，其中$Q_i\in{\forall, \exist},(i=1,2,\cdots,n), M(x_1,x_2,\cdots,x_n)$中不含邮任何量词

  • $(\forall x)(\forall y)(\exist z)(P(x)\wedge Q(y,z)\vee R(x,z))$

• Skolem标准型：从前束型范式中消去全部存在量词所得到的公式，并将谓词公式化为合取范式，这时所得的式子称为原公式的Skolem 标准型。

  • $(\forall x_1)(\forall x_2)\cdots(\forall x_n)M(x_1,x_2,\cdots,x_n)$，其中$M(x_1,x_2,\cdots,x_n)$不含有任何量词，且为合取范式

3.4.2 子句集及其应用

子句和子句集

• 文字：原子谓词公式及其否定

  P(x), Q(x), $\neg$P(x)

• 子句：任何文字的析取式

  P(x)$\vee$Q(x)

• 空子句: 不含任何文字的子句，NIL ，不能被任何解释满足，因此永假

• 子句集：由子句或者空子句构成的集合

子句集的化简

$(\forall x)((\forall y)P(x,y)\rightarrow\neg(\forall y)(Q(x,y)\rightarrow R(x,y)))$

1. 消去连接词$\rightarrow$和$\leftrightarrow$

   • 反复使用$P\rightarrow Q\Leftrightarrow \neg P\vee Q$和$P\leftrightarrow Q\Leftrightarrow (P\wedge Q)\vee(\neg Q\wedge \neg P)$

   • $(\forall x)(\neg(\forall y)P(x,y)\vee\neg(\forall y)(\neg Q(x,y)\vee R(x,y)))$

2. 减少否定符号的辖域

   • 反复使用 双重否定率、摩根定律、量词转换率，将每个否定符号移到仅靠谓词的位置，最多只作用于一个谓词上

   • $(\forall x)((\exist y)\neg P(x,y)\vee(\exist y)( Q(x,y)\wedge \neg R(x,y)))$

3. 对变元标准化

   • 在一个量词的辖域内，把谓词公式中受该量词约束的变元全部用另外一个没有出现过的任意变元代替，使不同量词约束的变元有不同的名字

   • $(\forall x)((\exist y)\neg P(x,y)\vee(\exist z)( Q(x,z)\wedge \neg R(x,z)))$

4. 化为前束范式

   • 把所有量词都移到公式的左边，并且在移动时不能改变其相对顺序

   • $(\forall x)(\exist y)(\exist z)(\neg P(x,y)\vee( Q(x,z)\wedge \neg R(x,z)))$

5. 消去存在量词

   • 若存在量词不出现在全称量词的辖域内(即它的左边没有全称量词)，只要用一个新的个体常量替换受该存在量词约束的变元，就可消去该存在量词

   • 若存在量词位于一个或多个全称量词的辖域内，需要用Skolem函数$f(x_1,x_2,\cdots,x_n)$替换受该存在量词约束的变元$y$，然后再消去该存在量

     词

     $(\forall x)(\neg P(x,f(x))\vee( Q(x,g(x))\wedge \neg R(x,g(x))))$ 用$f(x)$和$g(x)$替换$y$和$z$

6. 化为Skolem标准型

   • 应用分配律，使得为合取式

   • $(\forall x)((\neg P(x,f(x))\vee Q(x,g(x)))\wedge (\neg P(x,f(x))\vee \neg R(x,g(x)))))$

7. 消去全称量词

   • 母式中的全部变元均受全称量词约束，并且与全称量词的次序无关， 因此可省掉全称量词

   • $(\neg P(x,f(x))\vee Q(x,g(x)))\wedge (\neg P(x,f(x))\vee \neg R(x,g(x))))$

8. 消去合取词

   • 在母式中消去所有合取词，把母式用子句集的形式表示出来。其中，子句集中的每一个元 素都是一个子句。

   • $\neg P(x,f(x))\vee Q(x,g(x))$

     $\neg P(x,f(x))\vee \neg R(x,g(x))$

9. 更换变量名称

   • 对子句集中的某些变量重新命名，使任意两个子句中不出现相同的变量名。由于任意两个 不同子句的变量之间实际上不存在任何关系。

   • $\neg P(x,f(x))\vee Q(x,g(x))$

     $\neg P(y,f(y))\vee \neg R(y,g(y))$

子句集的应用

• 由于子句集化简过程在消去存在量词时所用的Skolem函数可以不同，因此 所得到的标准子句集不唯一
• 当原谓词公式为可满足时，它与其标准子句集不一定等价；但当原谓词公式为不可满足时，其标准子句集则一定是不可满足的，即Skolem化并不影响原谓词公式的不可满足性
• 定理3.1 设有谓词公式F，其标准子句集为S，则F为不可满足的充要条件是S为不可满足的。

3.4.3 鲁滨逊归结原理

1. 基本思想

• 关键前提：

  • 子句集中的子句之间是合取关系。因此，子句集中只要有一个子句为不可满足，则整个子句集就是不可满足的
  • 空子句是不可满足的。因此，一个子句集中如果包含有空子句， 则此子句集就一定是不可满足的

• 基本思想：

  首先把欲证明问题的结论否定，并加入子句集，得到一个扩充的子句集S’。然后设 法检验子句集S’是否含有空子句，若含有空子句，则表明S’是不可满足的;若不含有空子句，则继续使用归结法，在子句集中选择合适的子句进行归结，直至导出空子句或不能继续归结为止

2. 命题逻辑的归结

• 互补文字：若$P$是原子谓词公式，则称$P$与$\neg P$为互补文字

• 归结：设$C_1$和$C_2$是子句集中的任意两个子句，如果$C_1$中的文字$L_1$与$C_2$中的文字$L_2$互补，那么可从这两个子句中消去这两个文字，将余下的部分按析取关系构成一个新的子句$C_{12}$，这一过程叫做归结，称$C_{12}$为$C_1$和$C_2$的归结式，称$C_1$和$C_2$为$C_{12}$的亲本子句

  • 设$C_1$ =$\neg$P ∨Q ，$C_2$=$\neg$Q，$C_3$=P ，求$C_1$、$C_2$、$C_3$ 的归结式$C_{123}$

    

  • 归结树；归结过程不唯一

• 定理3.7：归结式$C_{12}$为其亲本子句$C_1$和$C_2$的逻辑结论

  • 推论1：设$C_1$和$C_2$是子句集S中的两个子句，$C_{12}$为$C_1$和$C_2$的归结式，用$C_{12}$代替$C_1$和$C_2$得到新的子句集$S_1$，则$S_1$的不满足性$\Rightarrow$S的不满足性
  • 推论2：把$C_{12}$加入S中得到新的子句集$S_2$，则$S_2$的不可满足性$\Leftrightarrow$S的不可满足性

• 定理3.8 ：子句集S是不可满足的，当且仅当存在一个从S到空子句的归结过程

谓词逻辑的归结

• 定义25：设$C_1$和$C_2$是两个没有公共变元的子句，$L_1$与$L_2$分别是$C_1$和$C_2$中的文字，如果$L_1$与$L_2$存在合一$\sigma$，则称$C_{12}=({C_{1\sigma}}-{L_{1\sigma}})\cup({C_{2\sigma}}-{L_{2\sigma}})$为$C_1$和$C_2$的二元归结式

• 设$C_1=P(a)\vee R(x),C_2=\neg P(y)\vee Q(b)$，求$C_{12}$

• 注意事项：

  • 不能同时消去两个互补对
  • 若子句内部有可以合一的文字，在归结之前应先进行合一，其中$C_{1\sigma}$为$C_1$的因子

3.4.4 归结演绎推理的方法

命题逻辑的归结反演

• 归结原理：假设F为已知前提，G为欲证明的结论，归结原理把证明G为F的逻辑结论转化为证明$F\wedge\neg G$为不可满足。再把公式集上的不可满足转化为子句集上的不可满足。
• 归结反演：应用归结原理证明定理的过程称为归结反演
• 在命题逻辑中，已知F，证明G为真的归结反演过程如下
  1. 否定目标公式G，得$\neg G$
  2. 把$\neg G$并入到公式集F中，得到{F，$\neg G$}
  3. 把{F，$\neg G$}化为子句集
  4. 应用归结原理对子句集S中的子句进行归结，并把每次得到的归结式并入S中。如此反复进行，若出现空子句，则停止归结，此时就证明了G为真

谓词逻辑的归结演绎推理

谓词逻辑的归结反演过程与命题逻辑的归结反演过程相比，其步骤基本相同， 但每步的处理对象不同。例如，在步骤(3)化简子句集时，谓词逻辑需要把由谓 词构成的公式集化为子句集;在步骤(4)按归结原理进行归结时，谓词逻辑的归 结原理需要考虑两个亲本子句的合一。

3.4.5 归结演绎推理的归结策略

归结策略是指在归结演绎推理过程的每一步如何选择进行归结的子句对， 以尽快得到空子句的策略，不同的归结策略影响归结过程、归结推理效率和完备性。

排序策略（广度优先策略）

设初始子句集为$S_0$

1. 从$S_0$出发，对$S_0$ 中的全部子句作所有可能的归结，得到第一层归结式，把 这些归结式的集合记为$S_1$
2. 用$S_0$ , $S_1$中的子句与$S_1$中的子句进行所有可能的归结，得到第二层归结式， 把这些归结式的集合记为$S_2$
3. 用$S_0$ , $S_1$, $S_2$中的子句与$S_2$中的子句进行所有可能的归结，得到第三层归结式， 把这些归结式的集合记为$S_3$
4. 如此继续，直到得出空子句或不能再继续归结为止

• 归结效率较低，当问题比较复杂时，还可能会出现组合爆炸
• 广度优先策略是完备的，并当问题有解时，它一定能找到最短归结路径
• 适合问题较小情况

删除策略

归结过程在寻找可归结子句时，子句集中的子句越多，需要付出的代价就会越大。如果在归结时能把子句集中无用的子句删除掉，这就会缩小搜索 范围，减少比较次数，从而提高归结效率

• 纯文字删除策略

  • 如果某文字$L$在子句集中不存在可与其互补的文字$\neg L$，则称该文字为纯文字.
  • 在归结过程中，纯文字不可能被消除，用包含纯文字的子句进行归结也不可能得到空子句，因此对包含纯文字的子句进行归结是没有意义的，应该把它从子句 集中删除。

• 重言式删除策略

  • 如果一个子句中包含有互补的文字对，则称其为重言式
  • 重言式是真值为真的子句。对一个子句集来说，不管是增加还是删除一个真值 为真的子句，都不会影响该子句集的不可满足性。因此，可删去

• 包孕删除策略

  • 设有子句C1 和C2 ，如果存在一个置换σ，使得C1 σ⊆C2 ，则称C1包孕于 C2

  • P(x) 包孕于 P(a)∨Q(z) , σ={a/x}

    P(x) ∨Q(a) 包孕于P(f(a))∨Q(a)∨R(y) σ={f(a)/x}

限制策略

• 支持集策略
  • 要求每一次参加归结的两个亲本子句中，至少应该有一个是由目标公式的否定所得到的子句或它们的后裔
  • 这种策略限制了子句集元素的剧增，但却增加了空子句的深度
• 线性输入策略
  • 要求每次参加归结的两个亲本子句中，至少应该有一个是初始子句集中的子句
  • 可限制生成归结式的数目，简单高效，但是一种不完备策略
• 祖先过滤策略
  • 每次参加归结的两个亲本子句，只要满足以下两个条件中的任意一 个就可进行归结: (1)两个亲本子句中至少有一个是初始子句集中的子句。(2)如果两个亲本子句都不是初始子句集中的子句，则一个子句应该是另一个 子句的先辈子句
  • 祖先过滤策略也是完备的
• 单文字子句策略
  • 单文字：如果一个子句只包含一个文字，则称此子句为单文字子句。
  • 基本思想：要求每次参加归结的两个亲本子句中至少有一个子句是单文字子句
  • 单文字子句策略是不完备的

3.4.6 用归结反演求取问题的答案

步骤：

1. 把已知条件用谓词公式表示，并化成相应的子句集S1
2. 把待求解的问题也用谓词公式表示，然后将其否定，并与谓词ANSWER构成析取式G1
3. 把G1化为子句集S2，并把子句集S1与S2合并构成新子句集S
4. 对子句集S应用谓词归结原理进行归结，在归结过程中通过合一置换， 改变ANSWER中的变元
5. 如果得到归结式ANSWER，则问题的答案就在ANSWER谓词中

第四章 搜索策略

4.1 概述

依靠经验，利用已有知识，根据问题的实际情况，不断寻找可利用知识， 从而构造一条代价最小的推理路线，使问题得以解决的过程称为搜索。

4.1.2 问题的概述

问题可形式化定义为三个组成部分

1. 初始状态(Initial state) （$s_0$）
2. 后继函数
   • 操作函数(Actions): {$a_1, a_2, a_3,…..$}
   • 路径耗散函数(PathCost)：
3. 目标测试函数(GoalTest)

问题的解：初始状态到目标状态操作的序列

4.1.3 状态空间法

• 状态：表示问题求解过程中每一步问题状况的数据结构
• *操作

4.2 状态空间盲目搜索

• Open表：用于存放刚生成的节点,未扩展的节点，Open表称为未扩展的节点表
• Closed表：用于存放已经扩展或将要扩展的节点，Closed称为已扩展的节点表
• $S_0$：表示问题的初始状态
• $S_g$：表示问题的目标状态

4.2.1 一般图搜索过程

1. 把初始节点S0放入Open表，并建立目前仅包S0的图G，建立一个Closed表， 置为空;
2. 检查Open表是否为空表，若为空，则问题无解，失败退出
3. 把Open表的第一个节点取出放入Closed表，并记该节点为n
4. 考察节点n是否为目标节点，若是则得到问题的解成功退出。
5. 扩展节点n ，生成一组子节点。把这些子节点中不是其父节点的那部分子节点计入集合M，并把这些子节点作为节点n的子节点加G中。
6. 针对M中子节点的不同情况，分别作如下处理:
   1. 对那些没有在G中出现过的M成员设置一个指向其父节点(即节点n)的指针，并将他它放入Open表。
   2. 对那些原来已经在G中出现过，但没有被扩展过的M成员，确定是否需要修改它指向父节点的指针
   3. 对那些原来已经在G中出现过，并已经被扩展过的M成员，确定是否需要修改其后继节点指向父节点的指针
7. 按某种策略对Open表中的节点进行排序
8. 转第2步

4.2.2 广度优先搜索

OPEN表中的节点总是按进入的先后顺序排列，先进入的节点排在前面，后 进入的排在后面

1. 把初始节点S0放入Open表,建立个CLOSED表，置为空;
2. 检查Open表是否为空表，若为空，则问题无解，失败退出
3. 把Open表的第一个节点取出放入Closed表，并记该节点为n
4. 考察节点n是否为目标节点，若是则得到问题的解成功退出
5. 若节点n不可扩展，则转第(2)步;
6. 扩展节点n， 将其子节点放入Open表的尾部，并为每个子节点设置指向父节 点的指针,转向第(2)步。

• 性质：

  • 当问题有解时，一定能找到解
  • 搜素效率低
  • 方法与问题无关，具有通用性
  • 搜索中得到的解是搜索树中路径最短的解（最优解）
  • 属于完备搜索策略

4.2.3 深度优先搜索

Open表是一种栈结构，最先进进入的节点排在最后面，最后进入的节点排最前面

1. 把初始节点S0放入Open表,建立个CLOSED表，置为空;
2. 检查Open表是否为空表，若为空，则问题无解，失败退出
3. 把Open表的第一个节点取出放入Closed表，并记该节点为n
4. 考察节点n是否为目标节点，若是则得到问题的解成功退出
5. 若节点n不可扩展，则转第(2)步
6. 扩展节点n， 将其子节点放入Open表的首部，并为每个子节点设置指向父节 点的指针, 转向第(2)步。

• 性质
  • 一般不能保证找到最优解
  • 最坏情况时，搜索空间等同于穷举
  • 是一个通用的与问题无关的方法

4.2.4 代价一致搜索(UCS)

在搜索树中给每条边标上其代价。这种边上有代价的树称为代价树。可以用g(n)表示从初始节点S0到节点n的代价，用c(n1, n2)表 示从父节点n1到n2的代价。对节点n2的代价有g(n2) = g(n1) + c(n1, n2)。在代价树中，最小代价的路径和最短路径是有可能不同的，最短路径不一 定是最小代价径，最小代价路径也不一定是路径最短。代价树搜索的目的是为了到最佳解，即找到一条代价最小的解路径。

• 基本思想：把从起 始节点S0到任一节点i的路径代价记为g(i)。从初始节点S0开始扩展， 若没有得到目标节点，则优先扩展最少代价g(i)的节点，一直如此 向下搜索。

• 过程：

  1. 把初始节点S0放入Open表，设g(s0)=0, 建立一个CLOSED表，置为空

  2. 检查Open表是否为空表，若为空，则问题无解，失败退出

  3. 把Open表的第一个节点取出放入Closed表，并记该节点为n

  4. 考察节点n是否为目标节点，若是则得到问题的解成功退出

  5. 若节点n不可扩展，则转第(2)步

  6. 扩展节点n， 生成子节点ni(i=1,2,……)，将其子节点放入Open表，并为每个子节点设置指向父节点的指针，计算各个节点的代价g(ni) ，将Open表内的节点按g(ni)从小到大排序, 转向第2步。

4.3 状态空间启发式搜索

4.3.1 启发性信息

• 启发性信息：
  • 启发性信息是指那种与具体问题求解过程有关的，并可指导搜索过程 朝着最有希望方向前进的控制信息
  • 启发信息的启发能力越强，扩展的无用结点越少，搜索算法越高效
  • 包括3种：
    • 有效地帮助确定扩展节点的信息
    • 有效地帮助决定哪些后继节点应被生成的信息
    • 能决定在扩展一个节点时哪些节点应从搜索树上删除的信息
• 估价函数：$f(n)=g(n)+h(n)$
  • g(n)是从初始节点到节点n的实际代价，h(n)是从节点n到目标节点的最优路径的估计代价

4.3.2 贪心算法

forward cost h(n)

4.3.3 A算法

• 概念：每一步都利用估价函数f(n)=g(n)+h(n)对Open表中的节点进行排序，则 称A算法。它是一种为启发式搜索算法
• 类型：
  • 全局择优：从Open表的所有节点中选择一个估价函数值最小的进行扩展
  • 局部择优：仅从刚生成的子节点中选择一个估价函数值最小的进行扩展
• 算法描述
  1. 把初始节点S0放入Open表中f(S0)=g(S0)+h(S0)
  2. 如果Open表为空，则问题无解，失败退出
  3. 把Open表的第一个节点取出放入Closed表，并记该节点为n
  4. 考察节点n是否为目标节点。若是，则找到了问题的解，成功退出
  5. 若节点n不可扩展，则转第(2)步;
  6. 扩展节点n，生成其子节点ni(i=1, 2, …)，计算每一个子节点的估价值f(ni )(i=1, 2, …)，并为每一个子节点设置指向父节点的指针，然后将这些子节点放入Open表中;
  7. 根据各节点的估价函数值，对Open表中的全部节点按从小到大的顺序重新进行排序
  8. 转第(2)步。

4.3.4 A*算法

假设f*(n)是从初始节点S0出发，约束经过节点n到达目标节点Sg的最小代价，估价函数f(n)是对f*(n)的估计值。f*(n)=g*(n)+h*(n)。其中，g*(n)是从S0出发到达Sg的最小代价,h*(n)是n 到Sg的最小代价

• 定义4.1 如果对A算法(全局择优)中的g(n)和h(n)分别提出如下限制，则称满足下述两条限制的A算法为A*算法
  • g(n)是对最小代价g*(n)的估计，且g(n)>0;
  • h(n)是最小代价h*(n)的下界，即对任意节点n均有h(n)≤h*(n)。
• 可纳性：对任一状态空间图，当从初始节点到目标节点有路经存在时，如果搜索 算法总能在有限步骤内找到一条从初始节点到目标节点的最佳路径， 并在此路径 上结束，则称该搜索算法是可采纳的
• 单调限制：如果启发函数满足以下两个条件，称h(n)满足单调限制:
  • h(Sg)=0;
  • 对任意节点ni及其任一子节点nj，都有$0\leq h(n_i)-h(n_j)\leq c(n_i,n_j)$，其中$ c(n_i,n_j)$是$n_i$到其子节点$n_j$的边代价
• 定理4.5 如果h满足单调条件，则当A*算法扩展节点n时，该节点就已经找到了通 往它的最佳路径，即g(n)=g*(n)。
• 定理4.6 如果h(n)满足单调限制，则A*算法扩展的节点序列的f 值是非递减的，即 f(ni )≤f(ni+1)。

4.4 与/或树搜索

4.5 博弈树的启发式搜索