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

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

，1879)(p→q)∧(p→r)∧～

p∧～

r→～

p3*2=6if(a>b)thena++;因与另一因以及两者彼此的联系。但此种联系的发展，相互作用，本身即是区别的变换，不过不是原因与原因的互换，而是因果关系中两环节的互换，就每一环节各自独立而为。概述语言3*2=6if(a>b)thena++;因与另3怪物洞穴人工智能的经典实验环境—怪物洞穴(wumpus世界)洞穴有多个房间组成某个房间中藏着一只怪物wumpus，它会吃掉进入这个房间的人，相邻房间中能够感觉到臭味某些房间中有陷阱，进入房间会被陷阱吞噬，相邻房间中能够感觉到微风游戏的主角是一个智能体，可以进入相邻的房间（对角线不可以）智能体有且仅有一支箭，用这支箭可以射杀怪物某个房间中有金子，游戏的目标是智能体找到金子怪物洞穴人工智能的经典实验环境—怪物洞穴(wumpus世界)4怪物洞穴智能体行动的关键是要根据获得的信息推理，从而判断那个房间有怪物，那个房间有陷阱，那个房间是安全的房间[4,2]和[2,3]有陷阱，房间[3,4]有怪物，房间[4,3]有金子怪物洞穴智能体行动的关键是要根据获得的信息推理，从而判断那个53.1命题逻辑3.1命题逻辑63.1命题逻辑命题—能够判断真假的陈述句陈述句真值唯一，可用二进制表示用小写字母进行标识例1、北京是中国的首都。2、长安大学位于钟楼附近。3、1+1=24、计算机系的学生必修C或JAVA。5、坐着花生过黄河5、x+1=26、吃饭了吗？7、南无阿弥陀佛8、我正在说假话3.1命题逻辑命题—能够判断真假的陈述句73.1命题逻辑简单命题与复合命题简单命题：（原子命题）一个命题无法分解为更简单的子命题复合命题：由简单命题用联结词联结而成的命题

1、由若干简单命题组成；2：由联结词联结例：1、北京是中国的首都。2、长安大学位于钟楼附近。3、计算机系的学生必修C或JAVA。4、这家的报价单配置合理并且价格低廉。5、“李四是犯罪嫌疑人”“李四有犯罪动机”

3.1命题逻辑简单命题与复合命题83.1命题逻辑合式公式：单个常量或者变量的命题构成合式公式联结词联结的合式公式的组合也是合式公式合式公式的有限次组合称为命题公式命题公式：有限次合式公式组合的形式化描述，本书中以大写字母标识。3.1命题逻辑合式公式：93.1命题逻辑基本联结(连接)符号～非，否定,﹁∧与，合取，AND的首字母∨或，析取，vel

→

蕴含式A：a→b表示，如果a为真，则b为真。

↔

等价联结符号的优先级～∧∨→

↔3.1命题逻辑基本联结(连接)符号103.1命题逻辑将命题从语言表述转换为命题公式step1、找出简单命题，并用符号表示step2、分析简单命题间的逻辑关系，用联结符号进行描述例1、3不是偶数令：p表示“3是偶数”，~p2、教室里有30名男生和10名女生令：p表示“教室里有30名男生”，

q表示“教室里有10名女生”

p∧q3、如果天下雨，出门带伞令p表示“天下雨”，q表示“出门带伞”p→q4、只要不下雨，我就骑自行车上班令p表示“天下雨”，q表示“骑自行车上班”

~p→q5、只有不下雨，我才骑自行车上班令p表示“天下雨”，q表示“骑自行车上班”

q→~p3.1命题逻辑将命题从语言表述转换为命题公式1、3不是偶数113.1命题逻辑例：怪物洞穴如果房间[1,1]中有臭味，则房间[1,2]或[2,1]中有怪物表示房间[i,j]中有臭味表示房间[i,j]中有怪物

