人工智能原理3-1

ReviewSearchTechnology1、StateSpaceExpression2、And-OrTreeExpression3、BlindSearch4、HeuristicSearch5、A*

Algorithm6、GameTreeSearch1Summary1、BlindSearch2、HeuristicSearch

总之搜索策略是人工智能研究的核心问题之一，已有许多成熟的结果，并在解决人工智能的有关问题中得到广泛应用。但目前仍有若干深入的问题有待发展，特别是结合实际问题，探索有效实用的策略仍是一个研究和开发的工作，还应当给予足够的重视。

21搜索引擎搜索引擎系统一般由蜘蛛（也叫网页爬行器）、切词器、索引器、查询器几部分组成。蜘蛛负责网页信息的抓取工作，一般情况下切词器和索引器一起使用，它们负责将抓取的网页内容进行切词处理并自动进行标引，建立索引数据库。查询器根据用户查询条件检索索引数据库并对检索结果进行排序和集合运算，如并集、交集运算，再提取网页简单摘要信息反馈给查询用户。31搜索引擎Google搜索引擎从功能上同样分为三大部分：网页爬行、标引入库和用户查询。网页爬行主要负责网页的抓取，由URL服务器、爬行器、存储器、分析器和URL解析器组成,爬行器是该部分的核心；标引入库主要负责对网页内容进行分析，对文档进行标引并存储到数据库里，该模块涉及许多文件和数据；用户查询主要负责分析用户输入的检索表达式，匹配相关文档，把检索结果返回给用户，由查询器和网页级别评定器组成，其中网页等级的计算是该部分的核心。41搜索引擎搜索引擎的主要工作流程是：首先从蜘蛛开始，蜘蛛程序每隔一定的时间（googlebot）自动启动并读取网页URL服务器上的URL列表，按深度优先或广度优先算法，抓取各URL所指定的网站，将抓取的网页分配一个唯一文档ID(DocId)，压缩存入文档数据库。并将当前页上的所的超链接存入到URL服务器中。在进行抓取的同时，切词器和索引器将已经抓取的网页文档进行切词处理，并按词在网页中出现的位置和频率计算权值，然后将切词结果存入索引数据库。整个抓取工作和索引工作完成后更新整个索引数据库和文档数据库，这样用户就可以查询最新的网页信息。查询器首先对用户输入的信息进行切词处理，并检索出所有包含检索词的记录，通过计算网页权重和级别对查询记录进行排序并进行集合运算，最后从文档数据库中提取各网页的摘要信息反馈给查询用户5什么是PageRank?

PageRank(网页级别)是Google用于评测一个网页“重要性”的一种方法。在揉合了诸如Title标识和Keywords标识等所有其它因素之后，Google通过PageRank来调整结果，使那些更具“重要性”的网页在搜索结果中令网站排名获得提升，从而提高搜索结果的相关性和质量。简单说来，Google通过下述几个步骤来实现网页在其搜索结果页(SERPS)中的排名：

1)找到所有与搜索关键词匹配的网页

2)根据页面因素如标题\关键词密度等排列等级

3)计算导入链接的锚文本中的关键词

4)通过PageRank得分调整网站排名结果6PageRankfromgoogle

PageRank，有效地利用了Web所拥有的庞大链接构造的特性。从网页A导向网页B的链接被看作是对页面A对页面B的支持投票，Google根据这个投票数来判断页面的重要性。可是Google不单单只看投票数(即链接数)，对投票的页面也进行分析。「重要性」高的页面所投的票的评价会更高，因为接受这个投票页面会被理解为「重要的物品」。

根据这样的分析,得到了高评价的重要页面会被给予较高的PageRank(网页等级)，在检索结果内的名次也会提高。PageRank是Google中表示网页重要性的综合性指标，而且不会受到各种检索(引擎)的影响。倒不如说，PageRank就是基于对“使用复杂的算法而得到的链接构造”的分析，从而得出的各网页本身的特性。

当然，重要性高的页面如果和检索词句没有关联同样也没有任何意义。为此Google使用了精练后的文本匹配技术，使得能够检索出重要而且正确的页面。「从许多优质的网页链接过来的网页，必定还是优质网页」7PageRank概念图(引自Pageetal.(1998)Figure2'SimplifiedPageCalculation')8PageRank的计算方法PageRank(A)=(1-d)+d(PageRank(T1)/C(T1)+...+PageRank(Tn)/C(Tn))其中PageRank(A)表示给定页面A的PageRank得分；

D为阻尼因子，一般设为0.85；

PageRank(T1)表示一个指向A页的网站其本身的PageRank得分；

C(T1)表示该页面所拥有的导出链接数量；

PageRank(Tn)/C(Tn)表示为每一个指向A页的页面重复相同的操作步骤。9A页的外部链接B能够带给A的PageRank得分与B的导出链接数量成反比，即随着B上导出链接数的增加，带给A的PageRank得分亦随之降低。这同样表明了一个网页的PageRank得分是该网页对其它页面投票的一个基本的度量形式。一个网页可以投票给一个或多个导出链接，但其总投票权一定，并被平均分配给所有的导出链接。假设B的PageRank得分是5，且B上只有一条指向A的链接，那么A将获得B全部的PageRank得分(B没有损失任何东西，而A赢得了B的PageRank得分)。但如果B上有N个链接，则A只能得到B的PageRank得分的N分之一。10导入链接导入链接时，一般总是容易陷入这样的误区：只看链接页的PageRank得分，得分越高就越好。而事实上，一个链接页的PageRank得分遵循平均分配原则被平均分配给该页面上的所有链接。所以，只注重外部链接的PageRank得分的链接策略无疑是片面的。正确的做法应该是既要考虑链接页的PageRank，又要考虑该页的链接数量11导出链接

