归结推理方法.ppt

《归结推理方法.ppt》由会员分享，可在线阅读，更多相关《归结推理方法.ppt（148页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、归结推理方法归结推理方法现在学习的是第1页，共148页2归结归结推理推理命题命题逻辑逻辑谓词逻谓词逻辑辑Skolem标准形、标准形、子句集子句集基本基本概念概念谓词逻辑谓词逻辑归结原理归结原理合一和置换、合一和置换、控制策略控制策略数理数理逻辑逻辑命题逻辑命题逻辑归结归结Herbrand定理定理现在学习的是第2页，共148页3第三章第三章归结推理方法归结推理方法概述概述命题逻辑的归结法命题逻辑的归结法谓词归结子句形谓词归结子句形归结原理归结原理归结过程的策略控制归结过程的策略控制现在学习的是第3页，共148页4概述概述归结原理归结原理由由J.A.Robinson由由1965年提出。年提出。与演

2、绎法与演绎法(deductiveinference)完全不同完全不同,新的逻辑演算新的逻辑演算(inductiveinference)算法。算法。一阶逻辑中一阶逻辑中,至今为止的最有效的至今为止的最有效的半可判定半可判定的算法。即的算法。即,一阶逻辑中任意恒真公式一阶逻辑中任意恒真公式,使用归结原理使用归结原理,总可以在总可以在有限步有限步内给以判定。内给以判定。语义网络、框架表示、产生式规则等等都是以推理方法语义网络、框架表示、产生式规则等等都是以推理方法为前提的。即为前提的。即,有了规则已知条件有了规则已知条件,顺藤摸瓜找到结果。顺藤摸瓜找到结果。而归结方法是而归结方法是自动推理自动推理、

3、自动推导自动推导证明用的。证明用的。(“数学定数学定理机器证明理机器证明”)本课程只讨论一阶谓词逻辑描述下的归结推理方本课程只讨论一阶谓词逻辑描述下的归结推理方法法,不涉及高阶谓词逻辑问题。不涉及高阶谓词逻辑问题。现在学习的是第4页，共148页5第三章第三章归结推理方法归结推理方法概述概述命题逻辑的归结法命题逻辑的归结法谓词归结子句形谓词归结子句形归结原理归结原理归结过程的策略控制归结过程的策略控制Herbrand定理定理现在学习的是第5页，共148页6第三章第三章归结推理方法归结推理方法概述概述命题逻辑的归结法命题逻辑的归结法谓词归结子句形谓词归结子句形归结原理归结原理归结过程的策略控制归结

4、过程的策略控制Herbrand定理定理现在学习的是第6页，共148页7命题例命题例命题：命题：能能判断真假判断真假(不是既真又假不是既真又假)的的陈述句陈述句。简单陈述句描述事实、事物的状态、关系等性质。简单陈述句描述事实、事物的状态、关系等性质。例如：例如：1.1+1=22.雪是黑色的。雪是黑色的。3.北京是中国的首都。北京是中国的首都。4.我我到冥王星去渡假。到冥王星去渡假。现在学习的是第7页，共148页8命题例命题例判判断断一一个个句句子子是是否否是是命命题题,有有先先要要看看它它是是否否是是陈陈述述句句,而而后后看看它它的的真真值值是是否否唯唯一一。以以上上的的例例子子都都是是陈陈述述

5、句句,第第4句句的的真真值值现现在在是是假假,随随着着人人类类科科学学的的发发展展,有有可可能能变变成成真真,但但不不管管怎怎样样,真真值值是是唯唯一一的的。因因此此,以以上上4个例子都是命题。个例子都是命题。而例如：而例如：1.快点走吧！快点走吧！2.到那去？到那去？3.x+y10等等句子等等句子,都不是命题。都不是命题。现在学习的是第8页，共148页9命题逻辑的归结法命题逻辑的归结法命题逻辑基础：命题逻辑基础：定义：定义：合取式：合取式：p与与q,记做记做p q析取式：析取式：p或或q,记做记做p q蕴含式：蕴含式：如果如果p则则q,记做记做pq等价式：等价式：p当且仅当当且仅当q,记做记

6、做pq。现在学习的是第9页，共148页10命题表示公式命题表示公式(1)将陈述句转化成命题公式。将陈述句转化成命题公式。如：设如：设“下雨下雨”为为p,“骑车上班骑车上班”为为q,1.“只只要要不不下下雨雨,我我骑骑自自行行车车上上班班”。p是是q的充分条件的充分条件,因而因而,可得命题公式：可得命题公式：pq2.“只只有有不不下下雨雨,我我才才骑骑自自行行车车上上班班”。p是是q的必要条件的必要条件,因而因而,可得命题公式：可得命题公式：q p现在学习的是第10页，共148页11命题表示公式命题表示公式(2)例如：例如：1.“如果我进城我就去看你如果我进城我就去看你,除非我很累。除非我很累。

