人工智能谓词演算.pptx

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,单击此处编辑母版标题样式,第2讲 基于谓词逻辑机器推理,一阶谓词逻辑,归结演绎推理,归结原理应用,Horn,子句与,Prolog,程序设计,1,人工智能谓词演算,第1页,第一节 一阶谓词逻辑,命题：凡可确定真假陈说句称为命题,能够取值“真”（,T）,或“假”（,F）,在一定条件下，只能取其中一个值,例：,（1）北京是中国首都,（2）3+2 10,（3）1+11=100（依据制数）,（4）禁止吸烟 （祈使句）,（5）本命题是假 （悖论）,2,人工智能谓词演算,第2页,谓词：是用来刻画个体词性质或个体词之间关系词（带参量命题叫谓词）,n,元谓词，,P（x,1,x,2,x,3,x,n,）,P,是谓词符号，代表一个确定特征（一个参量）或关系（多个参量）,x,1,x,2,x,3,x,n,称为参量或项（个体常元或个体变元）,叙述域（个体域）：个体变元取值范围,例：,北京是一个城市,CITY（,北京）,x,是人,HUMAN（x）,A,是,B,弟兄 弟兄（,A，B）,x,大于,y G（x，y）,不带个体变元谓词公式叫命题，命题是谓词公式特例,3,人工智能谓词演算,第3页,逻辑连接词：研究单个谓词是不够，还必须研究多个谓词之间关系，这需要引入逻辑连接词,：否定词,A,读为“非,A”，,当,A,为真时，,A,为假，当,A,为假时，,A,为真,：,合取词,A B,读为“,A,而且,B”，,当且仅当,A,和,B,都为真时，,A B,为真，不然,A B,为假,：,析取词,A B,读为“,A,或者,B”，,当且仅当,A,和,B,都为假时，,A B,为假，不然,A B,为真,4,人工智能谓词演算,第4页,：,蕴涵词,A B,读为“若,A,则,B”，,当且仅当,A,为真，且,B,为假时，,A B,为假，不然,A B,为真,在,A B,中，,A,称为前件，,B,称为后件,：等值词,A,B,读为“,A,等值于,B”，,当且仅当,A,和,B,同为真或同为假时，,A,B,为真，不然,A,B,为假,5,人工智能谓词演算,第5页,量词：有些陈说句包含表示数量词，如“全部”、“任一”、“存在”、“最少有一个”等，为了表示这么陈说句，需引入新符号，称为量词,全称量词,（,x）,表示“对于全部,x ”,例：,凡是人都有名字 （,x）（M（x）N（x）,（,x）A（x）,A（a,1,）A（a,2,）A（a,n,），,若论域为有限集合，且,a,1、,a,2、,、,a,n,是论域中全部个体,存在量词,（,x）,表示“对于某个,x ”,例：,存在不是偶数整数 （,x）（G（x）,E（x）,（,x）A（x）,A（a,1,）A（a,2,）A（a,n,）,例：见,P56,例13,6,人工智能谓词演算,第6页,项：（,P64,定义1）,（1）个体常元和个体变元都是项,（2）,f(t,1,t,2,t,n,),是项，,f,是,n,元函数，,t,1,t,2,t,n,是项,（3）只有有限次使用（1）、（2）得到符号串才是项,原子公式：（,P64,定义2）,设,P,为,n,元谓词符号，,t,1,t,2,t,n,是项，则,P（t,1,t,2,t,n,）,称为原子谓词公式，简称原子公式,7,人工智能谓词演算,第7页,谓词公式：（,P56,定义3）,（1）原子公式是谓词公式,（2）若,A、B,是谓词公式，则,AB、AB、,A、AB、A,B、,x A、,x A,也是谓词公式,（3）只有有限次应用（1）、（2）生成公式才是谓词公式,谓词公式又称为谓词逻辑中合式公式，记为,Wff(well-formed formula),几个概念：,辖域（,P57）：,紧接于量词之后被量词作用（说明）谓词公式称为该量词辖域,指导变元、约束变元和自由变元（,P57）,更名规则（,P57），,确保一个变元或者是约束变元，或者是自由变元,例：,x（H（x）G（x,y）,x A（x）B（x）,8,人工智能谓词演算,第8页,合取范式：（,P58,定义4）,A,为合取范式，,B,1,B,2,B,n,其中,B,i,形如,L,1,L,2,L,m,L,j,为原子公式或其否定,例,：（,P（x）,Q（y）,（,P（x）,Q（y）,R（x，y）,任一谓词公式均可化为与之等价合取范式，但普通不唯一,析取范式：（,P66,定义5）,A,为析取范式，,B,1,B,2,B,n,其中,B,i,形如,L,1,L,2,L,m,L,j,为原子公式或其否定,例,：（,P（x）,Q（y）,（,P（x）,Q（y）,R（x，y）,任一谓词公式均可化为与之等价析取范式，但普通不唯一,9,人工智能谓词演算,第9页,谓词公式永真（有效）、永假（不可满足）、可满足：（,P58,定义6、7）,与个体域相关,谓词公式之间关系,惯用逻辑等价式,P59,表3.1,注意,与区分，是等价符号，说明两个谓词公式之间等价性，是逻辑连接词，是谓词公式组成部分,惯用逻辑蕴涵式,P60,表3.2,注意,与区分，是推导符号，说明由左边谓词公式能够推导出右边谓词公式，是逻辑连接词，是谓词公式组成部分,10,人工智能谓词演算,第10页,自然演绎推理：,（1）将自然语言命题转化为谓词公式,（2）利用上面逻辑等价式和逻辑蕴涵式，能够进行推理，得出一些隐含在谓词公式中结论,例：,P61,例4-6,自然演绎推理实施困难，推理规则太多、应用规则需要很强模式识别能力、中间结论呈指数增加,引入新推理技术归结演绎推理技术,归结消解（,Resolution），,由,Robinson,于1965年提出，大大推进了自动定理证实发展,11,人工智能谓词演算,第11页,练习：,1、设已知以下事实：,A,B,AC,BCD,DQ,求证：,Q,为真。,12,人工智能谓词演算,第12页,证实：,因为,A，AC,C,B，C,B,C,BC，BCD,D,D，DQ,Q,所以,Q,为真,13,人工智能谓词演算,第13页,2、设已知以下事实：,（1）凡是轻易课程小王都喜欢。,（2）,C,班课程都是轻易。,（3）,ds,是,C,班一门课程。,求证：小王喜欢,ds,这门课程。,14,人工智能谓词演算,第14页,证实：事实,x（,EASY（x）LIKE（Wang，x）,x（C（x）EASY（x）,C（ds）,LIKE（Wang，ds）,因为,x（C（x）EASY（x）,所以,C（ds）EASY（ds）,所以,C（ds），C（ds）EASY（ds）,EASY（ds）,因为,x（EASY（x）LIKE（Wang，x）,所以,EASY（ds）LIKE（Wang，ds）,所以,EASY（ds），EASY（ds）LIKE（Wang，ds）,LIKE（Wang，ds）,15,人工智能谓词演算,第15页,第二节 归结演绎推理,建立子句集,文字、子句、空子句 （,P62,定义1）,建立谓词公式,G,子句集合 （,P62,定义2）,例：,P62,例3.7,例：,P63,例2 相关消去存在量词,子句集中各子句关系是 合取,经过变换后子句集,S，,与谓词公式,G,并不等价,子句集不可满足（,P64,定义3）,G,不可满足当且仅当,S,不可满足（,P64,定理1），即,G,永假是,S,永假充分必要条件,16,人工智能谓词演算,第16页,练习：,P93 1、,（1）p(x,y),Q(u,v),（2）,p(x,y)Q(x,y),（3）P(x,f(x),Q(x,f(x)R(x,f(x),（4）,P(x,z)Q(x,y)R(x,y),（5）P(a,b,z,f(z),v,g(z,v),Q(a,b,f(t),s,g(t,s),R(a,t,g(t,s),17,人工智能谓词演算,第17页,命题逻辑中归结原理,在定理证实系统中，已知一公式集,F,1,，F,2,，F,n,，,要证实,W（,定理）是否成立，即要证实,W,是公式集逻辑结果，有两种方法：,1、证实,F,1,F,2,F,n,W,为永真式（见上一节）,2、（反证法）证实,F,1,F,2,F,n,W,永假，即要证实对应子句集永假（不可满足）,几个概念：（,P64,定义4、5）互补文字、归结式（消解式）、亲本子句、消解基,例：例3.9,归结式是其亲本子句逻辑结果,P64,定理2,单向推导关系,18,人工智能谓词演算,第18页,归结原理：,C1 C2,（C1-L1）（C2-L2）,互补文字进行归结得空子句（,L,L=,），,另,L,L=F（,假），故空子句即永假子句,关于消解前后子句集可满足性,P65,推论 （证实略）,故：要证实一子句集永假，能够经过对子句集应用消解原理得到空子句来证实,利用归结原理证实定理例子：,P65,例11、12,*归结过程能够用一棵,归结演绎树,表示,19,人工智能谓词演算,第19页,替换与合一,为了对谓词逻辑子句集利用消解原理，即在子句集合中寻找含互补文字子句对，必须对子句进行替换合一操作,替换：,P66,定义6 ,t,1,/x,1,，t,2,/x,2,，t,n,/x,n,对表示式替换过程,P66,定义7,表示式 项、原子公式、文字、子句,两个替换乘积,P66-67,定义8,一部分仍是,替换对，只是,项被,作了替换；另一部分是,中与,不一样那些变量对,例：例3.13,替换乘积满足结合律,20,人工智能谓词演算,第20页,合一：,P67,定义9,是,S,一个合一,其中,S,是一个原子谓词公式集，,是一个替换,满足,F,1,=F,2,=F,n,一个公式集合一普通不唯一,最普通合一：,P67,定义10,是,S,一个合一,对于,S,任何一个合一,，,存在替换,，,使,=,称,为,S,最普通（最普通、最简单）合一,MGU,例：例3.14,MGU,替换限制最少，所产生例更普通化，这有利于归结过程灵活使用,一个公式集最普通合一也可不唯一，如,P（x），P（y），y/x、,x/y,都是它最普通合一,21,人工智能谓词演算,第21页,差异集：,P67,定义11,针对含有相同谓词名原子公式集,例：例3.15,合一算法：求非空有限含有相同谓词名原子公式集最普通合一,P67-68,合一算法是处理两个表示式匹配问题，两个表示式都能够含有变量，经过算法求得,MGU,并进行替换后就能够得到匹配例,例：例16、17,合一定理：,P68-69,定理3,可合一公式集一定存在最普通合一，用上述合一算法求得,22,人工智能谓词演算,第22页,谓词逻辑中归结原理,归结过程：,若,S,中两子句间有相同互补文字谓词，但它们项不一样，则必须找出对应不一致项,进行变量替换合一操作，使它们对应项一致,求归结式看能否导出空子句,几个概念：（,P69,定义12）谓词逻辑中二元归结式（二元消解式）、亲本子句、消解文字,例：例18、19,子句用文字集合表示，各文字之间关系是 析取,首先对子句内部可合一文字进行合一,23,人工智能谓词演算,第23页,因子、单因子 （,P69,定义13）,例：例14,子句归结（消解）式 （,P69,定义14）,定理：谓词逻辑中消解式是它亲本子句逻辑结果,谓词逻辑中归结原理：,C,1,C,2,（,C,1,-,L,1,）（,C,2,-,L,2,）,关于消解前后子句集可满足性,P70,（同命题逻辑）,故：要证实,F,1,F,2,F,n,W,为永真式，可证实,F,1,F,2,F,n,W,永假，这又能够经过对对应子句集应用消解原理得到空子句来证实（同命题逻辑）,24,人工智能谓词演算,第24页,例：例15、16,定理：归结原理完备性（,P71,）,练习：,P93 3、（1）-（5）,25,人工智能谓词演算,第25页,第三节 归结原理应用,例3.23：,P71,例3.24：,P72,练习：,P94 5、6、,26,人工智能谓词演算,第26页,归结策略,计算机实现归结原理普通算法：,1.将子句集,S,置入,CLAUSES,表；,2.若空子句,NIL,在,CLAUSES,中，则归结成功，结束。,3.若,CLAUSES,中存在可归结子句对，则归结之，并将归结式放入,CLAUSES,中；,4.归结失败，退出。,归结策略完备性,策略：删除策略、支持集策略、线性归结策略、输入归结策略、单元归结策略、祖先过滤形策略。,27,人工智能谓词演算,第27页,归结举例,Sam、Clyde,和,Oscar,是大象。关于它们，我们知道以下事实：,1）,Sam,是粉红色；,2）,Clyde,是灰色且喜欢,Oscar；,3）Oscar,是粉红色或者是灰色（但不是两种颜色）且喜欢,Sam。,用归结法证实一个灰色大象喜欢一个粉红色大象。,即证实：,x,yGray(x)Pink(y)Likes(x,y),谓词：,Gray(x),Pink(x),Like（x,y）,事实：1）,Pinky(Sam),2）,Gray(Clyde)Like(Clyde,Oscar),3）(,Gray(Oscar)Pink(Oscar)Likes(Oscar,Sam),28,人工智能谓词演算,第28页,子句集：1）,Pink(Sam),2）,Gray(Clyde),3）Like(Clyde,Oscar),4）,Gray(Oscar)Pink(Oscar),5）Likes(Oscar,Sam),6）,Gray(x),Pink(y),Likes(x,y),归结：7）,Gray(Oscar),Pink(Sam)5，6,得,8）,Gray(Clyde),Pink(Oscar)3，6,得,9）,Pink(Oscar),Pink(Sam)4，7,得,10）,Pink(Oscar)8，2,得,11）,Pink(Sam)9，10,得,12）,NIL1，10,得,29,人工智能谓词演算,第29页,第四节,Horn,子句与,Prolog,程序设计,子句蕴含表示,P90 （3-1）（3-4、4,、4,）,蕴含型子句归结,P90-91,正、负文字归结（在两头去找）,Horn,子句,定义：,P91,定义1,蕴含型,Horn,子句三种类型：,P91,蕴含型,Horn,子句归结,例：,P91,例1,注意归结次序,30,人工智能谓词演算,第30页,Prolog,程序设计,P30,Prolog,程序语句均是,Horn,子句,事实无条件子句,规则条件子句,问题目标子句,Prolog,程序,P31-33,Prolog,程序运行机制,P33-35,SLD,归结：,从目标子句开始进行归结,归结次序是从左到右,控制策略是深度优先,有回溯机制,31,人工智能谓词演算,第31页,Prolog,语言优缺点：,优点：,Prolog,语言是一个描述性语言，用,Prolog,语言进行程序设计时，只需要描述待求解问题中对象以及对象之间关系事实和变换规则。从这种意义上说，只需告诉计算机“做什么”，而不是“怎样做”，大大提升了程序设计效率。,缺点：,Prolog,语言解释系统或编译系统都是建立在适合于冯诺依曼计算机环境下，最终依然要转化为纯过程性机器指令序列来执行。所以显著地增加了软件开销，使其处理速度难以大幅度提升，从而限制了它们应用范围。,*上机环境,Visual Prolog 5.2,32,人工智能谓词演算,第32页,