导出链接并不会损失PageRank，但网站整体的PageRank将会降低。所以，选择导出链接时宜遵循这样的定律：

1.尽量保持自己网站的PageRank2.尽量使内部页面分得尽可能多的PageRank12SuggestionfromGoogle

选择导入链接时应首先考虑对方网站的内容如何，然后再考察其导出链接的数量进行决策。而在建立本站的导出链接时则应尽量使自己网站的PageRank维持在最大回馈和最小流失上。应确保合理的网站设计结构和内部联接方式。网站的结构和内部联接方式也会对PageRank产生影响，可利用其特性有效进行PagaRank在网站内部页面的再分布及尽可能保持网站整体的PageRank。网站的PageRank的提升应与该网站的访问者体验息息相关。即使获得再高的PageRank，如果没有客户访问，一样毫无价值。所以网站的内容始终是提升PageRank最关键的因素之一。132数据挖掘概念定义数据挖掘--从大量数据中寻找其规律的技术，是统计学、数据库技术和人工智能技术的综合。数据挖掘与统计学数据挖掘与人工智能数据挖掘与数据库技术数据挖掘与KDD142数据挖掘概念原由数据挖掘数据库越来越大有价值的知识可怕的数据152数据挖掘概念原由数据爆炸，知识贫乏

苦恼:淹没在数据中;不能制定合适的决策!数据知识决策模式趋势事实关系模型关联规则序列目标市场资金分配贸易选择在哪儿做广告销售的地理位置金融经济政府POS.人口统计生命周期162数据挖掘概念发展1989IJCAI会议：数据库中的知识发现讨论专题KnowledgeDiscoveryinDatabases(G.Piatetsky-ShapiroandW.Frawley,1991)1991-1994KDD讨论专题AdvancesinKnowledgeDiscoveryandDataMining(U.Fayyad,G.Piatetsky-Shapiro,P.Smyth,andR.Uthurusamy,1996)1995-1998KDD国际会议(KDD’95-98)JournalofDataMiningandKnowledgeDiscovery(1997)1998ACMSIGKDD,SIGKDD’1999-2002会议,以及SIGKDDExplorations数据挖掘方面更多的国际会议PAKDD,PKDD,SIAM-DataMining,(IEEE)ICDM,DaWaK,SPIE-DM,etc.17

关联规则发现的主要对象是交易型数据库，一个交易一般由交易处理时间，一组顾客购买的物品，有时也有顾客标识号(如信用卡号)组成。定义3.2：关联规则是描述在一个交易中物品之间同时出现的规律的知识模式，更确切的说，关联规则是通过量化的数字描述物品X的出现对物品Y的出现有多大的影响。

关联规则18

以零售业为例，体育用品商场通过对销售数据进行关联分析通常可以发现这些数据中常常隐含形式如下的规律——“购买篮球的顾客中有70%的人同时购买篮球运动服，所有交易中有40%的人同时购买篮球和篮球运动服”等等。这些规律即关联规则。

关联规则19定义3.3：关联规则挖掘的交易数据集记为D（一般为交易数据库），D＝｛T1，T2，…，Tk，…,Tn｝，Tk（k＝1,2,…，n）称为交易，对应每一个交易有唯一的标识，记作TID。元素im（m＝1,2,…，p）称为项。设I={i1，i2，…，im}是D中全体项组成的集合，且TkI。交易号（TID）

项集合（Itemsets）

T100I1，I2，I5T200I2，I4T300I2，I3T400I1，I2，I4T500I1，I3设X是一个I中项的集合，如果XTk，那么称交易Tk包含项集X。若X,Y为项集，XI,YI，并且XY=，则形如X==>Y的表达式称为关联规则。

关联规则形式化定义20置信度支持度

关联规则度量规则XY在交易数据集D中的置信度是对关联规则准确度的衡量。度量关联规则的强度。即在所有出现了X的活动中出现Y的频率，即规则XY的必然性有多大。记为confidence(XY)。计算方法：包含X和Y的交易数与包含X的交易数之比：confidence(XY)=P(Y∣X)=|{T:XYT，TD}|/|{T:XT，TD}|×100%规则XY在交易数据集D中的支持度是对关联规则重要性的衡量，反映关联是否是普遍存在的规律，说明这条规则在所有交易中有多大的代表性。即在所有交易中X与Y同时出现的频率记为：support(XY)。计算方法：交易数据集中同时包含X和Y的交易数与所有交易数之比：support(XY)=P(X∪Y)=|{T:XYT，TD}|/|D|×100%（其中|D|是交易数据集D中的所有交易数）21最小置信度阈值最小支持度阈值同时满足最小置信度阈值和最小支持度阈值的关联规则为强关联规则，是有意义有价值。

关联规则度量22

在给定一个交易数据集D，挖掘关联规则问题就是产生支持度和置信度分别大于用户给定的最小支持度阈值和最小置信度阈值的关联规则。

关联规则度量23经常使用的“支持度-可信度”的框架。这样的结构有时会产生一些错误的结果。例：假设体育类用品零售商调查了10000名顾客在购买什么商品，得到的结果是6000名顾客购买篮球，7500名顾客购买足球，4000名顾客购买篮球、足球。设最小支持度为30%，最小置信度为60%，可得到如下的关联规则：篮球足球（支持度＝40%，置信度为66%

）

这条规则其实是错误的，因为购买足球的比例是75%，甚至大于66%。