练习：如果房间[1,1]中没有臭味，则房间[1,2]和[2,1]中没有怪物3.1命题逻辑例：怪物洞穴练习：如果房间[1,1]中没有123.1命题逻辑练习：扫雷游戏设Xi,j表示方格[i,j]中有一个地雷。写出方格[1,1]周围恰好有2颗地雷的命题公式12345……543213.1命题逻辑练习：扫雷游戏12345…133.1命题逻辑命题公式的赋值对命题公式中的所有的命题变量各赋给一个值0，1。真值表pq~pp∧qp∨qp→qp↔q000110113.1命题逻辑命题公式的赋值pq~pp∧qp∨qp→qp↔143.1命题逻辑复合命题的真值例：p:周杰伦是一个流行歌手q:人工智能是计算机科学的一个分支

r:牛在天上飞求下列复合命题的真值~p∧qp∧~q((~p∧q)∨(p∧~q))→r(q∨r)→(p→~r)p→~r(~p∨r)

(p∧~r)我们关心的是复合命题中命题之间的真值关系，而不关心命题的内容。3.1命题逻辑复合命题的真值~p∧qp∧~q((~p∧q)153.1命题逻辑命题公式的分类重言式或永真式tautology，设A为任一命题公式，若A在它的各种赋值下取值均为真，则称A是重言式例：P∨~P矛盾式或永假式contradictory设A为任一命题公式，若A在它的各种赋值下取值均为假，则称A是永假式。例：P∧~P3.1命题逻辑命题公式的分类163.1命题逻辑可满足式

satisfiable设A为任一命题公式，如果存在一组取值使A为真，则A为可满足式。即：对于命题公式A，若A不是矛盾式，则称A是可满足式。例：P∧Q

非重言式的可满足式

既是可满足式，又不是重言式3.1命题逻辑可满足式satisfiable173.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；3.1命题逻辑等值逻辑运算183.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*蕴含等值式：A→B<=>~A∨B；*等价等值式：A↔B<=>(A→B)∧(B→A)；假言易位式：

A→B<=>~B→~

A

；等价否定等值式：A↔B<=>~A↔

~

B；归谬论：(A→B)∧(A→~B)<=>~A；3.1命题逻辑吸收率:A∨(A∧B)<=>193.1命题逻辑合取范式与析取范式简单析取式：有限个命题变元或其否定，析取联结符

p∨q;~p∨q;p;q合取范式：有限个简单析取式，合取

p∧(p∨q)∧(~p∨q)简单合取式：有限个命题变元或其否定，合取

p∧q;~p∧q;p;q析取范式：有限个简单合取式，析取

p∨(p∧q)∨(~p∧q)3.1命题逻辑合取范式与析取范式203.1命题逻辑任意命题公式都存在等值的析取范式和合取范式求取合取范式的步骤1、利用蕴含等值式和等价等值式消去命题公式中除{~，∨，∧}以外的联结词2、利用摩根律、双重否定律等进行置换，将~移到括号里面3、利用分配律得到合取范式3.1命题逻辑任意命题公式都存在等值的析取范式和合取范式213.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);

分配律3.1命题逻辑例P82计算(p∧(q→r)223.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)

;等幂律3.1命题逻辑例P82233.1命题逻辑课堂练习计算合取范式(p→q)∧~

(~q

→~

p)(~p∨q)∧~

q

∧

p3.1命题逻辑课堂练习243.1命题逻辑命题逻辑推理逻辑结论：如果A→B为重言式，则称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

)3.1命题逻辑命题逻辑推理253.1命题逻辑命题逻辑推理规则前提引入规则任何证明的步骤上，都可以引入前提；结论引入规则任何证明的步骤上，所得到的结论都可以作为后续证明的前提；置换规则任何证明的步骤上，命题公式中任何子命题都可以用与之等值的命题公式置换；3.1命题逻辑命题逻辑推理规则263.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析取三段论：3.1命题逻辑例：P84273.1命题逻辑例怪物洞穴表示房间[i,j]中有臭味表示房间[i,j]中有怪物表示房间[i,j]中有微风表示房间[i,j]中有陷阱3.1命题逻辑例怪物洞穴283.1命题逻辑初始状态，在房间[1,1]处没有感觉到微风，也没有臭味，则相邻房间为安全的，既没有怪物也没有陷阱。前提：

