1、1Review Search Technology 1、State Space Expression 2、And-Or Tree Expression 3、Blind Search 4、Heuristic Search 5、A* Algorithm 6、Game Tree Search2Summary1、Blind Search2、Heuristic Search 总之搜索策略是人工智能研究的核心问题之一，已有许多成熟的结果，并在解决人工智能的有关问题中得到广泛应用。但目前仍有若干深入的问题有待发展，特别是结合实际问题，探索有效实用的策略仍是一个研究和开发的工作，还应当给予足够的重视。31 搜
2、索引擎 搜索引擎系统一般由蜘蛛（也叫网页爬行器）、切词器、索引器、查询器几部分组成。蜘蛛负责网页信息的抓取工作，一般情况下切词器和索引器一起使用，它们负责将抓取的网页内容进行切词处理并自动进行标引，建立索引数据库。查询器根据用户查询条件检索索引数据库并对检索结果进行排序和集合运算，如并集、交集运算，再提取网页简单摘要信息反馈给查询用户。41 搜索引擎 Google搜索引擎从功能上同样分为三大部分：网页爬行、标引入库和用户查询。网页爬行主要负责网页的抓取，由URL服务器、爬行器、存储器、分析器和URL解析器组成, 爬行器是该部分的核心；标引入库主要负责对网页内容进行分析，对文档进行标引并存储到数
3、据库里，该模块涉及许多文件和数据；用户查询主要负责分析用户输入的检索表达式，匹配相关文档，把检索结果返回给用户，由查询器和网页级别评定器组成，其中网页等级的计算是该部分的核心。51 搜索引擎 搜索引擎的主要工作流程是：首先从蜘蛛开始，蜘蛛程序每隔一定的时间（googlebot）自动启动并读取网页URL服务器上的URL列表，按深度优先或广度优先算法，抓取各URL所指定的网站，将抓取的网页分配一个唯一文档ID(DocId)，压缩存入文档数据库。并将当前页上的所的超链接存入到URL服务器中。在进行抓取的同时，切词器和索引器将已经抓取的网页文档进行切词处理，并按词在网页中出现的位置和频率计算权值，然后
4、将切词结果存入索引数据库。整个抓取工作和索引工作完成后更新整个索引数据库和文档数据库，这样用户就可以查询最新的网页信息。查询器首先对用户输入的信息进行切词处理，并检索出所有包含检索词的记录，通过计算网页权重和级别对查询记录进行排序并进行集合运算，最后从文档数据库中提取各网页的摘要信息反馈给查询用户6什么是PageRank? PageRank(网页级别)是Google用于评测一个网页“重要性”的一种方法。在揉合了诸如Title标识和Keywords标识等所有其它因素之后，Google通过PageRank来调整结果，使那些更具“重要性”的网页在搜索结果中令网站排名获得提升，从而提高搜索结果的相关性
5、和质量。 简单说来，Google通过下述几个步骤来实现网页在其搜索结果页(SERPS)中的排名： 1) 找到所有与搜索关键词匹配的网页 2) 根据页面因素如标题关键词密度等排列等级 3) 计算导入链接的锚文本中的关键词 4) 通过PageRank得分调整网站排名结果7PageRank from google PageRank，有效地利用了 Web 所拥有的庞大链接构造的特性。 从网页A导向网页B的链接被看作是对页面A对页面B的支持投票，Google根据这个投票数来判断页面的重要性。可是 Google 不单单只看投票数(即链接数)，对投票的页面也进行分析。重要性高的页面所投的票的评价会更高，因为
6、接受这个投票页面会被理解为重要的物品。 根据这样的分析,得到了高评价的重要页面会被给予较高的 Page Rank(网页等级)，在检索结果内的名次也会提高。PageRank 是 Google 中表示网页重要性的综合性指标，而且不会受到各种检索(引擎)的影响。倒不如说，PageRank 就是基于对“使用复杂的算法而得到的链接构造”的分析，从而得出的各网页本身的特性。 当然，重要性高的页面如果和检索词句没有关联同样也没有任何意义。为此 Google 使用了精练后的文本匹配技术，使得能够检索出重要而且正确的页面。 从许多优质的网页链接过来的网页，必定还是优质网页从许多优质的网页链接过来的网页，必定还是
7、优质网页 8PageRank 概念图 (引自 Page et al.(1998) Figure 2 Simplified Page Calculation) 9PageRank的计算方法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)表示为每一个指向
8、A页的页面重复相同的操作步骤。10 A页的外部链接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分之一。11导入链接 导入
9、链接时，一般总是容易陷入这样的误区：只看链接页的PageRank得分，得分越高就越好。而事实上，一个链接页的PageRank得分遵循平均分配原则被平均分配给该页面上的所有链接。所以，只注重外部链接的PageRank得分的链接策略无疑是片面的。正确的做法应该是既要考虑链接页的PageRank，又要考虑该页的链接数量12导出链接 导出链接并不会损失PageRank，但网站整体的PageRank将会降低。所以，选择导出链接时宜遵循这样的定律： 1. 尽量保持自己网站的PageRank 2. 尽量使内部页面分得尽可能多的PageRank13Suggestion from Google 选择导入链接时应
10、首先考虑对方网站的内容如何，然后再考察其导出链接的数量进行决策。而在建立本站的导出链接时则应尽量使自己网站的PageRank维持在最大回馈和最小流失上。应确保合理的网站设计结构和内部联接方式。网站的结构和内部联接方式也会对PageRank产生影响，可利用其特性有效进行PagaRank在网站内部页面的再分布及尽可能保持网站整体的PageRank。 网站的PageRank的提升应与该网站的访问者体验息息相关。即使获得再高的PageRank，如果没有客户访问，一样毫无价值。所以网站的内容始终是提升PageRank最关键的因素之一。14-数据挖掘与统计学数据挖掘与统计学数据挖掘与人工智能数据挖掘与人工
11、智能数据挖掘与数据库技术数据挖掘与数据库技术15数据挖掘数据挖掘数据库越来越大数据库越来越大有价值的知识有价值的知识可怕的数据可怕的数据16数据爆炸，知识贫乏数据爆炸，知识贫乏 苦恼: 淹没在数据中 ; 不能制定合适的决策! 数据数据n模式模式n趋势趋势n事实事实n关系关系n模型模型n关联规则关联规则n序列序列n目标市场目标市场n资金分配资金分配n贸易选择贸易选择n在哪儿做广告在哪儿做广告n销售的地理位置销售的地理位置n金融金融n经济经济n政府政府nPOS.n人口统计人口统计n生命周期生命周期171989 IJCAI会议：会议： 数据库中的知识发现讨论专题数据库中的知识发现讨论专题 Knowl
12、edge Discovery in Databases (G. Piatetsky-Shapiro and W. Frawley, 1991)1991-1994 KDD讨论专题讨论专题 Advances in Knowledge Discovery and Data Mining (U. Fayyad, G. Piatetsky-Shapiro, P. Smyth, and R. Uthurusamy, 1996)1995-1998 KDD国际会议国际会议 (KDD95-98) Journal of Data Mining and Knowledge Discovery (1997)1998
13、ACM SIGKDD, SIGKDD1999-2002 会议会议,以及以及SIGKDD Explorations数据挖掘方面更多的国际会议数据挖掘方面更多的国际会议 PAKDD, PKDD, SIAM-Data Mining, (IEEE) ICDM, DaWaK, SPIE-DM, etc.18 关联规则发现的主要对象是交易型数据库，一个交易一般由交易处理时间，一组顾客购买的物品，有时也有顾客标识号(如信用卡号)组成。 定义3.2：关联规则关联规则是描述在一个交易中物品之间同时出现的规律的知识模式，更确切的说，关联规则是通过量化的数字描述物品X的出现对物品Y的出现有多大的影响。 关关 联联
14、规规 则则19 以零售业为例，体育用品商场通过对销售数据进行关联分析通常可以发现这些数据中常常隐含形式如下的规律“购买篮球的顾客中有70%的人同时购买篮球运动服，所有交易中有40%的人同时购买篮球和篮球运动服” 等等。这些规律即关联规则关联规则。 关关 联联 规规 则则20 定义定义3.33.3：关联规则挖掘的交易数据集记为D（一般为交易数据库），DT1，T2，Tk，,Tn，Tk（k1,2,，n）称为交易，对应每一个交易有唯一的标识，记作TID。 元素im（m1,2,，p）称为项。设I=i1，i2，im是D中全体项组成的集合，且TkI。交易号交易号（TID） 项集合项集合（Itemsets）
15、T100 I1，I2，I5 T200 I2，I4 T300 I2，I3 T400 I1，I2，I4 T500 I1，I3 设X是一个I中项的集合，如果XTk，那么称交易Tk包含项集X。若若X,Y为项集，为项集，X I, Y I，并且，并且X Y= ，则形，则形如如X = Y的表达式称为的表达式称为。 关联规则形式化定义关联规则形式化定义21置信度置信度支持度支持度 关联规则度量关联规则度量规则XY在交易数据集D中的是对关联规则准确度的衡量。度量关联规则的强度。即在所有出现了X的活动中出现Y的频率，即规则XY的必然性有多大。记为。计算方法：包含X和Y的交易数与包含X的交易数之比：confiden
16、ce(XY) = P(YX) = |T: XYT，TD|/|T:XT，TD|100%规则XY在交易数据集D中的是对关联规则重要性的衡量，反映关联是否是普遍存在的规律，说明这条规则在所有交易中有多大的代表性。即在所有交易中X与Y同时出现的频率记为：。计算方法：交易数据集中同时包含X和Y的交易数与所有交易数之比：support(XY) = P(XY) = |T: XYT，TD|/|D|100%（其中|D|是交易数据集D中的所有交易数）22同时满足和的关联规则为，是有意义有价值。 关联规则度量关联规则度量23 在给定一个交易数据集在给定一个交易数据集D D，挖掘关，挖掘关联规则问题就是产生支持度和置
17、联规则问题就是产生支持度和置信度分别大于用户给定的信度分别大于用户给定的最小支最小支持度阈值持度阈值和和最小置信度阈值最小置信度阈值的关的关联规则。联规则。 关联规则度量关联规则度量24经常使用的“支持度-可信度”的框架。这样的结 构有时会产生一些错误的结果。例：假设体育类用品零售商调查了10000名顾客在 购买什么商品，得到的结果是6000名顾客购买篮球，7500名顾客购买足球，4000名顾客购买篮球、足球。设最小支持度为30%，最小置信度为60%，可得到如下的关联规则： 篮球足球 （支持度40%，置信度为66% ） 这条规则其实是错误的，因为购买足球的比例 是75%，甚至大于66%。 关联
18、规则度量关联规则度量25名称描述公式置信度X出现的前提下，Y出现的频率P(Y|X) 支持度X、Y同时出现的频率 P(XY) 期望可信度 Y出现的频率 P(Y) 改善度 置信度对期望可信度的比值 P(Y|X)/P(Y) 关联规则度量关联规则度量26找出所有具有最小支持度的项集找出所有具有最小支持度的项集(频繁项集频繁项集) 。用用AprioriApriori、FP-Growth等算法来等算法来找出频繁项集。找出频繁项集。使用频繁项集生成期望的关联规则使用频繁项集生成期望的关联规则对于每一个频繁项集对于每一个频繁项集l l，找出其中，找出其中所有的非空子集；然后，对于每一所有的非空子集；然后，对于
19、每一个这样的子集个这样的子集a a，如果，如果support(l)support(l)与与support(a)support(a)的比值大于最小可信的比值大于最小可信度，则存在规则度，则存在规则a=(l-a)a=(l-a)。挖掘交易数据库挖掘交易数据库D D中所有关联规则的问题可以中所有关联规则的问题可以被划分为两个子问题：被划分为两个子问题：27找出频繁项集找出频繁项集AprioriApriori算法算法 Apriori 性质性质 Apriori 算法基本思想算法基本思想28交易号交易号项集合项集合T100 I1，I2，I5 T200 I2，I4 T300 I2，I3 T400 I1，I2，
20、I4 T500 I1，I3 T600 I2，I3 T700 I1，I3 T800 I1，I2，I3，I5 T900 I1，I2，I3 表1 交易数据库D 例：例：找出频繁项集找出频繁项集AprioriApriori算法算法29项集支持度计数I16I27I36I42I52项集支持度计数I16I27I36I42I52C1L1扫描D，对每个候选计数比较候选支持度计数与最小支持度计数找出频繁1项集的集合L1找出频繁项集找出频繁项集AprioriApriori算法算法例：最小支持度阈值 为230项集支持度计数I16I27I36I42I52项集I1，I2I1，I3I1，I4I1，I5I2，I3I2，I4I
21、2，I5I3，I4I3，I5I4，I5L1C2由L1产生候选C2Lk-1用于产生候选Ck 找出频繁项集找出频繁项集AprioriApriori算法算法连接连接& &剪枝剪枝31项集支持度计数I1，24I1，34I1，41I1，52I2，34I2，42I2，52I3，40I3，51I4，50项集支持度计数I1，24I1，34I1，52I2，34I2，42I2，52C2L2比较候选支持度计数与最小支持度计数扫描D，对每个候选计数32项集支持度计数I1，I24I1，I34I1，I52I2，I34I2，I42I2，I52L2项集I1，I2，I3I1，I2，I5由L2产生候选C3C3连接连接& &剪枝剪
22、枝33连接：C3L2 L2I1,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,I534剪枝：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的元素，因而不是频繁的。
23、因此，由C3中删除I2,I3,I5。剪枝后C3 I1,I2,I3, I1,I2,I5。 35项集支持度计数I1，I2，I32I1，I2，I52C3扫描D，对每个候选计数比较候选支持度计数与最小支持度计数项集支持度计数I1，I2，I32I1，I2，I52L3对每个交易，使用对每个交易，使用subsetsubset函数找出交易函数找出交易中是候选的所有子集，并对每个这样的中是候选的所有子集，并对每个这样的候选累加计数，所有满足最小支持度的候选累加计数，所有满足最小支持度的候选形成频繁项集候选形成频繁项集L L。36 输入：交易数据库D；最小支持度阈值min_sup。 输出：D中的频繁项集L。 方法
24、： (1) 找频繁项集1-项集; (2) apriori_gen(Lk-1,min_sup)函数做两个动作：用于在第k-1次遍历中生成的Lk-1生成Ck (3) 由Ck生成Lk AprioriApriori算法详述算法详述37 子集函数子集函数SubsetSubset ？子集函数Subset用于确定在一个给定的交易t中包含了哪些Ck中的项。候选集Ck被存放在一棵hash树中，hash树中的结点分为两类：一类包含一个项集列表(叶结点)，另一类包含一张hash表(内部结点)。在内部结点上，hash表中的每一个桶都指向另一个结点。假定hash树的根结点的深度等于1，则一个深度为d的内部结点指向深度为
25、d1的结点。项集都存放在叶子结点，当需要添加一个项集c的时候，就从根结点出发直到叶子结点。在一个深度为d的内部结点，对该项集的第d项应用hash函数来确定下一步遍历的分支。所有的结点最初都被创建为叶子结点。当一个叶子结点的项集数目超出某一个阈值时，该结点将会转化为一个内部结点。从根结点开始，子集函数按照如下的方式找出包含在交易t中的所有的候选集。如果在叶子结点，找出该叶子结点中所有包含在交易t中的项集，并且为它们添加一个指向结果集的索引；如果通过散列第i项到达某个内部结点，则散列交易t中第i项后的每一项，并且将这个过程递归地应用于相应的桶。对于根结点，则散列交易t中的每一项。子集函数能够返回所
26、需要的候选集的索引，对于任何交易t中包含的项集c，c的第一个项一定出现在t中。在根结点，通过散列交易t中的每一项，我们能够确定只忽略那些不是从t中的某一项开始的项集。同样的结论也适用于hash树中位于其他层次的结点。由于在每一个项集中的项都经过排序，如果我们通过散列项i到达当前的结点，则以后只需要考虑交易t中出现在项i后的项。 AprioriApriori算法详述（续）算法详述（续）38 步骤： a. 对于每个频繁项集l，找出l的所有非空子集； b.对于l的每个非空子集a，如果 support_count(l)/support_count(a)min_conf，则输出规则“a（la）”。频繁项
27、集产生强关联规则频繁项集产生强关联规则39例：假定数据包含频繁集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，I5I
28、1I2可输出，是强关联规则40不需要生成大量候选项集的频繁项集挖掘。算法采用分而治之的策略。频繁模式增长（频繁模式增长（FP-GrowthFP-Growth）算法）算法413 归结原理 1、一阶谓词基础 2、置换与合一 3、子句集 4、归结原理 5、归结反演42一阶谓词基础1、谓词：表示个体对象之间的关系、属性或状态。 其表示形式如下： P(x1,x2,x3,.xn)其中：P是谓词符号，表示x1,x2,x3,.xn个体对象之间的属性、状态或关系。x1,x2,x3,.xn是谓词的参量（或称项），一般表示个体，它可以是个体常量、个体变量或是个体函数。个体变元的变化范围称为个体域（或论域论域）例：P
29、(x):表示x是素数 FRIEND(a,b)：表示a和b是朋友43一阶谓词基础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表示个体函数符号。44一阶谓词基础3、量词 全称量词：“所有”,“一切”,“任一”,“全体”,“凡是”等词称为全称量词，记为存在量词：“
30、存在”、“有些”、“至少有一个”、“有的”等词统称为存在量词，记为引入量词和连接符（蕴涵，合取，析取，否定词）之后，谓词的表达能力大大扩充了。xx45一阶谓词基础4、谓词公式：用谓词、量词（存在量词，全称量词）、联接词（蕴涵，合取，析取）连接而成的复杂的符号表达式称为谓词公式。 例子：知识“不存在最大的整数”的表示 设：谓词G(x):表示x是整数，D(x,y)表示x大于y。 则表示如下：),()()(yxDyGyxGx46命题逻辑的归结1、基本概念命题：不带参数(肯定也不含量词)的谓词。命题公式：由连接词(蕴涵，合取，析取，等 价，否定词)将命题连接在一起构成 永真式：真值为T的命题公式称为永
31、真式或重 言式或有效的。永假式：真值为F的命题公式称为永假式或不 可满足的。非永真式：不是永真式的命题公式；可满足式：不是永假公式的命题公式； 47命题逻辑的归结原子公式：不含任何连接词的命题公式称为 原子公式或称原子.例如P,Q文字：原子公式及其否定形式称为文字. 例如P,L子句：文字的析取称为子句.例如:PRQ互补文字：设L为一个文字，则称L与L为互 补文字。48命题逻辑的归结 命题逻辑中的归结推理方法 若命题逻辑描述的命题A1,A2,.An和B,要证明在A1A2.An成立的条件下有B成立，或说A1A2.AnB。很显然A1A2.AnB等价于证明A1A2.AnB是矛盾(永假)式。归结推理的方
32、法就是从A1A2.AnB出发使用归结推理规则来寻找矛盾，从而证明A1A2.AnB的成立。49命题逻辑的归结1、归结式设有两个子句C1 = LC1C2 = LC2 从中消去互补对，所得新子句C12 = C1C2，则称这一过程为归结。称C12为子句C1和C2的归结式，称C1和C2为C12的亲本子句。50命题逻辑的归结51命题逻辑的归结 命题逻辑的归结推理过程 (1)利用逻辑蕴含式和逻辑等价式将命题公式化成合取范式合取范式(子句的析取) (2)子句集：将若干个子句的合取式中的合取词换成逗号，形成的集合称为子句集。 (3)从子句集S出发，仅只对S的子句间使用归结推理规则（即求归结式），并将所得归结式仍
33、放入S中，进而再对新子句集使用归结推理规则，重复这些步骤直到得到空子句（说明有矛盾）。便说明S是不可满足的，从而与子句集S对应的定理是成立的。52命题逻辑的归结 例：证明(PQ) Q= P 证：先将已知以及结论的反化成合取范式 (PQ) Q(P)=(PQ) QP，建立子句集S= PQ， Q，P 对S作归结 (1) PQ (2) Q (3)P (4) P.对(1)(2)求归结式 (5).对(3)(4)求归结式 得证。53谓词逻辑的归结1、谓词公式化为子句集(1)消去蕴涵符号：只应用和符号，以 AB替换AB。例如公式经等价变换后变成：),(),()(),()(yxRyxQyyxPyx),(),()
34、(),()()(yxRyxQyyxPyx54谓词逻辑的归结(2)利用下述等价关系把” ”移到紧靠谓词的位置上：),(),()(),()()(yxRyxQyyxPyx55谓词逻辑的归结(3)重新命名变元名，使不同量词约束的变元有不同的名字。),(),()(),()(yxRyxQyyxPyx),(),()(),()(zxRzxQzyxPyx56谓词逻辑的归结(4)消去存在量词。 消去存在量词时，还要进行变元替换。变元替换分两种情况：若该存在量词在某些全称量词的辖域内，则用这些全称量词指导变元的一个函数代替该存在量词辖域中的相应约束变元，这样的函数称为Skolem函数；若该存在量词不在任何全称量词的
35、辖域内，则用一个新的常量符号代替该存在量词辖域中相应约束变元，这样的常量符号称为Skolem常量； 57谓词逻辑的归结为什么需要Skolem?),(),()(),()(zxRzxQzyxPyx),()(),()()(,()(),()(axlikexyxlikexyxgxlikexyxlikeyx)(,()(,()(,()(xgxRxgxQxfxPx58谓词逻辑的归结(5)化为前束形到这一步，已不留下任何存在量词，而且每个全称量词都有自己的变量。把所有全称量词移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分。所得公式称为前束形。 前束形公式由前缀和母式组成，前缀由全称量词串组成，
36、母式由没有量词的公式组成，即 前束形 = (前缀) (母 式) 全称量词串 无量词公式 )(,()(,()(,()(xgxRxgxQxfxPx59谓词逻辑的归结(6)把母式化为合取范式 任何母式都可写成由一些谓词公式和(或)谓词公式的否定的析取的有限集组成的合取。这种母式叫做合取范式。我们可以反复应用分配律。把任一母式化成合取范式。利用ABC化为ABAC )(,()(,()(,()(xgxRxgxQxfxPx)(,()(,()(,()(,()(xgxRxfxPxgxQxfxPx60谓词逻辑的归结(7)消去全称量词到了这一步，我们可以消去前缀，即消去所有的全称量词。 )(,()(,()(,()(
37、,(xgxRxfxPxgxQxfxP)(,()(,()(,()(,()(xgxRxfxPxgxQxfxPx61谓词逻辑的归结(8)对变元更名，使不同子句中的变元不同名。)(,()(,()(,()(,(xgxRxfxPxgxQxfxP)(,()(,()(,()(,(ygyRyfyPxgxQxfxP62谓词逻辑的归结(9)消去合取词。消去合取词后，上式就边为下述子句集：)(,()(,()(,()(,(ygyRyfyPxgxQxfxP)(,()(,(ygyRyfyP)(,()(,(xgxQxfxP63谓词逻辑的归结 命题逻辑中的归结原理很简单，因为在命题逻辑中不含量词，而谓词逻辑中含有量词和个体变元
38、，这样寻找互补文字对就变得较复杂。例： 子句C1=P(x)Q(x)，子句C2=P(a)R(y),如直接比较，似乎找不到互补文字，但如果使用替换办法，将C1中的x替换成a,则C1和C2的归结式为R(C1,C2)=Q(a)R(y)即可消去互补文字。64谓词逻辑的归结2、代换代换(Substitution)： 代换是形如t1/x1,t2/x2,.tn/xn的有限集合。ti是项，称为替换的分子，xi是互不相同的个体变元，称为替换分母(i=1,2,.n)，且ti与xi不相同，xi与ti互不循环出现。ti/xi表示xi用ti替换。若ti都是不含变元的项(基项)，该替换称为基替换；没有元素的替换称为空替换，
39、记作，表示不做替换。65谓词逻辑的归结例：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)66谓词逻辑的归结3、复合代换、复合代换：设=t1/x1,.,tn/xn， =u1/y1,.,um/ym是两个替换，则将集合t1/x1,.,tn/xn，u1/y1,.,um/y
40、m中凡符合下列条件的元素删除 (1)ti/xi.当ti=xi时 (2)ui/yi.当yix1,x2,.xn 如此得到的集合仍然是一个替换，该替换称为与的复合或乘积，记为67谓词逻辑的归结例子：=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)，=68谓词逻辑的归结例子：=f(y)/x,z/y,=a/x,b/y,y/z,于是 =f(b)/x,y/z =a/x,b/y,y/z, f
41、(y)/x,z/y =a/x,b/y,z/z, f(y)/x,z/y = a/x,b/y所以： 69谓词逻辑的归结4、合一代换 定义1：设S=F1,F2,.,Fn是一个子句集（F1,F2,.Fn是文字的析取），若存在一个代换，可使F1=F2=.Fn，则称为S的一个合一（Unifier）,并称S为可合一的。一个谓词公式的合一不唯一。 定义2：设是谓词公式子句集S的一个合一，如果对S的任何一个合一，都存在一个代换,使得 =则称是子句集的最一般合一，简称MGU(Most General Unifier)。70谓词逻辑的归结 例子：设子句集S=P(u,y,g(y),P(x,f(u),z),S有一个最一
42、般合一MGU， =u/x,f(u)/y,g(f(u)/z,对S的任一合一，例如=a/x,f(a)/y,g(f(a)/z,a/u,存在一个替换=a/u，使得=.71谓词逻辑的归结 求MGU的目的是使子句集中的子句中的文字形式结构完全一致，从而得到消取互补文字的目的。 差异集差异集：设S是一个非空的具有相同谓词名的原子公式集，从S中各公式的左边第一项开始，同时向右比较，直到发现第一个不都相同的项为止，用这些项的差异部分组成一个集合，这个集合就是原子公式子句集的一个差异集。 例：S=P(x,y,z),P(x,f(a),h(b),则S的差异集 D1=y,f(a),D2=z,h(b)72谓词逻辑的归结求
43、子句集求子句集S的最一般合一（的最一般合一（MGU）的算法，）的算法，即合一算法（即合一算法（Unification Algorithm）73谓词逻辑的归结例：求公式集例：求公式集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=0a/z=a/z=a/z，S1=S0a/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)
44、/x,S2=S1h(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=33=2g(y)/u=a/z,h(a,u)/xg(y)/u=a/z,h(a,g(y)/x,g(y)/uS3=S2g(y)/u=P(a,h(a,g(y),f(g(y)是单元素集。根据求MGU算法，MGU=3=a/z,h(a,g(y)/x,g(y)/u74谓词逻辑的归结 判断判断S=P(x,x),P(y,f(y)是否可合一？是否可合一？（思考题）（思考题） 75谓词逻辑的归结5、谓词逻辑中的归结式 谓词逻辑下求两个子句的归结式，和命题逻辑
45、一样也是消去互补对，但需考虑变量的合一与置换。设S=C1,C2C1,C2是子句集中的子句，L1、L2分别是C1，C2中的文字，并且L1和L2有最一般合一，则子句C1-L1C2-L2称为C1、C2的归结式。C1，C2称为归结式的亲本子句，L1、L2称为归结文字。76谓词逻辑的归结 例：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-L1C2-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)
46、Q(a),C2=Q(x)R(y)求C1、C2的归结式。 R(C1,C2) = P(a,y) R(y) =a/x77谓词逻辑的归结 在对子句进行归结之前，可先在子句内部进行化简。如子句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)78归结反演 应用归结原理证明结论为真的过程称为归结反演。 定理1 Q为P1,P2,Pn的逻辑结论，当且仅当(P1P2 Pn)Q是不可满足的。 定理2 设有谓词公式F，其标准形的子句集为S，则F不可满足的充要条件是S不可满足。79归结反演 设F为
47、已知前提的公式集，Q为目标公式(逻辑结论)，用归结反演证明Q为真的步骤是：1) 否定Q，得到Q2) 把Q并入到公式集F中，得到F, Q3) 把公式集F, Q化为子句集S4) 应用归结原理对子句集S中的子句进行归结，并把每次归结得到的归结式都并入S中。如此反复进行，若出现了空子句，则停止归结，从而证明了Q为真。80归结反演81归结反演82基于归结反演的问题求解 归结反演除了可用于定理证明外，还可用来求取问题的答案，问题求解的方法与定理证明类似。问题求解的步骤如下：1) 把已知前提用谓词公式表示出来，并且化为相应的子句集S。2) 把待求解的问题也用谓词公式表示出来，然后把它的否定式与谓词ANSWE
48、R构成一个析取式，ANSWER是一个为了求解问题而专设的谓词，其变元必须与问题公式的变元完全一致。3) 把此析取式化为子句集，并且把该子句集并入到子句集S中，得到子句集S。4) 对S应用归结原理进行归结。5) 若得到归结式ANSWER，则答案就在ANSWER中。83基于归结反演的问题求解 例子:已知:; F1:王(Wang)先生是小李(Li)的老师; F2:小李和小张(Zhang)是同班同学; F3:如果x和y是同班同学,则x的老师也是y的老师问小张的老师是谁? 解:定义谓词T(x,y):x是y的老师;C(x,y):x与y是同班同学;则已知和待求解的问题可表示成如下的谓词公式：F1: T(Wa
49、ng, Li)F2: C(Li, Zhang)F3: G:),(),(),()()()(yzTxzTyxCzyx)(),()(xANSWERZhangxTx84基于归结反演的问题求解 把上述公式化为子句集并进行归结：(1)(2)(3)(4)(5) (1)与(3)归结(6) (4)与(5)归结(7) (2)与(6)归结),(LiWangT),(ZhangLiC),(),(),(yzTxzTyxC)(),(uANSWERZhanguT),(),(yWangTyLiC)(),(WangANSWERZhangLiC)(WangANSWER85基于归结反演的问题求解86归结反演的策略 1、删除策略 2、
50、支持集策略 3、线性输入策略 4、单文字子句策略 5、祖先过滤形策略87归结反演的策略1、删除策略 在归结的过程中删除以下子句 含有纯文字的子句; 含有永真式的子句; 子句集中被别的子句类含的子句; 2、支持集策略 支持集策略对参加归结的子句提出了如下限制：每一次归结时，亲本子句中至少应有一个是由目标公式的否定所得到的子句，或者是它们的后裔。88归结反演的策略3、线性输入策略 线性输入策略对参加归结的子句提出了如下限制：参加归结的两个子句中必须至少有一个是初始子句集中的子句。初始子句集是有已知前提与结论的否定组成的子句集。4、单文字子句策略 单文字子句策略要求参加归结的两个子句中必须有一个是单
