第三~四讲——产生式及一阶谓词

1、第三讲 产生式表示法及应用,2020/7/15,“产生式” 的概念由逻辑学家Post l943年提出，产生式表示法又称为产生式规则表示法，但由于缺乏控制策略，不适合开发实际的应用系统。 1972年，Newell和Simon在研究人类的认知模型中开发了基于规则的产生式系统。现在，已经发展成为人工智能系统中最典型的一种基本结构，是专家系统及其他应用人工智能系统中最自然的知识表示及推理的基本模型。,2020/7/15,2,第一节 知识的表示方法,一、确定性规则知识的表示方法 PQ 或IF P THEN Q 二、不确定性规则知识的表示方法 PQ ( 置信度) 或IF P THEN Q ( 置信度),2

2、020/7/15,4,第二节 产生式系统的组成,一个典型的产生式系统由规则库、综合数据库、推理机三大部分组成。它们之间的关系如图所示。,2020/7/15,5,一、 规则库(知识库),用于描述某领域内知识的产生式（规则）集合，是某领域知识的存储器。也称知识库。 包含着将问题从初始状态转换成目标状态（或解状态）的那些变换规则。 是专家系统的核心。,2020/7/15,6,二、 综合数据库,存储所求解问题的初始状态及已知事实，推理的中间结果以及结论。 随着产生式系统问题求解(推理)过程的进展，综合数据库的有些内容(如推理的中间结果)动态变化。综合数据库又称为动态数据库、短期数据库缓冲器。 综合数据

3、库是产生式系统中主要的数据结构，可以通过简单的表、数组、带索引的文件结构、关系数据库等来实现。,2020/7/15,7,三、 推理机,一个或一组程序，用来控制和协调规则库与综合数据库的运行。 包含推理方式和控制策略。,2020/7/15,8,第三节 产生式系统的控制策略,一、作用 确定选用什么规则或如何应用规则。 二、组成 由匹配、选择(冲突解决)、执行三个阶段组成。,匹配 将当前综合数据库中的事实与规则中的条件进行比较 冲突解决 根据预先确定的评价准则决定选择被执行规则 执行 把所选择规则的结论添加到综合数据库，作为新的事实。,2020/7/15,9,综合数据库,索引变量近似过滤,专一性排序

4、、规则排序、规模排序、折射、最新性、特殊性,规则库,匹配,冲突集,规则触发,规则执行,冲突消解,推理控制,2020/7/15,10,第四节 产生式系统的推理方式,产生式系统的问题求解过程事实上就是对解空间的搜索过程，又称为推理过程，根据推理过程进行的方向或者搜索的方向可分为正向推理、反向推理、双向推理。,2020/7/15,11,一、正向推理,它从已知事实出发，通过与规则库中产生式的条件匹配，然后执行匹配规则的动作，求得结论。正向推理方式又称为数据驱动方式。 推理过程,综合数据库中含有事实P1，则应用则进行正向推理，即从P1出发推导出q3 的过程：,如规则集：规则1：P1P2 规则2：P2P3

5、 规则3：P3q3,2020/7/15,12,产生式系统正向推理的一种算法,(1) 读入初始数据(事实)集到综合数据库； (2) Repeat 取出第i条规则； 规则i 所有前件与综合数据库的所有事实进行比较； if 规则匹配成功 then 把规则加入冲突集； if 冲突集为空 then goto (3)； 冲突消解； 把所选择规则的结论加入综合数据库； if 到达目标节点 then goto (3)； i=i+1； (3) 结束。,2020/7/15,13,例：初始状态 Start 目标状态 Goal,规则库,R1：if P and Q then Goal R2：if R and S the

6、n P R3：if W and R then Q R4：if T and U then Q R5：if V then S R6：if Start then V and R and Q,冲突原则： 选取最久以前被触发的或根本没有被触发的规则 如果出现“平局”，选取其中的第一个规则,2020/7/15,14,二、反向推理,基本原理：将目标与规则库中规则的动作部分匹配，然后把匹配规则的条件作为要证明的子目标，求得已知事实。反向推理方式又称为目标驱动方式 推理过程,如规则1：P1P2 规则2：P2P3 规则3： P3q3 应用反向推理方法获取目标q3的过程：,2020/7/15,15,例：初始状态 S

