3-人工智能经典逻辑推理.ppt

人工智能Artificial Intelligence 主讲：杨利英 西安电子科技大学 E_mail：yangliying1208@163.com 第三章 经典逻辑推理 3.1 基本概念 3.2 自然演绎推理 3.3 归结演绎推理 3.4 与或形演绎推理 3.1 基本概念 3.1.1 什么是推理 3.1.2 推理方式及其分类 1. 演绎推理、归纳推理、默认推理 3.1.2 推理方式及其分类 3. 单调推理、非单调推理 推出的结论是否单调增加 3.1.3 推理的控制策略 推理的控制策略主要包括：推理方向、有哪些信誉好的足球投注网站策略、冲突消解策略、求解策略及限制策略。 1. 正向推理（数据驱动推理） 基本思想：从用户提供的初始已知事实出发，在知识库KB中找出当前可适用的知识，构成可适用的知识集KS，然后按某种冲突消解策略从KS中选出一条知识进行推理，并将推出的新事实加入到数据库DB中，作为下一步推理的已知事实。在此之后，再在知识库中选取可适用的知识进行推理。如此重复进行这一过程，直到求得所要求的解。 正向推理示意图 2 逆向推理 基本思想 首先选定一个假设目标，然后寻找支持该假设的证据，若所需的证据都能找到，则说明原假设是成立的；若找不到所需要的证据，则说明原假设不成立，此时需要另作新的假设。 逆向推理示意图 3.1.3 推理的控制策略 3. 混合推理 先正向推理后逆向推理 先逆向推理后正向推理 4. 双向推理 正向推理与逆向推理同时进行，且在推理过程中的某一步上“碰头”。 5. 求解策略 只求一个解，还是求所有解以及最优解。 6. 限制策略 限制有哪些信誉好的足球投注网站的深度、宽度、时间、空间等等。 3.1.4 模式匹配 模式匹配是指对两个知识模式(例如两个谓词公式、框架片断、语义网络片断)进行比较，检查这两个知识模式是否完全一致或者近似一致。 3.1.4 模式匹配 确定性匹配是指两个知识模式完全一致，或者经过变量代换后变得完全一致。 知识：IF father(x,y) and man(y) THEN son(y,x) 事实：father(李四，李小四) and man(李小四) 不确定性匹配是指两个知识模式不完全一致，但是它们的相似程度又在规定的限度内。 变量代换（置换） 定义 代换是一个形如 {t1/x1,t2/x2,…,tn/xn} 的有限集合。 其中t1,t2,…,tn是项（常量、变量、函数）； x1,x2,…,xn是（某一公式中）互不相同的变元； ti/xi表示用ti代换xi 不允许ti与xi相同，也不允许变元xi循环地出现在另一个tj中。 令θ= {t1/x1,t2/x2,…,tn/xn}为一个代换，F为表达式，则Fθ表示对F用ti代换xi后得到的表达式。 Fθ称为F的特例。 代换的复合 定义 设 θ= {t1/x1,t2/x2,…,tn/xn} λ= {u1/y1,u2/y2,…,um/ym} 是两个代换，则这两个代换的复合也是一个代换，它是从 {t1λ/x1,t2λ/x2,…,tnλ/xn,u1/y1,u2/y2,…,um/ym} 中删去如下两种元素： tiλ/xi 当tiλ=xi ui/yi 当yi∈{x1,x2,…,xn} 后剩下的元素所构成的集合，记为θ°λ 。 代换复合的例子 例如，设有代换 θ= {f(y)/x,z/y} λ= {a/x,b/y,y/z} 则 θ°λ=? 公式集的合一 定义 设有公式集F={F1,F2,…,Fn}，若存在一个代换λ使得 F1λ=F2λ=…=Fnλ 则称λ为公式集F的一个合一，且称F1,F2,…,Fn是可合一的。 最一般合一 定义 设σ是公式集F的一个合一，如果对任一个合一θ都存在一个代换λ，使得θ=σ°λ 则称σ是一个最一般的合一。 求取最一般合一 差异集：两个公式中相同位置处不同符号的集合。 例如：F={F1:P(x,y,z), F2:P(x,f(a),h(b))} 则D1={y,f(a)}, D2={z,h(b)} 求取最一般合一的算法： 令k=0,Fk=F, σk=ε，ε是空代换。 若Fk只含一个表达式，则算法停止，σk就是最一般合一。 找出Fk的差异集Dk。 若Dk中存在元素xk和tk，其中xk是变元，tk是项，且xk不在tk中出现，则置： Fk+1=Fk{tk/xk} σK+1=σk°{tk/xk} k=k+1 然后转(2)。若不存在这样的xk和tk则算法停止。 算法终止，F的最一般合一不存在。 求取最一般合一的例子 求公式集 F={P(a,x,f(g(y))),P(z,f(z),f(u))} 的最一般合一。 求取最一般合一的例子 F={P(a,x,f(g(y))),P(z,f(z),f(u))} 求其最一