结论：证明：前提引入

等价等值式简化前提引入拒取式摩根律3.1命题逻辑初始状态，在房间[1,1]处没有感觉到微风，293.1命题逻辑归结原理证明的一般方法由已知条件正向推导结论，演绎推理假定结论不成立，逆向推导与已知条件矛盾，反证法命题逻辑证明的归谬思想P85归结原理的思想：如果证明A∧~B为永假式，则得证3.1命题逻辑归结原理30归结推理命题逻辑谓词逻辑Skolem标准形、子句集基本概念谓词逻辑归结原理合一和置换、控制策略数理逻辑命题逻辑归结Herbrand定理归结命题谓词逻Skolem标准形、基本谓词逻辑合一和置换、数313.1命题逻辑归结方法的思想1、将待证明问题转化为其逆否命题例：条件A，求证B.即A→B

其逆否命题为：

A∧~B2、求合取范式，得到子句集构成合取范式的有限个简单析取式构成的集合就是子句集3、对子句集进行归结，得到空子句3.1命题逻辑归结方法的思想323.1命题逻辑将待证明问题转化为其逆否命题证明问题的一般形式：已知：A成立求证：B成立即：证明A→BA→B<=>~A∨B蕴含等值式

<=>~(A∧~B)摩根率

A∧~B即为原命题的逆否命题3.1命题逻辑将待证明问题转化为其逆否命题333.1命题逻辑例：证明G是F的逻辑结论F1：P→WF2：~WG：~P分析：已知条件为：

(P→W)(~W)

结论为：~P

则，逆否命题为：

(P→W)∧(~W)3.1命题逻辑例：证明G是F的逻辑结论343.1命题逻辑子句与子句集P86对问题的逆否命题，求其合取范式对于一个合取范式，该范式中的每一条简单析取式都是一个子句。子句集：合取范式下的所有子句构成其子句集。例：p∧(p∨q)∧(~p∨q)子句集为

{p,p∨q,~p∨q}3.1命题逻辑子句与子句集P86353.1命题逻辑归结方法如果p∨q与~q∨r都为真，则p∨r为真证明1真值表pp∨qq~q~q∨rrp∨r1-----10110111证明2前提：(p∨q)∧(~q∨r)结论：p∨r证明:(p∨q)∧(~q∨r)<=>(~p→q)∧(q

→

r)蕴含等值式与双重否定律

=>(~p→r)假言三段论

<=>p∨r蕴含等值式

3.1命题逻辑归结方法pp∨qq~q~q∨rrp∨363.1命题逻辑归结式例{p∨q,~p∨q}归结后为:{q}归结的目标—空子句对于一个合取范式，如果有一个子句不可满足，则子句集就不可满足，该合取范式为永假式若一个子句集中包含空子句，则这个子句集一定是不可满足的例：{p,~p}归结后为

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

→~

p)证明：要证明原命题为真，只需证明(p→q)∧~

(~q

→~

p)为恒假

(p→q)∧~

(~q

→~

p)<=>(~p∨q)∧~

(q∨~

p)蕴含等值式

<=>(~p∨q)∧~

q

∧

p

摩根律于是，子句集为:1~

p∨q2~

q

3

p{~

p∨q,~

q,

p}4~

p1、2归结

5□3、4归结由此可得:(p→q)∧~

(~q

→~

p)为恒假，原命题为真