7、”设：设：p,我进城我进城,q,去看你去看你,r,我很累。我很累。则有命题公式：则有命题公式：r(pq)。2.“应应届届高高中中生生,得得过过数数学学或或物物理理竞竞赛赛的的一一等等奖奖,保保送上北京大学。送上北京大学。”设设：p,应应届届高高中中生生,q,保保送送上上北北京京大大学学上上学学,r,是是得得过过数数学一等奖。学一等奖。t,是得过物理一等奖。是得过物理一等奖。则有命题公式公式：则有命题公式公式：p(rt)q。现在学习的是第11页，共148页12命题逻辑基础命题逻辑基础定义：定义：若若A无成假赋值无成假赋值,则称则称A为为重言式重言式或永真式；或永真式；若若A无成真赋值无成真赋值,

8、则称则称A为为矛盾式矛盾式或永假式；或永假式；若若A至少有一个成真赋值至少有一个成真赋值,则称则称A为为可满足可满足的；的；析取范式：仅由有限个简单合取式组成的析取式。析取范式：仅由有限个简单合取式组成的析取式。合取范式：仅由有限个简单析取式组成的合取式。合取范式：仅由有限个简单析取式组成的合取式。现在学习的是第12页，共148页13命题逻辑基础命题逻辑基础基本等值式基本等值式24个个(1)交换律：交换律：p qq p；p qq p结合律：结合律：(p q)rp(q r);(p q)rp(q r)分配律：分配律：p(q r)(p q)(p r)；p(q r)(p q)(p r)现在学习的是第1

9、3页，共148页14命题逻辑基础命题逻辑基础基本等值式基本等值式(1)摩根律摩根律:(p q)p q；(p q)p q吸收律吸收律:p(p q)p；p(p q)p同一律同一律:p 0p；p 1p蕴含等值式蕴含等值式:pq p q假言易位式假言易位式:pq p q现在学习的是第14页，共148页15推理定律推理定律推理定律推理定律重言蕴涵式重言蕴涵式重要的推理定律重要的推理定律A(A B)附加律附加律(A B)A化简律化简律(AB)AB假言推理假言推理(AB)B A拒取式拒取式现在学习的是第15页，共148页16推理定律推理定律(A B)BA析取三段论析取三段论(AB)(BC)(AC)假言三段论

10、假言三段论(AB)(BC)(AC)等价三段论等价三段论(AB)(CD)(A C)(B D)构造性二难构造性二难(AB)(AB)(AA)B构造性二难构造性二难(特殊形式特殊形式)(AB)(CD)(BD)(AC)破坏性二难破坏性二难现在学习的是第16页，共148页17在自然推理系统在自然推理系统P中构造证明中构造证明1.直接证明法直接证明法例例用构造证明法构造下面推理的证明用构造证明法构造下面推理的证明:若明天是星期一或星期三若明天是星期一或星期三,我就有课我就有课.若有课若有课,今今天必备课天必备课.我今天下午没备课我今天下午没备课.所以所以,说明天是星说明天是星期一或星期三是不对的期一或星期三

11、是不对的.构造证明构造证明设设p:明天是星期一明天是星期一,q:明天是星期三明天是星期三,r:我有课我有课,s:我备课我备课形式结构形式结构前提前提:(p q)r,rs,s结论结论:pq现在学习的是第17页，共148页18证明证明rs前提引入前提引入 s前提引入前提引入 r拒取式拒取式(p q)r前提引入前提引入(p q)拒取式拒取式 pq置换置换现在学习的是第18页，共148页192.附加前提证明法附加前提证明法(1)欲证欲证:前提前提:A1,A2,Ak结论结论:CB(2)等价地证明等价地证明前提前提:A1,A2,Ak,C结论结论:B(3)理由理由:(A1 A2 Ak)(CB)(A1 A2

12、Ak)(C B)(A1 A2 Ak C)B(A1 A2 Ak C)B现在学习的是第19页，共148页20例例:构造下面推理的证明构造下面推理的证明2是素数或合数是素数或合数.若若2是素数是素数,则则21/2是无理数是无理数.若若21/2是无理数是无理数,则则4不是素数不是素数.所以所以,如果如果4是素数是素数,则则2是合数是合数.用附加前提证明法构造证明用附加前提证明法构造证明(1)设设p:2是素数是素数,q:2是合数是合数,r:21/2是无理数是无理数,s:4是素数是素数(2)形式结构形式结构前提前提:p q,pr,rs结论结论:sq现在学习的是第20页，共148页21(3)证明证明s附加前

