第三章-谓词逻辑与归结原理

《第三章-谓词逻辑与归结原理》由会员分享，可在线阅读，更多相关《第三章-谓词逻辑与归结原理（132页珍藏版）》请在金锄头文库上搜索。

1、人工智能第三章 谓词逻辑与归结原理概述n本章的内容与目标本章的内容与目标q智能体如何认识事物并且进行推理智能体如何认识事物并且进行推理q用形式化的语言描述推理过程用形式化的语言描述推理过程q机器证明的一般方法机器证明的一般方法归结原理归结原理概述n语言语言q自然语言：人们在日常生活中所使用的语言文字自然语言：人们在日常生活中所使用的语言文字 q半形式化语言：自然语言加特定的符号，如数学语半形式化语言：自然语言加特定的符号，如数学语言言(定义、定理等定义、定理等)q形式化语言：用精确的数学或机器可处理的公式定形式化语言：用精确的数学或机器可处理的公式定义的语言义的语言 。(逻辑学语言，弗雷格逻辑

2、学语言，弗雷格Frege ，1879) (pq)(pr) p r p 3*2=6if (ab) then a+;因与另一因以及两者彼此的联系。但此种联系的发展，相互作用，本因与另一因以及两者彼此的联系。但此种联系的发展，相互作用，本身即是区别的变换，不过不是原因与原因的互换，而是因果关系中两身即是区别的变换，不过不是原因与原因的互换，而是因果关系中两环节的互换，就每一环节各自独立而为。环节的互换，就每一环节各自独立而为。怪物洞穴n人工智能的经典实验环境人工智能的经典实验环境怪物洞穴怪物洞穴(wumpus世界世界)q洞穴有多个房间组成洞穴有多个房间组成q某个房间中藏着一只怪物某个房间中藏着一只怪

3、物wumpus，它会吃掉进入，它会吃掉进入这个房间的人，相邻房间中能够感觉到臭味这个房间的人，相邻房间中能够感觉到臭味q某些房间中有陷阱，进入房间会被陷阱吞噬，相邻某些房间中有陷阱，进入房间会被陷阱吞噬，相邻房间中能够感觉到微风房间中能够感觉到微风q游戏的主角是一个智能体，可以进入相邻的房间游戏的主角是一个智能体，可以进入相邻的房间（对角线不可以）（对角线不可以）q智能体有且仅有一支箭，用这支箭可以射杀怪物智能体有且仅有一支箭，用这支箭可以射杀怪物q某个房间中有金子，游戏的目标是智能体找到金子某个房间中有金子，游戏的目标是智能体找到金子怪物洞穴n智能体行动的关键是要智能体行动的关键是要根据获得

4、的信息推理，根据获得的信息推理，从而判断那个房间有怪从而判断那个房间有怪物，那个房间有陷阱，物，那个房间有陷阱，那个房间是安全的那个房间是安全的n房间房间4,2和和2,3有陷有陷阱，房间阱，房间3,4有怪物，有怪物，房间房间4,3有金子有金子3.1 命题逻辑3.1 命题逻辑n命题命题能够判断真假的陈述句能够判断真假的陈述句q陈述句陈述句q真值唯一，真值唯一， 可用二进制表示可用二进制表示q用小写字母进行标识用小写字母进行标识n例例1、北京是中国的首都。、北京是中国的首都。2、长安大学位于钟楼附近。、长安大学位于钟楼附近。3、 1+1=2 4、计算机系的学生必修、计算机系的学生必修C或或JAVA

5、。5、坐着花生过黄河、坐着花生过黄河5、x+1=26、吃饭了吗？、吃饭了吗？7、南无阿弥陀佛、南无阿弥陀佛8、我正在说假话、我正在说假话3.1 命题逻辑n简单命题与复合命题简单命题与复合命题q简单命题：（原子命题）简单命题：（原子命题）一个命题无法分解为更简单的子命题一个命题无法分解为更简单的子命题q复合命题：复合命题： 由简单命题用联结词联结而成的命题由简单命题用联结词联结而成的命题 1、由若干简单命题组成；、由若干简单命题组成； 2：由联结词联结：由联结词联结例：例：1、北京是中国的首都。、北京是中国的首都。2、长安大学位于钟楼附近。、长安大学位于钟楼附近。3、计算机系的学生必修、计算机系

6、的学生必修C或或JAVA。4、这家的报价单配置合理并且价格低廉。、这家的报价单配置合理并且价格低廉。5、“李四是犯罪嫌疑人李四是犯罪嫌疑人” “李四有犯罪动机李四有犯罪动机” 3.1 命题逻辑n合式公式：合式公式：q单个常量或者变量的命题构成合式公式单个常量或者变量的命题构成合式公式q联结词联结的合式公式的组合也是合式公式联结词联结的合式公式的组合也是合式公式q合式公式的有限次组合称为命题公式合式公式的有限次组合称为命题公式n命题公式：有限次合式公式组合的形式化描述，命题公式：有限次合式公式组合的形式化描述，本书中以大写字母标识。本书中以大写字母标识。3.1 命题逻辑n基本联结基本联结(连接连

7、接)符号符号q 非，否定非，否定, q 与，合取，与，合取，AND的首字母的首字母q 或，析取，或，析取，velq 蕴含蕴含 式式A： a b表示，如果表示，如果a为真，则为真，则b为真。为真。q 等价等价n联结符号的优先级联结符号的优先级 3.1 命题逻辑n将命题从语言表述转换为命题公式将命题从语言表述转换为命题公式step1、找出简单命题，并用符号表示、找出简单命题，并用符号表示step2、分析简单命题间的逻辑关系，用联结符号进行描述、分析简单命题间的逻辑关系，用联结符号进行描述例例1、3不是偶数不是偶数令：令：p表示表示“3是偶数是偶数”，p2、教室里有、教室里有30名男生和名男生和10

8、名女生名女生令：令：p表示表示“教室里有教室里有30名男生名男生”， q表示表示“教室里有教室里有10名女生名女生” pq3、如果天下雨，出门带伞、如果天下雨，出门带伞令令p表示表示“天下雨天下雨”，q表示表示“出门带伞出门带伞”pq4、只要不下雨，我就骑自行车上班、只要不下雨，我就骑自行车上班令令p表示表示“天下雨天下雨”，q表示表示“骑自行车上班骑自行车上班” pq5、只有不下雨，我才骑自行车上班、只有不下雨，我才骑自行车上班令令p表示表示“天下雨天下雨”，q表示表示“骑自行车上班骑自行车上班” q p3.1 命题逻辑n例：怪物洞穴例：怪物洞穴 q如果房间如果房间1,1中有臭味，则房间中有

9、臭味，则房间1,2或或2,1中中有怪物有怪物 表示房间表示房间i,j中有臭味中有臭味 表示房间表示房间i,j中有怪物中有怪物 练习：如果房间练习：如果房间1,1中没有臭味，中没有臭味，则房间则房间1,2和和2,1中没有怪物中没有怪物3.1 命题逻辑n练习：扫雷游戏练习：扫雷游戏q设设Xi,j表示方格表示方格i,j中中有一个地雷。有一个地雷。q写出方格写出方格1,1周围恰好周围恰好有有2颗地雷的命题公式颗地雷的命题公式1 2 3 4 5 543213.1 命题逻辑n命题公式的赋值命题公式的赋值q对命题公式中的所有的命题变量各赋给一个值对命题公式中的所有的命题变量各赋给一个值0，1。n真值表真值表

