第三~四讲-产生式及一阶谓词课件

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

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

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

4、突集规则触发规则执行冲突消解推理控制2022/7/2810第四节 产生式系统的推理方式 产生式系统的问题求解过程事实上就是对解空间的搜索过程，又称为推理过程，根据推理过程进行的方向或者搜索的方向可分为正向推理、反向推理、双向推理。2022/7/2811一、正向推理它从已知事实出发，通过与规则库中产生式的条件匹配，然后执行匹配规则的动作，求得结论。正向推理方式又称为数据驱动方式。推理过程 综合数据库中含有事实P1，则应用则进行正向推理，即从P1出发推导出q3 的过程：如规则集：规则1：P1P2 规则2：P2P3 规则3：P3q32022/7/2812产生式系统正向推理的一种算法(1) 读入初始数

5、据(事实)集到综合数据库；(2) Repeat 取出第i条规则； 规则i 所有前件与综合数据库的所有事实进行比较； if 规则匹配成功 then 把规则加入冲突集； if 冲突集为空 then goto (3)； 冲突消解； 把所选择规则的结论加入综合数据库； if 到达目标节点 then goto (3)； i=i+1； (3) 结束。2022/7/2813例：初始状态 Start 目标状态 Goal规则库R1：if P and Q then Goal R2：if R and S then PR3：if W and R then Q R4：if T and U then Q R5：if V

6、then SR6：if Start then V and R and Q执行过程动态库冲突集触发规则0Start1Start, V, R, Q6, 552Start, V, R, Q, S6, 5, 223Start, V, R, Q, S,P6, 5, 2, 114Start, V, R, Q, S,P, Goal6, 5, 2, 1终止冲突原则： 选取最久以前被触发的或根本没有被触发的规则 如果出现“平局”，选取其中的第一个规则2022/7/2814二、反向推理基本原理：将目标与规则库中规则的动作部分匹配，然后把匹配规则的条件作为要证明的子目标，求得已知事实。反向推理方式又称为目标驱动方式

7、推理过程如规则1：P1P2 规则2：P2P3 规则3： P3q3应用反向推理方法获取目标q3的过程：2022/7/2815例：初始状态 Start 目标状态 GoalR1：if P and Q then Goal R2：if R and S then PR3：if W and R then Q R4：if T and U then Q R5：if V then SR6：if Start then V and R and Q执行过程动态库冲突集触发规则0Goal111Goal, P, Q1, 2, 3, 422Goal, P, Q, R, S1, 2, 3, 4, 533Goal, P, Q,

8、R, S,W1, 2, 3, 4, 544Goal, P, Q, R, S, W, T, U1, 2, 3, 4, 555Goal, P, Q, R, S, W, T, U, V1, 2, 3, 4, 5, 666Goal, P,Q, R, S, W, T, U, V, Start1, 2, 3, 4, 5, 6终止冲突原则： 选取最久以前被触发的或根本没有被触发的规则 如果出现“平局”，选取其中的第一个规则2022/7/2816三、双向推理双向推理是一种既正向又反向的推理。推理从两个方向同时进行，直至某个中间界面上两个方向结果相符便成功结束。控制策略比前两种方法都要复杂。2022/7/281

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

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

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

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

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

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

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

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

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