7、tart 目标状态 Goal,R1：if P and Q then Goal R2：if R and S then P R3：if W and R then Q R4：if T and U then Q R5：if V then S R6：if Start then V and R and Q,冲突原则： 选取最久以前被触发的或根本没有被触发的规则 如果出现“平局”，选取其中的第一个规则,2020/7/15,16,三、双向推理,双向推理是一种既正向又反向的推理。推理从两个方向同时进行，直至某个中间界面上两个方向结果相符便成功结束。 控制策略比前两种方法都要复杂。,2020/7/15,17,第五

8、节 对产生式系统的评价,一、特点,具有丰富的知识表示能力，可以简单直观的规则方式表达人类的经验性知识。 知识表达模块化、结构化，每条规则具有相同的格式且相对独立。规则的组合、修改、增、删比较容易，规则的收集、整理比较方便。 容易排除故障，当系统工作异常时，通过跟踪产生式规则的触发序列，就可容易地发现故障，为系统调试和维护提供便利条件。,2020/7/15,18,产生式系统的规则链接推理过程相似于人类求解问题时的逻辑思维过程，可把产生式系统用作人类行为的启发式模型，模拟人类的逻辑思维过程。 推理方向的可逆性。由于产生式规则的前件和后件结构类似，可同时进行正向和反向推理，即混合推理。,2020/7

9、/15,19,二、适合场合,知识结构类似于产生式规则的领域，如医疗诊断系统。其特点是领域知识比较零乱，由大量经验性的独立事实和规则组成。 领域知识中包含一系列相互独立的动作，可以自然地用产生式规则的后件来表达的领域，如医院的病人监护系统。 领域知识可方便地从应用中分离出来的领域，如经典分类学等。,2020/7/15,20,三、缺陷,推理效率低 速度慢 实时性能差 容易产生组合爆炸,试验表明，产生式系统在匹配阶段所花费的时间大约为产生式系统工作周期的90。而冲突消解及执行阶段所花费的时间大约占工作周期的10。,2020/7/15,21,若欲求解的问题可视为问题空间中一个状态到另一个状态的变换序列

10、，则可用产生式系统求解。诸如 8数码(8 Puzzle)、旅行商(traveling salesman)、汉诺塔(Tower of Hanoi)、传教士与食人魔(Missionaries and cannibals)、符号积分(Symbolic integration)、猴子与香蕉(Monkey and bananas)等经典人工智能问题的求解，以人类专家知识为基础的专家系统的问题求解，从本质上都可以看作是从初始状态到目标状态的推导变换过程，因而都可用产生式系统来求解。,2020/7/15,22,专家系统,专家系统结构选择恰当与否，与专家系统的适用性和有效性密切相关的。,推理机根据动态库的当前

11、状态，利用知识库中的知识进行推理。,用户界面亦称人机接口，完成信息的内部形式和人可接收的形式之间进行转换。,动态库是用来记录控制信息、中间假设和中间结果,知识获取负责建立、 修改与扩充知识库， 对知识库的一致性、 完整性等进行维护。,包括:1与当前问题有关的数据信息；2 一般知识和领域知识。规则、网络和过程等形式表示。,2020/7/15,23,专家系统的开发过程 专家系统是一个复杂的智能软件，与一般软件类似，但又有不同的特点。 一般软件处理的对象是数值、文字、图形等信息，且有固定的算法序列，而专家系统软件处理的对象是以符号表示的知识，在运行过程中常有回溯发生，因此专家系统的开发过程与一般软件

12、的开发有所不同。 专家系统的创始人费根鲍姆教授把开发专家系统的技术称之为知识工程，即以知识获取、知识表示、知识运用(推理)为中心。根据这个思想，可把专家系统的开发过程分为以下几个阶段。,2020/7/15,24,1 问题定义与系统分析 在着手开发一个专家系统时，首先应了解清楚用户的需求，确定欲解决的问题的范围(领域)，系统所要达到的目标，系统功能，性能指标，输入输出，使用对象，人机接口形式，运行软硬件环境等。在此基础上进行系统可行性论证及经济效益或社会效益分析。最后写出系统工作的数据(信息)流程图，写出分析报告及有关文档。,2020/7/15,25,2 知识获取 知识获取阶段的主要工作是根据所