{□,~p,

p,~p∨q,~q}{~p,

p,~p∨q,~q}3.1命题逻辑例：证明(p→q)→(~q→~p){□393.1命题逻辑例：怪兽洞穴1、在房间[1,1]处没有感觉到微风，也没有臭味。2、在房间[1,2]处感觉到微风，但没有感觉到臭味。3、在房间[1,2]处没有感觉到微风，但感觉到臭味。求证：房间[3,1]处有怪物*；房间[1,3]处有洞穴；房间[2,2]是安全的。3.1命题逻辑例：怪兽洞穴403.1命题逻辑前提：求证：证明：要证明原命题为真，只需证明以下命题为恒假

3.1命题逻辑前提：413.1命题逻辑于是，得到子句集为：3.1命题逻辑于是，得到子句集为：423.1命题逻辑1~s1,22~w1,13s2,14~s2,1∨w1,1∨w2,2∨w3,1

5s1,2∨~

w1,1

6s1,2∨~

w2,27~

w3,18

w1,1∨w2,2∨w3,1

3,4归结

9w2,2∨w3,18,2归结10w2,29,7归结11s1,210,6归结12□11,1归结3.1命题逻辑1~s1,28w1,1433.1命题逻辑思考：归结算法的计算机实现？

{S0,S1,S2,S3…}

终止条件：

1、生成了空子句，证明结束

2、循环结束，没有可以添加的新语句，待证明的定理不成立

3.1命题逻辑思考：443.1命题逻辑好的归结控制策略初始状态优先选择包含结论的子句进行归结，之后每次都选择上一次归结得到的归结式与其他子句归结容易犯的错误字句集

1、P∨Q2、~P∨~Q3、□1、

2归结3、Q∨~Q1、2归结不允许同时归结两个项3.1命题逻辑好的归结控制策略3、Q∨~Q453.1命题逻辑归结方法是一种机械化的,可在计算机上加以实现的推理方法归结方法是一种反向推理形式提供了一种自动定理证明的方法归结的半完备性当定理可以证明时，归结方法是完备的当定理不可证明时，归结方法得不到任何结论，算法不一定会停止3.1命题逻辑归结方法是一种机械化的,可在计算机上加以实现463.2谓词逻辑3.2谓词逻辑473.2谓词逻辑

3.2.1基本概念命题逻辑描述简单的陈述性命题，但表示量化和谓词过于繁琐，也难以表示个体间的关系例：现在课堂上的所有学生都在上人工智能课命题逻辑s1:张三在上人工智能课s2:李四在上人工智能课s3:王五在上人工智能课

………例2：用命题逻辑归结原理证明：“人都是妈生的，张飞是人，所以张飞是妈生的”p:人都是妈生的q:张飞是人r:张飞是妈生的(p∧q)→r

p∧q∧~r3.2谓词逻辑

3.2.1基本概念命题逻辑描述简单的陈述483.2谓词逻辑

3.2.1基本概念谓词逻辑Class(x)表示x在上人工智能课

x=张三，就得到了s1；

x=李四，就得到了s2；

x=王五，就得到了s3；

Class(x,y)表示x在上y课x=张三，y=人工智能，表示张三在上人工智能课x=李四，y=线性代数，表示李四在上线性代数课x=王五，y=睡觉，表示王五在上睡觉课3.2谓词逻辑

3.2.1基本概念谓词逻辑493.2谓词逻辑

3.2.1基本概念命题是一个陈述句，它一般可分成主语和谓语两部分。有时还需要用到量词。主语：指独立存在的客体，可以是具体事物或抽象概念，也称为个体谓词：描述个体词性质或个体之间关系的词个体域：表示个体变量的取值范围，常用D表示常量：表示具体性质或关系的个体或者谓词变量：表示抽象或泛指的个体或者谓词。量词：表示数量的词。任意量词∀：表示“任意”，“所有”，也称为全称量词存在量词∃：表示“存在”3.2谓词逻辑

3.2.1基本概念命题是一个陈述句，它一503.2谓词逻辑

3.2.1基本概念例：“关羽是人”，“张飞是人”这是两个不同的命题，其主语（个体）不同但是谓词是相同的，“是人”把谓语部分抽出来，假设Human(x)表示x是人这两个命题都可以用这个谓词来描述

Human(guanyu)Human(zhangfei)其中x属于个体变量，guanyu和zhangfei属于个体常量3.2谓词逻辑

3.2.1基本概念例：“关羽是人”，“张513.2谓词逻辑

3.2.1基本概念例：1、所有的人都是要死的2、有的人能够活到100岁

P(x)表示x是要死的，Q(x)表示x活到100岁个体域D为人类集合个体域D为总个体域集合引入特殊谓词R(x)表示x是人3.2谓词逻辑

3.2.1基本概念例：523.2谓词逻辑语言描述转换为谓词公式1、确定并说明谓词2、确定个体和个体域3、确定量词4、判断谓词间的逻辑关系3.2谓词逻辑语言描述转换为谓词公式533.2谓词逻辑例：我是计算机系的学生1、确定并说明谓词：方法一：Student(x,y)表示X是Y系的学生2、个体域：X：学生的集合，y：系的集合

Student(I,computer)

方法二：Computer(x)表示X是计算机系的学生

Computer(I)

注意：必须对谓词进行说明

P(I,computer)3.2谓词逻辑例：我是计算机系的学生543.2谓词逻辑1、定义并说明谓词

Unlike(x,y)表示

x不喜欢y课2、个体域

x学生的集合，

y课程的集合3、量词存在例：有学生不喜欢上人工智能课Like(x,y)表示x喜欢y课Student(x)表示x是学生Like(x,y)表示x喜欢y课个体域x：人的集合逻辑关系：与3.2谓词逻辑1、定义并说明谓词例：有学生不喜欢上人工智能553.2谓词逻辑例：任何人的兄弟都是男性确定并说明谓词Brother(x,y)表示x是y的兄弟Male(x)表示x是男性个体域

Brother(x,y)x、y：人的集合

Male(x)x：人的集合量词任意确定逻辑关系与？或？非？蕴含？等价？

3.2谓词逻辑例：任何人的兄弟都是男性563.2谓词逻辑例：不管黑猫白猫，抓住老鼠就是好猫定义并说明谓词

Cat(x,y)表示是x是y颜色的猫

Goodcat(x)表示x是好猫

Catch(x,Mouse)表示x能抓住老鼠个体域

x:猫的集合，y：颜色的集合谓词间的关系

Cat(x,y)与Catch(x,Mouse)蕴含Goodcat(x)量词：任意3.2谓词逻辑例：不管黑猫白猫，抓住老鼠就是好猫573.2谓词逻辑

3.2.1基本概念量词使用中的注意事项不同的个体域中，命题符号化的形式可能不同没有给定个体域的情况下，应考虑全总个体域如果个体域为有限集，对任意谓词P(x)有：多个量词同时出现时，不能颠倒其先后顺利，否则会改变公式的含义。3.2谓词逻辑

3.2.1基本概念量词使用中的注意事项583.2谓词逻辑

3.2.1基本概念例：love(x,y)表示x喜爱y

表示对任意的x，都存在喜爱的对象y，即“每一个人都会喜爱某人”表示存在都一个y，任意的人x都喜爱他，即“上帝”

3.2谓词逻辑

3.2.1基本概念例：love(x,y)593.2谓词逻辑

3.2.2一阶谓词逻辑原子公式：设是任意n元谓词，是项，则称为原子公式。项：任何常量是项。任何变量是项。n≥1个参数的任何表达式（其中，是项，而f

是n

阶的函数）是项。闭包条款：其他东西都不是项。

3.2谓词逻辑

3.2.2一阶谓词逻辑原子公式：设603.2谓词逻辑

3.2.2一阶谓词逻辑谓词公式原子公式是谓词公式。若A为谓词公式，则～A也是一个谓词公式。若A和B都是谓词公式，则(A∧B)，(A∨B)，(A→B)和(AB)也都是谓词公式。若A是谓词公式，和也都是谓词公式。只有有限次应用上述规则得到的公式，才是谓词公式。

3.2谓词逻辑

3.2.2一阶谓词逻辑谓词公式613.2谓词逻辑

3.2.2一阶谓词逻辑对于，x称为指导变量A称为相应量词的辖域

∃x(p(x))x在辖域A中的出现称为约束出现x以外的变量在辖域A中的出现称为自由出现∃x(p(x,y))3.2谓词逻辑

3.2.2一阶谓词逻辑对于62对于，指导变量：∀的辖域：

x,

y都是约束出现3.2谓词逻辑

3.2.2一阶谓词逻辑例对于，指导变量:∃的辖域:

x、y是约束出现还是自由出现

y是约束出现，

x是自由出现对于633.2谓词逻辑

3.2.2一阶谓词逻辑不同量词如果采用相同的指导变量名，易引起混淆一般要求不同的量词使用不同的指导变量名称3.2谓词逻辑

3.2.2一阶谓词逻辑不同量词如果采用相643.2谓词逻辑

3.2.2一阶谓词逻辑当在一个公式中，一个变量符号既是约束出现的变量，又是自由出现的变量时，需要作变量符号更换。换名规则：将量词辖域中某个约束出现的变量及其指导变量替换为此辖域中未出现过的个体变量符号

x既作为指导变量约束出现又自由出现，因此要换掉其中之一换名规则更换的是指导变量可替换为3.2谓词逻辑

3.2.2一阶谓词逻辑当在一个公式中，一653.2谓词逻辑

3.2.2一阶谓词逻辑替代规则：对某自由出现的个体变量用与原公式中未出现过的变量符号去替代，且处处替代。

x既作为指导变量约束出现又自由出现，且多处自由出现替代规则更换的是自由出现的变量，且处处替代替换为3.2谓词逻辑

3.2.2一阶谓词逻辑替代规则：对某自由663.2谓词逻辑

3.2.2一阶谓词逻辑谓词公式的解释对谓词公式中的各种变量制定具体的常量去替代一个解释包括非空个体域D

D中一部分特定元素；

D上一些特定的函数；

D上一些特定的谓词。如果谓词公式在特定解释下为真，称这个解释满足这个谓词公式，是这个谓词公式的一个模型永真与不可满足3.2谓词逻辑

3.2.2一阶谓词逻辑谓词公式的解释673.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、3.2谓词逻辑

3.2.2一阶谓词逻辑例：p92683.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)∨(0∧1)=>12、

