人工智能概论 第5章课件.ppt

《人工智能概论 第5章课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3篇知识与推理第5章基于谓词逻辑的机器推理华南师范大学教育信息技术学院郑云翔1提纲一阶谓词逻辑归结演绎推理Horn子句归结与逻辑程序2一阶谓词逻辑谓词、函数、量词：设a1,a2,…,an表示个体对象,A表示它们的属性、状态或关系,则表达式A(a1,a2,…,an)在谓词逻辑中就表示一个(原子)命题。例如：素数(2),就表示命题“2是个素数”好朋友(张三,李四),就表示命题“张三和李四是好朋友”一般地,表达式P(x1,x2,…,xn)在谓词逻辑中称为n元谓词。其中P是谓词符号，也称谓词，代表一个确定的特征或关系(名

2、)。x1,x2,…,xn称为谓词的参量或者项，一般表示个体3一阶谓词逻辑谓词、函数、量词(续)：f(x1,x2,…,xn)表示个体变元x1,x2,…,xn所对应的个体y，并称之为n元个体函数，简称函数约定用大写英文字母作为谓词符号,用小写字母f,g,h等表示函数符号,用小写字母x,y,z等作为个体变元符号,用小写字母a,b,c等作为个体常元符号把“所有”、“一切”、“任一”、“全体”、“凡是”等词统称为全称量词,记为x;把“存在”、“有些”、“至少有一个”、“有的”等词统称为存在量词,记为x4一阶谓词逻辑谓词、函数

3、、量词(续)：对于任意的x,如果x是人,则x有名字——存在不是偶数的整数(存在x,x是整数并且x不是偶数)——不存在最大的整数——某些人对某些食物过敏——5一阶谓词逻辑谓词、函数、量词(续)：紧接于量词之后被量词作用(即说明)的谓词公式称为该量词的辖域，例如：(1)xP(x)(2)x(H(x)→G(x,y))(3)xA(x)∧B(x)其中(1)中的P(x)为x的辖域,(2)中的H(x)→G(x,y)为x的辖域,(3)中的A(x)为x的辖域,但B(x)并非x的辖域6一阶谓词逻辑谓词、函数、量词(续)：量词

4、后的变元如x,y中的x,y称为量词的指导变元(或作用变元),而在一个量词的辖域中与该量词的指导变元相同的变元称为约束变元,其他变元(如果有的话)称为自由变元,例如(2)中的x为约束变元,而y为自由变元,(3)中A(x)中的x为约束变元,但B(x)中的x为自由变元7提纲一阶谓词逻辑归结演绎推理Horn子句归结与逻辑程序8归结演绎推理原子谓词公式及其否定称为文字，若干个文字的一个析取式称为一个子句，1—文字子句叫单元子句，不含任何文字的子句称为空子句，记为或NIL例如下面的析取式都是子句：P∨Q∨乛RP(x,y)∨乛Q

5、(x)9归结演绎推理对一个谓词公式G，通过以下步骤所得的子句集合S，称为G的子句集(P102-103)定理1把证明一个公式G的不可满足性，转化为证明其子句集S的不可满足性定义3子句集S是不可满足的，当且仅当其全部子句的合取式是不可满足的10归结演绎推理命题逻辑中的归结原理：归结演绎推理是基于一种称为归结原理(亦称消解原理principleofresolution)的推理规则的推理方法归结原理是由鲁滨逊(J.A.Robinson)于1965年首先提出它是谓词逻辑中一个相当有效的机械化推理方法。归结原理的出现，被认为是

6、自动推理，特别是定理机器证明领域的重大突破11归结演绎推理命题逻辑中的归结原理(续)：设L为一个文字，则称L与乛L为互补文字设C1,C2是命题逻辑中的两个子句，C1中有文字L1，C2中有文字L2，且L1与L2互补，从C1,C2中分别删除L1,L2，再将剩余部分析取起来，记构成的新子句为C12，则称C12为C1,C2的归结式(或消解式)，C1,C2称为其归结式的亲本子句，L1,L2称为消解基例5.9设C1=乛P∨Q∨R,C2=乛Q∨S,于是C1,C2的归结式为乛P∨R∨S12归结演绎推理命题逻辑中的归结原理(续)：推

7、论设C1,C2是子句集S的两个子句，C12是它们的归结式，则：若用C12代替C1,C2，得到新子句集S1，则由S1的不可满足可推出原子句集S的不可满足。即S1不可满足S不可满足若把C12加入到S中，得到新子句集S2，则S2与原S的同不可满足。即S2不可满足S不可满足13归结演绎推理例5.11证明子句集{P∨乛Q,乛P,Q}是不可满足的证明：(1)P∨乛Q(2)乛P(3)Q(4)乛Q由(1),(2)(5)□由(3),(4)14归结演绎推理例5.12用归结原理证明R是P,(P∧Q)→R,(S∨U)→Q,U的逻辑结果证明

8、：先把诸前提条件化为子句形式，再把结论的非也化为子句，由所有子句得到子句集S={P,乛P∨乛Q∨R,乛S∨Q,乛U∨Q,U,乛R}，然后对该子句集施行归结，归结过程用下面的归结演绎树表示。由于最后推出了空子句，所以子句集S不可满足，即原命题公式不可满足，从而R是题设前提的逻辑结果15归结演绎推理替换与合一：在一阶谓词逻辑中应用消解原理，不像命题逻辑中那样简单