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某个房间中藏着一只怪物某个房间中藏着一只怪物wumpu
3、s，它会吃掉进入，它会吃掉进入这个房间的人，相邻房间中能够感觉到臭味这个房间的人，相邻房间中能够感觉到臭味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、计算机系的学生必修、计算机系的学生必修C或或JA
6、VA。4、这家的报价单配置合理并且价格低廉。、这家的报价单配置合理并且价格低廉。5、“李四是犯罪嫌疑人李四是犯罪嫌疑人”“李四有犯罪动机李四有犯罪动机”3.1 命题逻辑n合式公式：合式公式：q单个常量或者变量的命题构成合式公式单个常量或者变量的命题构成合式公式q联结词联结的合式公式的组合也是合式公式联结词联结的合式公式的组合也是合式公式q合式公式的有限次组合称为命题公式合式公式的有限次组合称为命题公式n命题公式：有限次合式公式组合的形式化描命题公式：有限次合式公式组合的形式化描述，本书中以大写字母标识。述，本书中以大写字母标识。3.1 命题逻辑n基本联结基本联结(连接连接)符号符号q 非，否定
7、非，否定,q 与，合取，与，合取，AND的首字母的首字母q 或，析取，或，析取，velq 蕴含蕴含 式式A：a b表示，如果表示，如果a为真，则为真，则b为真。为真。q 等价等价n联结符号的优先级联结符号的优先级 3.1 命题逻辑n将命题从语言表述转换为命题公式将命题从语言表述转换为命题公式step1、找出简单命题，并用符号表示、找出简单命题，并用符号表示step2、分析简单命题间的逻辑关系，用联结符号进行描述、分析简单命题间的逻辑关系，用联结符号进行描述例例1、3不是偶数不是偶数令：令：p表示表示“3是偶数是偶数”，p2、教室里有、教室里有30名男生和名男生和10名女生名女生令：令：p表示表
8、示“教室里有教室里有30名男生名男生”，q表示表示“教室里有教室里有10名女生名女生”pq3、如果天下雨，出门带伞、如果天下雨，出门带伞令令p表示表示“天下雨天下雨”，q表示表示“出门带出门带伞伞”pq4、只要不下雨，我就骑自行车上班、只要不下雨，我就骑自行车上班令令p表示表示“天下雨天下雨”，q表示表示“骑自行车上班骑自行车上班”pq5、只有不下雨，我才骑自行车上班、只有不下雨，我才骑自行车上班令令p表示表示“天下雨天下雨”，q表示表示“骑自行车上班骑自行车上班”q p3.1 命题逻辑n例：怪物洞穴例：怪物洞穴 q如果房间如果房间1,1中有臭味，则房间中有臭味，则房间1,2或或2,1中有怪中
9、有怪物物 表示房间表示房间i,j中有臭味中有臭味 表示房间表示房间i,j中有怪物中有怪物 ,i jw1,1s1,11,22,1()sww,i js1,22,1()ww 练习：如果房间练习：如果房间1,1中没有臭味，中没有臭味，则房间则房间1,2和和2,1中没有怪物中没有怪物3.1 命题逻辑n练习：扫雷游戏练习：扫雷游戏q设设Xi,j表示方格表示方格i,j中有中有一个地雷。一个地雷。q写出方格写出方格1,1周围恰好周围恰好有有2颗地雷的命题公式颗地雷的命题公式1 2 3 4 5 543212 12 21 22 12 21 22 12 21 2,()()()XXXXXXXXX3.1 命题逻辑n命题
10、公式的赋值命题公式的赋值q对命题公式中的所有的命题变量各赋给一个值对命题公式中的所有的命题变量各赋给一个值0，1。n真值表真值表pqppqpqpqpq000110113.1 命题逻辑n复合命题的真值复合命题的真值例：例：p:周杰伦是一个流行歌手周杰伦是一个流行歌手q:人工智能是计算机科学的一个分支人工智能是计算机科学的一个分支 r:牛在天上飞牛在天上飞求下列复合命题的真值求下列复合命题的真值pqpq(pq)(pq)r(qr)(pr)pr(pr)(pr)我们关心的是复合命题中命题之间的真值关系，我们关心的是复合命题中命题之间的真值关系，而不关心命题的内容。而不关心命题的内容。3.1 命题逻辑n命
11、题公式的分类命题公式的分类q重言式或永真式重言式或永真式 tautology，n设设A为任一命题公式，若为任一命题公式，若A在它的各种赋值下取值均为真，则称在它的各种赋值下取值均为真，则称A是重言式是重言式例：例：PPq矛盾式或永假式矛盾式或永假式 contradictory n设设A为任一命题公式，若为任一命题公式，若A在它的各种赋值下取值均为假，则称在它的各种赋值下取值均为假，则称A是永假式。是永假式。例：例：PP3.1 命题逻辑q可满足式可满足式 satisfiablen设设A为任一命题公式，如果存在一组取值使为任一命题公式，如果存在一组取值使A为真，则为真，则A为可满为可满足式。足式。
12、n即：对于命题公式即：对于命题公式A，若，若A不是矛盾式，则称不是矛盾式，则称A是可满足式。是可满足式。例：例：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；等幂率
13、：等幂率：A A A；A A A；*摩根律：摩根律：(A 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 q)(p s r);分配分配律律3.1 命题逻辑n例例 P82q计算计算(p q)r)p 的合取范式的合
16、取范式 (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逻辑结论：如果逻辑结论：如果AB为重言式，则称为重言式，则称B是是A的逻辑结的逻辑结论，记作论，记作A=B。n常用推理定律：常用推理定律：附加：附加：A=(A B)简化：简化：(A B)=A假言推理：假言
17、推理：(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前提引入规则前提引入规则 任何证明的步骤上，都可以引入前提；任何证明的步骤上，都可以引入前提；q结论引入规则结论引入规则 任何证明的步骤上，所得到的结论都可以作为后续任何证明的步骤上，所得到的结论都可以作为后续证明的前提；证明的前提；q置换规则置换规则 任何证明的步骤上，
18、命题公式中任何子命题都可以任何证明的步骤上，命题公式中任何子命题都可以用与之等值的命题公式置换；用与之等值的命题公式置换；3.1 命题逻辑n例：例：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
19、r，s 前提引入：前提引入：4、(s r)s)=r 假言推理：假言推理：5、(q r)r)=q 析取三段论：析取三段论：3.1 命题逻辑n例例 怪物洞穴怪物洞穴 表示房间表示房间i,j中有臭味中有臭味 表示房间表示房间i,j中有怪物中有怪物 表示房间表示房间i,j中有微风中有微风 表示房间表示房间i,j中有陷阱中有陷阱,i js,i jw,i jb,i jt3.1 命题逻辑n初始状态，在房间初始状态，在房间1,1处没有感觉到微风，也没有臭味，处没有感觉到微风，也没有臭味，则相邻房间为安全的，既没有怪物也没有陷阱。则相邻房间为安全的，既没有怪物也没有陷阱。前提：前提：结论：结论：证明：证明：前提
20、引入前提引入 等价等值式等价等值式 简化简化 前提引入前提引入 拒取式拒取式 摩根律摩根律112 11 2112 11 21111,swwbttsb2 11 22 11 2,wwtt112 11 21,sww112 11 2112 11 22 11 2112,()()()swwswwwws2 11 2113,wws114,s2 11 211112 11 25,()()wwssww2 11 22 11 26,()wwww3.1 命题逻辑n归结原理归结原理q证明的一般方法证明的一般方法n由已知条件正向推导结论，演绎推理由已知条件正向推导结论，演绎推理n假定结论不成立，逆向推导与已知条件矛盾，反证法
21、假定结论不成立，逆向推导与已知条件矛盾，反证法q命题逻辑证明的归谬思想命题逻辑证明的归谬思想 P85归结原理的思想：如果证明归结原理的思想：如果证明AB为永假式，则得证为永假式，则得证()ABABAB归结推理命题逻辑谓词逻辑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 则，逆否命
23、题为：则，逆否命题为：(PW)(W)P3.1 命题逻辑n子句与子句集子句与子句集 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前提：前提
24、：(pq)(q r)结论：结论：pr证明证明:(pq)(q r)(p q)(q r)蕴含等值式与双重否定律蕴含等值式与双重否定律 =(p r)假言三段论假言三段论 pr 蕴含等值式蕴含等值式 3.1 命题逻辑n归结式归结式 q例例 pq,p q 归结后为归结后为:q n归结的目标归结的目标空子句空子句q对于一个合取范式，如果有一个子句不可满足，则子句集就对于一个合取范式，如果有一个子句不可满足，则子句集就不可满足，该合取范式为永假式不可满足，该合取范式为永假式q若一个子句集中包含空子句，则这个子句集一定是不可满足若一个子句集中包含空子句，则这个子句集一定是不可满足的的 q例：例：p,p归结后为
25、归结后为 3.1 命题逻辑n归结法步骤归结法步骤q建立待归结命题公式。将证明建立待归结命题公式。将证明AB为真转化为证为真转化为证明明AB为矛盾式为矛盾式q求合取范式，得到子句集求合取范式，得到子句集q对子句集进行归结对子句集进行归结n归结式作为新子句加入子句集进行归结归结式作为新子句加入子句集进行归结n当归结式为空子句时停止，证明结束。当归结式为空子句时停止，证明结束。n出现空子句出现空子句，表示该子句集不可满足，表示该子句集不可满足n归结法的完备性：如果归结法的完备性：如果AB成立，则利用归成立，则利用归结法一定可以得到证明结法一定可以得到证明3.1 命题逻辑n例：证明例：证明(pq)(q
26、 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 3.1 命题逻辑n例：怪兽洞穴例：怪兽洞穴q1、在房间、在房间1,1处没有感觉处没有感觉到微风，也没有臭味。到微风，也没有臭味。q2、在房间、在房间1,2处感觉到微处感觉到微风，但没有
27、感觉到臭味。风，但没有感觉到臭味。q3、在房间、在房间1,2处没有感觉处没有感觉到微风，但感觉到臭味。到微风，但感觉到臭味。n求证：房间求证：房间3,1处有怪处有怪物物*；房间；房间1,3处有洞穴；处有洞穴；房间房间2,2是安全的。是安全的。3.1 命题逻辑前提：前提：求证：求证：证明：要证明原命题为真，只需证明以下命题为恒假证明：要证明原命题为真，只需证明以下命题为恒假 111 22 1,wss2 1112 23 1,swww1 2112 2,sww3 1,w2 1112 23 111 2112 12112 2,()swwswwswws3 1,w 2 1112 23 1,swww2 1112
28、 23 1,swww1 2112 2,sww1 2112 2,()sww1 2111 22 2,()()swsw3.1 命题逻辑于是，得到子句集为：于是，得到子句集为：1 2112 12 1112 23 11 2111 22 23 1,swsswwwswsww1 2112 12 1112 23 11 2111 22 23 1,()()()swsswwwswsww3.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,2w3,1
29、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、循环结束，没有可以添加的新语句，待证明的定、循环结束，没有可以添加的新语句，待证明的定理不成立理不成立 1,S2.S3.1 命题逻辑q好的归结控制策略好的归结控制策略 初始状态优先选择包含结论的子句进行归结，之后初始状态优先选择包含结论的子句进行归结，之后每次都选择上一次归结得到的归结式与其他子句归结每次都选择上一次归结得到
30、的归结式与其他子句归结q容易犯的错误容易犯的错误 字句集字句集 1、PQ 2、PQ 3、1、2归结归结3、Q Q 1、2归结归结不允许同时归结两个项不允许同时归结两个项3.1 命题逻辑n归结方法是一种机械化的归结方法是一种机械化的,可在计算机上加以可在计算机上加以实现的推理方法实现的推理方法n归结方法归结方法是一种反向推理形式是一种反向推理形式n提供了一种自动定理证明的方法提供了一种自动定理证明的方法n归结的半完备性归结的半完备性q当定理可以证明时，归结方法是完备的当定理可以证明时，归结方法是完备的q当定理不可证明时，归结方法得不到任何结论，算当定理不可证明时，归结方法得不到任何结论，算法不一
31、定会停止法不一定会停止3.2 谓词逻辑3.2 谓词逻辑3.2.1 基本概念n命题逻辑描述简单的陈述性命题，但表示量化命题逻辑描述简单的陈述性命题，但表示量化和谓词过于繁琐，也难以表示个体间的关系和谓词过于繁琐，也难以表示个体间的关系例：现在课堂上的所有学生都在上人工智能课例：现在课堂上的所有学生都在上人工智能课命题逻辑命题逻辑s1:张三在上人工智能课张三在上人工智能课s2:李四在上人工智能课李四在上人工智能课s3:王五在上人工智能课王五在上人工智能课 例例2：用命题逻辑归结原理证明：用命题逻辑归结原理证明：“人都是妈生人都是妈生的，张飞是人，所以张飞是妈生的的，张飞是人，所以张飞是妈生的”p:
32、人都是妈生的人都是妈生的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=线性代数，表示李四在上线性代数课线性代数，表示李四在上线性代数课x=王五，王五，y=睡觉，表示王五在上睡觉课睡觉，表示王五在上睡觉课3.2
33、 谓词逻辑3.2.1 基本概念n命题是一个陈述句，它一般可分成主语和谓语两部分。有命题是一个陈述句，它一般可分成主语和谓语两部分。有时还需要用到量词。时还需要用到量词。n主语：指独立存在的客体，可以是具体事物或抽象概念，主语：指独立存在的客体，可以是具体事物或抽象概念，也称为个体也称为个体n谓词：描述个体词性质或个体之间关系的词谓词：描述个体词性质或个体之间关系的词n个体域：表示个体变量的取值范围，常用个体域：表示个体变量的取值范围，常用D表示表示n常量：表示具体性质或关系的个体或者谓词常量：表示具体性质或关系的个体或者谓词n变量：表示抽象或泛指的个体或者谓词。变量：表示抽象或泛指的个体或者谓
34、词。n量词：表示数量的词。量词：表示数量的词。q任意量词任意量词：表示：表示“任意任意”，“所有所有”，也称为全称量词，也称为全称量词q存在量词存在量词：表示：表示“存在存在”3.2 谓词逻辑3.2.1 基本概念n例：例：“关羽是人关羽是人”，“张飞是人张飞是人”q这是两个不同的命题，其主语（个体）不同这是两个不同的命题，其主语（个体）不同q但是谓词是相同的，但是谓词是相同的，“是人是人”q把谓语部分抽出来，假设把谓语部分抽出来，假设 Human(x)表示表示x是人是人q这两个命题都可以用这个谓词来描述这两个命题都可以用这个谓词来描述 Human(guanyu)Human(zhangfei)q
35、其中其中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是人是人()xP x()xQ x()()x R xP x()()x R xQ x3.2 谓词逻辑n语言描述转换为谓词公式语言描述转换为谓词公式q1、确定并说明谓词、确定
36、并说明谓词q2、确定个体和个体域、确定个体和个体域q3、确定量词、确定量词q4、判断谓词间的逻辑关系、判断谓词间的逻辑关系3.2 谓词逻辑n例：我是计算机系的学生例：我是计算机系的学生1、确定并说明谓词：、确定并说明谓词：方法一：方法一：Student(x,y)表示表示X是是Y系的学生系的学生2、个体域：、个体域：X：学生的集合，：学生的集合，y：系的集合：系的集合 Student(I,computer)方法二：方法二：Computer(x)表示表示X是计算机系的学生是计算机系的学生 Computer(I)注意：必须对谓词进行说明注意：必须对谓词进行说明 P(I,computer)3.2 谓词
37、逻辑1、定义并说明谓词、定义并说明谓词 Unlike(x,y)表示表示 x不喜欢不喜欢y课课2、个体域、个体域 x学生的集合，学生的集合，y课程的集合课程的集合3、量词、量词 存在存在(,)x Unlike x AIn例：有学生不喜欢上人工智能课例：有学生不喜欢上人工智能课Like(x,y)表示表示x喜欢喜欢y课课(,)xLike x AIStudent(x)表示表示x是学生是学生Like(x,y)表示表示x喜欢喜欢y课课个体域个体域x：人的集合：人的集合()(,)x Student xLike x AI逻辑关系：与逻辑关系：与3.2 谓词逻辑n例：任何人的兄弟都是男性例：任何人的兄弟都是男性
38、q确定并说明谓词确定并说明谓词Brother(x,y)表示表示x是是y的兄弟的兄弟Male(x)表示表示x是男性是男性q个体域个体域 Brother(x,y)x、y：人的集合：人的集合 Male(x)x：人的集合：人的集合q量词量词 任意任意q确定逻辑关系确定逻辑关系 与？或？非？蕴含？等价？与？或？非？蕴含？等价？(,)()x y Brother x yMale x 3.2 谓词逻辑n例：不管黑猫白猫，抓住老鼠就是好猫例：不管黑猫白猫，抓住老鼠就是好猫q定义并说明谓词定义并说明谓词 Cat(x,y)表示是表示是x是是y颜色的猫颜色的猫 Goodcat(x)表示表示x是好猫是好猫 Catch(
39、x,Mouse)表示表示x能抓住老鼠能抓住老鼠q个体域个体域 x:猫的集合，猫的集合，y：颜色的集合：颜色的集合q谓词间的关系谓词间的关系 Cat(x,y)与与Catch(x,Mouse)蕴含蕴含Goodcat(x)q量词：量词：任意任意 (,)(),)()x y Cat x yCatch x MouseGoodcat x 3.2 谓词逻辑3.2.1 基本概念n量词使用中的注意事项量词使用中的注意事项q不同的个体域中，命题符号化的形式可能不同不同的个体域中，命题符号化的形式可能不同q没有给定个体域的情况下，应考虑全总个体域没有给定个体域的情况下，应考虑全总个体域q如果个体域为有限集如果个体域为
40、有限集 ，对任意谓词，对任意谓词P(x)有：有：q多个量词同时出现时，不能颠倒其先后顺利，否则多个量词同时出现时，不能颠倒其先后顺利，否则会改变公式的含义。会改变公式的含义。123,nDa a aa 123123()()()()()()()()()()nnxP xP aP aP aP axP xP aP aP aP a3.2 谓词逻辑3.2.1 基本概念n例：例：love(x,y)表示表示x喜爱喜爱y 表示对任意的表示对任意的x，都存在喜爱的对象，都存在喜爱的对象y，即，即“每一每一个人都会喜爱某人个人都会喜爱某人”表示存在都一个表示存在都一个y，任意的人，任意的人x 都喜爱他，即都喜爱他，即
41、 “上帝上帝”(,)x y Love x y(,)y x Love x y 3.2 谓词逻辑谓词逻辑3.2.2 一阶谓词逻辑一阶谓词逻辑n原子公式：设原子公式：设 是任意是任意n元谓词，元谓词，是项，则称是项，则称 为原子公式。为原子公式。n项：项：q任何常量是项。任何常量是项。q任何变量是项。任何变量是项。qn 1 个参数的任何表达式个参数的任何表达式 （其中，（其中，是项，而是项，而 f 是是 n 阶的函数）是项。阶的函数）是项。q闭包条款：闭包条款：其他东西都不是项。其他东西都不是项。123(,)nP x xxx123,nt ttt123(,)nP t ttt12(,)nf t ttit
42、3.2 谓词逻辑谓词逻辑3.2.2 一阶谓词逻辑一阶谓词逻辑n谓词公式谓词公式q原子公式是谓词公式。原子公式是谓词公式。q若若A为谓词公式，则为谓词公式，则A也是一个谓词公式。也是一个谓词公式。q若若A和和B都是都是谓词谓词公式，则公式，则(A B)，(A B)，(AB)和和(A B)也都是也都是谓词谓词公式。公式。q若若A是是谓词谓词公式，公式，和和 也都是也都是谓词谓词公式。公式。q只有有限次应用上述规则得到的公式，才是只有有限次应用上述规则得到的公式，才是谓词谓词公公式。式。xA xA 3.2 谓词逻辑谓词逻辑3.2.2 一阶谓词逻辑一阶谓词逻辑n对于对于 ，qx称为指导变量称为指导变量
43、 qA称为相应量词的称为相应量词的辖域辖域 x(p(x)qx在辖域在辖域A中的出现称为约束出现中的出现称为约束出现qx以外的变量在辖域以外的变量在辖域A中的出现称为自由出现中的出现称为自由出现 x(p(x,y)xA xA 对于对于 ，指导变量：指导变量：的辖域：的辖域：x,y都都是约束出现是约束出现3.2 谓词逻辑谓词逻辑3.2.2 一阶谓词逻辑一阶谓词逻辑n例例对于对于 ，指导变量指导变量:的辖域的辖域:x、y是约束出现还是自由是约束出现还是自由出现出现 y是约束出现，是约束出现，x是自由出现是自由出现()(,)x P xyQ x y (,)yQ x y()(,)x P xyQ x y ()
44、(,)P xyQ x y y(,)Q x yx3.2 谓词逻辑谓词逻辑3.2.2 一阶谓词逻辑一阶谓词逻辑n不同量词如果采用相同的指导变量名，易引起不同量词如果采用相同的指导变量名，易引起混淆混淆n一般要求不同的量词使用不同的指导变量名称一般要求不同的量词使用不同的指导变量名称()(,)xx P xMan x y3.2 谓词逻辑谓词逻辑3.2.2 一阶谓词逻辑一阶谓词逻辑n当在一个公式中，一个变量符号既是约束出现的变量，当在一个公式中，一个变量符号既是约束出现的变量，又是自由出现的变量时，需要作变量符号更换。又是自由出现的变量时，需要作变量符号更换。n换名规则：将量词辖域中某个约束出现的变量及
45、其换名规则：将量词辖域中某个约束出现的变量及其指指导变量导变量替换为此辖域中未出现过的个体变量符号替换为此辖域中未出现过的个体变量符号 x既作为指导变量约束出现又自由出现，因此要既作为指导变量约束出现又自由出现，因此要换掉其中之一换掉其中之一 换名规则更换的是指导变量换名规则更换的是指导变量 可替换为可替换为(,)(,)xP x yR x y(,)(,)zP z yR x y3.2 谓词逻辑谓词逻辑3.2.2 一阶谓词逻辑一阶谓词逻辑n替代规则：对某替代规则：对某自由出现的个体变量自由出现的个体变量用与原公用与原公式中未出现过的变量符号去替代，且式中未出现过的变量符号去替代，且处处替代处处替代
46、。x既作为指导变量约束出现又自由出现，既作为指导变量约束出现又自由出现，且多处自由出现且多处自由出现 替代规则更换的是自由出现的变量，且处替代规则更换的是自由出现的变量，且处处替代处替代 替换为替换为(,)(,)()xP x yR x yZ x(,)(,)()xP x yR z yZ z3.2 谓词逻辑谓词逻辑3.2.2 一阶谓词逻辑一阶谓词逻辑n谓词公式的解释谓词公式的解释q对谓词公式中的各种变量制定具体的常量去替代对谓词公式中的各种变量制定具体的常量去替代q一个解释包括一个解释包括n非空个体域非空个体域 Dn D中一部分特定元素；中一部分特定元素；n D上一些特定的函数；上一些特定的函数；
47、n D上一些特定的谓词。上一些特定的谓词。q如果谓词公式在特定解释下为真，称这个解释满足如果谓词公式在特定解释下为真，称这个解释满足这个谓词公式，是这个谓词公式的一个模型这个谓词公式，是这个谓词公式的一个模型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 求解释
48、求解释I下，下列谓词公式的真值下，下列谓词公式的真值 1、2、2 3,ID ()(,()x P f xQ x f x(,)x yR x y 3.2 谓词逻辑谓词逻辑3.2.2 一阶谓词逻辑一阶谓词逻辑n解解 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()(,()x P f xQ x f x3322(,)x yR x y 23(,)(,)x R xR x3.2 谓词逻辑谓词逻辑3.2.3 谓词演算与推理谓词演算与推理n谓词演算公
49、式谓词演算公式q约束变量换名规则，约束变量换名规则，Q为任意量词为任意量词 (Qx)P(x)(Qy)P(y)(Qx)P(x,z)(Qy)P(y,z)q量词消去等值式，对于有穷个体域量词消去等值式，对于有穷个体域q量词否定等值式量词否定等值式q量词分配等值式量词分配等值式()()()()x P xxp x ()()()()x P xxp x 123123()()()()()()()()()()()()nnx P xP aP aP aP ax P xP aP aP aP a()()()()()()()xP xQ xx P xx Q x ()()()()()()()xP xQ xx P xx Q x
50、 12,na aa3.2 谓词逻辑谓词逻辑3.2.3 谓词演算与推理谓词演算与推理q量词辖域收缩与扩张等值式量词辖域收缩与扩张等值式()()()()xP xQx P xQ ()()()()xP xQx P xQ ()()()()xP xQx P xQ ()()()()xP xQx P xQ ()()()()xP xQx P xQ ()()()()x QP xQx P x ()()()()xP xQx P xQ ()()()()x QP xQx P x 3.2 谓词逻辑谓词逻辑3.2.4 谓词知识表示谓词知识表示n谓词逻辑表达的规范形式谓词逻辑表达的规范形式P是谓词，而是谓词，而 表示个体（主体