10、pqppqpqpqpq000110113.1 命题逻辑n复合命题的真值复合命题的真值例：例：p: 周杰伦是一个流行歌手周杰伦是一个流行歌手q: 人工智能是计算机科学的一个分支人工智能是计算机科学的一个分支 r: 牛在天上飞牛在天上飞求下列复合命题的真值求下列复合命题的真值pqpq(pq)(pq) r(qr)(pr)pr(pr)(pr)我们关心的是复合命题中命题之间的真值关系，我们关心的是复合命题中命题之间的真值关系，而不关心命题的内容。而不关心命题的内容。 3.1 命题逻辑n命题公式的分类命题公式的分类q重言式或永真式重言式或永真式 tautology ，n设设A为任一命题公式，若为任一命题公

11、式，若A在它的各种赋值下取值均为真，则称在它的各种赋值下取值均为真，则称A是重言式是重言式例：例：PPq矛盾式或永假式矛盾式或永假式 contradictory n设设A为任一命题公式，若为任一命题公式，若A在它的各种赋值下取值均为假，则称在它的各种赋值下取值均为假，则称A是永假式。是永假式。例：例： P P3.1 命题逻辑q可满足式可满足式 satisfiablen设设A为任一为任一命题命题公式，如果存在一组取值使公式，如果存在一组取值使A为真，则为真，则A为可满为可满足式。足式。n即：对于命题公式即：对于命题公式A，若，若A不是矛盾式，则称不是矛盾式，则称A是可满足式。是可满足式。 例：例

12、：PQ q非重言式的可满足式非重言式的可满足式 既是可满足式，又不是重言式既是可满足式，又不是重言式3.1 命题逻辑n等值逻辑运算等值逻辑运算q 逻辑等值，等号连接的命题公式等价，逻辑等值，等号连接的命题公式等价，q基本等值算式基本等值算式 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

13、B) A B； (A B) A B；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 ；3.1 命题逻辑n合取范式与析取范式合取范式与析取范式q简单析取式：有限个命题变元或其否定，析取联

14、结符简单析取式：有限个命题变元或其否定，析取联结符 pq; p q ; p ; qq合取范式：有限个简单析取式，合取合取范式：有限个简单析取式，合取 p(pq) (p q)q简单合取式：有限个命题变元或其否定，合取简单合取式：有限个命题变元或其否定，合取 p q; p q ; p ; qq析取范式：有限个简单合取式，析取析取范式：有限个简单合取式，析取 p (p q) (p q)3.1 命题逻辑n任意命题公式都存在等值的析取范式和合取范任意命题公式都存在等值的析取范式和合取范式式n求取合取范式的步骤求取合取范式的步骤1、利用蕴含等值式和等价等值式消去命题公式中除、利用蕴含等值式和等价等值式消去

15、命题公式中除，以外的联结词以外的联结词 2、利用摩根律、双重否定律等进行置换，将、利用摩根律、双重否定律等进行置换，将移到括移到括号里面号里面3、 利用分配律得到合取范式利用分配律得到合取范式3.1 命题逻辑n例例 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

16、q ) ( p s r) ; 分配分配律律3.1 命题逻辑n例例 P82q计算计算 (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 ) ; 等幂律等幂律3.1 命题逻辑n课堂练习课堂练习 计算合取范式计算合取范式 (pq) (q p) (pq) q p3.1 命题逻辑n命题逻辑推理命题逻辑推理n逻辑结论：如果

17、逻辑结论：如果AB为重言式，则称为重言式，则称B是是A的逻辑结的逻辑结论，记作论，记作A=B。n常用推理定律：常用推理定律：附加：附加： 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 )3.1 命题逻辑n命题逻辑推理规则命题逻辑推理规则q前提引入

18、规则前提引入规则 任何证明的步骤上，都可以引入前提；任何证明的步骤上，都可以引入前提；q结论引入规则结论引入规则 任何证明的步骤上，所得到的结论都可以作为后续任何证明的步骤上，所得到的结论都可以作为后续证明的前提；证明的前提；q置换规则置换规则 任何证明的步骤上，命题公式中任何子命题都可以任何证明的步骤上，命题公式中任何子命题都可以用与之等值的命题公式置换；用与之等值的命题公式置换；3.1 命题逻辑n例：例：P84 如果今天下雨，则要带雨伞或雨衣。如果走路上班；如果今天下雨，则要带雨伞或雨衣。如果走路上班；则不带雨衣。今天下雨，走路上班，证明要带伞。则不带雨衣。今天下雨，走路上班，证明要带伞。

19、解：解： 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 析取三段论：析取三段论：3.1 命题逻辑n例例 怪物洞穴怪物洞穴 表示房间表示房间i,j中有臭中有臭味味 表示房间表示房间i,j中有怪中有怪物物 表示房间表示房间i,j中有

20、微中有微风风 表示房间表示房间i,j中有陷中有陷阱阱3.1 命题逻辑n初始状态，在房间初始状态，在房间1,1处没有感觉到微风，也没有臭味，处没有感觉到微风，也没有臭味，则相邻房间为安全的，既没有怪物也没有陷阱。则相邻房间为安全的，既没有怪物也没有陷阱。前提：前提： 结论：结论：证明：证明： 前提引入前提引入 等价等值式等价等值式 简化简化 前提引入前提引入 拒取式拒取式 摩根律摩根律3.1 命题逻辑n归结原理归结原理q证明的一般方法证明的一般方法n由已知条件正向推导结论，演绎推理由已知条件正向推导结论，演绎推理n假定结论不成立，逆向推导与已知条件矛盾，反证法假定结论不成立，逆向推导与已知条件矛

21、盾，反证法q命题逻辑证明的归谬思想命题逻辑证明的归谬思想 P85归结原理的思想：如果证明归结原理的思想：如果证明AB为永假式，则得证为永假式，则得证归结推理命题逻辑谓词逻辑Skolem标准形、子句集基本概念谓词逻辑归结原理合一和置换、控制策略数理逻辑命题逻辑归结Herbrand定理3.1 命题逻辑n归结方法的思想归结方法的思想q1、将待证明问题转化为其逆否命题、将待证明问题转化为其逆否命题例：条件例：条件 A，求证，求证B. 即即 AB 其逆否命题为：其逆否命题为： ABq2、求合取范式，得到子句集、求合取范式，得到子句集构成合取范式的有限个简单析取式构成的集合就是子句集构成合取范式的有限个简

22、单析取式构成的集合就是子句集q3、对子句集进行归结，得到空子句、对子句集进行归结，得到空子句 3.1 命题逻辑n将待证明问题转化为其逆否命题将待证明问题转化为其逆否命题q证明问题的一般形式：证明问题的一般形式： 已知：已知：A成立成立 求证：求证：B成立成立 即：证明即：证明 AB A B AB 蕴含等值式蕴含等值式 (AB) 摩根率摩根率 AB即为原命题的逆否命题即为原命题的逆否命题3.1 命题逻辑n例：证明例：证明 G是是F的逻辑结论的逻辑结论F1：PWF2：WG：P分析：已知条件分析：已知条件为： (PW) (W) 结论为：P 则，逆否命，逆否命题为： (PW) (W)3.1 命题逻辑n