关联规则度量24名称描述公式置信度X出现的前提下，Y出现的频率P(Y|X)支持度X、Y同时出现的频率

P(X∩Y)期望可信度

Y出现的频率

P(Y)改善度

置信度对期望可信度的比值

P(Y|X)/P(Y)

关联规则度量25找出所有具有最小支持度的项集(频繁项集)。用Apriori、FP-Growth等算法来找出频繁项集。使用频繁项集生成期望的关联规则对于每一个频繁项集l，找出其中所有的非空子集；然后，对于每一个这样的子集a，如果support(l)与support(a)的比值大于最小可信度，则存在规则a==>(l-a)。挖掘交易数据库D中所有关联规则的问题可以被划分为两个子问题：26找出频繁项集－－Apriori算法

Apriori性质

Apriori算法基本思想27交易号项集合T100I1，I2，I5T200I2，I4T300I2，I3T400I1，I2，I4T500I1，I3T600I2，I3T700I1，I3T800I1，I2，I3，I5T900I1，I2，I3表1交易数据库D例：找出频繁项集－－Apriori算法28项集支持度计数｛I1｝6｛I2｝7｛I3｝6｛I4｝2｛I5｝2项集支持度计数｛I1｝6｛I2｝7｛I3｝6｛I4｝2｛I5｝2C1L1扫描D，对每个候选计数比较候选支持度计数与最小支持度计数找出频繁1－项集的集合L1找出频繁项集－－Apriori算法例：最小支持度阈值为229项集支持度计数｛I1｝6｛I2｝7｛I3｝6｛I4｝2｛I5｝2项集｛I1，I2｝｛I1，I3｝｛I1，I4｝｛I1，I5｝｛I2，I3｝｛I2，I4｝｛I2，I5｝｛I3，I4｝｛I3，I5｝｛I4，I5｝L1C2由L1产生候选C2Lk-1用于产生候选Ck

找出频繁项集－－Apriori算法连接&剪枝30项集支持度计数｛I1，2｝4｛I1，3｝4｛I1，4｝1｛I1，5｝2｛I2，3｝4｛I2，4｝2｛I2，5｝2｛I3，4｝0｛I3，5｝1｛I4，5｝0项集支持度计数｛I1，2｝4｛I1，3｝4｛I1，5｝2｛I2，3｝4｛I2，4｝2｛I2，5｝2C2L2比较候选支持度计数与最小支持度计数扫描D，对每个候选计数31项集支持度计数｛I1，I2｝4｛I1，I3｝4｛I1，I5｝2｛I2，I3｝4｛I2，I4｝2｛I2，I5｝2L2项集｛I1，I2，I3｝｛I1，I2，I5｝由L2产生候选C3C3连接&剪枝32连接：C3＝L2∞L2＝{{I1,I2},{I1,I3},{I1,I5},{I2,I3},{I2,I4},{I2,I5}}∞{{I1,I2},{I1,I3},{I1,I5},{I2,I3},{I2,I4},{I2,I5}}={{I1,I2,I3},{I1,I2,I5},{I1,I3,I5},{I2,I3,I4},{I2,I3,I4},{I2,I3,I5},{I2,I4,I5}}33剪枝：{I1,I2,I3}的2-项子集是{I1,I2},{I1,I3}和{I2,I3}。{I1,I2,I3}的所有2-项子集都是L2的元素。因此，保留{I1,I2,I3}在C3中。{I2,I3,I5}的2-项子集是{I2,I3},{I2,I5}和{I3,I5}。{I3,I5}不是L2的元素，因而不是频繁的。因此，由C3中删除{I2,I3,I5}。剪枝后C3＝{{I1,I2,I3},{I1,I2,I5}}。

34项集支持度计数｛I1，I2，I3｝2｛I1，I2，I5｝2C3扫描D，对每个候选计数比较候选支持度计数与最小支持度计数项集支持度计数｛I1，I2，I3｝2｛I1，I2，I5｝2L3对每个交易，使用subset函数找出交易中是候选的所有子集，并对每个这样的候选累加计数，所有满足最小支持度的候选形成频繁项集L。35

输入：交易数据库D；最小支持度阈值min_sup。输出：D中的频繁项集L。方法：(1)找频繁项集1-项集;(2)apriori_gen(Lk-1,min_sup)函数做两个动作：连接和剪枝。用于在第k-1次遍历中生成的Lk-1生成Ck(3)由Ck生成Lk

Apriori算法详述36

子集函数Subset

？子集函数Subset用于确定在一个给定的交易t中包含了哪些Ck中的项。候选集Ck被存放在一棵hash树中，hash树中的结点分为两类：一类包含一个项集列表(叶结点)，另一类包含一张hash表(内部结点)。在内部结点上，hash表中的每一个桶都指向另一个结点。假定hash树的根结点的深度等于1，则一个深度为d的内部结点指向深度为d＋1的结点。项集都存放在叶子结点，当需要添加一个项集c的时候，就从根结点出发直到叶子结点。在一个深度为d的内部结点，对该项集的第d项应用hash函数来确定下一步遍历的分支。所有的结点最初都被创建为叶子结点。当一个叶子结点的项集数目超出某一个阈值时，该结点将会转化为一个内部结点。从根结点开始，子集函数按照如下的方式找出包含在交易t中的所有的候选集。如果在叶子结点，找出该叶子结点中所有包含在交易t中的项集，并且为它们添加一个指向结果集的索引；如果通过散列第i项到达某个内部结点，则散列交易t中第i项后的每一项，并且将这个过程递归地应用于相应的桶。对于根结点，则散列交易t中的每一项。子集函数能够返回所需要的候选集的索引，对于任何交易t中包含的项集c，c的第一个项一定出现在t中。在根结点，通过散列交易t中的每一项，我们能够确定只忽略那些不是从t中的某一项开始的项集。同样的结论也适用于hash树中位于其他层次的结点。由于在每一个项集中的项都经过排序，如果我们通过散列项i到达当前的结点，则以后只需要考虑交易t中出现在项i后的项。