13、确定的系统目标及限定的问题求解范围，收集专家知识。在当前的技术条件下主要是通过走访多个领域专家及现场技术人员，查阅国内外大量文献资料来收集、归纳、整理领域知识。 3 知识表示 知识表示阶段的任务是根据领域知识的性质，选择一种或组合数种知识表示方法，如前面介绍过的谓词逻辑表示法，框架表示法，产生式系统表示法等，把获取到的专家知识逻辑地表达出来，并以适当的形式存储到计算机中。,2020/7/15,26,4 软件实现 这一阶段的工作与一般软件设计类似，应遵循软件工程的原则，进行系统设计、编码、测试，建立知识库，实现推理机，动态存储器，人机接口，知识获取等专家系统程序模块，构成一个可运行的专家系统原型

14、软件。,2020/7/15,27,5 系统测试与评价 专家系统开发是一个长期反馈的过程，对所生成的专家系统原型软件必须反复进行测试，评价，发现并改正其中的错误，才能使之实用。 测试与评价的主要内容包括： 知识表示模式的选取是否恰当； 知识库中的知识的正确性，完整性，一致性如何； 知识库维护是否容易； 所采用的推理方法和技术是否正确，推导出的结论是否可信，用户是否满意； 人机接口使用是否方便，实用； 系统的成本与效益情况等。,2020/7/15,28,新一代专家系统,新一代专家系统的特征： (1) 并行技术与分布处理 (2) 多专家系统协同工作(synergetic expert system)

15、 (3) 具有自学习功能 (4) 引入新的推理机制 (5) 具有自纠错和自完善能力 (6) 先进的智能人机接口,第四讲 基于逻辑的问题求解方法,逻辑表示法 用数理逻辑表示知识 经典逻辑（标准逻辑） 非经典逻辑 一阶谓词是一种形式语言，可以表示和推理客观世界的属性和关系。,命题逻辑和一阶谓词逻辑,模态逻辑、时序逻辑、非单调逻辑、多值逻辑,2020/7/15,29,命题 取值为真或假(表示是否成立)的句子 谓词 带有变量(参数)的命题 谓词 p (x1，x2，xn) 一元谓词 谓词与一个个体的属性 blue ( desk ) 多元谓词 谓词与多个个体间的关系 TEACHER(x, y) 一阶谓词

16、xi 为常量、变元或函数 高阶谓词 xi 本身为一阶谓词,第一节 一阶谓词逻辑基础,谓词用来描述个体（可以独立存在的事物）之间的关系或属性,2020/7/15,30,一、谓词逻辑的符号体系,常量以小写字母组成的符号串 变量符号习惯上是大写字母开始 函数符号通常以小写字母或小写字母串表示 谓词符号通常以小写字母或小写字母串表示，不可拆散 逗号及括号(圆括号、方括号、花括号) 将变量符号、函数符号、谓词符号及常量隔开，仅用于构建公式，表示论域内的关系。 函数与谓词的形式分别为： 谓词 p(x1，x2，xn) 函数 f (xl，x2，xn),2020/7/15,31,连接词,：否定(非) inroo