23、子句与子句集子句与子句集 P86q对问题的逆否命题，求其合取范式对问题的逆否命题，求其合取范式q对于一个合取范式，该范式中的每一条简单析取式对于一个合取范式，该范式中的每一条简单析取式都是一个子句。都是一个子句。q子句集：合取范式下的所有子句构成其子句集。子句集：合取范式下的所有子句构成其子句集。例： p(pq) (p q)子句集为子句集为 p, pq, p q3.1 命题逻辑n归结方法归结方法 q如果如果pq与与 q r都为真，则都为真，则pr为真为真n证明证明1 真值表真值表ppqq q q rrpr1-10110111n证明证明2前提：前提： (pq)( q r ) 结论：结论： pr证

24、明证明: (pq)( q r ) (p q) (q r ) 蕴含等值式与双重否定律蕴含等值式与双重否定律 = (p r) 假言三段论假言三段论 pr 蕴含等值式蕴含等值式 3.1 命题逻辑n归结式归结式 q例例 pq, p q 归结后为归结后为: q n归结的目标归结的目标空子句空子句q对于一个合取范式，如果有一个子句不可满足，则子句集就对于一个合取范式，如果有一个子句不可满足，则子句集就不可满足，该合取范式为永假式不可满足，该合取范式为永假式q若一个子句集中包含空子句，则这个子句集一定是不可满足若一个子句集中包含空子句，则这个子句集一定是不可满足的的 q例：例：p, p归结后为归结后为 3.

25、1 命题逻辑n归结法步骤归结法步骤q建立待归结命题公式。将证明建立待归结命题公式。将证明AB为真转化为证明为真转化为证明A B为矛盾式为矛盾式q求合取范式，得到子句集求合取范式，得到子句集q对子句集进行归结对子句集进行归结n归结式作为新子句加入子句集进行归结归结式作为新子句加入子句集进行归结n当归结式为空子句当归结式为空子句时停止，证明结束。时停止，证明结束。n出现空子句出现空子句 ，表示该子句集不可满足，表示该子句集不可满足n归结法的完备性：如果归结法的完备性：如果AB成立，则利用归成立，则利用归结法一定可以得到证明结法一定可以得到证明3.1 命题逻辑n例：证明例：证明(pq) (q p)证