Apriori算法详述（续）37步骤：a.

对于每个频繁项集l，找出l的所有非空子集；b.对于l的每个非空子集a，如果

support_count(l)/support_count(a)≥min_conf，则输出规则“a＝>（l－a）”。频繁项集产生强关联规则38例：假定数据包含频繁集l＝{I1,I2,I5}，L的非空子集有{I1,I2},{I1,I5},{I2,I5},{I1},{I2},和{I5}。可以由l产生的关联规则：

I1I2I5，confidence＝2/4＝50%；

I1I5I2，confidence＝2/2＝100%；

I2I5I1，confidence＝2/2＝100%；

I1I2I5，confidence＝2/6＝33%；

I2I1I5，confidence＝2/7＝29%；

I5I1I2,confidence＝2/2＝100%；若最小置信度阈值为70%，则只有I1I5I2，I2I5I1，I5I1I2可输出，是强关联规则39不需要生成大量候选项集的频繁项集挖掘。算法采用分而治之的策略。频繁模式增长（FP-Growth）算法403归结原理1、一阶谓词基础2、置换与合一3、子句集4、归结原理5、归结反演41一阶谓词基础1、谓词：表示个体对象之间的关系、属性或状态。其表示形式如下：P(x1,x2,x3,...xn)其中：P是谓词符号，表示x1,x2,x3,...xn个体对象之间的属性、状态或关系。x1,x2,x3,...xn是谓词的参量（或称项），一般表示个体，它可以是个体常量、个体变量或是个体函数。个体变元的变化范围称为个体域（或论域）例：P(x):表示x是素数

FRIEND(a,b)：表示a和b是朋友42一阶谓词基础2、个体函数：表示项之间的关系有了个体函数之后，谓词的表达能力更强。假如个体函数father(b)表示“个体b的父亲”，则谓词FRIEND(a,father(b))表示“a和b的父亲是朋友”，显然表达能力更强了。约定：（1）谓词符号用大写字母表示，如P，Q，R，S等；（2）用小写字母x,y,z等作为个体变元符号；（3）用小写字母a,b,c等作为个体常元符号；（4）用小写字母f,g,h表示个体函数符号。43一阶谓词基础3、量词全称量词：“所有”,“一切”,“任一”,“全体”,“凡是”等词称为全称量词，记为存在量词：“存在”、“有些”、“至少有一个”、“有的”等词统称为存在量词，记为引入量词和连接符（→蕴涵，∧合取，∨析取，否定词┓）之后，谓词的表达能力大大扩充了。44一阶谓词基础4、谓词公式：用谓词、量词（存在量词，全称量词）、联接词（→蕴涵，∧合取，∨析取）连接而成的复杂的符号表达式称为谓词公式。例子：知识“不存在最大的整数”的表示设：谓词G(x):表示x是整数，D(x,y)表示x大于y。则表示如下：45命题逻辑的归结1、基本概念命题：不带参数(肯定也不含量词)的谓词。命题公式：由连接词(→蕴涵，∧合取，∨析取，等价<->，否定词┓)将命题连接在一起构成永真式：真值为T的命题公式称为永真式或重言式或有效的。永假式：真值为F的命题公式称为永假式或不可满足的。非永真式：不是永真式的命题公式；可满足式：不是永假公式的命题公式；46命题逻辑的归结原子公式：不含任何连接词的命题公式称为原子公式或称原子.例如P,Q文字：原子公式及其否定形式称为文字.

例如P,～L子句：文字的析取称为子句.例如:P∨R∨～Q互补文字：设L为一个文字，则称L与～L为互补文字。47命题逻辑的归结命题逻辑中的归结推理方法若命题逻辑描述的命题A1,A2,...An和B,要证明在A1∧A2∧...∧An成立的条件下有B成立，或说A1∧A2∧...∧An→B。很显然A1∧A2∧...∧An→B等价于证明A1∧A2∧...∧An∧～B是矛盾(永假)式。归结推理的方法就是从A1∧A2∧...∧An∧～B出发使用归结推理规则来寻找矛盾，从而证明A1∧A2∧...∧An→B的成立。48命题逻辑的归结1、归结式设有两个子句C1=L∨C1'C2=┐L∨C2'

从中消去互补对，所得新子句C12=C1‘∨C2’，则称这一过程为归结。称C12为子句C1和C2的归结式，称C1和C2为C12的亲本子句。49命题逻辑的归结50命题逻辑的归结命题逻辑的归结推理过程(1)利用逻辑蕴含式和逻辑等价式将命题公式化成合取范式(子句的析取)(2)子句集：将若干个子句的合取式中的合取词∧换成逗号，形成的集合称为子句集。(3)从子句集S出发，仅只对S的子句间使用归结推理规则（即求归结式），并将所得归结式仍放入S中，进而再对新子句集使用归结推理规则，重复这些步骤直到得到空子句□（说明有矛盾）。便说明S是不可满足的，从而与子句集S对应的定理是成立的。51命题逻辑的归结例：证明(P→Q)∧┐Q==>┐P证：先将已知以及结论的反化成合取范式(┐P∨Q)∧┐Q∧(┐┐P)==>(┐P∨Q)∧┐Q∧P，建立子句集S=｛┐P∨Q，┐Q，P｝对S作归结(1)┐P∨Q(2)┐Q(3)P(4)┐P对(1)(2)求归结式(5)□对(3)(4)求归结式得证。52谓词逻辑的归结1、谓词公式化为子句集(1)消去蕴涵符号：只应用∨和┐符号，以┐A∨B替换A→B。例如公式经等价变换后变成：53谓词逻辑的归结(2)利用下述等价关系把”┐”移到紧靠谓词的位置上：54谓词逻辑的归结(3)重新命名变元名，使不同量词约束的变元有不同的名字。55谓词逻辑的归结(4)消去存在量词。消去存在量词时，还要进行变元替换。变元替换分两种情况：

