概况三
点击此处输入相关文本内容 点击此处输入相关文本内容
2
overview
• 1. Rule based deduction system • 2. Production system • 3. Uncertainty knowledge and reasoning
3
归结反演的策略
以上讨论的几种基本的归结策略，在具体应用时可 把几种策略组合在一起使用。归结演绎推理是在自 动定理证明领域影响较大的一种推理方法，它比较 简单且又便于在计算机上实现。但由于它要求把逻 辑公式转化成子句集，就可能丢失蕴含式含有的逻
18
规则逆向演绎系统
19
规则逆向演绎系统
20
规则双向演绎系统
• 规则双向演绎系统的主要复杂之处在于 其终止条件，终止涉及两个图结构之间的 适当交接处。这些结构可由标有合一文字 的节点上的匹配棱线来连接。用对应的mgu 来标记匹配。
21
代换的一致性
• 无论对于正向演绎、逆向演绎还是双向演绎，
都要求推理过程中所用的代换集合具有一致性。
与/或形表示，其变换过程与正向演绎推理中对已 知事实的变换相似，只是要用存在量词约束的变 元的Skolem函数替换由全称量词约束的相应变元， 并且消去全称量词，然后再消去存在量词，且使 各主要析取式中的变元不同名。
15
规则逆向演绎系统
16
规则逆向演绎系统
• 2ቤተ መጻሕፍቲ ባይዱB规则的表示形式
B规则的表示形式为： W→L 其中，W为任 一与/或形公式，L为文字。如果已知的B规则不是 所要求的形式，可以把它化成规定的形式。
辑控制信息。例如下列逻辑公式：
(┐A∧┐B) →C
(┐A∧┐C) →B
(┐B∧┐C) →A ┐A→(B∨C)
A∨B∨C
┐B→(A∨C)
┐C→(A∨B)
4
1 规则演绎系统
• 对于许多公式来说，子句形是一种低效 率的表达式，因为一些重要信息可能在求 取子句形过程中丢失。可以采用易于叙述 的if then规则来求解问题，这种基于规则的 系统叫做规则演绎系统。
5
规则正向演绎系统
• 基于规则的演绎系统和产生式系统，均有 两种推理方式：正向推理(forward chanining)和逆向推理(backward chaining)。 正向推理：从if部分向then部分推理的过程， 它是从事实或状况向目标或动作进行操作 的。 逆向推理：从then部分向if部分推理的过程， 它是从目标或动作向事实或状况进行操作 的。
22
剪枝策略
• 剪枝策略的基本思想：每当选用一条规 则时，就进行一次一致性检查，如果当前 的部分解图是一致的，则继续向下扩展， 否则就放弃该规则而选用其他侯选规则。
23
剪枝策略
24
2 产生式系统
• 美国数学家Post，1943年提出了一种计算形式体 系里所使用的术语。主要是使用类似文法的规则， 对符号串做替换运算。这就是最早的一个产生式 系统。
比如：W→(L1∧L2)
W→(L1∨L2)？
W→L1, W→L2
• 3、已知事实的表示形式
在逆向演绎推理中，要求已知事实是文字的 合取形式，即形如F1∧F2∧…∧Fn
17
规则逆向演绎系统
• 4、推理过程 应用B规则进行逆向演绎推理的目的是求解问
题，从目标公式的与/或树出发，通过运用B规则 来进行求解。其推理过程为： 1) 先用与/或树把目标公式表示出来。 2) 用B规则的右部和与/或树的叶节点进行匹配，将 匹配成功的B规则加入到与/或树中。 3) 重复进行步骤2)，直到产生某个终止在事实节点 上的一致解图为止。
7
规则正向演绎系统
8
规则正向演绎系统
2、F规则的表示形式 在与/或形正向演绎推理中，要求F规则
具有如下形式：L→W 其中，L为单文字，W为与/或形。如果领 域知识的表示形式不是所要求的形式，则 需通过变换将它变成规定的形式。 3、目标公式的表示形式 在与/或形正向演绎推理中，要求目标公式 用子句表示，否则就需要化成子句形式。
• 到了60年代，产生式系统成为认知心理学研究人 类心理活动中信息加工过程的基础，由此心理学 家认为，人脑对知识的存储就是产生式形式。因 此，用它来建立人类认知模型。
10
规则正向演绎系统
11
规则正向演绎系统
12
规则正向演绎系统
13
规则正向演绎系统
14
规则逆向演绎系统
• 与/或形逆向演绎推理是从待证明的问题出发，逆 向使用蕴式(B规则)进行演绎推理，直至得到包含 已知事实的终止条件为止。
• 1、目标公式的与/或形及其与/或树表示 在与/或形逆向演绎推理中，要求目标公式用
6
规则正向演绎系统
1.事实表达式的与或形变换 在基于规则的正向演绎系统中，我们把事实表示为非蕴涵
形式的与或形，要把一个公式化为与或形，可采用下列步骤 (1) 利用(W1→W2)和(┐W1∨W2)的等价关系，消去符号→ (2) 用狄·摩根(De Morgan)定律把否定符号移进括号内，直到
每个否定符号的辖域最多只含有一个谓词为止。 (3) 对所得到的表达式进行Skolem化和前束化。 (4) 对全称量词辖域内的变量进行改名和变量标准化，而存
在量词量化变量用Skolem函数代替。 (5) 删去全称量词，且使各主要合取式中的变元不同名。
例如，我们有事实表达式 ( x ) y ( ) Q ( { y ,x ) [ R ( y ( ) P ( y ) S ) ( x ,y )]}
按上述步骤进行转化后得到与/或形表达式：
Q ( z ,a ) { R [ ( y ) ( P ( y ) ]S ( a ,y )]}
Review
• 1、Search Engine ---- PageRank • 2、Data Mining ----Association Rule • 3、Resolution --- based on clause
1
整体概述
概况一
点击此处输入相关文本内容 点击此处输入相关文本内容
概况二
点击此处输入相关文本内容 点击此处输入相关文本内容
9
规则正向演绎系统
4、推理过程
应用F规则进行推理的目的在于证明某个目标公 式。其推理过程为： 1) 首先用与/或树把已知事实表示出来。 2) 用F规则的左部和与/或树的叶节点进行匹 配，将
匹配成功的F规则加入与/或树中。 3) 重复进行步骤2)，直到产生一个含有以目标节点 作
为终止节点的解图为止。