人工智能搜索推理技术消解原理.ppt

《人工智能搜索推理技术消解原理.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、人工智能ArtificialIntelligence(AI)第3章搜索推理技术3.1图的搜索策略3.2盲目搜索3.3启发式搜索3.4与或树搜索（补充）3.5博弈树搜索（补充）3.6消解原理3.6消解原理3.6.1子句集的求取3.6.2消解原理（补充）3.6.3消解推理规则3.6.4含有变量的消解式3.6.5消解反演求解过程3.6.6Horn子句集消解（补充）3.6.7Prolog语言简介（补充）3.6消解原理第2章中介绍：谓词逻辑的基本知识合一算法（求最一般的一致置换或合一者mgu）本节：消解原理（或者归结原理）3.6.1子句集的求取如何将谓词公式转化为

2、子句集，作为合一算法的输入（公式集）3.6.1.1若干基本概念3.6.1.2子句集的求取3.6.1.1若干基本概念1自由变元与约束变元2前束范式与前束合取范式3斯科伦（Skolem）范式4子句集设α，β是一个谓词公式，将量词记作θ（即或）1自由变元与约束变元如果α中包含部分公式(θx)β，则β中变元x的一切出现都称为x在α中的约束出现，相应地称x为约束变元（哑元、虚构变量、约束变量）约束变元α中不在任何量词作用域内的变元x，称为变元x在α中的自由出现，相应地称x为自由变元（自由变量）自由变元：量词的作用域（辖域）是直接跟在它后面的公式如果有括号，则是

3、括号里的公式如果没有括号，则是最短的完整公式说明：例1：x(P(x)y(R(x,y)))x,y都是约束变元例2：x(P(x)(R(x,y)))x是约束变量，y是自由变元改名：将谓词公式中一个变元名改成另一个变元名，但是要求改名后的公式与原公式意义相同（真假值相同）原则：改成的新的变元名一定是量词作用域中没有出现过的变元名（包括约束变元和自由变元）约束变元的改名或变量的标准化例3：x(P(x)(R(x,y)))除了y外，可以将x改成任何变元名例4：xP(x)∧Q(y)可以改成任何变元名，包括y（建议不要用）2前束范式与前束合取范式定义：设谓

4、词公式α具有形式：α＝(θ1x1)…(θnxn)M其中：θi(i=1,…,n)是或M是不包含量词的谓词公式则，称α是前束范式称(θ1x1)…(θnxn)为前束称M为母式定义：设谓词公式α是一个前束范式，如果α的母式具有形式：（M11∨M12…∨M1n1）∧（M21∨M22…∨M2n2）∧……(Mm1∨Mm2…∨Mmnm）其中，Mij是原子公式或其非，则称α是前束合取范式。相应地有前束析取范式前束范式：(x)(y)(z)((～P(x)∧～Q(y))∨R(z))前束合取范式（交换律、分配律）(x)(y)(z)((R(z)∨～P(x))∧(R(

5、z)∨～Q(y)))例：3斯柯伦范式定义：前束中不含存在量词的前束范式称为斯柯伦范式①若xk(1≤k≤n)左边没有全称量词，则取不在母式中出现的常量替代母式中的所有xk，并删除前束中的xk消去存在量词的规则或前束范式化成斯柯伦的步骤是：②若xk(1

6、yzuvwA(x,y,z,u,v,w)(用a替代x，删除x)=yzuvwA(a,y,z,u,v,w)（用f(y,z)代替u，删除u）=yzvwA(a,y,z,f(y,z),v,w)（用h(y,z,v)代替w，删除w）=yzvA(a,y,z,f(y,z),v,h(y,z,v))例：求斯柯伦范式说明：一个谓词公式的斯科伦范式不是唯一的，尽可能将斯科伦函数取得简单一点化成前束范式化成前束合取范式化成斯科伦范式（斯科伦函数的变元较多）对于谓词公式：α=α1∧α2正常的做法：将α1、α2分别化成前束范式对α1、α2分别求出斯

7、柯伦范式β1、β2将β1∧β2的量词左移得到α的斯柯伦范式（即前束范式）简化的做法：好处：简化斯科伦函数α=α1∧α2α=y1x1P(x1,y1)∧x2y2Q(x2,y2)=y1x1x2y2(P(x1,y1)∧Q(x2,y2))（前束合取范式）=x1x2(P(x1,a1)∧Q(x2,f(x1,x2)))例：正常化法α=y1x1P(x1,y1)∧x2y2Q(x2,y2)=x1P(x1,a1)∧x2Q(x2,f(x2))（先分别化成斯科伦范式）=x1x2(P(x1,a1)∧Q(x2,f(x2)))(前束合取范式）简化化法4

8、子句集①原子命题是原子公式②如果t1,…,tn(n≥1)是项，P是谓词，则P(t