①若该存在量词在某些全称量词的辖域内，则用这些全称量词指导变元的一个函数代替该存在量词辖域中的相应约束变元，这样的函数称为Skolem函数；

②若该存在量词不在任何全称量词的辖域内，则用一个新的常量符号代替该存在量词辖域中相应约束变元，这样的常量符号称为Skolem常量；56谓词逻辑的归结为什么需要Skolem?57谓词逻辑的归结(5)化为前束形

到这一步，已不留下任何存在量词，而且每个全称量词都有自己的变量。把所有全称量词移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分。所得公式称为前束形。前束形公式由前缀和母式组成，前缀由全称量词串组成，母式由没有量词的公式组成，即

前束形=(前缀)(母式)

全称量词串无量词公式58谓词逻辑的归结(6)把母式化为合取范式

任何母式都可写成由一些谓词公式和(或)谓词公式的否定的析取的有限集组成的合取。这种母式叫做合取范式。我们可以反复应用分配律。把任一母式化成合取范式。利用A∨{B∧C}化为{A∨B}∧{A∨C}59谓词逻辑的归结(7)消去全称量词

到了这一步，我们可以消去前缀，即消去所有的全称量词。60谓词逻辑的归结(8)对变元更名，使不同子句中的变元不同名。61谓词逻辑的归结(9)消去合取词。消去合取词后，上式就边为下述子句集：62谓词逻辑的归结

命题逻辑中的归结原理很简单，因为在命题逻辑中不含量词，而谓词逻辑中含有量词和个体变元，这样寻找互补文字对就变得较复杂。例：子句C1=P(x)∨Q(x)，子句C2=～P(a)∨R(y),如直接比较，似乎找不到互补文字，但如果使用替换办法，将C1中的x替换成a,则C1和C2的归结式为R(C1,C2)=Q(a)∨R(y)即可消去互补文字。63谓词逻辑的归结2、代换(Substitution)：代换是形如｛t1/x1,t2/x2,...tn/xn｝的有限集合。ti是项，称为替换的分子，xi是互不相同的个体变元，称为替换分母(i=1,2,...n)，且ti与xi不相同，xi与ti互不循环出现。ti/xi表示xi用ti替换。若ti都是不含变元的项(基项)，该替换称为基替换；没有元素的替换称为空替换，记作ε，表示不做替换。64谓词逻辑的归结例：｛a/x,g(y)/y,f(g(b))/z｝就是一个替换（但不是基替换），而｛y/x,f(x)/y｝就不是一个替换，因为出现了x,y的循环替换。定义：若E是一个谓词公式，θ=｛t1/x1,t2/x2,...tn/xn｝是一个替换，对E施行θ替换之后所得的结果记为Eθ，称为E在θ下的例（instance）例：设谓词公式G=P(x,y,z),替换θ=｛a/x,f(b)/y,c/z｝，则Gθ=P(a,f(b),c)65谓词逻辑的归结3、复合代换：设θ=｛t1/x1,...,tn/xn｝，

λ=｛u1/y1,...,um/ym｝是两个替换，则将集合｛t1λ/x1,...,tnλ/xn，u1/y1,...,um/ym｝中凡符合下列条件的元素删除

(1)tiλ/xi当tiλ=xi时

(2)ui/yi当yi∈｛x1,x2,...xn｝如此得到的集合仍然是一个替换，该替换称为θ与λ的复合或乘积，记为θ·λ66谓词逻辑的归结例子：θ=｛f(y)/x,z/y｝,λ=｛a/x,b/y,y/z｝,于是｛f(y)λ/x,zλ/y,a/x,b/y,y/z｝

=｛f(b)/x,y/y,a/x,b/y,y/z｝，根据复合代换的定义，删除若干项之后得

θ·λ=｛f(b)/x,y/z｝代换的复合运算满足结合律，但不满足交换律，即有：(θ·λ)·u=θ·(λ·u)，θ·λ≠λ·θ，λ·ε=λ67谓词逻辑的归结例子：θ=｛f(y)/x,z/y｝,λ=｛a/x,b/y,y/z｝,于是

θ·λ=｛f(b)/x,y/z｝

λ·θ=｛aθ/x,bθ/y,yθ/z,f(y)/x,z/y｝

=｛a/x,b/y,z/z,f(y)/x,z/y｝

={a/x,b/y}所以：θ·λ≠λ·θ68谓词逻辑的归结4、合一代换定义1：设S=｛F1,F2,...,Fn｝是一个子句集（F1,F2,...Fn是文字的析取），若存在一个代换θ，可使F1θ=F2θ=...Fnθ，则称θ为S的一个合一（Unifier）,并称S为可合一的。一个谓词公式的合一不唯一。定义2：设δ是谓词公式子句集S的一个合一，如果对S的任何一个合一θ，都存在一个代换λ,使得