26、明：证明： 要证明原命题为真，只需证明要证明原命题为真，只需证明(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 3.1 命题逻辑n例：怪兽洞穴例：怪兽洞穴q1、在房间、在房间1,1处没有感处没有感觉到微风，也没有臭味。觉到微风，也没有臭味。q2、在房间、在房间1

27、,2处感觉到处感觉到微风，但没有感觉到臭味。微风，但没有感觉到臭味。q3、在房间、在房间1,2处没有感处没有感觉到微风，但感觉到臭味。觉到微风，但感觉到臭味。n求证：房间求证：房间3,1处有怪处有怪物物*；房间；房间1,3处有洞处有洞穴；房间穴；房间2,2是安全的。是安全的。3.1 命题逻辑前提：前提：求证：求证：证明：要证明原命题为真，只需证明以下命题为恒假证明：要证明原命题为真，只需证明以下命题为恒假 3.1 命题逻辑于是，得到子句集为：于是，得到子句集为：3.1 命题逻辑命题逻辑1 s1,22 w1,13 s2,14 s2,1 w1,1 w2,2 w3,1 5 s1,2 w1,1 6 s

28、1,2 w2,27 w3,1 8 w1,1 w2,2 w3,1 3, 4归结归结 9 w2,2w3,1 8,2归结归结10 w2,2 9,7归结归结11 s1,2 10,6归结归结12 11,1归结归结3.1 命题逻辑n思考：思考：q归结算法的计算机实现？归结算法的计算机实现？ S0,S1,S2,S3 终止条件：终止条件： 1、生成了空子句，证明结束、生成了空子句，证明结束 2、循环结束，没有可以添加的新语句，待证明的定、循环结束，没有可以添加的新语句，待证明的定理不成立理不成立 3.1 命题逻辑q好的归结控制策略好的归结控制策略 初始状态优先选择包含结论的子句进行归结，之后初始状态优先选择包

29、含结论的子句进行归结，之后每次都选择上一次归结得到的归结式与其他子句归结每次都选择上一次归结得到的归结式与其他子句归结q容易犯的错误容易犯的错误 字句集字句集 1、PQ 2、PQ 3 、 1 、 2归结归结3、Q Q 1 、 2归结归结不允许同时归结两个项不允许同时归结两个项3.1 命题逻辑n归结方法是一种机械化的归结方法是一种机械化的,可在计算机上加以可在计算机上加以实现的推理方法实现的推理方法n归结方法归结方法是一种反向推理形式是一种反向推理形式n提供了一种自动定理证明的方法提供了一种自动定理证明的方法n归结的半完备性归结的半完备性q当定理可以证明时，归结方法是完备的当定理可以证明时，归结

30、方法是完备的q当定理不可证明时，归结方法得不到任何结论，算当定理不可证明时，归结方法得不到任何结论，算法不一定会停止法不一定会停止3.2 谓词逻辑3.2 谓词逻辑3.2.1 基本概念n命题逻辑描述简单的陈述性命题，但表示量化命题逻辑描述简单的陈述性命题，但表示量化和谓词过于繁琐，也难以表示个体间的关系和谓词过于繁琐，也难以表示个体间的关系例：现在课堂上的所有学生都在上人工智能课例：现在课堂上的所有学生都在上人工智能课命题逻辑命题逻辑s1 : 张三在上人工智能课张三在上人工智能课s2 : 李四在上人工智能课李四在上人工智能课s3 : 王五在上人工智能课王五在上人工智能课 例例2：用命题逻辑归结原

31、理证明：用命题逻辑归结原理证明：“人都是妈生人都是妈生的，张飞是人，所以张飞是妈生的的，张飞是人，所以张飞是妈生的”p :人都是妈生的人都是妈生的q :张飞是人张飞是人r :张飞是妈生的张飞是妈生的(pq)r pqr3.2 谓词逻辑3.2.1 基本概念q谓词逻辑谓词逻辑Class(x)表示表示x在上人工智能课在上人工智能课 x=张三，就得到了张三，就得到了s1； x=李四，就得到了李四，就得到了s2； x=王五，就得到了王五，就得到了s3； Class(x,y)表示表示x在上在上y课课x=张三，张三， y=人工智能，表示张三在上人工智能课人工智能，表示张三在上人工智能课x=李四，李四， y=线

32、性代数，表示李四在上线性代数课线性代数，表示李四在上线性代数课x=王五，王五， y=睡觉，表示王五在上睡觉课睡觉，表示王五在上睡觉课3.2 谓词逻辑3.2.1 基本概念n命题是一个陈述句，它一般可分成主语和谓语两部分。有命题是一个陈述句，它一般可分成主语和谓语两部分。有时还需要用到量词。时还需要用到量词。n主语：指独立存在的客体，可以是具体事物或抽象概念，主语：指独立存在的客体，可以是具体事物或抽象概念，也称为个体也称为个体n谓词：描述个体词性质或个体之间关系的词谓词：描述个体词性质或个体之间关系的词n个体域：表示个体变量的取值范围，常用个体域：表示个体变量的取值范围，常用D表示表示n常量：表

33、示具体性质或关系的个体或者谓词常量：表示具体性质或关系的个体或者谓词n变量：表示抽象或泛指的个体或者谓词。变量：表示抽象或泛指的个体或者谓词。n量词：表示数量的词。量词：表示数量的词。q任意量词任意量词：表示：表示“任意任意”，“所有所有”，也称为全称量词，也称为全称量词q存在量词存在量词：表示：表示“存在存在”3.2 谓词逻辑3.2.1 基本概念n例：例：“关羽是人关羽是人”，“张飞是人张飞是人”q这是两个不同的命题，其主语（个体）不同这是两个不同的命题，其主语（个体）不同q但是谓词是相同的，但是谓词是相同的，“是人是人”q把谓语部分抽出来，假设把谓语部分抽出来，假设 Human(x)表示表

34、示x是人是人q这两个命题都可以用这个谓词来描述这两个命题都可以用这个谓词来描述 Human(guanyu) Human(zhangfei)q其中其中nx属于个体变量，属于个体变量，nguanyu和和zhangfei属于个体常量属于个体常量 3.2 谓词逻辑3.2.1 基本概念n例：例：1、所有的人都是要死的、所有的人都是要死的2、有的人能够活到、有的人能够活到100岁岁 P(x)表示表示x是要死的，是要死的， Q(x)表示表示x活到活到100岁岁q个体域个体域D为人类集合为人类集合q个体域个体域D为总个体域集合为总个体域集合n引入特殊谓词引入特殊谓词R(x)表示表示x是人是人3.2 谓词逻辑n

35、语言描述转换为谓词公式语言描述转换为谓词公式q1、确定并说明谓词、确定并说明谓词q2、确定个体和个体域、确定个体和个体域q3、确定量词、确定量词q4、判断谓词间的逻辑关系、判断谓词间的逻辑关系3.2 谓词逻辑n例：我是计算机系的学生例：我是计算机系的学生1、确定并说明谓词：、确定并说明谓词： 方法一：方法一：Student(x,y) 表示表示X是是Y系的学生系的学生2、个体域：、个体域：X：学生的集合，：学生的集合，y：系的集合：系的集合 Student(I,computer) 方法二：方法二：Computer(x) 表示表示X是计算机系的学生是计算机系的学生 Computer(I) 注意：必

36、须对谓词进行说明注意：必须对谓词进行说明 P(I,computer) 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：人的集合：人的集合逻辑关系：与逻辑关系：与3.2 谓词逻辑n例：任何人的兄弟都是男性例：任何人的兄弟都是男性q确定并说明谓词确定并说

37、明谓词Brother(x,y) 表示表示x是是y的兄弟的兄弟Male(x)表示表示x是男性是男性q个体域个体域 Brother(x,y) x、y：人的集合：人的集合 Male(x) x ：人的集合：人的集合q量词量词 任意任意q确定逻辑关系确定逻辑关系 与？或？非？蕴含？等价？与？或？非？蕴含？等价？ 3.2 谓词逻辑n例：不管黑猫白猫，抓住老鼠就是好猫例：不管黑猫白猫，抓住老鼠就是好猫q定义并说明谓词定义并说明谓词 Cat(x,y)表示是表示是x是是y颜色的猫颜色的猫 Goodcat(x)表示表示x是好猫是好猫 Catch(x,Mouse)表示表示x能抓住老鼠能抓住老鼠q个体域个体域 x:

38、猫的集合，猫的集合，y：颜色的集合：颜色的集合q谓词间的关系谓词间的关系 Cat(x,y)与与Catch(x,Mouse)蕴含蕴含Goodcat(x)q量词：量词： 任意任意 3.2 谓词逻辑3.2.1 基本概念n量词使用中的注意事项量词使用中的注意事项q不同的个体域中，命题符号化的形式可能不同不同的个体域中，命题符号化的形式可能不同q没有给定个体域的情况下，应考虑全总个体域没有给定个体域的情况下，应考虑全总个体域q如果个体域为有限集如果个体域为有限集 ，对任意谓词，对任意谓词P(x)有：有：q多个量词同时出现时，不能颠倒其先后顺利，否则多个量词同时出现时，不能颠倒其先后顺利，否则会改变公式的

39、含义。会改变公式的含义。3.2 谓词逻辑3.2.1 基本概念n例：例：love(x,y)表示表示x喜爱喜爱y 表示对任意的表示对任意的x，都存在喜爱的对象，都存在喜爱的对象y，即，即“每一个每一个人都会喜爱某人人都会喜爱某人” 表示存在都一个表示存在都一个y ，任意的人，任意的人x 都喜爱他，即都喜爱他，即 “上帝上帝” 3.2 谓词逻辑谓词逻辑3.2.2 一阶谓词逻辑一阶谓词逻辑n原子公式：设原子公式：设 是任意是任意n元谓词，元谓词， 是项，则称是项，则称 为原子公式。为原子公式。n项：项：q任何常量是项。任何常量是项。 q任何变量是项。任何变量是项。 qn 1 个参数的任何表达式个参数的

40、任何表达式 （其中，（其中， 是项，而是项，而 f 是是 n 阶的函数）是项。阶的函数）是项。 q闭包条款：闭包条款： 其他东西都不是项。其他东西都不是项。 3.2 谓词逻辑谓词逻辑3.2.2 一阶谓词逻辑一阶谓词逻辑n谓词公式谓词公式q原子公式是谓词公式。原子公式是谓词公式。q若若A为谓词公式，则为谓词公式，则A也是一个谓词公式。也是一个谓词公式。q若若A和和B都是都是谓词谓词公式，则公式，则(A B)，(A B)，(AB)和和(A B)也都是也都是谓词谓词公式。公式。q若若A是是谓词谓词公式，公式， 和和 也都是也都是谓词谓词公式。公式。q只有有限次应用上述规则得到的公式，才是只有有限次应

41、用上述规则得到的公式，才是谓词谓词公公式。式。 3.2 谓词逻辑谓词逻辑3.2.2 一阶谓词逻辑一阶谓词逻辑n对于对于 ，qx称为指导变量称为指导变量 qA称为相应量词的称为相应量词的辖域辖域 x(p(x)qx在辖域在辖域A中的出现称为约束出现中的出现称为约束出现qx以外的变量在辖域以外的变量在辖域A中的出现称为自由出现中的出现称为自由出现 x(p(x,y)对于对于 ， 指导变量：指导变量： 的辖域：的辖域： x, y都都是约束出现是约束出现3.2 谓词逻辑谓词逻辑3.2.2 一阶谓词逻辑一阶谓词逻辑n例例对于对于 ， 指导变量指导变量: 的辖域的辖域: x、y是约束出现还是自由是约束出现还是

42、自由出现出现 y是约束出现，是约束出现， x是自由出现是自由出现3.2 谓词逻辑谓词逻辑3.2.2 一阶谓词逻辑一阶谓词逻辑n不同量词如果采用相同的指导变量名，易引起不同量词如果采用相同的指导变量名，易引起混淆混淆n一般要求不同的量词使用不同的指导变量名称一般要求不同的量词使用不同的指导变量名称3.2 谓词逻辑谓词逻辑3.2.2 一阶谓词逻辑一阶谓词逻辑n当在一个公式中，一个变量符号既是约束出现的变量，当在一个公式中，一个变量符号既是约束出现的变量，又是自由出现的变量时，需要作变量符号更换。又是自由出现的变量时，需要作变量符号更换。n换名规则：将量词辖域中某个约束出现的变量及其换名规则：将量词

43、辖域中某个约束出现的变量及其指指导变量导变量替换为此辖域中未出现过的个体变量符号替换为此辖域中未出现过的个体变量符号 x既作为指导变量约束出现又自由出现，因此要既作为指导变量约束出现又自由出现，因此要换掉其中之一换掉其中之一 换名规则更换的是指导变量换名规则更换的是指导变量 可替换为可替换为3.2 谓词逻辑谓词逻辑3.2.2 一阶谓词逻辑一阶谓词逻辑n替代规则：对某替代规则：对某自由出现的个体变量自由出现的个体变量用与原公用与原公式中未出现过的变量符号去替代，且式中未出现过的变量符号去替代，且处处替代处处替代。 x既作为指导变量约束出现又自由出现，既作为指导变量约束出现又自由出现，且多处自由出

44、现且多处自由出现 替代规则更换的是自由出现的变量，且处替代规则更换的是自由出现的变量，且处处替代处替代 替换为替换为3.2 谓词逻辑谓词逻辑3.2.2 一阶谓词逻辑一阶谓词逻辑n谓词公式的解释谓词公式的解释q对谓词公式中的各种变量制定具体的常量去替代对谓词公式中的各种变量制定具体的常量去替代q一个解释包括一个解释包括n非空个体域非空个体域 Dn D中一部分特定元素；中一部分特定元素；n D上一些特定的函数；上一些特定的函数；n D上一些特定的谓词。上一些特定的谓词。q如果谓词公式在特定解释下为真，称这个解释满足如果谓词公式在特定解释下为真，称这个解释满足这个谓词公式，是这个谓词公式的一个模型这

45、个谓词公式，是这个谓词公式的一个模型q永真与不可满足永真与不可满足3.2 谓词逻辑谓词逻辑3.2.2 一阶谓词逻辑一阶谓词逻辑n例：例：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、3.2 谓词逻辑谓词逻辑3.2.2 一阶谓词逻辑一阶谓词逻辑n解解 1、 = (

46、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) =13.2 谓词逻辑谓词逻辑3.2.3 谓词演算与推理谓词演算与推理n谓词演算公式谓词演算公式q约束变量换名规则，约束变量换名规则，Q为任意量词为任意量词 (Qx)P(x) (Qy)P(y) (Qx)P(x,z) (Qy)P(y,z) q量词消去等值式，对于有穷个体域量词消去等值式，对于有穷个体域q量词否定等值式量词否定等值式q量词分配等值式量

47、词分配等值式3.2 谓词逻辑谓词逻辑3.2.3 谓词演算与推理谓词演算与推理q量词辖域收缩与扩张等值式量词辖域收缩与扩张等值式3.2 谓词逻辑谓词逻辑3.2.4 谓词知识表示谓词知识表示n谓词逻辑表达的规范形式谓词逻辑表达的规范形式P是谓词，而是谓词，而 表示个体（主体或者客体）表示个体（主体或者客体）n知识库：表达知识的一组谓词公式的集合。知识库：表达知识的一组谓词公式的集合。q语句的集合语句的集合q对环境、规则等信息的结构化描述对环境、规则等信息的结构化描述q基于知识的智能体的核心构件基于知识的智能体的核心构件3.2 谓词逻辑谓词逻辑3.2.4 谓词知识表示谓词知识表示n定义谓词定义谓词例

48、例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) 参数分别对应有没有微风、臭味、怪物、参数分别对应有没有微风、臭味、怪物、陷阱、金子陷阱、金子 R

49、oomi,j( 1, 1, 0, 0, 0)3.2 谓词逻辑谓词逻辑3.2.4 谓词知识表示谓词知识表示n例：例： 准前女友准前女友q双眼皮双眼皮,大眼睛大眼睛doublefold(x) bigeyes(x)q一头乌黑的头发一头乌黑的头发blackhair(x) thickhair(x)q一身漂亮的呢子大衣一身漂亮的呢子大衣beautifuldress(x)q走路的姿态赛过模特走路的姿态赛过模特graceful(x)3.2 谓词逻辑谓词逻辑3.2.4 谓词知识表示谓词知识表示n知识表示知识表示 例例 P97 房间里有机器人房间里有机器人Robot、积木块、积木块Box 、两个桌子两个桌子A和和

50、B 。q定义谓词定义谓词Table(A) A是桌子是桌子 EmptyHanded(Robot) 机器人空手机器人空手At(Robot, A) 机器人位置在机器人位置在A旁旁Holds(Robot, Box) 机器人拿着机器人拿着BoxOn(Box,A) Box在桌子在桌子A上上3.2 谓词逻辑谓词逻辑3.2.4 谓词知识表示谓词知识表示q初始状态初始状态EmptyHanded(Robot)At(Robot, A)On(Box,A)Table(A)Table(B)q机器人拿起机器人拿起BoxAt(Robot, A)Holds(Robot, Box)Table(A)Table(B)3.2 谓词逻辑

51、谓词逻辑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)3.2 谓词逻辑谓词逻辑3.2.3 谓词演算与推理谓词演算与推理n前束范式前束范式约

52、束在前面的范式约束在前面的范式q将所有的量词都移到最左边就得到了前束范式将所有的量词都移到最左边就得到了前束范式n与合取范式类似，所有的谓词公式都可以改写成前束与合取范式类似，所有的谓词公式都可以改写成前束范式的形式范式的形式n求前束范式的步骤求前束范式的步骤q前束范式中每个量词的指导变量不同，如果指导变量相同，前束范式中每个量词的指导变量不同，如果指导变量相同，则需要利用换名规则进行替换。则需要利用换名规则进行替换。q如果自由变量与指导变量相同，则需利用换名规则或替代规如果自由变量与指导变量相同，则需利用换名规则或替代规则替换其中之一则替换其中之一q利用量词辖域收缩扩张等值式替换利用量词辖域

53、收缩扩张等值式替换3.2 谓词逻辑谓词逻辑3.2.3 谓词演算与推理谓词演算与推理n例例 P94 求前束范式求前束范式量词与指导变量：量词与指导变量： ，自由出现的变量：自由出现的变量： ， 换名规则换名规则 替代规则替代规则 P93 3-7 3.2 谓词逻辑谓词逻辑3.2.3 谓词演算与推理谓词演算与推理 P93 3-8 P93 3-3 P93 3-43.2 谓词逻辑谓词逻辑3.2.3 谓词演算与推理谓词演算与推理n谓词推理谓词推理q例：例： 20世纪世纪70年代的漫画都是日本漫画家创作的，这幅漫画是年代的漫画都是日本漫画家创作的，这幅漫画是20世纪世纪70年代的作品；因此它是日本漫画家的作

54、品年代的作品；因此它是日本漫画家的作品解：设解：设P(x)：属于：属于20世纪世纪70年代的漫画年代的漫画 Q(y)：属于日本漫画家的作品：属于日本漫画家的作品 a : 一幅漫画一幅漫画 前提前提: 结论结论: Q(a) 证明证明: 前提引入前提引入 量词消去量词消去 前提引入前提引入 假言推理假言推理3.3 谓词逻辑归结原理3.3 谓词逻辑归结原理谓词逻辑归结原理3.3.1 归结原理归结原理n命题逻辑归结原理：命题逻辑归结原理：q将由前提将由前提A得到结论得到结论B的证明过程转化为证明的证明过程转化为证明A B为矛盾式为矛盾式q将其转化为合取范式，得到子句集将其转化为合取范式，得到子句集 对

55、于形如对于形如 的公式求取子句集时，可的公式求取子句集时，可以分别求以分别求 各自的子句集，再取并集各自的子句集，再取并集q利用归结原理消去互补项，利用归结原理消去互补项，q直到得到空子句。直到得到空子句。 3.3 谓词逻辑归结原理谓词逻辑归结原理3.3.1 归结原理归结原理n例例 (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)

56、(P R) (P Q) (P R) (P Q) (P R) (P Q) (P R) (P Q) (P R)子句集为：子句集为：PQR, P Q, P, R3.3 谓词逻辑归结原理谓词逻辑归结原理3.3.1 归结原理归结原理归结：归结： 1、 PQR 2、 P Q 3、P 4、R 5、 PR 1、2归结归结 6、 R 3、5归结归结 7、 4、6归结归结因此得证因此得证3.3 谓词逻辑归结原理谓词逻辑归结原理3.3.1 归结原理归结原理步骤步骤命题逻辑归结原理命题逻辑归结原理谓词逻辑归结原理谓词逻辑归结原理1、建立、建立AB命题逻辑公式命题逻辑公式谓词逻辑公式谓词逻辑公式2、求子、求子句集句集求

57、合取范式求合取范式求前束合取范式求前束合取范式消去量词消去量词3、归结、归结直接消去互补项直接消去互补项利用置换与合一消去利用置换与合一消去互补项互补项归结式加入子句集归结式加入子句集归结式加入子句集归结式加入子句集3.3 谓词逻辑归结原理谓词逻辑归结原理3.3.1 归结原理归结原理n谓词逻辑归结原理的重点谓词逻辑归结原理的重点q如何对前束合取范式消去量词如何对前束合取范式消去量词 命题逻辑命题逻辑 谓词逻辑谓词逻辑q如何利用置换与合一对不同变量的子句进行置换如何利用置换与合一对不同变量的子句进行置换 命题逻辑命题逻辑 谓词逻辑谓词逻辑3.3 谓词逻辑归结原理谓词逻辑归结原理3.3.1 归结原

58、理归结原理n求前束合取范式：求前束合取范式：q方法一：先转化为前束范式，再将辖域中的谓词公式转化为方法一：先转化为前束范式，再将辖域中的谓词公式转化为合取范式合取范式q方法二：方法二：(1)消去联结词消去联结词 和和。 (2)将联结词将联结词向内深入，使之只作用于原子公式。向内深入，使之只作用于原子公式。 (3)利用换名或替代规则使所有约束变元的符号都不同，并且自利用换名或替代规则使所有约束变元的符号都不同，并且自由变元与约束变元的符号也不同。由变元与约束变元的符号也不同。 (4)利用量词辖域的扩张和收缩，扩大量词至整个公式。利用量词辖域的扩张和收缩，扩大量词至整个公式。 (5)再将辖域中的谓

59、词公式转化为合取范式。再将辖域中的谓词公式转化为合取范式。3.2 谓词逻辑谓词逻辑3.2.3 谓词演算与推理谓词演算与推理q量词辖域收缩与扩张等值式量词辖域收缩与扩张等值式3.2 谓词逻辑谓词逻辑3.2.3 谓词演算与推理谓词演算与推理n求前束合取范式求前束合取范式 ( 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、辖域中的公式辖域中的公式化为合取范式化为合取范式3.3

60、 谓词逻辑归结原理谓词逻辑归结原理3.3.2 Skolem标准型标准型n例例 求前束合取范式求前束合取范式 3.3 谓词逻辑归结原理谓词逻辑归结原理3.3.2 Skolem标准型标准型nSkolem标准型：对前束合取范式消去所有的标准型：对前束合取范式消去所有的量词。量词。P100q第一步：消去存在量词第一步：消去存在量词 ：1、如果、如果 之前之前(左边左边)没有任意量词没有任意量词 , 则用常量替换则用常量替换 的指导的指导变量变量 可用常量可用常量b替换替换x消去存在量词，得消去存在量词，得P(b,a)2、如果、如果 之前之前(左边左边)有任意量词有任意量词 ，则用任意量词的函数替，则用

61、任意量词的函数替换换 的指导变量的指导变量 可用可用f(x)替换替换y消去存在量词，消去存在量词，q第二步消去任意量词第二步消去任意量词 ：简单的省略即可：简单的省略即可3.3 谓词逻辑归结原理谓词逻辑归结原理3.3.2 Skolem标准型标准型例：例：1、消去存在量词、消去存在量词 y和和 u ： y 前面有前面有任意量词，指导变量为任意量词，指导变量为x，因此用，因此用f(x)替换替换y， u前面有前面有任意量词，指导变量为任意量词，指导变量为x，因此用，因此用g(x)替换替换u2、消去任意量词：、消去任意量词：3.3 谓词逻辑归结原理谓词逻辑归结原理3.3.2 Skolem标准型标准型n

62、例例 判断下列的消去量词的过程是否正确。判断下列的消去量词的过程是否正确。 证明：证明： 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) 成立成立3.3 谓词逻辑归结原理谓词逻辑归结原理3.3.3 子句集子句集n定义定义q文字：不含任何联结词的谓词公式文字：不含任何联结词的谓词公式q子

63、句：一些文字或其非的析取子句：一些文字或其非的析取q子句集：所有子句的集合子句集：所有子句的集合n计算过程计算过程q将谓词公式转化为前束合取范式将谓词公式转化为前束合取范式q消去存在量词，略去任意量词，得消去存在量词，略去任意量词，得Skolem标准型标准型q将各子句提出，得到子句集将各子句提出，得到子句集n谓词公式不可满足，当且仅当其子句集不可满足的谓词公式不可满足，当且仅当其子句集不可满足的n形如形如 的谓词公式在求子句集时可以分的谓词公式在求子句集时可以分别对别对 求子句，再取其并集求子句，再取其并集3.3 谓词逻辑归结原理谓词逻辑归结原理3.3.1 归结原理归结原理n谓词逻辑归结原理的

64、重点谓词逻辑归结原理的重点q如何对前束合取范式消去量词如何对前束合取范式消去量词 命题逻辑命题逻辑 谓词逻辑谓词逻辑q如何利用置换与合一对不同变量的子句进行置换如何利用置换与合一对不同变量的子句进行置换 命题逻辑命题逻辑 谓词逻辑谓词逻辑3.3 谓词逻辑归结原理谓词逻辑归结原理3.3.4 置换与合一置换与合一n置换：形如置换：形如 的有限集合的有限集合qxi 必须是变量，称为置换变量必须是变量，称为置换变量qti 可以是常量、变量或者函数，称为置换项可以是常量、变量或者函数，称为置换项q表示用项表示用项 ti 替换谓词公式中的变量替换谓词公式中的变量 xi q要求要求ti xi , xi不能不

65、能循环的循环的出现在另一个出现在另一个ti中中 x/y, y/z x/y, y/x x/y, y/z, z/x 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

66、, f(a),b)置换置换5为：为： s5=x/b3.3 谓词逻辑归结原理谓词逻辑归结原理3.3.4 置换与合一置换与合一n例：设例：设=f(y)/x , z/y,=a/x , b/y, y/z, 对对L =P(x,f(y),b)，先做，先做置换，再做置换，再做置换，置换，即求即求 3.3 谓词逻辑归结原理谓词逻辑归结原理3.3.4 置换与合一置换与合一n置换的合成：置换的合成： 对谓词公式对谓词公式L，设设=t1/x1 , t2/x2 , , tn/xn 和和=u1/y1 , u2/y2 , , un/yn 为两个置换，为两个置换，则则 , 称为称为和和的合成，可由下式的合成，可由下式得到得