13、提引入附加前提引入pr前提引入前提引入rs前提引入前提引入ps假言三段论假言三段论 p拒取式拒取式p q前提引入前提引入q析取三段论析取三段论现在学习的是第21页，共148页223.归谬法归谬法(或称反证法或称反证法)(1)欲证欲证A1 A2 AkB前提前提:A1,A2,Ak结论结论:B(2)将将 B当前提当前提,推出矛盾推出矛盾,得证得证(1)正确正确(3)理由理由A1 A2 AkB(A1 A2 Ak)B(A1 A2 AkB)括号内部为矛盾式当且仅当括号内部为矛盾式当且仅当(A1 A2 AkB)为重为重言式言式现在学习的是第22页，共148页23例例:前提前提:(p q)r,rs,s,p结论

14、结论:q证明证明(用归缪法用归缪法)q结论否定引入结论否定引入rs前提引入前提引入 s前提引入前提引入 r拒取式拒取式(p q)r前提引入前提引入(p q)析取三段论析取三段论 pq置换置换 p析取三段论析取三段论p前提引入前提引入 p p合取合取现在学习的是第23页，共148页24命题逻辑的归结法命题逻辑的归结法基本单元：简单命题基本单元：简单命题(陈述句陈述句)例：例：命题：命题：A1、A2、A3和和B求证：求证：A1 A2 A3成立成立,则则B成立成立,即：即：A1 A2 A3B反证法：证明反证法：证明A1 A2 A3 B是矛盾式是矛盾式(永假式永假式)现在学习的是第24页，共148页2

15、5命题逻辑的归结法命题逻辑的归结法建立子句集建立子句集n合取范式：命题、命题或的与合取范式：命题、命题或的与,如：如：P(PQ)(PQ)n子子句句集集S：合合取取范范式式形形式式下下的的子子命命题题(元元素素)的的集合集合例：命题公式：例：命题公式：P(PQ)(PQ)子句集子句集S：S=P,PQ,PQ现在学习的是第25页，共148页26命题逻辑的归结法命题逻辑的归结法归结式归结式消除互补文字对消除互补文字对,求新子句求新子句得到归结式得到归结式。如子句：如子句：C1=C1L,C2=C2L,归结式：归结式：R(C1,C2)=C1C2注意：注意：C1C2R(C1,C2),反之反之不一定不一定不一定

16、不一定成立。成立。现在学习的是第26页，共148页27命题逻辑的归结法命题逻辑的归结法归结过程归结过程将命题写成合取范式将命题写成合取范式求出子句集求出子句集对子句集使用归结推理规则对子句集使用归结推理规则归结式作为新子句参加归结归结式作为新子句参加归结归结式为空子句归结式为空子句,S是不可满足的是不可满足的(矛盾矛盾),原命题成立。原命题成立。(证明完毕证明完毕)谓词的归结：除了有量词和函数以外谓词的归结：除了有量词和函数以外,其余和命题其余和命题归结过程一样。归结过程一样。现在学习的是第27页，共148页28命题逻辑归结例题命题逻辑归结例题(1)例题例题,证明公式：证明公式：(PQ)(QP

17、)证明：证明：(1)根据归结原理根据归结原理,将待证明公式转化成待归结命题公式：将待证明公式转化成待归结命题公式：(PQ)(QP)(2)分别将公式前项化为合取范式：分别将公式前项化为合取范式：PQPQ结论求后的后项化为合取范式：结论求后的后项化为合取范式：(QP)(QP)QP两项合并后化为合取范式：两项合并后化为合取范式：(PQ)QP(3)则子句集为：则子句集为：PQ,Q,P现在学习的是第28页，共148页29命题逻辑归结例题命题逻辑归结例题(2)子句集为：子句集为：PQ,Q,P(4)对子句集中的子句进行归结可得：对子句集中的子句进行归结可得：1.PQ2.Q3.P4.Q,(1,3归结归结)5.

18、,(2,4归结归结)由上可得原公式成立。由上可得原公式成立。现在学习的是第29页，共148页30第三章第三章归结推理方法归结推理方法概述概述命题逻辑的归结法命题逻辑的归结法谓词归结子句形谓词归结子句形归结原理归结原理归结过程的策略控制归结过程的策略控制Herbrand定理定理现在学习的是第30页，共148页31第三章第三章归结推理方法归结推理方法概述概述命题逻辑的归结法命题逻辑的归结法谓词归结子句形谓词归结子句形归结原理归结原理归结过程的策略控制归结过程的策略控制Herbrand定理定理现在学习的是第31页，共148页32谓词归结原理基础谓词归结原理基础一阶逻辑一阶逻辑基本概念基本概念个体词：