18、ic) like (he，painting) 析取(或) plays ( liming，basketball) plays( liming ，football) 蕴含 (IFTHEN) owns ( she，book-1) color(book-1，blue) 等价(双条件)2022/7/2832量词 量词是由量词符号和被量化的变元所组成的表达式：全称量词符号，表示所有的。 例如，所有的篮球运动员都很高，表示为 (X) (basketball_player(X) tall(X)：存在量词符号，表示存在某一些。 例如，一些人喜欢狗，表示为 (X ) (person(X) likes(X, dog

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

20、741，301)2022/7/28352 非形式化的领域例如 所有的整数不是偶数就是奇数定义 integer(X): X为整数； even(X): X为偶数; odd(X): X为奇数 谓词表示 ( X) (integer(X) even (X)odd (X) )2022/7/2836 在人工智能中常用的是一阶谓词逻辑，因此本章介绍的内容主要针对一阶谓词逻辑。 设有三个积木块a，b，c，它们之间的位置关系可用下列谓词表示： on (a, b) on (b, c) on (a, c) on (a, b)on (b, c) on (a, c)2022/7/2837三、谓词演算公式原子公式 不含任何

21、连接词及量词的谓词公式 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)所得的公式才是合式公式。2022/7/2838第二节 逻辑推理如果谓词公式p对任意非空个体域上的任一解释都取得真值true，则称p永真。对于谓词公式p，如果至少存在非空个体域D上的一个解释，使公式p在此解释下的真值为true，则称公式p在D上是可满足的。谓词公式的可满

22、足性也称为相容性。如果谓词公式p对非空个体域D上的任一解释都取真值false，则称P永假。谓词公式的永假性又称不可满足性或不相容性。 2022/7/2839一、等价式交换律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 2022/7/2840吸收律 P(PQ) P P(PQ) P补余律 PP TPP F逆否定律 PQ Q PPQ P Q量词转换律 (x)P(x) (x)(P(x) (x)P(x) ( x)(P(x)量词分配律2022

23、/7/2841p(a)p(b)p(a)p(b)p(a)p(a)p(b)p(a)p(a)p(b)ttttttftttfttttfffttp(a)p(a)p(b) p(a)p(a)p(b)p(a)p(a)p(b) 或 p(a)p(a)p(b) 是永真的2022/7/2842二、自然演绎推理1 析取三段论 P, PQ Q2 假言推理 P, PQ Q3 假言三段论 PQ ，QR P R4 拒取三段论 Q, PQ P2022/7/2843 例 设已知如下事实： (1) 只要是需要编程序的课，王程都喜欢。 (2) 所有的程序设计语言课都是需要编程序的课 (3) C是一门程序设计语言课。求证：王程喜欢C这门

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

25、guage (C), language (Y) program (Y) program (C) 假言推理 program (C), program (X) like ( wang, X) like ( wang, C) 王程喜欢C这门课。 把一个真的谓词公式中的任意的全称量词变量替换为定义域中的任意的适当项。2022/7/2845二、归结(消解)原理简介 1965年Robinson发现的归结原理(refutation)。是以逻辑演绎为基础进行逻辑推理。它的基本思想可用如下定理解释： 定理 Q为P的逻辑结论，当且仅当 (P) (Q)是不可满足的。 把已知条件表示谓词公式，再化为一组子句； 欲证的

26、目标也化为一个子句的否定， 把目标子句与条件子句合在一起推理，若能推出矛盾(空子句)，则可证明此目标是成立的。2022/7/2846 已知两子句 C1=P C1 和 C2= P C2 ， C1不等于C2，其中一个所含的 P，刚好是另一个子句中P 的否定，根据这两个子句，推出一个新子句，即R(C1, C2)= C1 C2 ，称作这两个子句的归结式。 P、P为互补对。 实现归结推理的关键步骤是置换合一与寻求子句集中的互补对。2022/7/2847归结式 PQ PQ归结式 Q父辈1 析取三段论 2 合并3 重言式4 空子句(矛盾)5 假言三段论P PQ (PQ) 归结式 Q父辈P Q P Q归结式

27、Q Q 父辈P Q P Q P P P P归结式 NIL 父辈PQ (PQ) QR (QR) 归结式 PR (PR) 父辈2022/7/2848自动归结证明的过程：(1)否定G，得 G；(2) 把G添加到S中，得新集合S, G；(3) 把新产生的集合S, G化成子句集；(4) 重复归结过程，推导出一个表示矛盾的空子句。 2022/7/2849WFF化为子句的基本步骤重复运用蕴含等价式，消去蕴含 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) 移所有量

28、词到前部，形成前束范式 (X) p(X) (W)q(W) 改为 (X) (W) p(X) q(W)2022/7/2850 消去存在量词，形成对应的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函数2022/7/2851例 已知每个使用Internet的人都想从网络获得信息，证明如网络没有信息就不会有人使用Internet。证：设U (x, y)： 表示x使用y； G(v, u)： 表示v得到u； I(z)： 表示z是Inter

29、net； F (u)： 表示u是信息； 已知： W=(x) (y)(U(x, y) I(y) (u)( F(u)G (x, u) 结论：G(u) F (u) (x)(y)( I(y) U (x, y)2022/7/2852 条件：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)

30、(U(x, y)I(y)(u) (F(u)E(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)2022/7/2853 (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 对应子句集的两个子句

31、： U(x，y)I(y)(F(f(x) U(x，y)I(y)E(x，f(x) 2022/7/2854 结论：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) 2022/7/2855对(1)施加置换 cf

32、(x)，再与(3)归结得 (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) I(y) U(x, y) U(x, y) NIL归结反演树2022/7/2856归结策略 归结演绎推理实际上就是从子句集中不断寻找可进行归结的子句对，并通过对这些子句对的归结，最终得出一个空子句的过

33、程。 盲目地全面进行归结，产生许多无用的归结式，严重的是会产生组合爆炸问题。 常用的归结策略可分为两大类:删除策略通过删除某些无用的子句来缩小归结范围；限制策略通过对参加归结的子句进行某些限制，来减少归结的盲目性，以尽快得到空子句。 2022/7/2857例 等腰三角形ABC，AD为底边的高，试证明BD=CD.证明：已知: AB=AC ADBC 求证：BD=CDE(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的两个边(

34、角)等E(BD,CD), E(BD, CD) 直角三角形两边相等，第三遍也相等。ABCD2022/7/2858问题求解例 已知：张和李是同班同学。如果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)

35、At(y,u)2022/7/2859问题求解（续）把目标的否定用谓词公式表示如下 (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/v2022/7/

36、2860WFF的基本等价式及推理规则现一并归纳于下： 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)2022/