67、到 1、如果、如果 ，则消去，则消去 2、当、当 ，删去，删去3.3 谓词逻辑归结原理谓词逻辑归结原理3.3.4 置换与合一置换与合一n例：设例：设=f(y)/x , z/y,=a/x , b/y, y/z 求求1、如果、如果 ti=xi , 则消去则消去ti/xi 2、当、当 ，删去，删去3.3 谓词逻辑归结原理谓词逻辑归结原理3.3.4 置换与合一置换与合一n例：对子句集例：对子句集 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( ) 3.3 谓词逻辑归结原理

68、谓词逻辑归结原理3.3.4 置换与合一置换与合一n合一：设有公式集合一：设有公式集 ，如果存在一，如果存在一个置换个置换，使，使 ， 则称则称是是F的一的一个合一。个合一。n如果谓词公式如果谓词公式F1、 F2 可合一，那么可合一，那么 就是一对互补项就是一对互补项 P(x), P(a) 经合一经合一 a/x 得到得到 P(a), P(a) n谓词逻辑归结原理：如果子句集中的两个字句谓词逻辑归结原理：如果子句集中的两个字句含有互补项，则可以进行归结消去含有互补项，则可以进行归结消去3.3 谓词逻辑归结原理谓词逻辑归结原理3.3.4置换与合一置换与合一例：下列字句都可以归结例：下列字句都可以归结