19、表示主语的词个体词：表示主语的词谓词：刻画个体性质或个体之间关系的词谓词：刻画个体性质或个体之间关系的词量词：表示数量的词量词：表示数量的词现在学习的是第32页，共148页33谓词归结原理基础谓词归结原理基础小王是个工程师。小王是个工程师。8是个自然数。是个自然数。我去买花。我去买花。小丽和小华是朋友。小丽和小华是朋友。其其中中,“小小王王”、“工工程程师师”、“我我”、“花花”、“8”、“小小丽丽”、“小小华华”都都是是个个体体词词,而而“是是个个工工程程师师”、“是是个个自自然然数数”、“去去买买”、“是是朋朋友友”都都是是谓谓词词。显显然然前前两两个个谓谓词词表表示示的的是是事事物物的的

20、性性质质,第第三三个个谓谓词词“去去买买”表表示示的的一一个个动动作作也也表表示示了了主主、宾宾两两个个个个体体词词的的关关系系,最最后后一一个个谓谓词词“是是朋朋友友”表表示示两两个个体词之间的关系。个个体词之间的关系。现在学习的是第33页，共148页34谓词归结原理基础谓词归结原理基础一阶逻辑一阶逻辑公式及其解释公式及其解释个体常量：个体常量：a,b,c个体变量：个体变量：x,y,z谓词符号：谓词符号：P,Q,R量词符号：量词符号：,现在学习的是第34页，共148页35谓词归结原理基础谓词归结原理基础例如：例如：(1)所有的人都是要死的。所有的人都是要死的。(2)有的人活到一百岁以上。有的

21、人活到一百岁以上。在个体域在个体域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活到一百岁以上。活到一百岁以上。现在学习的是第35页，共1

22、48页36谓词归结原理基础谓词归结原理基础量词否定等值式：量词否定等值式：(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)现在学习的是第36页，共148页37一阶一阶(firstorder)逻辑的合式公式逻辑的合式公式项项原子公式原子公式合式公式合式公式现在学习的是第37页，共1

