人工智能及应用_ch3_1.ppt

1、经典逻辑推理,推理的基本概念 推理的逻辑基础 自然演绎推理 归结演绎推理 与/或型演绎推理,推理的基本概念,推理是按某种策略由已知判断推出另一判断的思维过程。 人工智能中的推理是由程序完成的-推理机。,已掌握的与求解问题有关的知识 关于问题的已知事实,结论,推理的方式及分类-演绎推理,演绎推理：由一般到具体（个别）的推理，演绎推理一般是三段论： 大前提：已知的一般性知识或假设。 小前提：关于所研究的具体情况或个别事实的判断。 结论：由大前提推出的适合小前提所示情况的新判断。,推理的方式及分类-演绎推理,例： 大前提：足球运动员身体是强壮的。 小前提：高波是足球运动员。 结论：所以高波的身体是强

2、壮的。,推理的方式及分类-归纳推理,归纳推理是由个别到一般的推理过程。按归纳时所选事例的广泛性，可分为完全归纳和不完全归纳。,产品抽样检查,数学归纳法,默认推理（缺省推理）,在知识不完全的情况下，假设某些条件已经具备的情况下进行的推理。例如，A成立，在此条件下是否有B成立不清楚，假设A成立并且AB成立，并利用其进行推理。,确定性推理和不确定性推理,确定性推理是指推理时使用的知识都是精确的，推出的结论也是确定的。本章主要研究此部分内容。 不确定性推理是指推理时所使用的知识有不精确或不确定的，推出的结论也不完全肯定。 人类的思维活动常常在知识不完全、不精确的情况下进行的，相对来说，不确定性推理更接

3、近人类的思维过程。,单调推理和非单调推理,单调推理是指推理过程中，随着推理的向前推进及新知识的加入，推出的结论越来越接近最终目标。 非单调推理是指推理过程中，随着推理的向前推进及新知识的加入，不仅没有加强已有的结论，反而要否定它，使推理退回到前面的某一步。,推理的控制策略,推理方向。 搜索策略：第五章介绍。 冲突消解策略。 求解策略-求出一个解？求出所有的解？求出最优解？ 限制策略-防止无穷推理过程。,推理方向-正向推理,从已知事实出发的一种推理，又称为数据驱动推理、前件推理，其基本思想为： 从用户提供的初始事实出发，在知识库KB中找出当前可适用的知识，构成可使用知识集KS，然后按某种冲突消解

4、策略从KS中选择出一条知识进行推理，并将推出的结论作为新事实加入到数据库中作为下一步推理的已知事实。重复此过程直到求得所要求的解或知识库中无知识可用为止。,开始,把已知事实送入数据库,DB包含问 题的解？,把KB中适用知识选出形成KS,KS空？,KB中有可 用知识吗？,按冲突消解策略选出知识推理,得到新事实？,将新事实加入DB,成功退出,用户能否补 充新事实？,失败退出,把用户提供的 新事实加入DB,Y,N,N,Y,Y,N,Y,N,N,Y,正向推理的特点,优点：直观，允许用户提供有用的事实，适用于诊断、设计、预测和监控等领域的问题求解。 缺点：推理无明确目标，求解问题时可能会执行许多与解无关的

5、操作，推理效率低。,推理方向-逆向推理,以某个假设目标为出发点的一种推理，又称为目标驱动推理、后件推理，其基本思想为： 首先选定一个假设目标，然后寻找支持假设目标的证据，若所需要的证据都能找到，则说明假设成立。若无论如何都找不到所需的证据，则说明假设不成立。此时需要另做新的假设。,开始,提出假设,假设在数 据库中？,把KB中适用知识选出形成KS,该假设是 证据吗？,按冲突消解策略选出一条知识 并将该知识的一个运用条件作 为新的假设目标,询问用户 有此事实？,成功退出,N,Y,N,Y,该假设成立,该假设成立 并将事实存入 数据库DB,还有假设？,N,N,Y,KS是空？,失败退出,Y,N,Y,Y,

6、逆向推理示例,以上一章动物判别的产生式系统为例。 以“虎”为假设目标，数据库DB为空。 检查数据库DB中有无“虎”这个事实？无。 判断该目标是否是证据？r10的结论是“虎”，所以不是证据。 在知识库中查找所有能导出该目标的知识。 r10是适用知识。,逆向推理示例,将r10的条件作为新的假设进行验证。 条件1：该动物是黄褐色 条件2：该动物有黑色条纹 条件3：该动物是哺乳动物 条件4：该动物是食肉动物 条件1-新假设：该动物是黄褐色 不在数据库中，是证据。 询问用户是否是事实？是，存入数据库,逆向推理示例,条件2：新假设-该动物有黑色条纹 不在数据库中，是证据。 询问用户是否是事实？是，存入数据