θ=δ·λ则称δ是子句集的最一般合一，简称MGU(MostGeneralUnifier)。69谓词逻辑的归结例子：设子句集S=｛P(u,y,g(y)),P(x,f(u),z)｝,S有一个最一般合一MGU，δ=｛u/x,f(u)/y,g(f(u))/z｝,对S的任一合一，例如θ=｛a/x,f(a)/y,g(f(a))/z,a/u｝,存在一个替换λ=｛a/u｝，使得θ=δ.λ70谓词逻辑的归结求MGU的目的是使子句集中的子句中的文字形式结构完全一致，从而得到消取互补文字的目的。差异集：设S是一个非空的具有相同谓词名的原子公式集，从S中各公式的左边第一项开始，同时向右比较，直到发现第一个不都相同的项为止，用这些项的差异部分组成一个集合，这个集合就是原子公式子句集的一个差异集。例：S=｛P(x,y,z),P(x,f(a),h(b))｝,则S的差异集

D1=｛y,f(a)｝,D2=｛z,h(b)｝71谓词逻辑的归结求子句集S的最一般合一（MGU）的算法，即合一算法（UnificationAlgorithm）72谓词逻辑的归结例：求公式集S=｛P(a,x,f(g(y)),P(z,h(z,u),f(u))｝的MGU。解：k=0;S0=S;δ0=ε;①S0不是单元素集，求得差异集D0=｛a/z｝,其中z是变元，a是项，且z不在a中出现。k=k+1=1有δ1=δ0·｛a/z｝=ε·｛a/z｝=｛a/z｝，②S1=S0·｛a/z｝=｛P(a,x,f(g(y)),P(a,h(a,u),f(u))｝,S1不是单元素集，求得差异集D1=｛x,h(a,u)｝,k=k+1=2;δ2=δ1·｛h(a,u)/x｝=｛a/z,h(a,u)/x｝,③S2=S1·｛h(a,u)/x｝=｛P(a,h(a,u),f(g(y)),P(a,h(a,u),f(u))｝，S2不是单元素集，求得差异集D2=｛g(y),u｝,k=k+1=3δ3=δ2·｛g(y)/u｝=｛a/z,h(a,u)/x｝·｛g(y)/u｝=｛a/z,h(a,g(y))/x,g(y)/u｝④S3=S2·｛g(y)/u｝=｛P(a,h(a,g(y)),f(g(y)))｝是单元素集。根据求MGU算法，MGU=δ3=｛a/z,h(a,g(y))/x,g(y)/u｝73谓词逻辑的归结判断S=｛P(x,x),P(y,f(y))｝是否可合一？（思考题）

74谓词逻辑的归结5、谓词逻辑中的归结式谓词逻辑下求两个子句的归结式，和命题逻辑一样也是消去互补对，但需考虑变量的合一与置换。设S=｛C1,C2｝C1,C2是子句集中的子句，L1、L2分别是C1，C2中的文字，并且L1和～L2有最一般合一δ，则子句｛C1δ-L1δ｝∪｛C2δ-L2δ｝称为C1、C2的归结式。C1，C2称为归结式的亲本子句，L1、L2称为归结文字。75谓词逻辑的归结例：S=｛C1,C2｝=S=｛P(x)∨Q(x),┐P(a)∨R(y)｝，求C1，C2的归结式。L1=P(x)，L2=┐P(a)，则L1与L2的MGUδ=｛a/x｝,则｛C1δ-L1δ｝∪｛C2δ-L2δ｝=｛P(a)∨Q(a)｝-｛P(a)｝∪｛┐P(a)∨R(y)｝-｛┐P(a)｝=｛Q(a)∨R(y)｝即R(C1,C2)=Q(a)∨R(y)δ=｛a/x｝例：C1=｛P(x,y)∨┐Q(a)｝,C2=｛Q(x)∨R(y)｝求C1、C2的归结式。

R(C1,C2)={P(a,y)∨R(y)}δ=｛a/x｝76谓词逻辑的归结在对子句进行归结之前，可先在子句内部进行化简。如子句C=P(x)∨Q(f(y)),令置换δ=｛f(y)/x｝，则Cδ=P(f(y))∨Q(f(y)),Cδ称为C的因子。R(C1,C2)=R(C1δ,C2)=R(C1,C2δ)=R(C1δ,C2δ)77归结反演

应用归结原理证明结论为真的过程称为归结反演。定理1Q为P1,P2,…Pn的逻辑结论，当且仅当(P1∧P2∧…∧Pn)∧┐Q是不可满足的。定理2设有谓词公式F，其标准形的子句集为S，则F不可满足的充要条件是S不可满足。78归结反演

设F为已知前提的公式集，Q为目标公式(逻辑结论)，用归结反演证明Q为真的步骤是：1)否定Q，得到┐Q 2)把┐Q并入到公式集F中，得到{F,┐Q}3)把公式集{F,┐Q}化为子句集S4)应用归结原理对子句集S中的子句进行归结，并把每次归结得到的归结式都并入S中。如此反复进行，若出现了空子句，则停止归结，从而证明了Q为真。79归结反演80归结反演81基于归结反演的问题求解

