第三章人工智能蔡自兴

《人工智能原理》第三章归结推理方法1第三章归结推理方法•概述•命题逻辑的归结法•谓词归结子句形•归结原理•归结过程的策略控制•Herbrand定理《人工智能原理》第三章归结推理方法2归结推理命题逻辑谓词逻辑Skolem标准形、子句集基本概念谓词逻辑归结原理合一和置换、控制策略数理逻辑命题逻辑归结Herbrand定理《人工智能原理》第三章归结推理方法3第三章归结推理方法•概述•命题逻辑的归结法•谓词归结子句形•归结原理•归结过程的策略控制《人工智能原理》第三章归结推理方法4概述•归结原理由J.A.Robinson由1965年提出。–是一阶逻辑中至今为止的最有效的半可判定的算法。即，一阶逻辑中任意恒真公式，使用归结原理，总可以在有限步内给以判定。–语义网络、框架表示、产生式规则等等都是以推理方法为前提的。即：有了规则已知条件，顺藤摸瓜找到结果。而归结方法是自动推理、自动推导证明用的。（“数学定理机器证明”）•本课程只讨论一阶谓词逻辑描述下的归结推理方法，不涉及高阶谓词逻辑问题。《人工智能原理》第三章归结推理方法5第三章归结推理方法•概述•命题逻辑的归结法•谓词归结子句形•归结原理•归结过程的策略控制•Herbrand定理《人工智能原理》第三章归结推理方法6命题逻辑的归结法•命题逻辑基础：定义：–合取式：p与q，记做pΛq–析取式：p或q，记做p∨q–蕴含式：如果p则q，记做p→q–等价式：p当且仅当q，记做p=q。。。。。。《人工智能原理》第三章归结推理方法7命题逻辑基础•定义：–若A无成假赋值，则称A为重言式或永真式；–若A无成真赋值，则称A为矛盾式或永假式；–若A至少有一个成真赋值，则称A为可满足的；–析取范式：仅由有限个简单合取式组成的析取式。–合取范式：仅由有限个简单析取式组成的合取式。《人工智能原理》第三章归结推理方法8命题逻辑基础•基本等值式–交换率：p∨q=q∨p；pΛq=qΛp–结合率：(p∨q)∨r=p∨(q∨r);(pΛq)Λr=pΛ(qΛr)–分配率：p∨(qΛr)=(p∨q)Λ(p∨r)；pΛ(q∨r)=(pΛq)∨(pΛr)《人工智能原理》第三章归结推理方法9命题逻辑基础•基本等值式–摩根率:～(p∨q)=～pΛ～q；～(pΛq)=～p∨～q–吸收率:p∨(pΛq)=p；pΛ(p∨q)=p–同一律:p∨0=p；pΛ1=p–蕴含等值式:p→q=～p∨q–假言易位式:p→q=～q→～p《人工智能原理》第三章归结推理方法10命题举例•命题：能判断真假（不是既真又假）的陈述句。简单陈述句描述事实、事物的状态、关系等性质。例如：1．1+1=22．雪是黑色的。3．北京是中国的首都。4．到冥王星去渡假。判断一个句子是否是命题，有先要看它是否是陈述句，而后看它的真值是否唯一。以上的例子都是陈述句，第4句的真值现在是假，随着人类科学的发展，有可能变成真，但不管怎样，真值是唯一的。因此，以上4个例子都是命题。而例如：1．快点走吧！2．到那去？3．x+y10等等句子，都不是命题。《人工智能原理》第三章归结推理方法11命题表示公式（1）将陈述句转化成命题公式。如：设“下雨”为p，“骑车上班”为q，，1．“只要不下雨，我骑自行车上班”。～p是q的充分条件，因而，可得命题公式：～p→q2．“只有不下雨，我才骑自行车上班”。～p是q的必要条件，因而，可得命题公式：q→～p《人工智能原理》第三章归结推理方法12命题表示公式（2）例如：•1．“如果我进城我就去看你，除非我很累。”设：p，我进城；q，去看你；r，我很累。则有命题公式：～r→(p→q)。•2．“应届高中生，得过数学或物理竞赛的一等奖，保送上北京大学。”设：p，应届高中生，q，保送上北京大学上学，r，是得过数学一等奖。t，是得过物理一等奖。则有命题公式公式：p∧(r∨t)→q。《人工智能原理》第三章归结推理方法13命题逻辑的推理规则附加：A=（A∨B)简化：(AΛB)=A假言推理:((A→B)ΛA)=B拒取式：((A→B)Λ～B)=～A析取三段论：((A∨B)Λ～A)=B假言三段论：((A→B)Λ(B→C))=(A→C)等价三段论：((A—B)Λ(B—C))=(A—C)构造性两难：((A→B)Λ(C→D)Λ（A∨C))=(B∨D)《人工智能原理》第三章归结推理方法14利用规则构造证明例：前提：p∨q,p→～r,s→t,～s→r,～t结论：q证明：①s→t前提引入②～t前提引入③～s①②拒取规则④～s→r前提引入⑤r③④⑥p→～r前提引入⑦～p⑤⑥拒取规则⑧p∨q前提引入⑨q⑦⑧析取三段论《人工智能原理》第三章归结推理方法15命题逻辑的归结法•基本单元：简单命题（陈述句）例：命题：A1、A2、A3和B求证：A1ΛA2ΛA3成立，则B成立，即：A1ΛA2ΛA3→B反证法：证明A1ΛA2ΛA3Λ～B是矛盾式（永假式）《人工智能原理》第三章归结推理方法16归谬法证明例：前提：p→（～（rΛs)→q),p,～s结论：q证明：①p→（～（rΛs)→q)前提引入②p前提引入③～（rΛs)→q①②假言推理④～q否定结论引入⑤（rΛs)③④拒取式⑥～s前提引入⑦s⑤简化⑧sΛ～s⑦⑥合取得到矛盾结果《人工智能原理》第三章归结推理方法17命题逻辑的归结法•归结原理是在谓词公式的子句集合之上进行归结的，因而首先讨论子句集。•建立子句集合取范式：命题、命题和的与，如：PΛ（P∨Q）Λ（～P∨Q）子句集S：合取范式形式下的子命题（元素）的集合例：命题公式：PΛ（P∨Q）Λ（～P∨Q）子句集S：S={P,P∨Q,～P∨Q}《人工智能原理》第三章归结推理方法18命题逻辑的归结法•归结式消除互补对，求新子句→得到归结式。如子句：C1,C2，归结式：R(C1,C2)=C1ΛC2注意：C1ΛC2→R(C1,C2)，反之不一定成立。《人工智能原理》第三章归结推理方法19命题逻辑的归结法•归结过程–将命题写成合取范式–求出子句集–对子句集使用归结推理规则–归结式作为新子句参加归结–归结式为空子句□，S是不可满足的（矛盾），原命题成立。�（证明完毕）•谓词的归结：除了有量词和函数以外，其余和命题归结过程一样。《人工智能原理》第三章归结推理方法20命题逻辑归结例题（1）•例题，证明公式：(P→Q)→(～Q→～P)•证明：（1）根据归结原理，将待证明公式转化成待归结命题公式：(P→Q)∧～(～Q→～P)（2）分别将公式前项化为合取范式：P→Q＝～P∨Q结论求～后的后项化为合取范式：～(～Q→～P)＝～(Q∨～P)＝～Q∧P两项合并后化为合取范式：（～P∨Q）∧～Q∧P（3）则子句集为：{～P∨Q，～Q，P}《人工智能原理》第三章归结推理方法21命题逻辑归结例题（2）子句集为：{～P∨Q，～Q，P}（4）对子句集中的子句进行归结可得：•1.～P∨Q•2.～Q•3.P•4.Q，（1，3归结）•5.，（2，4归结）由上可得原公式成立。《人工智能原理》第三章归结推理方法22第三章归结推理方法•概述•命题逻辑的归结法•谓词归结子句形•归结原理•归结过程的策略控制•Herbrand定理《人工智能原理》第三章归结推理方法23谓词归结原理基础一阶逻辑•基本概念–个体词：表示主语的词–谓词：刻画个体性质或个体之间关系的词–量词：表示数量的词《人工智能原理》第三章归结推理方法24谓词归结原理基础•小王是个工程师。•8是个自然数。•我去买花。•小丽和小华是朋友。其中，“小王”、“工程师”、“我”、“花”、“8”、“小丽”、“小华”都是个体词，而“是个工程师”、“是个自然数”、“去买”、“是朋友”都是谓词。显然前两个谓词表示的是事物的性质，第三个谓词“去买”表示的一个动作也表示了主、宾两个个体词的关系，最后一个谓词“是朋友”表示两个个体词之间的关系。《人工智能原理》第三章归结推理方法25谓词归结原理基础一阶逻辑•公式及其解释–个体常量：a,b,c–个体变量：x,y,z–谓词符号：P,Q,R–量词符号：,《人工智能原理》第三章归结推理方法26谓词归结原理基础•例如：（1）所有的人都是要死的。•（2）有的人活到一百岁以上。在个体域D为人类集合时，可符号化为：（1）xP(x)，其中P(x)表示x是要死的。（2）xQ(x),其中Q(x)表示x活到一百岁以上。在个体域D是全总个体域时，引入特殊谓词R(x)表示x是人，可符号化为：（1）x（R(x)→P(x)）,其中，R(x)表示x是人；P(x)表示x是要死的。（2）x（R(x)∧Q(x)），其中，R(x)表示x是人；Q(x)表示x活到一百岁以上。《人工智能原理》第三章归结推理方法27谓词归结原理基础量词否定等值式：–～(x）M（x）=（y）～M（y）–～(x）M（x）=（y）～M（y）量词分配等值式：–(x）(P（x）ΛQ（x）)=(x）P（x）Λ(x）Q（x）–(x）(P（x）∨Q（x）)=(x）P（x）∨(x）Q（x）消去量词等值式：设个体域为有穷集合（a1,a2,…an）–(x）P（x）=P（a1）ΛP（a2）Λ…ΛP（an）–(x）P（x）=P（a1）∨P（a2）∨…∨P（an）《人工智能原理》第三章归结推理方法28谓词归结原理基础量词辖域收缩与扩张等值式：–(x）(P（x）∨Q)=(x）P（x）∨Q–(x）(P（x）ΛQ)=(x）P（x）ΛQ–(x）(P（x）→Q)=(x）P（x）→Q–(x）(Q→P（x）)=Q→(x）P（x）–(x）(P（x）∨Q)=(x）P（x）∨Q–(x）(P（x）ΛQ)=(x）P（x）ΛQ–(x）(P（x）→Q)=(x）P（x）→Q–(x）(Q→P（x）)=Q→(x）P（x）《人工智能原理》第三章归结推理方法29谓词归结子句形(Skolem标准形)SKOLEM标准形–前束范式定义：说公式A是一个前束范式，如果A中的一切量词都位于该公式的最左边（不含否定词），且这些量词的辖域都延伸到公式的末端。《人工智能原理》第三章归结推理方法30谓词归结子句形(Skolem标准形)即：把所有的量词都提到前面去，然后消掉所有量词(Q1x1)(Q2x2)…(Qnxn)M(x1,x2,…,xn)约束变项换名规则：–(Qx）M（x）=（Qy）M（y）–(Qx）M（x,z）=（Qy）M（y,z）《人工智能原理》第三章归结推理方法31谓词归结子句形(Skolem标准形)–量词消去原则：消去存在量词“”，即将该量词约束的变量用任意常量（a,b）或任意变量函数(f(x)、g(y)）代替。略去任意量词“”。《人工智能原理》第三章归结推理方法32谓词归结子句形(Skolem标准形)–SKOLEM定理：谓词逻辑的任意公式都可以化为与之等价的前束范式，但其前束范式不唯一。–SKOLEM标准形定义：消去量词后的谓词公式。注意：谓词公式G的SKOLEM标准形同G并不等值。《人工智能原理》第三章归结推理方法33谓词归结子句形(Skolem标准形)例:将下式化为Skolem标准形：～(x)(y)P(a,x,y)→(x)(～(y)Q(y,b)→R(x))–解：第一步，消去→号，得：～(～(x)(y)P(a,x,y))∨(x)(～～(y)Q(y,b)∨R(x))–第二步，～深入到量词内部，得：(x)(y)P(a,x,y)∨(x)((y)Q(y,b)∨R(x))–第三步，变元易名，得(x)((y)P(a,x,y)∨(u)(v)(Q(v,b)∨R(u))–第四步，存在量词左移，直至所有的量词移到前面，得：(x)(y)(u)(v)P(a,x,y)∨(Q(v,b)∨R(u))由此得到前述范式《人工智能原理》第三章归结推理方法34谓词归结子句形(Skolem标准形)–第五步，消去“”（存在量词），略去“”任意量词消去(