23、48页38项项(term)个体常项和个体变项是项个体常项和个体变项是项若若(x1,x2,xn)是是n元函数元函数,t1,t2,tn是项是项,则则(t1,t2,tn)是项是项所有的项都是有限次地应用上述规则形所有的项都是有限次地应用上述规则形成的成的例如例如:a,x,f(a),g(a,x),g(x,f(a)现在学习的是第38页，共148页39原子公式原子公式(atomicformula)若若R(x1,x2,xn)是是n元谓词元谓词,t1,t2,tn是项是项,则则R(t1,t2,tn)是原子公式是原子公式例如例如:F(a),G(a,y),F(f(a),G(x,g(a,y)现在学习的是第39页，共1

24、48页40合式公式合式公式(well-formedformula)原子公式是合式公式原子公式是合式公式若若A是合式公式是合式公式,则则(A)是合式公式是合式公式若若A,B是合式公式是合式公式,则则(AB),(AB),(AB),(AB)也是合式公式也是合式公式若若A是合式公式是合式公式,则则 xA,xA也是合式也是合式公式公式只有有限次地应用上述规则形成的符号只有有限次地应用上述规则形成的符号串才是合式公式串才是合式公式现在学习的是第40页，共148页41合式公式合式公式(举例举例)x(F(x)y(G(y)H(x,y)F(f(a,a),b)约定：省略多余括号约定：省略多余括号最外层最外层优先级递

25、减：优先级递减：,;,;,现在学习的是第41页，共148页42合式公式中的变项合式公式中的变项量词辖域量词辖域:在在 xA,xA中中,A是量词的辖域是量词的辖域.例如例如:x(F(x)y(G(y)H(x,y)指导变项指导变项:紧跟在量词后面的个体变项紧跟在量词后面的个体变项.例如例如:x(F(x)y(G(y)H(x,y)约束出现约束出现:在辖域中与指导变项同名的变项在辖域中与指导变项同名的变项.例如例如:x(F(x)y(G(y)H(x,y)自由出现自由出现:既非指导变项又非约束出现既非指导变项又非约束出现.例如例如:y(G(y)H(x,y)现在学习的是第42页，共148页43合式公式中的变项合

26、式公式中的变项(举例举例)H(x,y)xF(x)y(G(y)H(x,y)x与与y是指导变项是指导变项x与与y是约束出现是约束出现x与与y是自由出现是自由出现现在学习的是第43页，共148页44换名换名(rename)规则规则把某个把某个指导变项指导变项和其量词辖域中所有同和其量词辖域中所有同名的名的约束出现约束出现,都换成某个新的个体变都换成某个新的个体变项符号项符号.例如例如:x(A(x)B(x)y(A(y)B(y)xA(x)xB(x)yA(y)zB(z)H(x,y)xF(x)y(G(y)H(x,y)H(x,y)zF(z)u(G(u)H(x,u)现在学习的是第44页，共148页45代替代替(

27、substitute)规则规则把某个把某个自由变项自由变项的所有出现的所有出现,都换成某都换成某个新的个体变项符号个新的个体变项符号.例如例如:A(x)B(x)A(y)B(y)xA(x)B(x)xA(x)B(y)H(x,y)xF(x)y(G(y)H(x,y)H(s,t)xF(x)y(G(y)H(s,y)现在学习的是第45页，共148页46解释解释(interpret)对一个合式公式的对一个合式公式的解释解释包括给出包括给出个体域个体域谓词谓词函数函数个体常项个体常项的具体含义的具体含义现在学习的是第46页，共148页47解释解释(举例举例)F(f(a,a),b)解释解释1：个体域是全体自然数个

28、体域是全体自然数;a:2;b:4;f(x,y)=x+y;F(x,y):x=y原公式解释成原公式解释成:“2+2=4”。解释解释2：个体域是全体实数个体域是全体实数;a:3;b:5;f(x,y)=x-y;F(x,y):xy原公式解释成原公式解释成:“3-35”。现在学习的是第47页，共148页48谓词归结原理基础谓词归结原理基础量词分配等值式量词分配等值式 x(A(x)B(x)xA(x)xB(x)x(A(x)B(x)xA(x)xB(x)注意注意:对对 无分配律无分配律,对对 无分配律无分配律现在学习的是第48页，共148页49量词分配量词分配(反例反例)x(A(x)B(x)xA(x)xB(x)x

29、(A(x)B(x)xA(x)xB(x)个体域为全体自然数个体域为全体自然数;A(x):x是偶数是偶数B(x):x是奇数是奇数;左左1,右右0 x(A(x)B(x)xA(x)xB(x)x(A(x)B(x)xA(x)xB(x)个体域为全体自然数个体域为全体自然数;A(x):x是偶数是偶数B(x):x是奇数是奇数;左左0,右右1现在学习的是第49页，共148页50谓词归结原理基础谓词归结原理基础量词辖域收缩与扩张等值式：量词辖域收缩与扩张等值式：(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)(QP(x)Q(x)P(x)(x)(P(x

30、)Q)(x)P(x)Q(x)(P(x)Q)(x)P(x)Q(x)(P(x)Q)(x)P(x)Q(x)(QP(x)Q(x)P(x)现在学习的是第50页，共148页51前束范式前束范式前束范式与公式的前束范式前束范式与公式的前束范式1.前束范式前束范式定义定义设设A为一个一阶逻辑公式为一个一阶逻辑公式,若若A具有如下形式具有如下形式Q1x1Q2x2QkxkB则称则称A为为前束范式前束范式,其中其中Qi(1 i k)为为 或或,B为不含量词的公为不含量词的公式式.例如例如,x(F(x)y(G(y)H(x,y)不是前束范式不是前束范式,x y(F(x)(G(y)H(x,y)是前束范式是前束范式.又如又

31、如,x(F(x)G(x)不是前束范式不是前束范式,x(F(x)G(x)是前束范式是前束范式.现在学习的是第51页，共148页522.公式的前束范式公式的前束范式定理定理(前束范式存在定理前束范式存在定理)一阶逻辑中的任何公一阶逻辑中的任何公式都存在与之等值的前束范式式都存在与之等值的前束范式(不惟一不惟一)3.如何求公式的前束范式如何求公式的前束范式利用重要等值式、置换规则、换名规则、代替利用重要等值式、置换规则、换名规则、代替规则进行等值演算规则进行等值演算现在学习的是第52页，共148页53例例求下列公式的前束范式求下列公式的前束范式(1)x(M(x)F(x)(2)xF(x)xG(x)(3

32、)xF(x)xG(x)(4)xF(x)y(G(x,y)H(y)(5)x(F(x,y)y(G(x,y)H(x,z)解解(1)x(M(x)F(x)x(M(x)F(x)(量词否定等值式量词否定等值式)x(M(x)F(x)两步结果都是前束范式两步结果都是前束范式,说明不惟一性说明不惟一性.现在学习的是第53页，共148页54(2)xF(x)xG(x)xF(x)x G(x)(量词否定等值式量词否定等值式)x(F(x)G(x)(量词分配等值式量词分配等值式)另有一种形式另有一种形式 xF(x)xG(x)xF(x)x G(x)xF(x)y G(y)x y(F(x)G(y)两种形式是等值的两种形式是等值的现在

33、学习的是第54页，共148页55(3)xF(x)xG(x)xF(x)x G(x)x(F(x)G(x)(为什么？为什么？)或或 x y(F(x)G(y)(为什么？为什么？)现在学习的是第55页，共148页56(4)xF(x)y(G(x,y)H(y)zF(z)y(G(x,y)H(y)(换名规则换名规则)z y(F(z)(G(x,y)H(y)(为什么为什么?)或或 xF(x)y(G(z,y)H(y)(代替规则代替规则)x y(F(x)(G(z,y)H(y)现在学习的是第56页，共148页57(5)可用换名规则可用换名规则,也可用代替规则也可用代替规则,这里用这里用代替规则代替规则 x(F(x,y)y

34、(G(x,y)H(x,z)x(F(x,u)y(G(x,y)H(x,z)x y(F(x,u)G(x,y)H(x,z)注意注意:x与与 y不能颠倒不能颠倒现在学习的是第57页，共148页58谓词推理谓词推理(举例举例)前提前提:x(F(x)G(x),F(a)结论结论:G(a)证明证明:(1)F(a)前提引入前提引入(2)x(F(x)G(x)前提引入前提引入(3)F(a)G(a)(2)UI(4)G(a)(1)(3)假言推理假言推理现在学习的是第58页，共148页59谓词归结子句形谓词归结子句形(Skolem标准形标准形)SKOLEM标准形标准形前束范式前束范式说公式说公式A是一个是一个前束范式前束范

35、式,如果如果A中的一切量中的一切量词都位于该公式的最左边词都位于该公式的最左边(不含否定词不含否定词),且这且这些量词的辖域都延伸到公式的末端。些量词的辖域都延伸到公式的末端。现在学习的是第59页，共148页60谓词归结子句形谓词归结子句形(Skolem标准形标准形)即：即：把所有的量词都提到前面去把所有的量词都提到前面去,然后消然后消掉所有量词掉所有量词(Q1x1)(Q2x2)(Qnxn)M(x1,x2,xn)约束变项换名规则：约束变项换名规则：(Qx)M(x)(Qy)M(y)(Qx)M(x,z)(Qy)M(y,z)现在学习的是第60页，共148页61谓词归结子句形谓词归结子句形(Skole

36、m标准形标准形)量词消去原则：量词消去原则：消去存在量词消去存在量词“”,略去全程量词略去全程量词“”。注意：注意：左边有全程量词的存在量词左边有全程量词的存在量词,消去消去时该变量改写成为全程量词的函数；如时该变量改写成为全程量词的函数；如没有没有,改写成为常量。改写成为常量。现在学习的是第61页，共148页62谓词归结子句形谓词归结子句形(Skolem标准形标准形)Skolem定理定理：谓词逻辑的任意公式都可以化为与之等价的谓词逻辑的任意公式都可以化为与之等价的前束范式前束范式,但其但其前束范式不唯一前束范式不唯一。SKOLEM标准形定义：标准形定义：消去量词后的谓词公式。消去量词后的谓词

37、公式。注意注意：谓词公式谓词公式G的的SKOLEM标准形同标准形同G并不等值并不等值。现在学习的是第62页，共148页63谓词归结子句形谓词归结子句形(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)(x)(y)(Q(y,b)R(x)现在学习的是第63页，共148

38、页64谓词归结子句形谓词归结子句形(Skolem标准形标准形)第三步第三步,任意量词左移任意量词左移(分配律分配律),变元易名变元易名,得得(x)(y)P(a,x,y)(z)(Q(z,b)R(x)第第四四步步,存存在在量量词词左左移移,直直至至所所有有的的量量词词移移到到前面前面,得：得：(x)(y)(z)P(a,x,y)Q(z,b)R(x)由此得到前束范式由此得到前束范式现在学习的是第64页，共148页65谓词归结子句形谓词归结子句形(Skolem标准形标准形)第第五五步步,消消去去“”(存存在在量量词词),略略去去“”全全称称量量词词消消去去(y),因因为为它它左左边边只只有有(x),所以

39、使用所以使用x的函数的函数f(x)代替之代替之,这样得到：这样得到：(x)(z)(P(a,x,f(x)Q(z,b)R(x)消去消去(z),同理使用同理使用g(x)代替之代替之,这样得到：这样得到：(x)(P(a,x,f(x)Q(g(x),b)R(x)则则,略去全称变量略去全称变量,原式的原式的Skolem标准形为：标准形为：P(a,x,f(x)Q(g(x),b)R(x)现在学习的是第65页，共148页66谓词归结子句形谓词归结子句形子句与子句集子句与子句集文字：不含任何连接词的谓词公式。文字：不含任何连接词的谓词公式。子句：一些文字的析取子句：一些文字的析取(谓词的和谓词的和)。子句集子句集S

40、的求取：的求取：GSKOLEM标准形标准形消去存在变量消去存在变量以以“,”取代取代“”,并表示为集合形式并表示为集合形式。现在学习的是第66页，共148页67谓词归结子句形谓词归结子句形G是不可满足的是不可满足的S是不可满足的是不可满足的G与与S不等价不等价,但但在不可满足得意义下是一致在不可满足得意义下是一致的的。定理：定理：若若G是给定的公式是给定的公式,而而S是相应的子句集是相应的子句集,则则G是不可满足的是不可满足的S是不可满足的。是不可满足的。注意注意：G真不一定真不一定S真真,而而S真必有真必有G真。真。即：即：SG现在学习的是第67页，共148页68谓词归结子句形谓词归结子句形

41、G=G1G2G3Gn的子句形的子句形G的字句集可以分解成几个单独处理。的字句集可以分解成几个单独处理。有有SG=S1US2US3UUSn则则SG与与S1US2US3UUSn在在不不可可满满足足得得意义上是一致的。意义上是一致的。即即SG不不可可满满足足S1US2US3UUSn不不可可满足满足现在学习的是第68页，共148页69求取子句集例求取子句集例(1)例例：对对所所有有的的x,y,z来来说说,如如果果y是是x的的父父亲亲,z又又是是y的的父父亲亲,则则z是是x的的祖祖父父。又又知知每每个个人人都都有有父父亲亲,试试问问对对某个人来说谁是它的祖父？某个人来说谁是它的祖父？求：用一阶逻辑表示这

42、个问题求：用一阶逻辑表示这个问题,并建立子句集。并建立子句集。解：这里我们首先引入谓词：解：这里我们首先引入谓词：P(x,y)表示表示x是是y的父亲的父亲Q(x,y)表示表示x是是y的祖父的祖父ANS(x)表示问题的解答表示问题的解答现在学习的是第69页，共148页70求取子句集例求取子句集例(2)对于第一个条件对于第一个条件,“如果如果x是是y的父亲的父亲,y又是又是z的的父亲父亲,则则x是是z的祖父的祖父”,一阶逻辑表达式如下：一阶逻辑表达式如下：A1：(x)(y)(z)(P(x,y)P(y,z)Q(x,z)SA1：P(x,y)P(y,z)Q(x,z)对于第二个条件：对于第二个条件：“每个

43、人都有父亲每个人都有父亲”,一阶一阶逻辑表达式：逻辑表达式：A2：(y)(x)P(x,y)SA2：P(f(y),y)现在学习的是第70页，共148页71求取子句集例求取子句集例(2)对于结论：某个人是它的祖父对于结论：某个人是它的祖父B：(x)(y)Q(x,y)否定后得到子句：否定后得到子句：(x)(y)Q(x,y)ANS(x)SB：Q(x,y)ANS(x)则得到的相应的子句集为：则得到的相应的子句集为：SA1,SA2,SB现在学习的是第71页，共148页72第三章第三章归结推理方法归结推理方法概述概述命题逻辑的归结法命题逻辑的归结法谓词归结子句形谓词归结子句形归结原理归结原理归结过程的策略控

44、制归结过程的策略控制Herbrand定理定理现在学习的是第72页，共148页73第三章第三章归结推理方法归结推理方法概述概述命题逻辑的归结法命题逻辑的归结法谓词归结子句形谓词归结子句形归结原理归结原理归结过程的策略控制归结过程的策略控制Herbrand定理定理现在学习的是第73页，共148页74归结原理归结原理归结原理正确性的根本在于归结原理正确性的根本在于,找到矛盾找到矛盾可以肯定不真。可以肯定不真。方法：方法：和命题逻辑一样。和命题逻辑一样。但由于有函数但由于有函数,所以要考虑所以要考虑合一合一和和置换置换。现在学习的是第74页，共148页75置换置换置换：置换：可以简单的理解为是在一个谓

45、词公式中用置换项去置换变量。可以简单的理解为是在一个谓词公式中用置换项去置换变量。定义：定义：置置换换是是形形如如t1/x1,t2/x2,tn/xn的的有有限限集集合合。其其中中,x1,x2,xn是是互互不不相相同同的的变变量量,t1,t2,tn是是不不同同于于xi的的项项(常常量量、变变量量、函函数数)；ti/xi表表示示用用ti置置换换xi,并并且且要要求求ti与与xi不不能相同能相同,而且而且xi不能循环地出现在另一个不能循环地出现在另一个ti中。中。例如例如a/x,c/y,f(b)/z是一个置换。是一个置换。g(y)/x,f(x)/y不是一个置换不是一个置换,现在学习的是第75页，共1

46、48页76置换的合成置换的合成设设 t1/x1,t2/x2,tn/xn,u1/y1,u2/y2,un/yn,是两个置换。是两个置换。则则 与与 的合成也是一个置换的合成也是一个置换,记作记作 。它是从集合。它是从集合t1/x1,t2/x2,tn/xn,u1/y1,u2/y2,un/yn中删去以下两种元素：中删去以下两种元素：当当ti=xi时时,删去删去ti/xi(i=1,2,n);当当yi x1,x2,xn时时,删去删去uj/yj(j=1,2,m)最后剩下的元素所构成的集合。最后剩下的元素所构成的集合。合成即是对合成即是对ti先做先做 置换然后再做置换然后再做 置换置换,置换置换xi现在学习的

47、是第76页，共148页77置换的合成置换的合成例：例：设：设：f(y)/x,z/y,a/x,b/y,y/z,求求 与与 的合成。的合成。解：先求出集合解：先求出集合f(b/y)/x,(y/z)/y,a/x,b/y,y/zf(b)/x,y/y,a/x,b/y,y/z其其中中,f(b)/x中中的的f(b)是是置置换换 作作用用于于f(y)的的结结果果；y/y中中的的y是是置置换换 作作用用于于z的的结结果果。在在该该集集合合中中,y/y满满足足定定义义中中的的条条件件i,需需要要删删除除；a/x,b/y满满足足定定义义中中的的条条件件ii,也也需需要要删删除除。最后得最后得 f(b)/x,y/z现

48、在学习的是第77页，共148页78合一合一合合一一可可以以简简单单地地理理解解为为“寻寻找找相相对对变变量量的的置置换换,使使两两个谓词公式一致个谓词公式一致”。定定义义：设设有有公公式式集集FF1,F2,Fn,若若存存在在一一个个置置换换,可可使使F1 F2=Fn,则则称称 是是F的的一一个个合合一一。同同时时称称F1,F2,.,Fn是可合一的。是可合一的。例：例：设设有有公公式式集集FP(x,y,f(y),P(a,g(x),z),则则 a/x,g(a)/y,f(g(a)/z是它的一个合一。是它的一个合一。注意：一般说来注意：一般说来,一个公式集的合一不是唯一的。一个公式集的合一不是唯一的。

49、现在学习的是第78页，共148页79归结原理归结原理归结的注意事项：归结的注意事项：1.谓词的一致性谓词的一致性,P()与与Q(),不可以不可以2.常量的一致性常量的一致性,P(a,)与与P(b,.),不可以不可以变量变量,P(a,.)与与P(x,),可以可以3.变量与函数变量与函数,P(a,x,.)与与P(x,f(x),),不可以；不可以；4.是不能同时消去两个互补对是不能同时消去两个互补对,PQ与与PQ的空的空,不可以不可以5.先进行内部简化先进行内部简化(置换、合并置换、合并)现在学习的是第79页，共148页80归结原理归结原理归结的过程归结的过程写出谓词关系公式写出谓词关系公式用反演法

50、写出谓词表达式用反演法写出谓词表达式SKOLEM标准形标准形子句集子句集S对对S中可归结的子句做归结中可归结的子句做归结归结式仍放入归结式仍放入S中中,反复归结过程反复归结过程得到空子句得到空子句命题得证命题得证现在学习的是第80页，共148页81例题例题“快乐学生快乐学生”问题问题假假设设任任何何通通过过计计算算机机考考试试并并获获奖奖的的人人都都是是快快乐乐的的,任任何何肯肯学学习习或或幸幸运运的的人人都都可可以以通通过过所所有有的的考考试试,张张不不肯肯学学习习但但他他是是幸幸运运的的,任任何何幸幸运运的的人人都都能能获获奖奖。求证：张是快乐的。求证：张是快乐的。解：先将问题用谓词表示如