谓词逻辑与归结原理.pptx

概述本章的内容与目标智能体如何认识事物并且进行推理用形式化的语言描述推理过程机器证明的一般方法归结原理第1页/共132页概述语言自然语言：人们在日常生活中所使用的语言文字 半形式化语言：自然语言加特定的符号，如数学语言(定义、定理等)形式化语言：用精确的数学或机器可处理的公式定义的语言。(逻辑学语言，弗雷格Frege，1879)(pq)(pr)p r p 3*2=6if(ab)then a+;因与另一因以及两者彼此的联系。但此种联系的发展，相互作用，本身即是区别的变换，不过不是原因与原因的互换，而是因果关系中两环节的互换，就每一环节各自独立而为。第2页/共132页怪物洞穴人工智能的经典实验环境怪物洞穴(wumpus世界)洞穴有多个房间组成某个房间中藏着一只怪物wumpus，它会吃掉进入这个房间的人，相邻房间中能够感觉到臭味某些房间中有陷阱，进入房间会被陷阱吞噬，相邻房间中能够感觉到微风游戏的主角是一个智能体，可以进入相邻的房间（对角线不可以）智能体有且仅有一支箭，用这支箭可以射杀怪物某个房间中有金子，游戏的目标是智能体找到金子第3页/共132页怪物洞穴智能体行动的关键是要智能体行动的关键是要根据获得的信息推理，根据获得的信息推理，从而判断那个房间有怪从而判断那个房间有怪物，那个房间有陷阱，物，那个房间有陷阱，那个房间是安全的那个房间是安全的房间房间4,2和和2,3有陷有陷阱，房间阱，房间3,4有怪物，有怪物，房间房间4,3有金子有金子第4页/共132页3.1 命题逻辑第5页/共132页3.1 命题逻辑命题能够判断真假的陈述句陈述句真值唯一，可用二进制表示用小写字母进行标识例1、北京是中国的首都。2、长安大学位于钟楼附近。3、1+1=2 4、计算机系的学生必修C或JAVA。5、坐着花生过黄河5、x+1=26、吃饭了吗？7、南无阿弥陀佛8、我正在说假话第6页/共132页3.1 命题逻辑简单命题与复合命题简单命题：（原子命题）一个命题无法分解为更简单的子命题复合命题：由简单命题用联结词联结而成的命题 1、由若干简单命题组成；2：由联结词联结例：1、北京是中国的首都。2、长安大学位于钟楼附近。3、计算机系的学生必修C或JAVA。4、这家的报价单配置合理并且价格低廉。5、“李四是犯罪嫌疑人”“李四有犯罪动机”第7页/共132页3.1 命题逻辑合式公式：合式公式：单个常量或者变量的命题构成合式公式单个常量或者变量的命题构成合式公式联结词联结的合式公式的组合也是合式公式联结词联结的合式公式的组合也是合式公式合式公式的有限次组合称为命题公式合式公式的有限次组合称为命题公式命题公式：有限次合式公式组合的形式化描命题公式：有限次合式公式组合的形式化描述，本书中以大写字母标识。述，本书中以大写字母标识。第8页/共132页3.1 命题逻辑基本联结(连接)符号 非，否定,与，合取，AND的首字母 或，析取，vel 蕴含 式A：a b表示，如果a为真，则b为真。等价联结符号的优先级 第9页/共132页3.1 命题逻辑将命题从语言表述转换为命题公式step1、找出简单命题，并用符号表示step2、分析简单命题间的逻辑关系，用联结符号进行描述例1、3不是偶数令：p表示“3是偶数”，p2、教室里有30名男生和10名女生令：p表示“教室里有30名男生”，q表示“教室里有10名女生”p q3、如果天下雨，出门带伞令p表示“天下雨”，q表示“出门带伞”pq4、只要不下雨，我就骑自行车上班令p表示“天下雨”，q表示“骑自行车上班”pq5、只有不下雨，我才骑自行车上班令p表示“天下雨”，q表示“骑自行车上班”q p第10页/共132页3.1 命题逻辑例：怪物洞穴 如果房间1,1中有臭味，则房间1,2或2,1中有怪物 表示房间i,j中有臭味 表示房间i,j中有怪物 练习：如果房间1,1中没有臭味，则房间1,2和2,1中没有怪物第11页/共132页3.1 命题逻辑练习：扫雷游戏设Xi,j表示方格i,j中有一个地雷。写出方格1,1周围恰好有2颗地雷的命题公式1 2 3 4 5 54321第12页/共132页3.1 命题逻辑命题公式的赋值命题公式的赋值对命题公式中的所有的命题变量各赋给一个值对命题公式中的所有的命题变量各赋给一个值0，1。真值表真值表pqppqpqpqpq00011011第13页/共132页3.1 命题逻辑复合命题的真值例：p:周杰伦是一个流行歌手q:人工智能是计算机科学的一个分支 r:牛在天上飞求下列复合命题的真值p qp q(p q)(p q)r(q r)(pr)pr(p r)(p r)我们关心的是复合命题中命题之间的真值关系，我们关心的是复合命题中命题之间的真值关系，而不关心命题的内容。而不关心命题的内容。第14页/共132页3.1 命题逻辑命题公式的分类重言式或永真式 tautology，设A为任一命题公式，若A在它的各种赋值下取值均为真，则称A是重言式例：PP矛盾式或永假式 contradictory 设A为任一命题公式，若A在它的各种赋值下取值均为假，则称A是永假式。例：PP第15页/共132页3.1 命题逻辑可满足式 satisfiable设A为任一命题公式，如果存在一组取值使A为真，则A为可满足式。即：对于命题公式A，若A不是矛盾式，则称A是可满足式。例：PQ 非重言式的可满足式 既是可满足式，又不是重言式第16页/共132页3.1 命题逻辑等值逻辑运算 逻辑等值，等号连接的命题公式等价，基本等值算式 P80交换率:A B B A；A B B A；结合率:(A B)C A(B C)；(A B)C A (B C)；*分配率:A (B C)(A B)(A C)；A(B C)(A B)(A C)；双重否定律：A A；等幂率：A A A；A A A；*摩根律：(A B)A B；(A B)A B；第17页/共132页3.1 命题逻辑吸收率:A(A B)A；A (A B)A；同一率:A 0 A；A 1 A；零率:A 1 1；A 0 0；排中律：A A 1矛盾律：A A 0*蕴含等值式：AB A B；*等价等值式：AB(AB)(B A)；假言易位式：A B B A；等价否定等值式：A B A B；归谬论：(A B)(A B)A；第18页/共132页3.1 命题逻辑合取范式与析取范式简单析取式：有限个命题变元或其否定，析取联结符 pq;p q ;p ;q合取范式：有限个简单析取式，合取 p(pq)(p q)简单合取式：有限个命题变元或其否定，合取 p q;p q ;p ;q析取范式：有限个简单合取式，析取 p(p q)(p q)第19页/共132页3.1 命题逻辑任意命题公式都存在等值的析取范式和合取范式求取合取范式的步骤1、利用蕴含等值式和等价等值式消去命题公式中除，以外的联结词 2、利用摩根律、双重否定律等进行置换，将移到括号里面3、利用分配律得到合取范式第20页/共132页3.1 命题逻辑例 P82 计算(p (q r)s 的合取范式 (p (q r)s (p (q r)s;蕴含等值式 (p (q r)s;蕴含等值式 p (q r)s;摩根律 p(q r)s;摩根律 p(q r)s;双重否定律 (p s)(q r);交换律 (p s q)(p s r);分配律第21页/共132页3.1 命题逻辑例 P82计算(p q)r)p 的合取范式 (p q)r)p (p q)r)p ；蕴含等值式 (p q)r)p ;蕴含等值式 (p q)r)p ;摩根律 (p q)r)p ;双重否定律 (p q p)(r p);分配律 (p q)(r p);等幂律第22页/共132页3.1 命题逻辑课堂练习 计算合取范式(pq)(q p)(pq)q p第23页/共132页3.1 命题逻辑命题逻辑推理逻辑结论：如果AB为重言式，则称B是A的逻辑结论，记作A=B。常用推理定律：附加：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)第24页/共132页3.1 命题逻辑命题逻辑推理规则前提引入规则 任何证明的步骤上，都可以引入前提；结论引入规则 任何证明的步骤上，所得到的结论都可以作为后续证明的前提；置换规则 任何证明的步骤上，命题公式中任何子命题都可以用与之等值的命题公式置换；第25页/共132页3.1 命题逻辑例：P84 如果今天下雨，则要带雨伞或雨衣。如果走路上班；则不带雨衣。今天下雨，走路上班，证明要带伞。解：p:今天下雨；q:带雨伞；r:带雨衣；s:走路上班 前提：p(q r)；s r；p；s 求证：q证明：1、p(q r)，p 前提引入：2、(p(q r)p)=q r 假言推理：3、s r，s 前提引入：4、(s r)s)=r 假言推理：5、(q r)r)=q 析取三段论：第26页/共132页3.1 命题逻辑例例 怪物洞穴怪物洞穴 表示房间表示房间i,j中有臭中有臭味味 表示房间表示房间i,j中有怪中有怪物物 表示房间表示房间i,j中有微中有微风风 表示房间表示房间i,j中有陷中有陷阱阱第27页/共132页3.1 命题逻辑初始状态，在房间1,1处没有感觉到微风，也没有臭味，则相邻房间为安全的，既没有怪物也没有陷阱。前提：结论：证明：前提引入 等价等值式 简化 前提引入 拒取式 摩根律第28页/共132页3.1 命题逻辑归结原理证明的一般方法由已知条件正向推导结论，演绎推理假定结论不成立，逆向推导与已知条件矛盾，反证法命题逻辑证明的归谬思想 P85归结原理的思想：如果证明AB为永假式，则得证第29页/共132页归结推理命题逻辑谓词逻辑Skolem标准形、子句集基本概念谓词逻辑归结原理合一和置换、控制策略数理逻辑命题逻辑归结Herbrand定理第30页/共132页3.1 命题逻辑归结方法的思想1、将待证明问题转化为其逆否命题例：条件 A，求证B.即 AB 其逆否命题为：AB2、求合取范式，得到子句集构成合取范式的有限个简单析取式构成的集合就是子句集3、对子句集进行归结，得到空子句 第31页/共132页3.1 命题逻辑将待证明问题转化为其逆否命题证明问题的一般形式：已知：A成立 求证：B成立 即：证明 AB A B AB 蕴含等值式 (AB)摩根率 AB即为原命题的逆否命题第32页/共132页3.1 命题逻辑例：证明 G是F的逻辑结论F1：PWF2：WG：P分析：已知条件分析：已知条件为：(PW)(W)结论为：P 则，逆否命，逆否命题为：(PW)(W)第33页/共132页3.1 命题逻辑子句与子句集 P86对问题的逆否命题，求其合取范式对于一个合取范式，该范式中的每一条简单析取式都是一个子句。子句集：合取范式下的所有子句构成其子句集。例：p(pq)(p q)子句集为 p,pq,p q第34页/共132页3.1 命题逻辑归结方法归结方法 如果如果pq与与 q r都为真，则都为真，则pr为真为真证明证明1 真值表真值表ppqq q q rrpr1-10110111n证明证明2前提：前提：(pq)(q r)结论：结论：pr证明证明:(pq)(q r)(p q)(q r)蕴含等值式与双重否定律蕴含等值式与双重否定律 =(p r)假言三段论假言三段论 pr 蕴含等值式蕴含等值式 第35页/共132页3.1 命题逻辑归结式 例 pq,p q 归结后为:q 归结的目标空子句对于一个合取范式，如果有一个子句不可满足，则子句集就不可满足，该合取范式为永假式若一个子句集中包含空子句，则这个子句集一定是不可满足的 例：p,p归结后为 第36页/共132页3.1 命题逻辑归结法步骤建立待归结命题公式。将证明AB为真转化为证明AB为矛盾式求合取范式，得到子句集对子句集进行归结归结式作为新子句加入子句集进行归结当归结式为空子句时停止，证明结束。出现空子句，表示该子句集不可满足归结法的完备性：如果AB成立，则利用归结法一定可以得到证明第37页/共132页3.1 命题逻辑例：证明(pq)(q p)证明：要证明原命题为真，只需证明(pq)(q p)为恒假 (pq)(q p)(pq)(q p)蕴含等值式 (pq)q p 摩根律 于是，子句集为:1 pq 2 q 3 p pq,q,p 4 p 1、2归结 5 3、4归结 由此可得:(pq)(q p)为恒假，原命题为真 ,p,p,pq,q p,p,pq,q 第38页/共132页3.1 命题逻辑例：怪兽洞穴例：怪兽洞穴1、在房间、在房间1,1处没有感处没有感觉到微风，也没有臭味。觉到微风，也没有臭味。2、在房间、在房间1,2处感觉到处感觉到微风，但没有感觉到臭味。微风，但没有感觉到臭味。3、在房间、在房间1,2处没有感处没有感觉到微风，但感觉到臭味。觉到微风，但感觉到臭味。求证：房间求证：房间3,1处有处有怪物怪物*；房间；房间1,3处有处有洞穴；房间洞穴；房间2,2是安是安全的。全的。第39页/共132页3.1 命题逻辑前提：前提：求证：求证：证明：要证明原命题为真，只需证明以下命题为恒假证明：要证明原命题为真，只需证明以下命题为恒假 第40页/共132页3.1 命题逻辑于是，得到子句集为：第41页/共132页3.1 命题逻辑1 s1,22 w1,13 s2,14 s2,1 w1,1 w2,2 w3,1 5 s1,2 w1,1 6 s1,2 w2,27 w3,1 8 w1,1 w2,2 w3,1 3,4归结 9 w2,2 w3,1 8,2归结10 w2,2 9,7归结11 s1,2 10,6归结12 11,1归结第42页/共132页3.1 命题逻辑思考：归结算法的计算机实现？S0,S1,S2,S3 终止条件：1、生成了空子句，证明结束 2、循环结束，没有可以添加的新语句，待证明的定理不成立 第43页/共132页3.1 命题逻辑好的归结控制策略 初始状态优先选择包含结论的子句进行归结，之后每次都选择上一次归结得到的归结式与其他子句归结容易犯的错误 字句集 1、PQ 2、PQ 3、1、2归结3、Q Q 1、2归结不允许同时归结两个项第44页/共132页3.1 命题逻辑归结方法是一种机械化的,可在计算机上加以实现的推理方法归结方法是一种反向推理形式提供了一种自动定理证明的方法归结的半完备性当定理可以证明时，归结方法是完备的当定理不可证明时，归结方法得不到任何结论，算法不一定会停止第45页/共132页3.2 谓词逻辑第46页/共132页3.2 谓词逻辑3.2.1 基本概念命题逻辑描述简单的陈述性命题，但表示量化和谓词过于繁琐，也难以表示个体间的关系例：现在课堂上的所有学生都在上人工智能课命题逻辑s1:张三在上人工智能课s2:李四在上人工智能课s3:王五在上人工智能课 例2：用命题逻辑归结原理证明：“人都是妈生的，张飞是人，所以张飞是妈生的”p:人都是妈生的q:张飞是人r:张飞是妈生的(p q)r p q r第47页/共132页3.2 谓词逻辑3.2.1 基本概念谓词逻辑Class(x)表示x在上人工智能课 x=张三，就得到了s1；x=李四，就得到了s2；x=王五，就得到了s3；Class(x,y)表示x在上y课x=张三，y=人工智能，表示张三在上人工智能课x=李四，y=线性代数，表示李四在上线性代数课x=王五，y=睡觉，表示王五在上睡觉课第48页/共132页3.2 谓词逻辑3.2.1 基本概念命题是一个陈述句，它一般可分成主语和谓语两部分。有时还需要用到量词。主语：指独立存在的客体，可以是具体事物或抽象概念，也称为个体谓词：描述个体词性质或个体之间关系的词个体域：表示个体变量的取值范围，常用D表示常量：表示具体性质或关系的个体或者谓词变量：表示抽象或泛指的个体或者谓词。量词：表示数量的词。任意量词：表示“任意”，“所有”，也称为全称量词存在量词：表示“存在”第49页/共132页3.2 谓词逻辑3.2.1 基本概念例：“关羽是人”，“张飞是人”这是两个不同的命题，其主语（个体）不同但是谓词是相同的，“是人”把谓语部分抽出来，假设 Human(x)表示x是人这两个命题都可以用这个谓词来描述 Human(guanyu)Human(zhangfei)其中x属于个体变量，guanyu和zhangfei属于个体常量 第50页/共132页3.2 谓词逻辑3.2.1 基本概念例：1、所有的人都是要死的2、有的人能够活到100岁 P(x)表示x是要死的，Q(x)表示x活到100岁个体域D为人类集合个体域D为总个体域集合引入特殊谓词R(x)表示x是人第51页/共132页3.2 谓词逻辑语言描述转换为谓词公式1、确定并说明谓词2、确定个体和个体域3、确定量词4、判断谓词间的逻辑关系第52页/共132页3.2 谓词逻辑例：我是计算机系的学生1、确定并说明谓词：方法一：Student(x,y)表示X是Y系的学生2、个体域：X：学生的集合，y：系的集合 Student(I,computer)方法二：Computer(x)表示X是计算机系的学生 Computer(I)注意：必须对谓词进行说明 P(I,computer)第53页/共132页3.2 谓词逻辑1、定义并说明谓词 Unlike(x,y)表示 x不喜欢y课2、个体域 x学生的集合，y课程的集合3、量词 存在n例：有学生不喜欢上人工智能课Like(x,y)表示表示x喜欢喜欢y课课Student(x)表示表示x是学生是学生Like(x,y)表示表示x喜欢喜欢y课课个体域个体域x：人的集合：人的集合逻辑关系：与逻辑关系：与第54页/共132页3.2 谓词逻辑例：任何人的兄弟都是男性确定并说明谓词Brother(x,y)表示x是y的兄弟Male(x)表示x是男性个体域 Brother(x,y)x、y：人的集合 Male(x)x：人的集合量词 任意确定逻辑关系 与？或？非？蕴含？等价？第55页/共132页3.2 谓词逻辑例：不管黑猫白猫，抓住老鼠就是好猫定义并说明谓词 Cat(x,y)表示是x是y颜色的猫 Goodcat(x)表示x是好猫 Catch(x,Mouse)表示x能抓住老鼠个体域 x:猫的集合，y：颜色的集合谓词间的关系 Cat(x,y)与Catch(x,Mouse)蕴含Goodcat(x)量词：任意 第56页/共132页3.2 谓词逻辑3.2.1 基本概念量词使用中的注意事项不同的个体域中，命题符号化的形式可能不同没有给定个体域的情况下，应考虑全总个体域如果个体域为有限集 ，对任意谓词P(x)有：多个量词同时出现时，不能颠倒其先后顺利，否则会改变公式的含义。第57页/共132页3.2 谓词逻辑3.2.1 基本概念例：love(x,y)表示x喜爱y 表示对任意的x，都存在喜爱的对象y，即“每一个人都会喜爱某人”表示存在都一个y，任意的人x 都喜爱他，即 “上帝”第58页/共132页3.2 谓词逻辑3.2.2 一阶谓词逻辑原子公式：设 是任意n元谓词，是项，则称 为原子公式。项：任何常量是项。任何变量是项。n 1 个参数的任何表达式 （其中，是项，而 f 是 n 阶的函数）是项。闭包条款：其他东西都不是项。第59页/共132页3.2 谓词逻辑3.2.2 一阶谓词逻辑谓词公式原子公式是谓词公式。若A为谓词公式，则A也是一个谓词公式。若A和B都是谓词公式，则(A B)，(A B)，(AB)和(A B)也都是谓词公式。若A是谓词公式，和 也都是谓词公式。只有有限次应用上述规则得到的公式，才是谓词公式。第60页/共132页3.2 谓词逻辑3.2.2 一阶谓词逻辑对于 ，x称为指导变量 A称为相应量词的辖域 x(p(x)x在辖域A中的出现称为约束出现x以外的变量在辖域A中的出现称为自由出现 x(p(x,y)第61页/共132页对于 ，指导变量：的辖域：x,y都是约束出现3.2 谓词逻辑3.2.2 一阶谓词逻辑例对于 ，指导变量:的辖域:x、y是约束出现还是自由出现 y是约束出现，x是自由出现第62页/共132页3.2 谓词逻辑3.2.2 一阶谓词逻辑不同量词如果采用相同的指导变量名，易引起混淆一般要求不同的量词使用不同的指导变量名称第63页/共132页3.2 谓词逻辑3.2.2 一阶谓词逻辑当在一个公式中，一个变量符号既是约束出现的变量，又是自由出现的变量时，需要作变量符号更换。换名规则：将量词辖域中某个约束出现的变量及其指导变量替换为此辖域中未出现过的个体变量符号 x既作为指导变量约束出现又自由出现，因此要换掉其中之一 换名规则更换的是指导变量 可替换为第64页/共132页3.2 谓词逻辑3.2.2 一阶谓词逻辑替代规则：对某自由出现的个体变量用与原公式中未出现过的变量符号去替代，且处处替代。x既作为指导变量约束出现又自由出现，且多处自由出现 替代规则更换的是自由出现的变量，且处处替代 替换为第65页/共132页3.2 谓词逻辑3.2.2 一阶谓词逻辑谓词公式的解释对谓词公式中的各种变量制定具体的常量去替代一个解释包括非空个体域 D D中一部分特定元素；D上一些特定的函数；D上一些特定的谓词。如果谓词公式在特定解释下为真，称这个解释满足这个谓词公式，是这个谓词公式的一个模型永真与不可满足第66页/共132页3.2 谓词逻辑3.2.2 一阶谓词逻辑例：p92 给定解释I如下 个体域:函数 f(x):f(2)=3,f(3)=2 谓词：P(x)为 P(2)=0,P(3)=1 Q(x,y)为 Q(i,j)=1,i,j=2,3 R(x,y)为 R(2,2)=R(3,3)=1，R(2,3)=R(3,2)=0 求解释I下，下列谓词公式的真值 1、2、第67页/共132页3.2 谓词逻辑3.2.2 一阶谓词逻辑解 1、=(P(f(2)Q(2,f(2)(P(f(3)Q(3,f(3)=(P()Q(2,)(P()Q(3,)=(1 1)(01)=1 2、=(R(2,2)R(2,3)(R(3,2)R(3,3)=(1 0)(01)=1第68页/共132页3.2 谓词逻辑3.2.3 谓词演算与推理谓词演算公式约束变量换名规则，Q为任意量词 (Qx)P(x)(Qy)P(y)(Qx)P(x,z)(Qy)P(y,z)量词消去等值式，对于有穷个体域量词否定等值式量词分配等值式第69页/共132页3.2 谓词逻辑3.2.3 谓词演算与推理量词辖域收缩与扩张等值式第70页/共132页3.2 谓词逻辑3.2.4 谓词知识表示谓词逻辑表达的规范形式P是谓词，而 表示个体（主体或者客体）知识库：表达知识的一组谓词公式的集合。语句的集合对环境、规则等信息的结构化描述基于知识的智能体的核心构件第71页/共132页3.2 谓词逻辑3.2.4 谓词知识表示定义谓词例1、小李与小张打网球 Play(x,y,z)表示x,y在进行z运动 Play(Li,Zhang,tennis)2、我在长安大学当教师 Work(x,y,z)表示x在y单位从事z工作 Work(Me,Chd,teacher)3、怪物洞穴中某个房间有微风、有臭味、没有怪物、没有陷阱、没有金子 Roomi,j(x,y,z,m,n)参数分别对应有没有微风、臭味、怪物、陷阱、金子 Roomi,j(1,1,0,0,0)第72页/共132页3.2 谓词逻辑3.2.4 谓词知识表示例：准前女友双眼皮,大眼睛doublefold(x)bigeyes(x)一头乌黑的头发blackhair(x)thickhair(x)一身漂亮的呢子大衣beautifuldress(x)走路的姿态赛过模特graceful(x)第73页/共132页3.2 谓词逻辑3.2.4 谓词知识表示知识表示 例 P97 房间里有机器人Robot、积木块Box、两个桌子A和B。定义谓词Table(A)A是桌子 EmptyHanded(Robot)机器人空手At(Robot,A)机器人位置在A旁Holds(Robot,Box)机器人拿着BoxOn(Box,A)Box在桌子A上第74页/共132页3.2 谓词逻辑3.2.4 谓词知识表示初始状态初始状态EmptyHanded(Robot)At(Robot,A)On(Box,A)Table(A)Table(B)机器人拿起机器人拿起BoxAt(Robot,A)Holds(Robot,Box)Table(A)Table(B)第75页/共132页3.2 谓词逻辑3.2.4 谓词知识表示q机器人放下机器人放下BoxEmptyHanded(Robot)At(Robot,B)On(Box,B)Table(A)Table(B)q机器人走到机器人走到B桌桌At(Robot,B)Holds(Robot,Box)Table(A)Table(B)在这个例子里，可以把EmptyHanded(Robot)和Holds(Robot,Box)合并，用Holds(Robot,None)来代替EmptyHanded(Robot)第76页/共132页3.2 谓词逻辑3.2.3 谓词演算与推理前束范式约束在前面的范式将所有的量词都移到最左边就得到了前束范式与合取范式类似，所有的谓词公式都可以改写成前束范式的形式求前束范式的步骤前束范式中每个量词的指导变量不同，如果指导变量相同，则需要利用换名规则进行替换。如果自由变量与指导变量相同，则需利用换名规则或替代规则替换其中之一利用量词辖域收缩扩张等值式替换第77页/共132页3.2 谓词逻辑3.2.3 谓词演算与推理例 P94 求前束范式量词与指导变量：，自由出现的变量：，换名规则 替代规则 P93 3-7 第78页/共132页3.2 谓词逻辑3.2.3 谓词演算与推理 P93 3-8 P93 3-3 P93 3-4第79页/共132页3.2 谓词逻辑3.2.3 谓词演算与推理谓词推理例：20世纪70年代的漫画都是日本漫画家创作的，这幅漫画是20世纪70年代的作品；因此它是日本漫画家的作品解：设P(x)：属于20世纪70年代的漫画 Q(y)：属于日本漫画家的作品 a :一幅漫画 前提:结论:Q(a)证明:前提引入 量词消去 前提引入 假言推理第80页/共132页3.3 谓词逻辑归结原理第81页/共132页3.3 谓词逻辑归结原理3.3.1 归结原理命题逻辑归结原理：将由前提A得到结论B的证明过程转化为证明A B为矛盾式将其转化为合取范式，得到子句集 对于形如 的公式求取子句集时，可以分别求 各自的子句集，再取并集利用归结原理消去互补项，直到得到空子句。第82页/共132页3.3 谓词逻辑归结原理3.3.1 归结原理例 (P(QR)(P Q)(P R)转化为待归结命题公式：(P(QR)(P Q)(P R)求子句集:分别对(P(QR)和(P Q)(P R)两部分求取子句集，再取并集1、(P(QR)(P(QR)(PQR)2、(P Q)(P R)(P Q)(P R)(P Q)(P R)(P Q)(P R)(P Q)(P R)子句集为：PQR,P Q,P,R第83页/共132页3.3 谓词逻辑归结原理3.3.1 归结原理归结：1、PQR 2、P Q 3、P 4、R 5、PR 1、2归结 6、R 3、5归结 7、4、6归结因此得证第84页/共132页3.3 谓词逻辑归结原理3.3.1 归结原理步骤步骤命题逻辑归结原理命题逻辑归结原理谓词逻辑归结原理谓词逻辑归结原理1、建立、建立AB命题逻辑公式命题逻辑公式谓词逻辑公式谓词逻辑公式2、求子、求子句集句集求合取范式求合取范式求前束合取范式求前束合取范式消去量词消去量词3、归结、归结直接消去互补项直接消去互补项利用置换与合一消去利用置换与合一消去互补项互补项归结式加入子句集归结式加入子句集归结式加入子句集归结式加入子句集第85页/共132页3.3 谓词逻辑归结原理3.3.1 归结原理谓词逻辑归结原理的重点如何对前束合取范式消去量词 命题逻辑 谓词逻辑如何利用置换与合一对不同变量的子句进行置换 命题逻辑 谓词逻辑第86页/共132页3.3 谓词逻辑归结原理3.3.1 归结原理求前束合取范式：方法一：先转化为前束范式，再将辖域中的谓词公式转化为合取范式方法二：(1)消去联结词 和。(2)将联结词向内深入，使之只作用于原子公式。(3)利用换名或替代规则使所有约束变元的符号都不同，并且自由变元与约束变元的符号也不同。(4)利用量词辖域的扩张和收缩，扩大量词至整个公式。(5)再将辖域中的谓词公式转化为合取范式。第87页/共132页3.2 谓词逻辑3.2.3 谓词演算与推理量词辖域收缩与扩张等值式第88页/共132页3.2 谓词逻辑3.2.3 谓词演算与推理求前束合取范式 (x)P(x)Q(x)(x)P(x)Q(x)(x)(P(x)Q(x)(x)(P(x)Q(y)(x)(P(x)Q(y)(x)(P(x)Q(y)1、消去和2、向内深入3、换名或替代4、量词前束5、辖域中的公式化为合取范式第89页/共132页3.3 谓词逻辑归结原理3.3.2 Skolem标准型例 求前束合取范式 第90页/共132页3.3 谓词逻辑归结原理3.3.2 Skolem标准型Skolem标准型：对前束合取范式消去所有的量词。P100第一步：消去存在量词 ：1、如果 之前(左边)没有任意量词,则用常量替换 的指导变量 可用常量b替换x消去存在量词，得P(b,a)2、如果 之前(左边)有任意量词 ，则用任意量词的函数替换 的指导变量 可用f(x)替换y消去存在量词，第二步消去任意量词：简单的省略即可第91页/共132页3.3 谓词逻辑归结原理3.3.2 Skolem标准型例：1、消去存在量词 y和 u：y 前面有任意量词，指导变量为x，因此用f(x)替换y，u前面有任意量词，指导变量为x，因此用g(x)替换u2、消去任意量词：第92页/共132页3.3 谓词逻辑归结原理3.3.2 Skolem标准型例 判断下列的消去量词的过程是否正确。证明：x y G(x,y)y G(x,y)消去 x G(x,a)消去 y对任意x，都存在一个恒定常量a，使G(x,a)成立 x y G(x,y)x G(x,f(x)消去消去 y G(x,f(x)消去消去 x对任意对任意x，都存在一个与之对应的都存在一个与之对应的f(x)，使，使G(x,f(x)成立成立第93页/共132页3.3 谓词逻辑归结原理3.3.3 子句集定义文字：不含任何联结词的谓词公式子句：一些文字或其非的析取子句集：所有子句的集合计算过程将谓词公式转化为前束合取范式消去存在量词，略去任意量词，得Skolem标准型将各子句提出，得到子句集谓词公式不可满足，当且仅当其子句集不可满足的形如 的谓词公式在求子句集时可以分别对 求子句，再取其并集第94页/共132页3.3 谓词逻辑归结原理3.3.1 归结原理谓词逻辑归结原理的重点如何对前束合取范式消去量词 命题逻辑 谓词逻辑如何利用置换与合一对不同变量的子句进行置换 命题逻辑 谓词逻辑第95页/共132页3.3 谓词逻辑归结原理3.3.4 置换与合一置换：形如 的有限集合xi 必须是变量，称为置换变量ti 可以是常量、变量或者函数，称为置换项表示用项 ti 替换谓词公式中的变量 xi 要求ti xi,xi不能循环的出现在另一个ti中 x/y,y/z x/y,y/x x/y,y/z,z/x 第96页/共132页3.3 谓词逻辑归结原理3.3.4 置换与合一例:设有公式P(x,f(y),b)置换1为：s1=z/x,w/y P(x,f(y),b)s1=P(z,f(w),b)置换2为：s2=a/y P(x,f(y),b)s2=P(x,f(a),b)置换3为：s3=q(z)/x,a/yP(x,f(y),b)s3=P(q(z),f(a),b)置换4为：s4=c/x,a/y P(x,f(y),b)s4=P(c,f(a),b)置换5为：s5=x/b第97页/共132页3.3 谓词逻辑归结原理3.3.4 置换与合一例：设=f(y)/x,z/y,=a/x,b/y,y/z,对L=P(x,f(y),b)，先做置换，再做置换，即求 第98页/共132页3.3 谓词逻辑归结原理3.3.4 置换与合一置换的合成：对谓词公式L，设=t1/x1,t2/x2,tn/xn 和=u1/y1,u2/y2,un/yn 为两个置换，则 ,称为和的合成，可由下式得到 1、如果 ，则消去 2、当 ，删去第99页/共132页3.3 谓词逻辑归结原理3.3.4 置换与合一例：设=f(y)/x,z/y,=a/x,b/y,y/z 求1、如果 ti=xi ,则消去ti/xi 2、当 ，删去第100页/共132页3.3 谓词逻辑归结原理3.3.4 置换与合一例：对子句集 P(x),P(a)做置换a/x 得到 P(a),P(a)P(x,y),P(a,b)Q(x)做置换a/x,b/y P(a,b),P(a,b)Q()第101页/共132页3.3 谓词逻辑归结原理3.3.4 置换与合一合一：设有公式集 ，如果存在一个置换，使 ，则称是F的一个合一。如果谓词公式F1、F2 可合一，那么 就是一对互补项 P(x),P(a)经合一 a/x 得到 P(a),P(a)谓词逻辑归结原理：如果子句集中的两个字句含有互补项，则可以进行归结消去第102页/共132页3.3 谓词逻辑归结原理置换与合一例：下列字句都可以归结 P(x),P(x)P(x),P(a)经合一 a/x后，P(x),P(a)可合一 P(x,y),P(a,z)经合一a/x,z/y，P(x,y),P(a,z)可合一 这些子句的文字可合一，都可以进行归结 P(a,x,f(g(y),P(z,f(a),f(u)需要一个判断公式集能否合一的算法第103页/共132页3.3 谓词逻辑归结原理3.3.4 置换与合一最一般合一(mgu)设 是谓词公式F的一个合一，如果对于F的任意一个合一，都存在一个置换，使 ,则称 是一个最一般合一。求取办法：对每一项逐一比较并进行合一置换P104 P104 1 1、令2 2、令3 3、如果 已经合一，停止迭代，；否则，找不一致集4 4、若 中存在元素 和 ，且 不出现于 中，转5 5；否则，不可合一5 5、令 ，6 6、k=k+1,转3 3 第104页/共132页3.3 谓词逻辑归结原理3.3.4 置换与合一例 P(a,x,f(g(y),P(z,f(a),f(u)，计算mgu 解:1 W=P(a,x,f(g(y),P(z,f(a),f(u)2 3 W0未合一，从左到右找不一致集，4 5 令 ，6 k=k+1,转3 3 第105页/共132页3.3 谓词逻辑归结原理3.3.4 置换与合一 3 W1 未合一，从左到右找不一致集，4 5 令 ，6 k=k+1,转3 3 3 3 W2未合一，从左到右找不一致集，4 5 令 已合一，第106页/共132页3.3 谓词逻辑归结原理3.3.5 归结式归结式：设 为两个无公共变量的子句,分别是 的文字，如果 可合一，则 为 的归结式例：1 P(x)Q(x,y)与 P(a)R(b,z)的归结式：经合一a/x置换归结得到：2 P(x,y)Q(x)R(x)与 P(a,z)Q(b)的归结式：经合一a/x,z/y归结得到：经合一b/x归结得到：P(b,y)R(b)P(a,z)第107页/共132页3.3 谓词逻辑归结原理 3.3.5 归结式几种不能归结的情况谓词不一致不能进行归结如：P(x)与Q(x)不能归结常量之间不能进行归结如：P(a)与 P(b)不能归结,不能在常量之间置换a/b变量与其函数之间不能进行归结如：P(x)与 P(f(x)不能归结，不能做置换f(x)/x不能同时消去两个互补对 第108页/共132页3.3 谓词逻辑归结原理 3.3.5 归结式如果子句可以简化，应该先简化再归结例 C1可以简化，做合一置换 f(x)/y,取mgu=g(a)/x,归结式为 Q(b)Q(g(g(a)第109页/共132页3.3 谓词逻辑归结原理3.3.6 归结过程n写出谓词关系公式n写出待归结的谓词表达式n化为Skolem标准型n求子句集Sn对S中的互