69、 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) 需要一个判断公式集能否合一的算法需要一个判断公式集能否合一的算法3.3 谓词逻辑归结原理谓词逻辑归结原理3.3.4 置换与合一置换与合一n最一般合一最一般合一(mgu)设设 是谓词公式是谓词公式F的一个合一，如果对于的一个合一，如果对于F的任意一个合一的任意

70、一个合一，都存都存在一个置换在一个置换，使，使 , ,则称则称 是一个最一般合一。是一个最一般合一。n求取办法：对每一项逐一比较并进行合一置换求取办法：对每一项逐一比较并进行合一置换P104 P104 1 1、令、令2 2、令、令3 3、如果、如果 已经合一，停止迭代，已经合一，停止迭代， ；否则，找不一致集；否则，找不一致集4 4、若、若 中存在元素中存在元素 和和 ，且，且 不出现于不出现于 中，转中，转5 5；否则，不可合；否则，不可合一一5 5、令、令 ，6 6、k=k+1, ,转转3 3 3.3 谓词逻辑归结原理谓词逻辑归结原理3.3.4 置换与合一置换与合一n例例 P(a,x,f(

71、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 3.3 谓词逻辑归结原理谓词逻辑归结原理3.3.4 置换与合一置换与合一 3 W1 未合一未合一 ，从左到右找不一致集，从左到右找不一致集， 4 5 令令 ， 6 k=k+1, ,转转3 3 3 3 W2未合一未合一 ，从左到右找不一致集，从左到右找不一致集， 4 5 令令 已合一，已合一，3.3 谓词逻辑归结原理谓词逻辑归结

72、原理3.3.5 归结式归结式n归结式：设归结式：设 为两个无公共变量的子句为两个无公共变量的子句, 分别是分别是 的文字，如果的文字，如果 可合一，则可合一，则 为为 的归结式的归结式例：例：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) 3.3 谓词逻辑归结原理谓词逻辑归结原理 3.3.

73、5 归结式归结式n几种不能归结的情况几种不能归结的情况q谓词不一致不能进行归结谓词不一致不能进行归结如：如：P(x)与与Q(x) 不能归结不能归结q常量之间不能进行归结常量之间不能进行归结如：如：P(a)与与 P(b)不能归结不能归结, 不能在常量之间置换不能在常量之间置换a/bq变量与其函数之间不能进行归结变量与其函数之间不能进行归结如：如：P(x)与与 P(f(x)不能归结，不能做置换不能归结，不能做置换f(x)/xq不能同时消去两个互补对不能同时消去两个互补对 3.3 谓词逻辑谓词逻辑归结原理 3.3.5 归结式n如果子句可以简化，应该先简化再归结如果子句可以简化，应该先简化再归结例例

74、C1可以简化，做合一置换可以简化，做合一置换 f(x)/y, 取取mgu=g(a)/x, 归结式为归结式为 Q(b) Q(g(g(a) 3.3 谓词逻辑归结原理谓词逻辑归结原理3.3.6 归结过程归结过程1.写出谓词关系公式写出谓词关系公式2.写出待归结的谓词表达式写出待归结的谓词表达式3.化为化为Skolem标准型标准型4.求子句集求子句集S5.对对S中的互补子句进行归结中的互补子句进行归结6.归结式仍加入归结式仍加入S，反复进行归结，反复进行归结7.得到空子句得到空子句8.得证得证3.3 谓词逻辑归结原理谓词逻辑归结原理3.3.6 归结过程归结过程n例：人都是妈生的，张飞是人，张飞是妈生的

75、例：人都是妈生的，张飞是人，张飞是妈生的定义谓词：定义谓词： Mum(x)表示表示x是妈生的是妈生的 Human(x)表示表示x是人是人前提：前提： x (Human(x)Mum(x), Human(ZF)结论：结论： Mum(ZF)写出逆否命题：写出逆否命题：3.3 谓词逻辑归结原理谓词逻辑归结原理3.3.6 归结过程归结过程1. Human(x) Mum(x)2. Human(ZF)3. Mum(ZF) 3与与1归结，经置换归结，经置换 得到得到4. Human(ZF) 5. 4与与2归结得到归结得到 所以，逆否命题为恒假，原命题为真所以，逆否命题为恒假，原命题为真优先选包含结论优先选包含

76、结论的子句归结的子句归结ZF/x3.3 谓词逻辑归结原理谓词逻辑归结原理3.3.6 归结过程归结过程n例：已知：例：已知： R1:会朗读的生物是识字的，会朗读的生物是识字的， R2:海豚海豚 不识字，不识字， R3: 海豚是很机灵的。海豚是很机灵的。 证明：有些很机灵的东西不会朗读。证明：有些很机灵的东西不会朗读。 分析：分析： 1、需要几个谓词？、需要几个谓词？ 2、海豚是否必须设为谓词？、海豚是否必须设为谓词？ 3、生物是否必须设为谓词？、生物是否必须设为谓词？ R (x)表示表示x会朗读会朗读W(x)表示表示x识字识字D(x)表示表示x是海豚是海豚C(x)表示表示x是机灵的是机灵的个体域

77、：生物个体域：生物3.3 谓词逻辑归结原理谓词逻辑归结原理3.3.6 归结过程归结过程结论结论换名换名3.3 谓词逻辑归结原理谓词逻辑归结原理3.3.6 归结过程归结过程4、5归结，归结，a/t6、1归结，归结，a/x7、2归结，归结，a/y8、3归结归结3.3 谓词逻辑归结原理谓词逻辑归结原理3.3.6 归结过程归结过程例：设任何通过计算机考试并获奖的人都是快乐的；任例：设任何通过计算机考试并获奖的人都是快乐的；任何肯学习或幸运的人都能通过所有的考试；张不肯学何肯学习或幸运的人都能通过所有的考试；张不肯学习但他是幸运的；任何幸运的人都能获奖。求证：张习但他是幸运的；任何幸运的人都能获奖。求证

78、：张是快乐的是快乐的 定义谓词：定义谓词： Pass(x,y) 表示表示x通过通过y考试考试 Win(x,prize) 表示表示x能获奖能获奖 Lucky(x) 表示表示x是幸运的是幸运的 Study(x) 表示表示x肯学习肯学习 Happy(x) 表示表示x是快乐的是快乐的3.3 谓词逻辑归结原理谓词逻辑归结原理3.3.6 归结过程归结过程写出谓词公式：写出谓词公式：前提：前提：结论：结论：Happy(zhang) ，取否，取否 Happy(zhang) 证明：对前提和结论分别求子句证明：对前提和结论分别求子句 3.3 谓词逻辑归结原理谓词逻辑归结原理3.3.6 归结过程归结过程n得到两个子

79、句得到两个子句3.3 谓词逻辑归结原理谓词逻辑归结原理3.3.6 归结过程归结过程n得子句得子句 Study(zhang) Lucky(zhang)n得子句得子句 Luck(w) Win(w,prize) n结论：结论： Happy(zhang) n共得到共得到7条子句条子句 3.3 谓词逻辑归结原理谓词逻辑归结原理3.3.6 归结过程归结过程1、2、3、4、 Study(zhang) 5、 Lucky(zhang)6、 Luck(w) Win(w,prize) 7、 Happy(zhang) 8、 zhang/x 1-79、 zhang/w 8-610、 9-511 、 zhang/u, c

80、omputer/v 10-312、11与与5归结，得归结，得结论结论3.3 谓词逻辑归结原理谓词逻辑归结原理 3.3.6 归结过程归结过程n例：小张和小李是同班同学；如果例：小张和小李是同班同学；如果x和和y是同班同学，则是同班同学，则x上课的教室也是上课的教室也是y上课的教室。小张在上课的教室。小张在301上课，问小李在上课，问小李在哪个教室上课？哪个教室上课？定义谓词：定义谓词：classmates(x,y) x和和y是同班同学是同班同学room(x,z) x上课的教室是上课的教室是z前提：前提： classmates(Zhang,Li) room(Zhang,301)结论：结论：取逆否：

81、取逆否：3.3 谓词逻辑归结原理谓词逻辑归结原理 3.3.6 归结过程归结过程3.3 谓词逻辑归结原理谓词逻辑归结原理 3.3.6 归结过程归结过程1 classmates(Zhang,Li)2 3 room(Zhang,301)4 567 因此，小李在因此，小李在301上课上课结论结论3.3 谓词逻辑归结原理谓词逻辑归结原理3.3.6 归结过程归结过程n本章作业本章作业qP94-95：3、9、12、16q用命题逻辑归结原理证明：用命题逻辑归结原理证明：P(Q P) (P (Q R) (P Q) (P R)q判断下列子句是否可以合一。如果可以，写出最一般合判断下列子句是否可以合一。如果可以，写

82、出最一般合一；否一；否则解解释为什么不能合一。什么不能合一。P(x,B,B), P(A,y,z)P(x,f(x),P(y,y) P(f(x,x),A),P(f(y,f(y,A),A) 3.3 谓词逻辑归结原理谓词逻辑归结原理3.3.7 归结过程控制策略归结过程控制策略n控制的要点控制的要点q要解决的问题是归结方法的知识爆炸要解决的问题是归结方法的知识爆炸q控制的目的是归结点尽可能少控制的目的是归结点尽可能少q控制的原则是删除不必要的子句或对参加归结的子控制的原则是删除不必要的子句或对参加归结的子句加以限制句加以限制q仅选择合适的子句进行归结，避免多余的、不必要仅选择合适的子句进行归结，避免多余

83、的、不必要的子句归结式出现的子句归结式出现3.3 谓词逻辑归结原理谓词逻辑归结原理3.3.7 归结过程控制策略归结过程控制策略n删除策略删除策略1、删除永真子句、删除永真子句2、删除可被其他子句归类的子句、删除可被其他子句归类的子句 归类：如果两个子句归类：如果两个子句C和和D，若有置换，若有置换，使，使 ，则称，则称子句子句C把把D归类，可从子句集中删除归类，可从子句集中删除D例：两个子句例：两个子句 C=P(x), D=P(a) Q(y) 还原为谓词公式：还原为谓词公式：P(x)(P(a) Q(y) 取置换取置换a/x，可知，可知子句子句C把把D归类，归类，D可删除可删除3.3 谓词逻辑归

84、结原理谓词逻辑归结原理3.3.7 归结过程控制策略归结过程控制策略n支撑集策略支撑集策略q一个不可满足的子句集一个不可满足的子句集S的子集的子集T，如果，如果S-T是可满是可满足的，则足的，则T为为S的支撑集的支撑集q对于对于AB定理证明问题来定理证明问题来说，说， B就是支撑集就是支撑集q归结过程中每次都选择支归结过程中每次都选择支撑集及其归结式与其他子撑集及其归结式与其他子句归结句归结3.3 谓词逻辑归结原理谓词逻辑归结原理3.3.7 归结过程控制策略归结过程控制策略n语义归结策略语义归结策略q将子句集按一定的语义分为两部分将子句集按一定的语义分为两部分 q每部分内的子句不允许进行归结，每

85、部分内的子句不允许进行归结，q同时引入文字次序。归结时，其中一个子句的被同时引入文字次序。归结时，其中一个子句的被归结文字是该子句中排序最前的文字。归结文字是该子句中排序最前的文字。例：例：S=PQ R, PQ , QR, R, 文字次序为文字次序为P,Q,R， 令解释令解释I=P,Q,R，在在I下为假的子句记为下为假的子句记为s1，为真的语，为真的语句记为句记为s2；则；则 3.3 谓词逻辑归结原理谓词逻辑归结原理3.3.7 归结过程控制策略归结过程控制策略 归结如下：归结如下：1 s2 2 s1 3 s1 4 s2 5 1、2归结，归结， s2 6 R 5、3归结，归结， s1 7 6、4

86、归结归结3.3 谓词逻辑归结原理谓词逻辑归结原理3.3.7 归结过程控制策略归结过程控制策略n线性归结策略线性归结策略 每次都用上一次归结得到的归结式与其他子句归结每次都用上一次归结得到的归结式与其他子句归结n单元归结策略单元归结策略 每次归结都有一个子句是单元子句，即只含一个文字每次归结都有一个子句是单元子句，即只含一个文字的子句的子句n输入归结策略输入归结策略 每次归结必有一个子句是原始子句集中的子句每次归结必有一个子句是原始子句集中的子句本章重点本章重点n命题逻辑归结原理命题逻辑归结原理n将语言描述转化为谓词公式将语言描述转化为谓词公式n自由出现、约束出现、前束范式自由出现、约束出现、前束范式n置换、置换的合成置换、置换的合成n合一、最一般合一合一、最一般合一n谓词逻辑归结原理谓词逻辑归结原理