人工智能技术简明教程 教学课件 作者 廉师友 第5章 知识表示与推理.ppt

第5章 知识表示与推理 5.1 概述 5.2 基于谓词逻辑的机器推理 5.3 基于产生式规则的机器推理 5.4 几种结构化知识表示及其推理 5.5 不确定性知识的表示与推理 5.1 概述 5.1.1 知识及其表示 ◆一些常用的知识表示形式： 一阶谓词逻辑、产生式规则、框架、语义网络、类和对象、模糊集合、贝叶斯网络、脚本、过程等。 5.1.2 机器推理 ◆演绎推理、归纳推理和类比推理 ◆不确定性推理和不确切性推理 ◆约束推理、定性推理、范例推理、非单调推理 5.2 基于谓词逻辑的机器推理 基于谓词逻辑的机器推理也称自动推理。它是人工智能早期的主要研究内容之一。一阶谓词逻辑是一种表达力很强的形式语言，而且这种语言很适合当前的数字计算机。因而就成为知识表示的首选。基于这种语言，不仅可以实现类似于人推理的自然演绎法自动推理，而且也可实现不同于人的归结（或称消解）法自动推理。本节主要介绍基于谓词逻辑归结演绎推理。 归结演绎推理是基于一种称为归结原理(亦称消解原理principle of resolution)的推理规则的推理方法。归结原理是由鲁滨逊(J.A.Robinson)于1965年首先提出。它是谓词逻辑中一个相当有效的机械化推理方法。归结原理的出现，被认为是自动推理，特别是定理机器证明领域的重大突破。 5.2.1 子句集 定义1 原子谓词公式及其否定称为文字，若干个文字的一个析取式称为一个子句，由r个文字组成的子句叫r—文字子句，1—文字子句叫单元子句，不含任何文字的子句称为空子句，记为或NIL。 例： P∨Q∨﹁R P(x,y)∨﹁ Q(x) 定义2 对一个谓词公式G，通过以下步骤所得的子句集合S，称为G的子句集。 (1)消去蕴含词→和等值词←→。 (2)缩小否定词﹁的作用范围，直到其仅作用于原子公式。 (3)适当改名，使量词间不含同名指导变元和约束变元。 (4)消去存在量词。 (5)消去所有全称量词。 (6)化公式为合取范式。 (7)适当改名，使子句间无同名变元。 (8)消去合取词∧，以子句为元素组成集合S。 定理1 谓词公式G不可满足当且仅当其子句集S不可满足。 定义3 子句集S是不可满足的，当且仅当其全部子句的合取式是不可满足的。 5.2.2 命题逻辑中的归结原理 定义 设C1,C2是命题逻辑中的两个子句，C1中有文字L1，C2中有文字L2，且L1与L2互补，从C1,C2中分别删除L1,L2，再将剩余部分析取起来，记构成的新子句为C12，则称C12为C1,C2的归结式(或消解式)，C1,C2称为其归结式的亲本子句， L1,L2称为消解基。 例5.9 设C1= ﹁ P∨Q∨R, C2= ﹁ Q∨S, 则C1,C2的归结式为 ﹁ P∨R∨S 定理2 归结式是其亲本子句的逻辑结果。 由定理2即得推理规则： C1∧C2＝＞ (C1-｛L1｝)∪(C2-｛L2｝) 其中C1,C2是两个子句，L1,L2分别是C1,C2中的文字，且L1,L2互补。 此规则就是命题逻辑中的归结原理。 例3.10 用归结原理验证分离规则和拒取式 A∧(A→B) ＝＞ B (A→B)∧﹁ B ＝＞﹁ A 解 A∧(A→B) ＝ A∧(﹁ A∨B) ＝＞ B (A→B)∧﹁ B ＝ (﹁ A∨B)∧(﹁ B) ＝＞ ﹁ A 例5.11 证明子句集{ P∨﹁Q,﹁P,Q }是不可满足的。 证 (1)P∨﹁Q (2)﹁P (3)Q (4)﹁Q 由(1),(2) (5)□ 由(3),(4) 例5.1