17、m (robot，r2) 合取(与) like ( he，music) like (he，painting) 析取(或) plays ( liming，basketball) plays( liming ，football) 蕴含 (IFTHEN) owns ( she，book-1) color(book-1，blue) 等价(双条件),2020/7/15,32,量词,量词是由量词符号和被量化的变元所组成的表达式 ：全称量词符号，表示所有的。 例如，所有的篮球运动员都很高，表示为 (X) (basketball_player(X) tall(X) ：存在量词符号，表示存在某一些。 例如，一些

18、人喜欢狗，表示为 (X ) (person(X) likes(X, dog),2020/7/15,33,二、谓词逻辑的知识表示,若量词仅对谓词的个体(变量)而不能对谓词自身起限定作用，即把谓词名视为常量，称其为一阶谓词。 一阶谓词逻辑可严密而精确地表达复杂的人类知识，在很多领域可以得到直接的应用。 可以表示： 事物的状态、属性、概念的事实性知识； 否定、析取或合取符号连接起来的谓词公式 事物的因果关系 蕴含式表示 x y,2020/7/15,34,1 形式化的领域,在形式化的领域中，知识或信息是用对象和它们的属性，以及它们之间的关系表示的。 关系数据库可以认为是采用了一阶谓词逻辑的形式，每个关

19、系类型对应着一个谓词。,occupant( owen，301) telephone (741，301),2020/7/15,35,2 非形式化的领域,例如 所有的整数不是偶数就是奇数,定义 integer(X): X为整数； even(X): X为偶数; odd(X): X为奇数 谓词表示 ( X) (integer(X) even (X)odd (X) ),2020/7/15,36,在人工智能中常用的是一阶谓词逻辑，因此本章介绍的内容主要针对一阶谓词逻辑。,设有三个积木块a，b，c，它们之间的位置关系可用下列谓词表示： on (a, b) on (b, c),on (a, c),on (a,

20、 b)on (b, c) on (a, c),2020/7/15,37,三、谓词演算公式,原子公式 不含任何连接词及量词的谓词公式 p ( X1, X2, ，Xn) ，X个体变量 谓词演算的合式公式( WFF well-formed formula) 原子公式是合式公式。 若A是合式公式，则A也是合式公式。 若A，B是合式公式，则AB，AB，AB，AB，也都是合式公式。 若A是合式公式，X是个体变量，则(X)A，(X)A也是合式公式 只有按a)d)所得的公式才是合式公式。,2020/7/15,38,第二节 逻辑推理,如果谓词公式p对任意非空个体域上的任一解释都取得真值true，则称p永真。 对

21、于谓词公式p，如果至少存在非空个体域D上的一个解释，使公式p在此解释下的真值为true，则称公式p在D上是可满足的。谓词公式的可满足性也称为相容性。 如果谓词公式p对非空个体域D上的任一解释都取真值false，则称P永假。谓词公式的永假性又称不可满足性或不相容性。,2020/7/15,39,一、等价式,交换律PQ QP PQ QP 结合律(PQ) R P(QR) (PQ)R P(QR) 分配律P(QR) (PQ)(PR) P(QR) (PQ)(PR) 摩根定理 (PQ) PQ (PQ) P Q 否定之否定 (P) P,2020/7/15,40,吸收律 P(PQ) P P(PQ) P 补余律 P