归结反演除了可用于定理证明外，还可用来求取问题的答案，问题求解的方法与定理证明类似。问题求解的步骤如下：1)把已知前提用谓词公式表示出来，并且化为相应的子句集S。2)把待求解的问题也用谓词公式表示出来，然后把它的否定式与谓词ANSWER构成一个析取式，ANSWER是一个为了求解问题而专设的谓词，其变元必须与问题公式的变元完全一致。3)把此析取式化为子句集，并且把该子句集并入到子句集S中，得到子句集S’。4)对S’应用归结原理进行归结。5)若得到归结式ANSWER，则答案就在ANSWER中。82基于归结反演的问题求解例子:已知:;F1:王(Wang)先生是小李(Li)的老师;F2:小李和小张(Zhang)是同班同学;F3:如果x和y是同班同学,则x的老师也是y的老师问小张的老师是谁?解:定义谓词T(x,y):x是y的老师;C(x,y):x与y是同班同学;则已知和待求解的问题可表示成如下的谓词公式：F1:T(Wang,Li)F2:C(Li,Zhang)F3:G:83基于归结反演的问题求解把上述公式化为子句集并进行归结：(1)(2)(3)(4)(5)(1)与(3)归结(6)(4)与(5)归结(7)(2)与(6)归结84基于归结反演的问题求解85归结反演的策略1、删除策略2、支持集策略3、线性输入策略4、单文字子句策略5、祖先过滤形策略86归结反演的策略1、删除策略在归结的过程中删除以下子句①含有纯文字的子句;

②含有永真式的子句;

③子句集中被别的子句类含的子句;2、支持集策略支持集策略对参加归结的子句提出了如下限制：每一次归结时，亲本子句中至少应有一个是由目标公式的否定所得到的子句，或者是它们的后裔。87归结反演的策略3、线性输入策略线性输入策略对参加归结的子句提出了如下限制：参加归结的两个子句中必须至少有一个是初始子句集中的子句。初始子句集是有已知前提与结论的否定组成的子句集。4、单文字子句策略单文字子句策略要求参加归结的两个子句中必须有一个是单文字子句。88归结反演的策略5、祖先过滤形策略祖先过滤形策略与线性策略相似，但放宽了限制。当对两个子句C1和C2进行归结时，要求他们满足下述两个条件中的任意一个条件：

1)C1与C2中至少有一个是初始子句集中的子句。

2)如果两个子句都不是初始子句集中的子句，则一个应是另一个的祖先。89归结反演的策略

以上讨论的几种基本的归结策略，在具体应用时可把几种策略组合在一起使用。归结演绎推理是在自动定理证明领域影响较大的一种推理方法，它比较简单且又便于在计算机上实现。但由于它要求把逻辑公式转化成子句集，就可能丢失蕴含式含有的逻辑控制信息。例如下列逻辑公式：

(┐A∧┐B)→C(┐A∧┐C)→B(┐B∧┐C)→A┐A→(B∨C)┐B→(A∨C)┐C→(A∨B)A∨B∨C904规则演绎系统

对于许多公式来说，子句形是一种低效率的表达式，因为一些重要信息可能在求取子句形过程中丢失。可以采用易于叙述的ifthen规则来求解问题，这种基于规则的系统叫做规则演绎系统。91规则正向演绎系统基于规则的演绎系统和产生式系统，均有两种推理方式：正向推理(forwardchanining)和逆向推理(backwardchaining)。

正向推理：从if部分向then部分推理的过程，它是从事实或状况向目标或动作进行操作的。

逆向推理：从then部分向if部分推理的过程，它是从目标或动作向事实或状况进行操作的。

92规则正向演绎系统

1.事实表达式的与或形变换

在基于规则的正向演绎系统中，我们把事实表示为非蕴涵形式的与或形，要把一个公式化为与或形，可采用下列步骤(1)利用(W1→W2)和(┐W1∨W2)的等价关系，消去符号→(2)用狄·摩根(DeMorgan)定律把否定符号移进括号内，直到每个否定符号的辖域最多只含有一个谓词为止。(3)对所得到的表达式进行Skolem化和前束化。(4)对全称量词辖域内的变量进行改名和变量标准化，而存在量词量化变量用Skolem函数代替。(5)删去全称量词，且使各主要合取式中的变元不同名。

例如，我们有事实表达式

按上述步骤进行转化后得到与/或形表达式：93规则正向演绎系统94规则正向演绎系统2、F规则的表示形式在与/或形正向演绎推理中，要求F规则具有如下形式：L→W

其中，L为单文字，W为与/或形。如果领域知识的表示形式不是所要求的形式，则需通过变换将它变成规定的形式。3、目标公式的表示形式在与/或形正向演绎推理中，要求目标公式用子句表示，否则就需要化成子句形式。95规则正向演绎系统4、推理过程

应用F规则进行推理的目的在于证明某个目标公式。其推理过程为：

1)首先用与/或树把已知事实表示出来。

2)用F规则的左部和与/或树的叶节点进行匹配，将匹配成功的F规则加入与/或树中。

3)重复进行步骤2)，直到产生一个含有以目标节点作为终止节点的解图为止。96规则正向演绎系统97规则正向演绎系统98规则正向演绎系统99规则正向演绎系统100规则逆向演绎系统与/或形逆向演绎推理是从待证明的问题出发，逆向使用蕴式(B规则)进行演绎推理，直至得到包含已知事实的终止条件为止。1、目标公式的与/或形及其与/或树表示在与/或形逆向演绎推理中，要求目标公式用与/或形表示，其变换过程与正向演绎推理中对已知事实的变换相似，只是要用存在量词约束的变元的Skolem函数替换由全称量词约束的相应变元，并且消去全称量词，然后再消去存在量词，且使各主要析取式中的变元不同名。101规则逆向演绎系统102规则逆向演绎系统2、B规则的表示形式