=>

=>(R(2,2)∨R(2,3))∧(R(3,2)∨R(3,3))=>(1∨0)∧(0∨1)=>13.2谓词逻辑

3.2.2一阶谓词逻辑解1、693.2谓词逻辑

3.2.3谓词演算与推理谓词演算公式约束变量换名规则，Q为任意量词

(Qx)P(x)<=>(Qy)P(y)(Qx)P(x,z)<=>(Qy)P(y,z)量词消去等值式，对于有穷个体域量词否定等值式量词分配等值式3.2谓词逻辑

3.2.3谓词演算与推理谓词演算公式703.2谓词逻辑

3.2.3谓词演算与推理量词辖域收缩与扩张等值式3.2谓词逻辑

3.2.3谓词演算与推理量词辖域收缩与扩713.2谓词逻辑

3.2.4谓词知识表示谓词逻辑表达的规范形式P是谓词，而表示个体（主体或者客体）知识库：表达知识的一组谓词公式的集合。语句的集合对环境、规则等信息的结构化描述基于知识的智能体的核心构件3.2谓词逻辑

3.2.4谓词知识表示谓词逻辑表达的规范723.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)3.2谓词逻辑

3.2.4谓词知识表示定义谓词733.2谓词逻辑

3.2.4谓词知识表示例：准前女友双眼皮,大眼睛doublefold(x)∧bigeyes(x)一头乌黑的头发blackhair(x)∧thickhair(x)一身漂亮的呢子大衣beautifuldress(x)走路的姿态赛过模特graceful(x)3.2谓词逻辑

