国考经典逻辑推理

第四章 经典逻辑推理基本概念 命题逻辑的归结法 子句形 Herbrand定理 归结原理 归结过程的策略控制 12013-7-12 福州大学阳光学院计算机系

国考经典逻辑推理

第四章 经典逻辑推理基本概念 命题逻辑的归结法 子句形 Herbrand定理 归结原理 归结过程的策略控制 22013-7-12 福州大学阳光学院计算机系

国考经典逻辑推理

基本概念 推理

什么是推理：依据一定的规则(策略) 从已知的事实推出新事实(结论)的过 程称为推理。

3

2013-7-12

福州大学阳光学院计算机系

国考经典逻辑推理

基本概念 推理

推理方式及其分类 p.112

演绎推理、归纳推理(完全与否)、默认推 理 确定推理、不确定推理 单调推理、非单调推理 启发式推理、非启发式推理 …………42013-7-12 福州大学阳光学院计算机系

国考经典逻辑推理

基本概念

推理

推理的控制策略，即求解问题的策略。有推理方向、 搜索策略、冲突消解策略、求解策略及限制策略等。 推理方向 正向推理：由原始数据出发寻找可用的知识得出新事 实，如此继续直至得到结论。自底向上(bottomup) ,事实驱动方式。 反向推理：先提出假设，由此出发，进一步寻找支持 假设的证据，当所需证据与用户提供原始数据相匹配 则成功。自顶向下(top-down),目标驱动方式。

5

2013-7-12

福州大学阳光学院计算机系

国考经典逻辑推理

基本概念

正向推理过程1)规则集中的规则与数据库中的事实进行匹配，

得到匹配的规则集合。 2)从匹配的规则集合中选择一条规则作为使用规 则。 3)执行使用规则的后件。将该使用规则的后件输 入数据库。 4)重复进行，直到达到目标。62013-7-12 福州大学阳光学院计算机系

国考经典逻辑推理

基本概念

正向推理算法(产生式系统)1)断言一个事实 2)使事实与某个规则的前提相匹配

3)完成事实和前提的合一代换4)把代换应用于规则的结论 5)断言结果，并把它应用于进一步的推理 6)重复1)~ 5)

7

2013-7-12

福州大学阳光学院计算机系

国考经典逻辑推理

基本概念输入信息

正 向 推 理 算 法 流 程

从KB中选择合适知识有适用知识

新结果存入数据库 Y

Y

进行推理

结果是新的

N Y DB是否有解 N输出解 无解退出2013-7-12

N Y还有适用知识

N

8

福州大学阳光学院计算机系

国考经典逻辑推理

基本概念

设计一正向推理系统1)能用数据库(黑板)中的事实去匹配规则的前

提，若匹配不成功，能自动地进行下一条规则 的匹配，在匹配时，采用什么策略等问题应考 虑周到。 2)若某条规则匹配成功了，系统能将此规则的结 论部分自动加入数据库。 3)能判断什么时候结束推理。 4)能将匹配成功的规则记录下来。92013-7-12 福州大学阳光学院计算

机系

国考经典逻辑推理

基本概念

反向推理过程1)用规则集中的规则后件与目标事实进行匹配，

得到匹配的规则集合。 2)从匹配的规则集合中选择一条规则作为使用规 则。 3)把执行的使用规则的前件作为下一个循环的目 标事实 。 4)重复进行，直到达到目标。102013-7-12 福州大学阳光学院计算机系

国考经典逻辑推理

基本概念

反向推理算法(产生式系统)提出获取事实(目标)的请求 目标和任何已知的事实都不匹配 目标和一条规则的结论匹配 进行目标和结论的合一代换 将代换应用于规则的前提 这个结论成为系统的新目标 新目标将执行动作 8) 重复1)~ 7)1) 2) 3) 4) 5) 6) 7)匹配知识库中的 事实 匹配规则的结论， 以更进一步推理 要求用户回答必 要的信息 失败，原目标也 失败

11

2013-7-12

福州大学阳光学院计算机系

国考经典逻辑推理

基本概念反 向 推 理 算 法 流 程找一个假设 在事实库 选一 条知 识让 它的 条件 作为 新假 设 N 有证据 N找出结论部分 含此假设的所 有知识

YY 此假设为真 还有假设

NY N 结 束问用户 有此证据

此假设为假 存入事实库

Y

12

2013-7-12

福州大学阳光学院计算机系

国考经典逻辑推理

基本概念

设计一反向推理系统1) 能根据用户要求或情况提出假设。 2) 能验证此假设是否在数据库中。 3) 能从知识库中将结论部分包含此假设的规则都找出来。 4) 能将找出来的规则的前提部分取出并作为新假设逐条