22、P TPP F 逆否定律 PQ Q PPQ P Q 量词转换律 (x)P(x) (x)(P(x) (x)P(x) ( x)(P(x) 量词分配律,2020/7/15,41,p(a)p(a)p(b) p(a)p(a)p(b) p(a)p(a)p(b) 或 p(a)p(a)p(b) 是永真的,2020/7/15,42,二、自然演绎推理,1 析取三段论 P, PQ Q 2 假言推理 P, PQ Q 3 假言三段论 PQ ，QR P R 4 拒取三段论 Q, PQ P,2020/7/15,43,例 设已知如下事实： (1) 只要是需要编程序的课，王程都喜欢。 (2) 所有的程序设计语言课都是需要编程序

23、的课 (3) C是一门程序设计语言课。 求证：王程喜欢C这门课。 证明：首先定义谓词 program (X) X是需要编程序的课。 like (X,Y) X喜欢Y。 language (X) X 是门程序设计语言课。,program (X)like (wang, X),(X)( language (X) program (X),language (C),2020/7/15,44,把已知事实及待求解问题用谓词公式表示如下： program (X) like ( wang, X)、 (X)( language (X) program (X)、language (C) 应用推理规则进行推理： 全称例

24、化 language (Y) program (Y) 假言推理 language (C), language (Y) program (Y) program (C) 假言推理 program (C), program (X) like ( wang, X) like ( wang, C) 王程喜欢C这门课。,把一个真的谓词公式中的任意的全称量词变量替换为定义域中的任意的适当项。,2020/7/15,45,二、归结(消解)原理简介,1965年Robinson发现的归结原理(refutation)。是以逻辑演绎为基础进行逻辑推理。它的基本思想可用如下定理解释： 定理 Q为P的逻辑结论，当且仅当 (

25、P) (Q)是不可满足的。 把已知条件表示谓词公式，再化为一组子句； 欲证的目标也化为一个子句的否定， 把目标子句与条件子句合在一起推理，若能推出矛盾(空子句)，则可证明此目标是成立的。,2020/7/15,46,已知两子句 C1=P C1 和 C2= P C2 ， C1不等于C2，其中一个所含的 P，刚好是另一个子句中P 的否定，根据这两个子句，推出一个新子句，即 R(C1, C2)= C1 C2 ， 称作这两个子句的归结式。 P、P为互补对。 实现归结推理的关键步骤是置换合一与寻求子句集中的互补对。,2020/7/15,47,归结式 ,1 析取三段论 2 合并 3 重言式 4 空子句(矛盾

26、) 5 假言三段论,2020/7/15,48,自动归结证明的过程：,(1)否定G，得 G； (2) 把G添加到S中，得新集合S, G； (3) 把新产生的集合S, G化成子句集； (4) 重复归结过程，推导出一个表示矛盾的空子句。,2020/7/15,49,WFF化为子句的基本步骤,重复运用蕴含等价式，消去蕴含 p(X) q(X) p(X) q(X) 减少的辖域，使最多只作用一个谓词上 (p(X) q(X) q(X) q(X) (X) p(X) ( X) p(X) 变量改名 ( X)p(X) (Y)p(Y) 移所有量词到前部，形成前束范式 (X) p(X) (W)q(W) 改为 (X) (W)

27、 p(X) q(W),2020/7/15,50,消去存在量词，形成对应的S范式标准式 (X) p(X) q (g(X) W=g(X) 利用分配律，把母式化成析取式的合取式。 p(X) (q(X) r(X) (p(X) q(X) (p(X) r(X) 以逗号替代所有的 ，形成子句集,母式,Skolem函数,2020/7/15,51,例 已知每个使用Internet的人都想从网络获得信息，证明如网络没有信息就不会有人使用Internet。,证：设U (x, y)： 表示x使用y； G(v, u)： 表示v得到u； I(z)： 表示z是Internet； F (u)： 表示u是信息； 已知： W=(

28、x) (y)(U(x, y) I(y) (u)( F(u)G (x, u) 结论：G(u) F (u) (x)(y)( I(y) U (x, y),2020/7/15,52,条件：W= (x) (y)(U(x, y)I(y)(u)(F(u)E(x, u) 变换为子句集。,(1) 消去蕴含 办法：P(x) Q(x) P(x) Q(x) W = (x)(y)(U(x, y)I(y)(u)(F(u)E(x, u) (2) 把的辖域减少到最多只作用于一个谓词 利用(P(x)Q(x) P(x)Q(x)；( x) P(x)( x)P(x) W = (x) (y)(U(x, y)I(y)(u) (F(u)E

29、(x, u) (x) (y) U(x, y)I(y)(u) (F(u)E(x, u) 消存在量词,形成S范式 W(x)(y) U(x, y)I(y) F(f(x)E(x, f(x),母式,u=f(x),2020/7/15,53,(4) 把母式化成合取范式 U(x, y)I(y)F(f(x)E(x, f(x) =U(x, y) I(y)(F(f(x) U(x, y) I(y)E(x, f(x) (5)以逗号替代所有的(消去符号)，形成子句集 S = U(x, y) I(y)(F(f(x), U(x, y) I(y)E(x, f(x),前提 W 对应子句集的两个子句： U(x，y)I(y)(F(f

30、(x) U(x，y)I(y)E(x，f(x),2020/7/15,54,结论：G(u)F(u)(x) (y)(I(y)U(x，y) 否定结论G，并化为S 范式 G = (u)F(u)(x)(y)(I(y)U(x，y) (u)F(u)(x)(y)(I(y)U(x，y) (u)F(u) (x)(y) (I(y)U(x，y) (x)(y)(u)F(u)I(y)U(x，y) 引入常量c，消去G中的存在量词，得 (x)(y)F(c)I(y)U(x，y) 隐去全称量词，得到G对应子句集的三个子句： F(c) I(y) U(x，y),2020/7/15,55,对(1)施加置换 cf(x)，再与(3)归结得

31、(6) U(x, y)I(y) 由(4)，(6)归结，得 (7) I(y) (5)，(7)归结，得 U(x, y) U(x, y) = 故，结论G得证。,(1) U(x, y)I(y)(F(f(x) (2) U(x, y)I(y)E(x, f(x) (3) F(c) (4) I(y) (5) U(x, y),U(x, y)I(y)(F(f(x),F(c),cf(x),U(x, y)I(y),归结反演树,2020/7/15,56,归结策略,归结演绎推理实际上就是从子句集中不断寻找可进行归结的子句对，并通过对这些子句对的归结，最终得出一个空子句的过程。 盲目地全面进行归结，产生许多无用的归结式，严

32、重的是会产生组合爆炸问题。 常用的归结策略可分为两大类: 删除策略通过删除某些无用的子句来缩小归结范围； 限制策略通过对参加归结的子句进行某些限制，来减少归结的盲目性，以尽快得到空子句。,2020/7/15,57,例 等腰三角形ABC，AD为底边的高，试证明BD=CD.,证明：,已知: AB=AC ADBC 求证：BD=CD,E(AB,AC)，E(ADB, ADC) ， E(ADB, 90),(x)(y)E(mx,my) E(nx,ny) E(lx,ly) 子句：E(mx,my) E(nx,ny) E(lx,ly),E(rp, tq) 表示三角形p、q的两个边(角)等,E(BD,CD), E(

33、BD, CD),直角三角形两边相等，第三遍也相等。,2020/7/15,58,问题求解,例 已知：张和李是同班同学。如果x和y是同班同学，则x的教室也是y的教室。现在张在302教室上课。 问：现在李在哪里上课?,解：定义谓词： C(x,y) x和y是同班同学 At(x，u) x在u教室上课 已知前提用谓词公式表示， 并化为子句集： C(zhang，1i) C(zhang，1i) (x)(y)(u)(C(x,y)At(x,u)At(y,u) C(x,y)At(x,u)At(y,u) At (zhang, 302) At (zhang, 302),(C(x,y) At(x,u)At(y,u),20

34、20/7/15,59,问题求解（续）,把目标的否定用谓词公式表示如下 (v)At(1i，v) 把目标的否定化成子句式，并用重言式At(li,v)At(li,v)替代,子句集：C(zhang，1i)、C(x,y)At(x,u)At(y,u)、At(zhang，302)、At(li,v)At(li,v),At(li,v)At(li,v),C(x,y)At(x,u)At(y,u),At(li,v) C(x,li)At(x,v),C(zhang,1i),At(li,v) At(zhang,v),At(zhang, 302),At(li, 302), li/y, v/u, zhang/x, 302/v,

35、2020/7/15,60,WFF的基本等价式及推理规则现一并归纳于下： 1 双重否定律(否定之否定) (P) P 2 蕴含等价式P(x) Q(x) P(x) Q(x) 3 摩根定律 (P(x) Q(x) P(x) Q(x) (P(x) Q(x) P(x) Q(x) 4 逆否律 P(x) Q(x) Q(x) P(x) 5 分配律 P(x) (Q(x) R(x) (P(x) Q(x) (P(x) R(x) P(x) (Q(x) R(x) (P(x) Q(x) (P(x) R(x) 6 交换律 P(x) Q(x) Q(x) P(x) P(x) Q(x) Q(x) P(x) 7 结合律 (P(x) Q(x) R(x) P(x) (Q(x) R(x) (P(x) R(x) R(x) P(x) (Q(x) R(x),2020/7/15,61,WFF的基本等价式及推理规则（续）： 8 量词转换律 (x) P(x)