3.2.4谓词知识表示例：准前女友743.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上3.2谓词逻辑

3.2.4谓词知识表示知识表示753.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)3.2谓词逻辑

3.2.4谓词知识表示初始状态机器人拿起763.2谓词逻辑

3.2.4谓词知识表示机器人放下BoxEmptyHanded(Robot)At(Robot,B)On(Box,B)Table(A)Table(B)机器人走到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.4谓词知识表示机器人放下Box机773.2谓词逻辑

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

3.2.3谓词演算与推理前束范式—约束在783.2谓词逻辑

3.2.3谓词演算与推理例P94求前束范式量词与指导变量：，自由出现的变量：，

换名规则替代规则

P933-7

3.2谓词逻辑

3.2.3谓词演算与推理例P94求793.2谓词逻辑

3.2.3谓词演算与推理

P933-8

P933-3

P933-43.2谓词逻辑

3.2.3谓词演算与推理803.2谓词逻辑

3.2.3谓词演算与推理谓词推理例：20世纪70年代的漫画都是日本漫画家创作的，这幅漫画是20世纪70年代的作品；因此它是日本漫画家的作品解：设P(x)：属于20世纪70年代的漫画

Q(y)：属于日本漫画家的作品

a:一幅漫画前提:

结论:Q(a)