B规则的表示形式为：W→L其中，W为任一与/或形公式，L为文字。如果已知的B规则不是所要求的形式，可以把它化成规定的形式。比如：W→(L1∧L2)W→L1,W→L23、已知事实的表示形式在逆向演绎推理中，要求已知事实是文字的合取形式，即形如F1∧F2∧…∧Fn103规则逆向演绎系统4、推理过程应用B规则进行逆向演绎推理的目的是求解问题，从目标公式的与/或树出发，通过运用B规则来进行求解。其推理过程为：1)先用与/或树把目标公式表示出来。2)用B规则的右部和与/或树的叶节点进行匹配，将匹配成功的B规则加入到与/或树中。3)重复进行步骤2)，直到产生某个终止在事实节点上的一致解图为止。104规则逆向演绎系统105规则逆向演绎系统106规则双向演绎系统

规则双向演绎系统的主要复杂之处在于其终止条件，终止涉及两个图结构之间的适当交接处。这些结构可由标有合一文字的节点上的匹配棱线来连接。用对应的mgu来标记匹配棱线。107代换的一致性

无论对于正向演绎、逆向演绎还是双向演绎，都要求推理过程中所用的代换集合具有一致性。108剪枝策略

剪枝策略的基本思想：每当选用一条规则时，就进行一次一致性检查，如果当前的部分解图是一致的，则继续向下扩展，否则就放弃该规则而选用其他侯选规则。109剪枝策略1105产生式系统美国数学家Post，1943年提出了一种计算形式体系里所使用的术语。主要是使用类似文法的规则，对符号串做替换运算。这就是最早的一个产生式系统。到了60年代，产生式系统成为认知心理学研究人类心理活动中信息加工过程的基础，由此心理学家认为，人脑对知识的存储就是产生式形式。因此，用它来建立人类认知模型。到目前为止，产生式系统已发展成为人工智能系统中最典型最普遍的一种结构。产生式表示方法是专家系统中知识表式的第一选择。111产生式系统组成产生式系统由3个部分组成，即总数据库(或全局数据库)、产生式规则和控制策略。各部分间的关系如图所示。

112产生式系统组成①产生式规则是一个以“如果满足这个条件，就应当采取某些操作”形式表示的语句。P→Q或ifPthenQ例如，

规则:

if某种动物是哺乳动物，并且吃肉

then

这种动物被称为食肉动物②总数据库有时也被称作上下文，全局数据库，GlobalData-base。总数据库是产生式规则的注意中心。产生式规则的左边表示在启用这一规则之前总数据库内必须准备好的条件。执行产生式规则的操作会引起总数据库的变化，这就使其他产生式规则的条件可能被满足。

113产生式系统组成

控制策略其作用是说明下一步应该选用什么规则，也就是如何应用规则。通常从选择规则到执行操作分3步：匹配、冲突解决和操作。

(1)匹配在这一步，把全局数据库与规则的条件部分相匹配。如果两者完全匹配，则把这条规则称为触发规则。当按规则的操作部分去执行时，称这条规则为启用规则。被触发的规则不一定总是启用规则，因为可能同时有几条规则的条件部分被满足，这就要在解决冲突步骤中来解决这个问题。在复杂的情况下，在数据库和规则的条件部分之间可能要进行近似匹配。匹配结果分为：完全匹配,近似匹配,不匹配

114产生式系统组成(2)冲突解决当有一条以上规则的条件部分和当前数据库相匹配时，就需要决定首先使用哪一条规则，这称为冲突解决。举例如下:设有以下两条规则,

规则R1IFfourthdawnshortyardageTHENpunt

规则R2IFfourthdawnshortyardagewithin30yards(fromthegoalline)THENfieldgoal全局数据库包括：”fourthdawn””shortyardage””within30yards”

115产生式系统组成有很多种冲突解决策略，其中一种策略是先使用规则R2，因为R2的条件部分包括了更多的限制，因此规定了一个更为特殊的情况。这是一种按专一性来编排顺序的策略，称为专一性排序。还有不少其他的冲突解决策略116产生式系统组成(a)专一性排序如果某一规则条件部分规定的情况，比另一规则条件部分规定的情况更有针对性，则这条规则有较高的优先级。(b)

规则排序

如果规则编排的顺序就表示了启用的优先级，则称之为规则排序。(c)数据排序

把规则条件部分的所有条件按优先级次序编排起来，运行时首先使用在条件部分包含较高优先级数据的规则。(d)规模排序

按规则的条件部分的规模排列优先级，优先使用被满足的条件较多的规则。(e)就近排序

把最近使用的规则放在最优先的位置。这和人类的行为有相似之处。如果某一规则经常被使用，则人们倾向于更多地使用这条规则。(f)上下文限制

把产生式规则按它们所描述的上下文分组，也就是说按上下文对规则分组。在某种上下文条件下，只能从与其相对应的那组规则中选择可应用的规则。117产生式系统组成控制策略(1)匹配(2)冲突解决(3)操作操作就是执行规则的操作部分，经过操作以后，当前数据库将被修改。然后，其他的规则有可能被使用118产生式系统表示1、事实的表示：一般用三元组（对象，属性，值）或 （关系，对象1，对象2）例：（Lee,Age,35）,(Friend,Lee,Chang)119产生式系统表示2、规则表示例子：MYCIN系统中典型规则的定义：

<rule>=(IF<antecedent>THEN<action>(ELSE<action>))

<antecedent>=(AND<condition>)

<condition>=(OR｛<condition>｜(<predicate><associative_triple>)

<associative_triple>=(<attribute><object><value>)

<action>=｛<consequent>｝｜｛<procedure>｝

<consequent>=(<associative_triple><certainty_facto