7、库 条件3：新假设-该动物是哺乳动物 不在数据库中，不是证据。 在知识库中寻找适用知识，r1,r2。 将r1,r2的条件有毛、有奶作为假设。,逆向推理示例,新假设：有毛不在数据库中。是证据。 询问用户是否是事实？是，存入数据库 新假设：有奶不在数据库中。是证据。 询问用户是否是事实？是，存入数据库,逆向推理示例,条件4：新假设-该动物是食肉动物 不在数据库中，不是证据。 在知识库中寻找适用知识，r5,r6。 将r5,r6的条件吃肉、有犬齿、有爪、眼盯前方作为假设。 新假设：吃肉不在数据库中。是证据。 询问用户是否是事实？是，存入数据库 。 。 。 结论：该动物是“虎”,逆向推理的特点,优点：不

8、必使用与目标无关的知识，目的性强。 缺点：目标选择盲目，若不符合实际就要多次提出假设，影响推理效率。,混合推理,正向推理：具有盲目性，效率低。 逆向推理：假设选择的盲目性。 两者结合起来使推理发挥各自的优点。 混合推理的方法： 先正向后逆向混合推理； 先逆向后正向混合推理； 双向混合推理。,先正向后逆向混合推理框图,开始,进行正向推理,需要逆向 推理吗？,以正向推理的结论作为 假设进行逆向推理,Y,Y,N,还需要正向 推理吗？,退出,N,先正向后逆向混合推理框图,开始,进行逆向推理,需要正向 推理吗？,进行正向推理,Y,Y,N,还需要逆向 推理吗？,退出,N,双向混合推理,开始,选择推理方向,

9、是逆向吗？,比较正向推理的结论 和逆向推理的结论,Y,N,匹配吗？,成功退出,N,进行逆向推理,进行正向推理,Y,混合推理的适用场合,已知事实不够充分。 正向推理的结果可信度不高。 希望得到更多的结论。,推理的冲突消解策略,冲突：推理过程中，知识库中有多条适用知识时称发生冲突。 冲突消解：从多条适用知识中选择一条最佳知识进行推理的过程称为冲突消解。 冲突消解策略：冲突消解所用的策略。,常用冲突消解策略,特殊知识优先。 新鲜知识优先。 差异性大的知识优先。 领域知识优先。 前提条件少者优先。 上下文关系优先。,推理的逻辑基础,谓词公式的解释 定义3-1 设D为谓词公式P的个体域，若对P中的个体常

10、量、函数和谓词按如下规定赋值： 为每一个个体常量指派D中的一个元素； 为每个n元函数指派一个从DnD的映射； 为每个n元谓词指派一个DnT，F的映射 则称这些指派为谓词公式P在D上的一个解释。,谓词公式的解释的示例,例 设个体域D=1，2，求公式A=(x)(y)P(x,y)在D上的解释，并指出在每一中解释下公式A的真值。,谓词公式的解释的示例,对第一个解释有： x=1 y=1时 P(x,y)的真值为T x=2 y=1时 P(x,y)的真值为T 对x在D上的任意取值，都存在y=1使谓词公式P(x,y)的真值为T，所以在此解释下谓词公式A=(x)(y)P(x,y)的真值为T,谓词公式的永真性和可满

11、足性,定义3-2 如果谓词公式对非空个体域D上的任何解释都取真值T，则称P在D上是永真的；如果P在任何非空个体域上均是永真的，则称P是永真的。 定义3-3 对于谓词公式P，如果至少存在D上的一个解释使P在此解释下的真值为T，则称公式P在D上可满足。,谓词公式的永真性和可满足性,定义3-4 如果谓词公式对非空个体域D上的任何解释都取真值F，则称P在D上是永假的；如果P在任何非空个体域上均是永假的，则称P是永假的。 永假性又称为不可满足性,谓词公式的等价性,定义3-5 设P和Q是两个谓词公式，D是它们共同的非空个体域，若对D上的任何解释，P与Q都有相同的真值，则称P和Q在D上是等价的；如果D是任意

12、个体域，则称P和Q是等价的。一般记为： PQ,经常使用的等价式,交换律：PVQ QVP，PQ QP 结合律：(PVQ)VR PV(QVR), (PQ) R P (QR) 分配律：PV(QR) (PVQ)(PVR), P (QVR) (PQ) V(PR) 德.摩根律：(PVQ) P Q, (PQ) P V Q,经常使用的等价式,双重否定律：P P 吸收律：PV(PQ) P, P(PVQ) P 补余律：PVP T,P P F 连词化归律：P Q P V Q, PQ (PQ) V (PQ),经常使用的等价式,量词转换律：(x)P (x)P (x)P (x)P 量词分配律: (x)(PQ) (x)P(

13、x)Q (x)(PVQ) (x)PV(x)Q,永真蕴含式,定义3-6 设P和Q是两个谓词公式，如果PQ永真，则称P永真蕴含Q，且称Q是P的逻辑结论。一般记为： PQ,常用的永真蕴含式,化简式：PQP， PQQ 附加式：PPVQ， QPVQ 析取三段论：P，PVQQ 假言推理：P，PQ Q 拒取式： Q， PQ P,常用的永真蕴含式,假言三段论：PQ，QRPR 两难推论： PVQ，PR，QRR 全称固化：(x)P(x)P(y)，其中y是个体域中的任一个个体。 存在固化：(x)P(x)P(y)，其中y是个体域中使P(x)为真的个体。,谓词公式的范式,所谓范式是指公式的标准形式，常用的命题、谓词公式