证明:

前提引入量词消去前提引入假言推理3.2谓词逻辑

3.2.3谓词演算与推理谓词推理813.3谓词逻辑归结原理3.3谓词逻辑归结原理823.3谓词逻辑归结原理

3.3.1归结原理命题逻辑归结原理：将由前提A得到结论B的证明过程转化为证明A∧~B为矛盾式将其转化为合取范式，得到子句集

对于形如的公式求取子句集时，可以分别求各自的子句集，再取并集利用归结原理消去互补项，直到得到空子句。

3.3谓词逻辑归结原理

3.3.1归结原理命题逻辑归结原833.3谓词逻辑归结原理

3.3.1归结原理例(P→(Q→R))→

((P→Q)

→(P→R))

转化为待归结命题公式：(P→(Q→R))∧~((P→Q)

→(P→R))求子句集:分别对(P→(Q→R))和~((P→Q)→(P→R))两部分求取子句集，再取并集1、(P→(Q→R))<=>(~P∨(~Q∨R))<=>(~P∨~Q∨R)

2、~((P→Q)

→(P→R))<=>~(~(~P∨Q)∨(~P∨R))<=>~((P∧~Q)∨(~P∨R))<=>(~(P∧~Q)∧~(~P∨R))<=>((~P∨Q)∧(P∧

~R))子句集为：{~P∨~Q∨R,~P∨Q,P,~R}3.3谓词逻辑归结原理

3.3.1归结原理例(P→843.3谓词逻辑归结原理

3.3.1归结原理归结：

1、

~P∨~Q∨R

2、~P∨Q

3、P

4、~R

5、~P∨R1、2归结

6、R3、5归结

7、□4、6归结因此得证3.3谓词逻辑归结原理

3.3.1归结原理归结：853.3谓词逻辑归结原理

3.3.1归结原理步骤命题逻辑归结原理谓词逻辑归结原理1、建立A∧~B命题逻辑公式谓词逻辑公式2、求子句集求合取范式求前束合取范式消去量词3、归结直接消去互补项利用置换与合一消去互补项归结式加入子句集归结式加入子句集3.3谓词逻辑归结原理

3.3.1归结原理步骤命题逻辑归863.3谓词逻辑归结原理

3.3.1归结原理谓词逻辑归结原理的重点如何对前束合取范式消去量词命题逻辑谓词逻辑如何利用置换与合一对不同变量的子句进行置换命题逻辑谓词逻辑3.3谓词逻辑归结原理

3.3.1归结原理谓词逻辑归结原873.3谓词逻辑归结原理

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

3.3.1归结原理求前束合取范式883.2谓词逻辑

3.2.3谓词演算与推理量词辖域收缩与扩张等值式3.2谓词逻辑

3.2.3谓词演算与推理量词辖域收缩与扩893.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、辖域中的公式化为合取范式3.2谓词逻辑

3.2.3谓词演算与推理求前束合取范式1903.3谓词逻辑归结原理

3.3.2Skolem标准型例求前束合取范式

3.3谓词逻辑归结原理

3.3.2Skolem标准型例913.3谓词逻辑归结原理

3.3.2Skolem标准型Skolem标准型：对前束合取范式消去所有的量词。P100第一步：消去存在量词

：1、如果

之前(左边)没有任意量词

,则用常量替换

的指导变量可用常量b替换x消去存在量词，得P(b,a)2、如果

之前(左边)有任意量词

，则用任意量词的函数替换

的指导变量可用f(x)替换y消去存在量词，第二步消去任意量词

：简单的省略即可3.3谓词逻辑归结原理

3.3.2Skolem标准型Sk923.3谓词逻辑归结原理

3.3.2Skolem标准型例：1、消去存在量词

y和

u

：

y前面有任意量词，指导变量为x，因此用f(x)替换y，

u前面有任意量词，指导变量为x，因此用g(x)替换u2、消去任意量词：3.3谓词逻辑归结原理

3.3.2Skolem标准型例：933.3谓词逻辑归结原理

3.3.2Skolem标准型例判断下列的消去量词的过程是否正确。证明：①

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.2Skolem标准型例943.3谓词逻辑归结原理

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

3.3.3子句集定义953.3谓词逻辑归结原理

3.3.1归结原理谓词逻辑归结原理的重点如何对前束合取范式消去量词命题逻辑谓词逻辑如何利用置换与合一对不同变量的子句进行置换命题逻辑谓词逻辑3.3谓词逻辑归结原理

3.3.1归结原理谓词逻辑归结原963.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}3.3谓词逻辑归结原理