验证。 5) 能判断假设是否是证据节点，若是，能向用户提出相 应问题并记录结果。 6) 能将匹配成功的规则记录下来。 7) 能判断何时应结束推理。 132013-7-12 福州大学阳光学院计算机系

国考经典逻辑推理

基本概念

推理

冲突消解策略1 规则排序：规则的编排顺序就是规则启用的优先级。 专一性排序：若某一规则的条件部分规定的情况比另 一条规则的条件部分所规定的情况更专门，则这条规 则有较高的优先级。 就近排序：把最近使用的规则放在最优先的位置。 规模排序：按规则条件部分复杂程度排序，越复杂越 优先。

14

2013-7-12

福州大学阳光学院计算机系

国考经典逻辑推理

基本概念

推理

冲突消解策略2 数据排序：把规则条件部分的所有条件项按优先级次 序组织，可用知识的次序由这些知识所含条件按字典 排序方法进行选择。 上下文限制：按问题求解状态或新描述的上下文分块 组织知识库，在某一求解状态，只能使用相对应组中 的知识。 数据冗余限制：若知识的操作产生上下文冗余项时， 则降低该知识的优先级。

15

2013-7-12

福州大学阳光学院计算机系

国考经典逻辑推理

基本概念

模式匹配(代换与合一) 什么叫模式匹配：是指对两个知识模式(谓词公式、框架片

断、语义网络片断等)的比较与耦合，即检查 这两个知识模式是否完全一致或近似一致。模式匹配 有确定性匹配与不确定性匹配。

什么叫合一：一个表达式(公式)的项可以是常量、 变量或函数，合一就是寻找项对变量的代换而使得表 达式(公式)一致的过程。合一是AI中很重要的过程。

16

2013-7-12

福州大学阳光学院计算机系

国考经典逻辑推理

基本概念

模式匹配(代换与合一)定义4.1

代换：有序对的集合S={ t1/x1,t2/x2,…,tn/xn } 表示代换。其中ti/xi表示在公式中用ti代替xi 。

例：公式 P[ x, f(y), B ] s1={ z/x, w/y } 则 P[ z, f(w), B ] s2={ A/y } 则 P[ x, f(A), B ] s3={ g(z)/x } 则 P[ g(z), f(y), B ]用代换s作用于公式E所得到的式子记为Es2013-7-12 福州大学阳光学院计算机系

国考经典逻辑推理

基本概念

模式匹配(代换与合一)定义4.2代换的复合：设有 ={t1/x1,t2/x2,…,tn/xn} 和 ={u1/y1,u2/y2,…,un/yn}是两个代换。则两个代换 的复合 也是一个代换。 ={t1 /x1,t2 /x2,…,tn /xn, u1/y1,u2/y2,…,um/ym} 其中 ti xi 并且 yi {x1,x2,…,xn} 例： s1={ g(x,y)/z,u/w } s2={ A/x, B/y,C/w,D/z,w/u } 则s1 s2 ={ g(A,B)/z, A/x, B/y,w/u } 性质：满足结合律，而不满足交换律 ( 1) 2 = ( 1 2),而一般 1 2 2 1 2013-7-12 福州大学阳光学院计算机系

国考经典逻辑推理

基本概念

模式匹配(代换与合一)定义4.3

可合一：设有公式集合F={F1,F2,…,Fn},若存 在一个代换 使得 F1 =F2 =…=Fn ,则称公式 集F是可合一的。称 为公式集F的一个合一 。 例：F={ P[ x, f(y), B ], P[ x, f(B), B ] } 则 s1={ A/x,B/y } 是公式集F的一个合一 s2={ B/y } 也是公式集F的一个合一2013-7-12 福州大学阳光学院计算机系

国考经典逻辑推理

基本概念

模式匹配(代换与合一)定义4.4 最一般合一mgu (Most General Unifier):设 是公式集F的一个合一，如果对任一个合一 都 存在一个代换 ,使得 = 则称 是一个最 一般的合一。 可以证明mgu是唯一的。 求mgu算法

20

2013-7-12

福州大学阳光学院计算机系

国考经典逻辑推理

基本概念

求mgu算法(设公式集为F) :1)令k=0,Fk=F, k= 。 是一个空代换。 2)若Fk只含一个表达式，则算法停止，

mgu。 3)找出Fk的差异集Dk 。 4)若Dk中存在元素xk和tk ,其中xk是变元， tk是项， 且xk不在tk中出现，则置： k+1 = k {tk/xk} , Fk+1=Fk { tk/xk } , k=k+1, 然后转2)5) 算法终止，F的mgu不存在

k即为所求的

21

2013-7-12

福州大学阳光学院计算机系