14、范式有： 析取范式 合取范式 前束范式 Skolem范式,析取范式与合取范式,定义3-7 原子或原子的否定称为文字，有限个文字的析取式称为一个子句；有限个文字的合取式称为短语。 定义3-8 有限个短语的析取式称为析取范式；有限个子句的合取式称为合取范式。 定理3-1 对于任意命题公式，都存在与之等价的析取范式和合取范式。,析取范式与合取范式-示例,文字：P，P 子句：P，PVQVR，PVQ 短语：P，PQR，PQ 合取范式：P，PQ，PVQ， （PVQVR） （PVQ） 析取范式： P，PQ，PVQ， （P Q R）V（P Q）,；,析取范式与合取范式-说明,一个文字即可是短语也可是子句； 一

15、个文字即可是析取范式也可是合取范式； 一个子句即可是析取范式也可是合取范式； 一个短语即可是析取范式也可是合取范式。,前束范式,定义3-9 谓词公式G称为前束范式，如果G有如下形状：(Q1x1) (Q2x2) (Qnxn)M，其中(Qixi) 是 (xi) 或(xi) ，i=1,2,n，M是不含量词的谓词公式，(Q1x1) (Q2x2) (Qnxn)称为首标，M称为母式。 定理3-2 对任意谓词公式G，都存在与其等价的前束范式。,Skolem范式,定义3-10 谓词公式G的等价前束范式为(Q1x1) (Q2x2) (Qnxn)M，其中M为合取范式， (Qixi)是存在量词，并且它左边没有全称量

16、词，则取异与出现在M中的所有常量符号c，并用c代替M中的所有xi ，然后在首标中删除(Qixi)。若Qs1Qs2Qsm为所有出现在(Qixi) 左边的全称量词，则取异于出现在M中的所有函数符号的m元函数符号f(xs1xs2xsm )，并用f(xs1xs2xsm )代替M中的所有xi ，然后在首标中删除(Qixi)。 经处理得到的公式S称为G的Skolem范式。,Skolem范式,定理3-3 对任意谓词公式G，S是与之相应Skolem范式，则G与S的不可满足性是等价的。,谓词范式-示例,前束范式： (x)(y)(z)(P(x,y)Q(x,z) (x)(y)(z)(Q(x,y,z)R(x,z) S

17、kolem范式： (x)(y)(z)(P(x,f(x)Q(x,z) (z)(Q(a,b,z)VR(a,z)P(z),置换和合一,定义3-11 置换是形如t1/x1,t2/x2,tn/xn 的有限集合，其中t1,t2,tn 是项，x1,x2,xn 是互不相同的变元； ti/xi 表示用ti 置换xi。并且要求ti与xi不能相同， xi不能循环出现在另一个ti中。一般用希腊字母、表示。 例：a/x,c/y,f(b)/z是一个置换 f(a,y)/x,g(x)/y由于x,y循环出现，故不是置换。,置换的例示,定义3-12 设=t1/x1,t2/x2,tn/xn 是一个置换，F是一个谓词公式，把公式中的

18、所有xi换成ti i=1,2,n，得到一个新公式G，称G为F在置换下的例示，记作G=F。 结论：一个谓词公式的任何例示都是该谓词公式的逻辑结论。即有： FG,置换的合成,定义3-13 设=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 i=1,2,n. 当 yix1,x2,xn时删去ui/yi i=1,2,m 最后剩下的元素所构成的集合。,置换合成-示例,设=f(y)/x,z/y,=

19、a/x,b/y,y/z求和的合成。 置换集合 f(b)/x,y/y,a/x,b/y,y/z 删除得 f(b)/x,y/z,合一,定义3-14 设公式集F=F1,F2,Fm ，若存在一个置换，可使F1 =F2 =Fm ，则称是F的一个合一。称F1,F2,Fm 是可合一的。 例：设公式集F=P(x,y,f(y),P(a,g(x),z) 则：=a/x,g(a)/y,f(g(a)/z 是F的一个合一。,最一般合一,定义3-15 设是公式集F的一个合一，如果对F的任何一个合一都存在一个置换，使得= ，则称是一个最一般合一。 结论：一个公式集的一般合一不是唯一的，但最一般合一是唯一的。,合一算法,定义3-16 设F=F1,F2,Fm 是一个非空有限的公式集，从F中每个公式的第一个符号同时右比较，直到发现第一个不同符号为止，从F的各个公式中取出