3.3.4置换与合一置换：形如973.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/y} P(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}3.3谓词逻辑归结原理

3.3.4置换与合一例:设有公式983.3谓词逻辑归结原理

3.3.4置换与合一例：设θ={f(y)/x,z/y},λ={a/x,b/y,y/z},

对L=P(x,f(y),b)，先做θ置换，再做λ置换，即求

3.3谓词逻辑归结原理

3.3.4置换与合一例：设θ={993.3谓词逻辑归结原理

3.3.4置换与合一置换的合成：对谓词公式L，设θ={t1/x1,t2/x2,…,tn/xn}

和λ={u1/y1,u2/y2,…,un/yn}

为两个置换，则

,称为θ和λ的合成，可由下式得到

1、如果，则消去

2、当，删去3.3谓词逻辑归结原理

3.3.4置换与合一置换的合成：1003.3谓词逻辑归结原理

3.3.4置换与合一例：设θ={f(y)/x,z/y},λ={a/x,b/y,y/z}

求1、如果tiλ=xi

,则消去tiλ/xi

2、当，删去3.3谓词逻辑归结原理

3.3.4置换与合一例：设θ={1013.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()}3.3谓词逻辑归结原理

3.3.4置换与合一例：对子句集1023.3谓词逻辑归结原理

3.3.4置换与合一合一：设有公式集，如果存在一个置换θ，使，则称θ是F的一个合一。如果谓词公式F1、F2

可合一，那么就是一对互补项

{P(x),~P(a)}经合一{a/x}得到{P(a),~P(a)}谓词逻辑归结原理：如果子句集中的两个字句含有互补项，则可以进行归结消去3.3谓词逻辑归结原理

3.3.4置换与合一合一：设有公1033.3谓词逻辑归结原理

3.3.4置换与合一例：下列字句都可以归结

{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置换与合一例：下列字句都1043.3谓词逻辑归结原理

3.3.4置换与合一最一般合一(mgu)设是谓词公式F的一个合一，如果对于F的任意一个合一θ，都存在一个置换λ，使

,则称是一个最一般合一。求取办法：对每一项逐一比较并进行合一置换P1041、令2、令3、如果已经合一，停止迭代，；否则，找不一致集4、若中存在元素和，且不出现于中，转5；否则，不可合一5、令，6、k=k+1,转3

3.3谓词逻辑归结原理

3.3.4置换与合一最一般合一(1053.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))}

23W0未合一，从左到右找不一致集，

45令