人工智能讲义课件

第五章消解反演系统5.1 消解反演z正向消解演绎系统的缺点z什么是消解反演将结论取反加入前提条件再进行消解推理,其目标是产生一个空子句NIL.空子句表示有矛盾.因为只有在子句集中出现P和P形式的母体子句对时,才会产生消解式NIL.消解反演有效性的证明将结论取反加到前提条件中推出矛盾,即证明前提和结论的否定不可能同时成立.设前提公式集为S,结论公式为WS(W)(S(W)(S V(W)(S V W)(S W)所以若S(W)推出矛盾,即S(W)永假,则S W永真.消解反演的优点目标明确,简单易行.z消解反演系统的基本算法RESOLUTION将前提公式集S和结论公式W的否定W化为子句集S0until NIL S0 或没有可消解的子句对 do Begin在S0中选取可消解的子句对Ci和Cj计算Ci和Cj的消解式Rij把Rij加入到S0中endz举例例一每个储蓄钱的人都要获得利息.请证明:如果没有利息,那么就没有人去储蓄钱.证明:令S(x,y)表示“x储蓄y”M(x)表示“x是钱”I(x)表示“x是利息”E(x,y)表示“x要获得y”S:(x)(y)(S(x,y)M(y)(z)(I(z)E(x,z)W:(x)I(x)(y)(z)(S(y,z)M(z)1 把前提化为子句形 (x)(y)(S(x,y)M(y)V(z)(I(z)E(x,z)(x)(y)(S(x,y)M(y)V(z)(I(z)E(x,z)(x)(y)(S(x,y)VM(y)V(z)(I(z)E(x,z)令z=f(x)为Skolem函数:(x)(y)(S(x,y)VM(y)V(I(f(x)E(x,f(x)(x)(y)(S(x,y)VM(y)V I(f(x)(S(x,y)VM(y)V E(x,f(x)得到下列子句:(1)S(x,y)VM(y)V I(f(x)(2)S(x,y)VM(y)V E(x,f(x)2 结论的否定 (x)I(x)(y)(z)(S(y,z)M(z)化为子句形 (x)I(x)V(y)(z)(S(y,z)M(z)(x)I(x)(y)(z)(S(y,z)M(z)(x)(I(x)(y)(z)(S(y,z)M(z)(x)(I(x)(y)(z)(S(y,z)M(z)(x)(I(x)S(A,B)M(B)得到下列子句:(3)I(z)(4)S(A,B)(5)M(B)3 消解S(x,y)VM(y)V I(f(x)I(z)S(A,B)M(B)S(x,y)VM(y)M(B)NILf(x)/zA/x,B/y5.2 消解反演系统的控制策略z引言例已知:任何能够阅读者都是识字的.海豚不识字但某些海豚是有智力的.求证:某些有智力者不能阅读.证:令R(x)表示x能阅读,L(x)表示x识字,D(x)表示x是海豚,I(x)表示x有智能.前提:(1)(x)(R(x)L(x)(2)(x)(D(x)L(x)(3)(x)(D(x)I(x)结论:(4)(x)(I(x)R(x)将结论取反后加入前提谓词公式集并化为子句集:(1)R(x)VL(x)(2)D(y)VL(y)(3)D(A),I(A)(4)I(z)VR(z)I(A)I(z)VR(z)R(x)VL(x)D(y)VL(y)D(A)R(A)L(A)L(A)I(z)VL(z)R(y)VD(y)I(z)VD(z)D(A)R(A)I(A)NILD(A)I(A)讨论对所有可消解的子句对进行消解对应于反演图的宽度优先搜索.子句集:S,(S),(S),迅速增大,系统效率很低.高效比完备更重要.z简化字句集 阅读PP8587P86“2.归类消去”:如果有一个子句L中含有的文字组成的集合为Li,而另一子句N中含有的文字组成的集合为Nj 则说子句L可以归类子句Nz文字优先消解法在当前子句集的能消解的子句对中,选其中有一个是文字的优先进行消解.前例采用文字优先消解法的消解过程:讨论 为什么可以删除重言式?归类消去的依据是什么?P(A)为什么不能归类P(x)?T S SP(x)(P(A)V R(y)V S(z)P(x)I(A)I(z)VR(z)R(x)VL(x)D(y)VL(y)D(A)R(A)L(A)L(A)D(A)NILNILz支持集优先消解法支持集:目标公式取反后化成的子句和祖先中有这些子句的消解式所构成的子句集.支持集优先消解法:母体子句对中至少有一个子句在支持集中时才进行消解.逆向推理与反演前例采用支持集优先消解法的消解过程:I(A)I(z)VR(z)R(x)VL(x)D(y)VL(y)D(A)R(A)L(A)I(z)VL(z)I(z)VD(z)D(A)I(A)NILD(A)D(A)NILNILNILL(A)z锁消解法配锁与锁合并对子句集中所出现的每一个文字(不论是否相同)都加以不同的编号,称为配锁.编号称为锁号.如:C1=1P(x)V2Q(x)V3P(A)V4Q(A)C2=5Q(y)V6P(A)V7W(y)在同一子句中经过置换出现相同的文字进行合一时,给该文字保留最小的锁号,称为锁合并.如:S=A/x 则 C1S=1P(A)V2Q(A)V3P(A)V4Q(A)=1P(A)V2Q(A)锁消解当两子句中锁号最小的文字为互补文字时才进行消解,称为锁消解.如C1=1P(A)V2Q(x)C2=3P(A)V4Q(A)C3=6P(A)V5Q(A)C1和C2可进行锁消解得 2Q(x)V4Q(A)C1和C3不可进行锁消解 举例:设初始子句集为 (1)1Q(B)V2P(u)(2)3P(w)V4Q(B)(3)5W(v)V6Q(v)(4)7W(v)V8Q(B)1Q(B)V2P(u)7W(v)V8Q(B)3P(w)V4Q(B)5W(v)V6Q(v)6Q(v)V8Q(B)2P(u)4Q(B)NIL锁消解法的完备性虽然配锁是任意的,但是只要一个子句集是不可满足的,总可以找到能进行锁消解的子句对,直至出现空子句.即锁消解法是完备的.非形式的证明(反证法):若一个子句集是不可满足的,而找不到可进行锁消解的子句对,即所有子句中最小锁号的文字均不互补,则只要把这些最小锁号的文字中的正文字取值为真,而把带“”号的文字取值为假,则每个子句均为真,故子句集是可以满足的,与前提矛盾.例:C1=1P(A)V2Q(x)C2=3P(A)V4Q(x)C3=6P(A)V5Q(x)所有子句中最小锁号的文字为:P(A),P(A),Q(x).只要取 P(A)=T,Q(x)=F,则 C1 C2 C3=Tz习题P100 第4题P100 第7题:“对于所有的x,y 和 z”P100 第10题P100 第3题P100 第11题5.3 由消解反演求取答案的方法z推定证明谓词演算不仅能用于定理证明,也能用于其他问题求解.例如,从前提公式集S出发,要证明结论(x)W(x),是一个一般的谓词演算证明问题,而如果要推出是哪一个x能满足W(x),即要产生满足条件的变量x的实例,则是一个推定证明的问题.简例:已知无论约翰(John)在哪里,菲多(Fido)也在那里;现在约翰在学校,请问菲多在哪里?从给定的条件出发来推出某个事实,称为推定证明.z答案求取过程 消解反演法的启示先证明从S能得到(x)W(x)的结论.将结论与结论的否定构成的重言式与前提条件一起组成初始公式集参加消解.消解的过程仿照证明的消解反演过程进行,消解结束后会留下结论的有关部分,即为答案,其中的变量已被进行必要的置换(例化).简例的求解前提:(x)(AT(JOHN,x)AT(FIDO,x)AT(JOHN,SCHOOL)先证:(x)AT(FIDO,x)化成子句,消解反演:AT(FIDO,x)AT(JOHN,y)V AT(FIDO,y)AT(JOHN,x)AT(JOHN,SCHOOL)NILx/ySCHOOL/x“菲多在哪里?”的消解反演树AT(FIDO,x)VAT(FIDO,x)AT(JOHN,y)V AT(FIDO,y)AT(FIDO,x)VAT(JOHN,x)AT(JOHN,SCHOOL)AT(FIDO,SCHOOL)x/ySCHOOL/x“菲多在哪里?”的修改证明树要么菲多不在任何地方,要么菲多在某个地方.通过消解反演求取问题答案的步骤(1)先把要求解的问题变成相应的证明问题,得到一棵消解反演树;(2)把目标公式的否定产生的每个子句再加以否定,加入到原子句中构成重言式,并与原前提条件子句组成新的初始子句集;(3)从新的初始子句集开始,执行和反演树一样的消解,在对应于反演树根部空子句处得到的子句即为问题的一个答案,消解所产生的树称为修改证明树.举例(PP94-96)前提公式子句集：A(x)VF(x)VG(f(A)x不是大学生V x听计算机课V A的 兄弟是研究生F(y)VB(y)y听计算机课y懂外语F(z)VC(z)z听计算机课z懂计算机G(x1)VB(x1)x1是研究生x1懂外语G(y1)VD(y1)y1是研究生y1会写论文A(E)VF(h(z1)E是大学生V z1的学生听计算机课 (z1为计算机系的老师)谁既懂外语又懂计算机或既会写论文又懂外语？目标公式：(x)(B(x)C(x)V(D(x)B(x)目标公式取反后化为子句：B(x2)VC(x2)D(y2)VB(y2)答案：(B(E)C(E)V(D(f(A)B(f(A)V(B(h(z1)C(h(z1)E既懂外语又懂计算机；A的兄弟既会写论文又懂外语；z1（计算机系老师）的学生既懂外语又懂计算机。z含有全称量词的目标公式的答案提取目标公式子句中的Skolem函数当目标公式含有全称量词时,在目标公式的否定式中就会出现存在量词,把公式变成子句就要引入Skolem函数,在提取回答时,应正确解释这些Skolem函数的意义.例1 前提:每个人都是某人的孩子.(x)(y)C(x,y)如果x是y的孩子,那么y是x的父辈.(x)(y)C(x,y)P(y,x)问题:对于任意一个x,谁是他的父辈?目标:对于任一个x,存在y是他的父辈.(x)(y)P(y,x)前提子句:(1)C(x,f(x)(2)C(x,y)V P(y,x)目标公式的否定化为子句:(x)(y)P(y,x)不是所有的x都有父辈(x)(y)P(y,x)存在x没有父辈 (3)P(y,A)消解反演树:P(y,A)C(x,y)V P(y,x)C(A,y)C(x,f(x)NIL修改证明树:P(y,A)V P(y,A)C(x,y)V P(y,x)C(A,y)V P(y,A)C(x,f(x)P(f(A),A)Skolem函数A在这里的意义是,对任何一个人A,我们都能证明P(f(A),A),即A总有一个父辈f(A).因此,在修改证明树中可以把目标公式子句中出现的Skolem函数换成新的变量,如t.这样得到的回答语句为P(f(t),t),意义更为明了,即任一个人t的父辈是f(t).要么有某人无父辈,要么任一人都有父辈 例2 前提:或者是B叫所有的人自己投自己的票,或者 是A叫所有的人自己投自己的票.(w)P(B,w,w)V(u)P(A,u,u)问题:谁在叫所有的人投什么人的票?目标:存在一个人叫所有的人投某人的票.(x)(y)(z)P(x,y,z)前提子句:P(B,w,w)V P(A,u,u)目标的否定化为子句:(x)(y)(z)P(x,y,z)(x)(y)(z)P(x,y,z)P(x,g(x),z)消解反演树P(x,g(x),z)P(B,w,w)V P(A,u,u)P(B,w,w)NILA/x,g(A)/u,g(A)/zB/x,g(B)/w,g(B)/z修改证明树P(x,t,z)V P(x,t,z)P(B,w,w)V P(A,u,u)P(B,w,w)V P(A,t,t)A/x,t/u,t/zP(A,t,t)V P(B,t,t)B/x,t/w,t/z比较答案与目标的形式可知问题有两个答案，两文字受不同的全称量词约束答案求取过程的步骤首先按某种消解策略寻找一个消解反演树,并记下每一步消去的文字;将由目标公式的否定式求得的子句中的Skolem函数以新的变量代替;把由目标公式的否定的到的子句与子句的否定式构成重言式;仿照原始反演树的结构生成一棵修改证明树,在修改证明树中每次所消去的文字是由反演树中相应的消解决定的;修改证明树树根上的子句就是所求取的回答语句.5.4 Horn子句逻辑z一般子句与Horn子句(P97)zHorn子句的逻辑程序(PP9799)zHorn子句逻辑程序运行的实质过程与事实目标口zHorn子句与Prolog逻辑程序设计语言:-sister(x,Edward),parents(y,z,Edward)sister(x,y):-female(x),parents(y,u,v),parents(x,u,v):-female(x),parents(Edward,u,v),parents(x,u,v),parents(y,z,Edward)Female(Sdifen):-:-parents(Edward,u,v),parents(Alice,u,v),parents(y,z,Edward)Parents(Edward,Victoria,Albert):-:-parents(Sdifen,Victoria,Albert),parents(y,z,Edward)Female(Alice):-:-parents(Edward,u,v),parents(Sdifen,u,v),parents(y,z,Edward):-parents(Edward,u,v),parents(Alice,u,v),parents(y,z,Edward):-parents(Alice,Victoria,Albert),parents(y,z,Edward)parents(Alice,Victoria,Albert):-Parents(Edward,Victoria,Albert):-:-parents(y,z,Edward)parents(Sdifen,Mary,Edward):-z习题P101 第13题P101 第16题P100-4(x)P(x)的否定化为子句:(x)P(x),(x)P(x),P(x)P(x)P(A1)VP(A2)P(A2)NILA1/xA2/x而P(A)的否定P(A)显然不能和P(A1)VP(A2)消解说明:前者的意义是只要有一个x满足P(x)即可,而公式P(A1)VP(A2)告诉我们,A1和A2中至少有一个满足P.后者的意义是要证明某一个A满足P,而我们只知道A1或A2满足P,无法证明A是否满足P.(x)(Doctor(x)(y)(Patient(y)Like(y,x)(x)(y)(Poor-D(x)Patient(y)Like(y,x)(x)(Doctor(x)Poor-D(x)Doctor(x)V Patient(f(x),Doctor(x)V Like(f(x),x)Poor-D(y)V Patient(z)V Like(z,y)Doctor(A),Poor-D(A)Doctor(A)Doctor(x)V Patient(f(x)Patient(f(A)Doctor(x)V Like(f(x),x)Like(f(A),A)Poor-D(y)V Patient(z)V Like(z,y)Poor-D(A)Poor-D(A)NIL(x)(y)(Patient(x)Doctor(y)Poor-D(y)Like(x,y)划线部分与目标矛盾，永假。学科前沿讲座学科前沿讲座皇帝的新脑还是人类的终结皇帝的新脑还是人类的终结 一、关于人工智能 一、关于人工智能z从数值计算文字、图像等多媒体信息处理初步实现了Leibniz提出的“将人的思维机器化”的思想z让机器拥有人的心智成为计算机专家梦寐以求的理想！1956年，M.L.Minsky，C.Shanon，J.McCarthy(人工智能之父)等在美国达德茅斯大学召开第一届人工智能学术会议。会上首次使用“人工智能”这一术语。标志着人工智能学科的诞生。一、关于人工智能1950年，W.格雷.瓦尔特，可以自己充电的“乌龟”1960年，K.M.柯尔，模拟了一个精神病疗法专家电脑下棋方面，97年的“深蓝”(Deep Blue)，03年的“小深”(Deep Junior)一、关于人工智能z医生：我可以为你效劳吗z病人：我不知道z医生：请告诉我一些情形z病人：不z医生：请你说得仔细些z病人：今天我厌烦得很z医生：你知道这是什么原因z病人：是的我老了z医生：请继续讲z病人：仿佛任何事情都激不起我的兴致z医生：请更多地告诉我你的这种感觉z病人：我也有些知道为何我会这样感觉z医生：是吗z病人：我似乎在想有一个家z医生：什么东西使你有这样的想法z病人：它是一种挑战z医生：为什么那对你是重要的二、电脑能否实现人的智能？z机器zz体力z电脑zz计算速度和准确性z人脑zz思维z是否电脑能代替人脑实现智能？z一旦能够实现，这种被认为是特权的智能行为将受到挑战。二、电脑能否实现人的智能？二、电脑能否实现人的智能？二、电脑能否实现人的智能？l人真实地回答问题并试图说服质问者，他确实是人；l电脑被编好“说谎”的程序，试图说服质问者它是人。三、目前人工智能两个代表性的观点：三、目前人工智能两个代表性的观点：z爱因斯坦曾经将其比喻为“与上帝的对话”三、目前人工智能两个代表性的观点：三、目前人工智能两个代表性的观点：四、对人工智能领域有影响的理论与书籍 四、对人工智能领域有影响的理论与书籍z推荐网址zhttp:/ 四、对人工智能领域有影响的理论与书籍z镶嵌图案 埃舍尔的版画(1957)四、对人工智能领域有影响的理论与书籍问题求解逻辑推理与定理证明自然语言理解自动程序设计专家系统机器学习神经网络机器人学五、目前人工智能的研究与应用领域模式识别机器视觉智能控制智能检索智能调度与指挥分布式人工智能与Agent计算智能与进化智能数据挖掘与知识发现 六、计算机视觉中的困惑z这些与人类视觉活动相比，显得微不足道。z人类视觉中的视觉含义的把握以及主观经验在视觉中的作用，使机器不可能拥有的。六、计算机视觉中的困惑六、计算机视觉中的困惑 六、计算机视觉中的困惑六、计算机视觉中的困惑z著名的混沌理论“蝴蝶效应”：美国气象学家洛伦芝（Lorenz）于1960年代提出一篇论文，名叫一只蝴蝶拍一下翅膀会不会在德克萨斯州引起龙卷风？，他说，亚马逊流域的一只蝴蝶扇动翅膀，会掀起密西西比河流域的一场风暴。洛伦芝把这种现象戏称做蝴蝶效应，意思即一件表面上看来毫无关系、非常微小的事情，可能带来巨大的改变。六、计算机视觉中的困惑z眼睛和大脑的组合并不只具有“摄像机”般的功能。z虽然，人们对“视觉理解”发生的机制还不太清楚，但可以肯定其中含有非线性突变的因素，而且导致某种结果的因素是不确定的。（即蝴蝶效应）z“视觉理解”中抹不去的主观因素不可能通过确定的算法给出。七、展望z在计算机上要实现人的心智，充满困境。z要冲破这一困境，必须有理论性的突破：z大自然的机理+算法 七、展望z问题的解决不依赖于复杂的逻辑运算，而是利用装置本身的复杂性功能。七、展望z大自然的机理+算法z目前，在计算原理和模式方面出现了一些新的尝试：p生物计算p量子计算p光子计算p