谓词逻辑与归结原理

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

p∧～

r→～

p3第三页，共一百八十页，编辑于2023年，星期二怪物洞穴人工智能的经典实验环境—怪物洞穴(wumpus世界)洞穴有多个房间组成某个房间中藏着一只怪物wumpus，它会吃掉进入这个房间的人，相邻房间中能够感觉到臭味某些房间中有陷阱，进入房间会被陷阱吞噬，相邻房间中能够感觉到微风游戏的主角是一个智能体，可以进入相邻的房间(对角线不可以)智能体有且仅有一支箭，用这支箭可以射杀怪物某个房间中有金子，游戏的目标是智能体找到金子4第四页，共一百八十页，编辑于2023年，星期二怪物洞穴智能体行动的关键是要根据获得的信息推理，从而判断哪个房间有怪物？哪个房间有陷阱？哪个房间是安全的？房间[4,2]和[2,3]有陷阱，房间[3,4]有怪物，房间[4,3]有金子5第五页，共一百八十页，编辑于2023年，星期二3.1命题逻辑6第六页，共一百八十页，编辑于2023年，星期二3.1命题逻辑命题—能够判断真假的陈述句陈述句真值唯一，可用二进制表示用小写字母进行标识例1、北京是中国的首都。2、华南师范大学位于岗顶附近。3、1+1=24、计算机系的学生必修C或JAVA。5、坐着花生过黄河5、x+1=26、吃饭了吗？7、南无阿弥陀佛8、我正在说假话7第七页，共一百八十页，编辑于2023年，星期二3.1命题逻辑简单命题与复合命题简单命题：(原子命题)一个命题无法分解为更简单的子命题复合命题：由简单命题用联结词联结而成的命题

1、由若干简单命题组成；2：由联结词联结例：1、北京是中国的首都。2、华南师范大学位于岗顶附近。3、计算机系的学生必修C或JAVA。4、这家的报价单配置合理并且价格低廉。5、“李四是犯罪嫌疑人”“李四有犯罪动机”8第八页，共一百八十页，编辑于2023年，星期二3.1命题逻辑合式公式：单个常量或者变量的命题构成合式公式联结词联结的合式公式的组合也是合式公式合式公式的有限次组合称为命题公式命题公式：有限次合式公式组合的形式化描述，本书中以大写字母标识。9第九页，共一百八十页，编辑于2023年，星期二3.1命题逻辑基本联结(连接)符号～非，否定,﹁；∧与，合取，AND的首字母；∨或，析取，vel

→

蕴含式A：a→b表示，如果a，则b；

↔

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

↔10第十页，共一百八十页，编辑于2023年，星期二3.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→~p11第十一页，共一百八十页，编辑于2023年，星期二3.1命题逻辑例：怪物洞穴如果房间[1,1]中有臭味，则房间[1,2]或[2,1]中有怪物表示房间[i,j]中有臭味表示房间[i,j]中有怪物

练习：如果房间[1,1]中没有臭味，则房间[1,2]和[2,1]中没有怪物12第十二页，共一百八十页，编辑于2023年，星期二3.1命题逻辑练习：扫雷游戏设Xi,j表示方格[i,j]中有一个地雷。写出方格[1,1]周围恰好有2颗地雷的命题公式12345……5432113第十三页，共一百八十页，编辑于2023年，星期二3.1命题逻辑命题公式的赋值对命题公式中的所有的命题变量各赋给一个值0，1。真值表pq~pp∧qp∨qp→qp↔q0001101114第十四页，共一百八十页，编辑于2023年，星期二3.1命题逻辑复合命题的真值例：p:周杰伦是一个流行歌手q:人工智能是计算机科学的一个分支

r:牛在天上飞求下列复合命题的真值~p∧qp∧~q((~p∧q)∨(p∧~q))→r(q∨r)→(p→~r)p→~r(~p∨r)(p∧~r)我们关心的是复合命题中命题之间的真值关系，而不关心命题的内容。15第十五页，共一百八十页，编辑于2023年，星期二3.1命题逻辑命题公式的分类重言式或永真式tautology，设A为任一命题公式，若A在它的各种赋值下取值均为真，则称A是重言式例：P∨~P矛盾式或永假式contradictory设A为任一命题公式，若A在它的各种赋值下取值均为假，则称A是永假式。例：P∧~P16第十六页，共一百八十页，编辑于2023年，星期二3.1命题逻辑可满足式satisfiable设A为任一命题公式，如果存在一组取值使A为真，则A为可满足式。即：对于命题公式A，若A不是矛盾式，则称A是可满足式。例：P∧Q

非重言式的可满足式既是可满足式，又不是重言式17第十七页，共一百八十页，编辑于2023年，星期二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；18第十八页，共一百八十页，编辑于2023年，星期二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*蕴含等值式：A→B<=>~A∨B；*等价等值式：A↔B<=>(A→B)∧(B→A)；假言易位式：

A→B<=>~B→~

A

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

~

B；归谬论：(A→B)∧(A→~B)<=>~A；19第十九页，共一百八十页，编辑于2023年，星期二3.1命题逻辑合取范式与析取范式简单析取式：有限个命题变元或其否定，析取联结符

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

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

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

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

分配律22第二十二页，共一百八十页，编辑于2023年，星期二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)

;等幂律23第二十三页，共一百八十页，编辑于2023年，星期二3.1命题逻辑课堂练习计算合取范式(p→q)∧~

(~q

→~

p)(~p∨q)∧~

q

∧

p24第二十四页，共一百八十页，编辑于2023年，星期二3.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

)25第二十五页，共一百八十页，编辑于2023年，星期二3.1命题逻辑命题逻辑推理规则前提引入规则任何证明的步骤上，都可以引入前提；结论引入规则任何证明的步骤上，所得到的结论都可以作为后续证明的前提；置换规则任何证明的步骤上，命题公式中任何子命题都可以用与之等值的命题公式置换；26第二十六页，共一百八十页，编辑于2023年，星期二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析取三段论：27第二十七页，共一百八十页，编辑于2023年，星期二3.1命题逻辑例怪物洞穴表示房间[i,j]中有臭味表示房间[i,j]中有怪物表示房间[i,j]中有微风表示房间[i,j]中有陷阱28第二十八页，共一百八十页，编辑于2023年，星期二3.1命题逻辑初始状态，在房间[1,1]处没有感觉到微风，也没有臭味，则相邻房间为安全的，既没有怪物也没有陷阱。前提：

结论：证明：前提引入

等价等值式简化前提引入拒取式摩根律29第二十九页，共一百八十页，编辑于2023年，星期二3.1命题逻辑归结原理证明的一般方法由已知条件正向推导结论，演绎推理假定结论不成立，逆向推导与已知条件矛盾，反证法命题逻辑证明的归谬思想P85归结原理的思想：如果证明A∧~B为永假式，则得证30第三十页，共一百八十页，编辑于2023年，星期二归结推理命题逻辑谓词逻辑Skolem标准形、子句集基本概念谓词逻辑归结原理合一和置换、控制策略数理逻辑命题逻辑归结Herbrand定理31第三十一页，共一百八十页，编辑于2023年，星期二3.1命题逻辑归结方法的思想1、将待证明问题转化为其逆命题例：条件A，求证B.即A→B

其逆命题为：

A∧~B2、求合取范式，得到子句集构成合取范式的有限个简单析取式构成的集合就是子句集3、对子句集进行归结，得到空子句

32第三十二页，共一百八十页，编辑于2023年，星期二3.1命题逻辑将待证明问题转化为另一种形式证明问题的一般形式：已知：A成立求证：B成立即：证明A→BA→B<=>~A∨B蕴含等值式

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

A∧~B如果退出矛盾，则结论成立33第三十三页，共一百八十页，编辑于2023年，星期二3.1命题逻辑例：证明G是F的逻辑结论F1：P→WF2：~WG：~P分析：已知条件为：

(P→W)∧(~W)

结论为：~P

则，变换形式为：

(P→W)∧(~W)∧P34第三十四页，共一百八十页，编辑于2023年，星期二3.1命题逻辑子句与子句集P86对问题的变换形式，求其合取范式对于一个合取范式，该范式中的每一条简单析取式都是一个子句。子句集：合取范式下的所有子句构成其子句集。例：p∧(p∨q)∧(~p∨q)子句集为

{p,p∨q,~p∨q}35第三十五页，共一百八十页，编辑于2023年，星期二3.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蕴含等值式

36第三十六页，共一百八十页，编辑于2023年，星期二3.1命题逻辑归结式例{p∨q,~p∨q}归结后为:{q}归结的目标—空子句对于一个合取范式，如果有一个子句不可满足，则子句集就不可满足，该合取范式为永假式若一个子句集中包含空子句，则这个子句集一定是不可满足的例：{p,~p}归结后为

{□}37第三十七页，共一百八十页，编辑于2023年，星期二3.1命题逻辑归结法步骤建立待归结命题公式。将证明A→B为真转化为证明A∧~B为矛盾式求合取范式，得到子句集对子句集进行归结归结式作为新子句加入子句集进行归结当归结式为空子句□时停止，证明结束。出现空子句□，表示该子句集不可满足归结法的完备性：如果A→B成立，则利用归结法一定可以得到证明38第三十八页，共一百八十页，编辑于2023年，星期二3.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}39第三十九页，共一百八十页，编辑于2023年，星期二3.1命题逻辑例：怪兽洞穴1、在房间[1,1]处没有感觉到微风，也没有臭味。2、在房间[1,2]处感觉到微风，但没有感觉到臭味。3、在房间[2,1]处没有感觉到微风，但感觉到臭味。求证：房间[3,1]处有怪物*；房间[1,3]处有洞穴；房间[2,2]是安全的。40第四十页，共一百八十页，编辑于2023年，星期二3.1命题逻辑前提：求证：证明：要证明原命题为真，只需证明以下命题为恒假

41第四十一页，共一百八十页，编辑于2023年，星期二3.1命题逻辑于是，得到子句集为：42第四十二页，共一百八十页，编辑于2023年，星期二3.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归结43第四十三页，共一百八十页，编辑于2023年，星期二3.1命题逻辑思考：归结算法的计算机实现？

{S0,S1,S2,S3…}

终止条件：

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

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

44第四十四页，共一百八十页，编辑于2023年，星期二3.1命题逻辑好的归结控制策略初始状态优先选择包含结论的子句进行归结，之后每次都选择上一次归结得到的归结式与其他子句归结容易犯的错误字句集

1、P∨Q2、~P∨~Q3、□1、2归结3、Q∨~Q1、2归结不允许同时归结两个项45第四十五页，共一百八十页，编辑于2023年，星期二3.1命题逻辑归结方法是一种机械化的,可在计算机上加以实现的推理方法归结方法是一种反向推理形式提供了一种自动定理证明的方法归结的半完备性当定理可以证明时，归结方法是完备的当定理不可证明时，归结方法得不到任何结论，算法不一定会停止46第四十六页，共一百八十页，编辑于2023年，星期二3.2谓词逻辑47第四十七页，共一百八十页，编辑于2023年，星期二3.2.1基本概念命题逻辑描述简单的陈述性命题，但表示量化和谓词过于繁琐，也难以表示个体间的关系例：现在课堂上的所有学生都在上人工智能课命题逻辑s1:张三在上人工智能课s2:李四在上人工智能课s3:王五在上人工智能课

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

p∧q∧~r48第四十八页，共一百八十页，编辑于2023年，星期二3.2.1基本概念谓词逻辑Class(x)表示x在上人工智能课

x=张三，就得到了s1；

x=李四，就得到了s2；

x=王五，就得到了s3；

Class(x,y)表示x在上y课x=张三，y=人工智能，表示张三在上人工智能课x=李四，y=线性代数，表示李四在上线性代数课x=王五，y=睡觉，表示王五在上睡觉课49第四十九页，共一百八十页，编辑于2023年，星期二3.2.1基本概念命题是一个陈述句，它一般可分成主语和谓语两部分。有时还需要用到量词。主语：指独立存在的客体，可以是具体事物或抽象概念，也称为个体谓词：描述个体词性质或个体之间关系的词个体域：表示个体变量的取值范围，常用D表示常量：表示具体性质或关系的个体或者谓词变量：表示抽象或泛指的个体或者谓词。量词：表示数量的词。任意量词∀：表示“任意”，“所有”，也称为全称量词存在量词∃：表示“存在”50第五十页，共一百八十页，编辑于2023年，星期二3.2.1基本概念例：“关羽是人”，“张飞是人”这是两个不同的命题，其主语(个体)不同但是谓词是相同的，“是人”把谓语部分抽出来，假设Human(x)表示x是人这两个命题都可以用这个谓词来描述

Human(guanyu)Human(zhangfei)其中x属于个体变量，guanyu和zhangfei属于个体常量51第五十一页，共一百八十页，编辑于2023年，星期二3.2.1基本概念例：1、所有的人都是要死的2、有的人能够活到100岁

P(x)表示x是要死的，Q(x)表示x活到100岁个体域D为人类集合个体域D为总个体域集合引入特殊谓词R(x)表示x是人52第五十二页，共一百八十页，编辑于2023年，星期二3.2.1基本概念语言描述转换为谓词公式1、确定并说明谓词2、确定个体和个体域3、确定量词4、判断谓词间的逻辑关系53第五十三页，共一百八十页，编辑于2023年，星期二3.2.1基本概念例：我是计算机系的学生1、确定并说明谓词：方法一：Student(x,y)表示X是Y系的学生2、个体域：X：学生的集合，y：系的集合

Student(I,computer)

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

Computer(I)

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

P(I,computer)54第五十四页，共一百八十页，编辑于2023年，星期二3.2.1基本概念1、定义并说明谓词

Unlike(x,y)表示

x不喜欢y课2、个体域

x学生的集合，

y课程的集合3、量词存在例：有学生不喜欢上人工智能课Like(x,y)表示x喜欢y课Student(x)表示x是学生Like(x,y)表示x喜欢y课个体域x：人的集合逻辑关系：与55第五十五页，共一百八十页，编辑于2023年，星期二3.2.1基本概念例：任何人的兄弟都是男性确定并说明谓词Brother(x,y)表示x是y的兄弟Male(x)表示x是男性个体域

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

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

56第五十六页，共一百八十页，编辑于2023年，星期二3.2.1基本概念例：不管黑猫白猫，抓住老鼠就是好猫定义并说明谓词

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

Goodcat(x)表示x是好猫

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

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

Cat(x,y)与Catch(x,Mouse)蕴含Goodcat(x)量词：任意57第五十七页，共一百八十页，编辑于2023年，星期二3.2.1基本概念量词使用中的注意事项不同的个体域中，命题符号化的形式可能不同没有给定个体域的情况下，应考虑全总个体域如果个体域为有限集，对任意谓词P(x)有：多个量词同时出现时，不能颠倒其先后顺利，否则会改变公式的含义。58第五十八页，共一百八十页，编辑于2023年，星期二3.2.1基本概念例：love(x,y)表示x喜爱y

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

59第五十九页，共一百八十页，编辑于2023年，星期二3.2.2一阶谓词逻辑原子公式：设是任意n元谓词，是项，则称为原子公式。项：任何常量是项。任何变量是项。n≥1个参数的任何表达式(其中，是项，而f

是n

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

60第六十页，共一百八十页，编辑于2023年，星期二3.2.2一阶谓词逻辑谓词公式原子公式是谓词公式。若A为谓词公式，则～A也是一个谓词公式。若A和B都是谓词公式，则(A∧B)，(A∨B)，(A→B)和(AB)也都是谓词公式。若A是谓词公式，和也都是谓词公式。只有有限次应用上述规则得到的公式，才是谓词公式。61第六十一页，共一百八十页，编辑于2023年，星期二3.2.2一阶谓词逻辑对于，x称为指导变量

A称为相应量词的辖域

∃x(p(x))x在辖域A中的出现称为约束出现x以外的变量在辖域A中的出现称为自由出现∃x(p(x,y))62第六十二页，共一百八十页，编辑于2023年，星期二对于，指导变量：∀的辖域：

x,

y都是约束出现3.2.2一阶谓词逻辑例对于，指导变量:∃的辖域:

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

y是约束出现，

x是自由出现63第六十三页，共一百八十页，编辑于2023年，星期二3.2.2一阶谓词逻辑不同量词如果采用相同的指导变量名，易引起混淆一般要求不同的量词使用不同的指导变量名称64第六十四页，共一百八十页，编辑于2023年，星期二3.2.2一阶谓词逻辑当在一个公式中，一个变量符号既是约束出现的变量，又是自由出现的变量时，需要作变量符号更换。换名规则：将量词辖域中某个约束出现的变量及其指导变量替换为此辖域中未出现过的个体变量符号

x既作为指导变量约束出现又自由出现，因此要换掉其中之一换名规则更换的是指导变量可替换为65第六十五页，共一百八十页，编辑于2023年，星期二3.2.2一阶谓词逻辑替代规则：对某自由出现的个体变量用与原公式中未出现过的变量符号去替代，且处处替代。

x既作为指导变量约束出现又自由出现，且多处自由出现替代规则更换的是自由出现的变量，且处处替代替换为66第六十六页，共一百八十页，编辑于2023年，星期二3.2.2一阶谓词逻辑谓词公式的解释对谓词公式中的各种变量制定具体的常量去替代一个解释包括非空个体域D

D中一部分特定元素；

D上一些特定的函数；

D上一些特定的谓词。如果谓词公式在特定解释下为真，称这个解释满足这个谓词公式，是这个谓词公式的一个模型永真与不可满足67第六十七页，共一百八十页，编辑于2023年，星期二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、68第六十八页，共一百八十页，编辑于2023年，星期二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)=>169第六十九页，共一百八十页，编辑于2023年，星期二3.2.3谓词演算与推理谓词演算公式约束变量换名规则，Q为任意量词

(Qx)P(x)<=>(Qy)P(y)(Qx)P(x,z)<=>(Qy)P(y,z)量词消去等值式，对于有穷个体域量词否定等值式量词分配等值式70第七十页，共一百八十页，编辑于2023年，星期二3.2.3谓词演算与推理量词辖域收缩与扩张等值式71第七十一页，共一百八十页，编辑于2023年，星期二3.2.3谓词演算与推理前束范式—约束在前面的范式将所有的量词都移到最左边就得到了前束范式与合取范式类似，所有的谓词公式都可以改写成前束范式的形式求前束范式的步骤前束范式中每个量词的指导变量不同，如果指导变量相同，则需要利用换名规则进行替换。如果自由变量与指导变量相同，则需利用换名规则或替代规则替换其中之一利用量词辖域收缩扩张等值式替换72第七十二页，共一百八十页，编辑于2023年，星期二3.2.3谓词演算与推理例P94求前束范式量词与指导变量：，自由出现的变量：，

换名规则替代规则

P933-7

73第七十三页，共一百八十页，编辑于2023年，星期二3.2.3谓词演算与推理

P933-8

P933-3

P933-474第七十四页，共一百八十页，编辑于2023年，星期二3.2.3谓词演算与推理谓词推理例：20世纪70年代的漫画都是日本漫画家创作的，这幅漫画是20世纪70年代的作品；因此它是日本漫画家的作品解：设P(x)：属于20世纪70年代的漫画

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

a:一幅漫画前提:

结论:Q(a)

证明:

前提引入量词消去前提引入假言推理75第七十五页，共一百八十页，编辑于2023年，星期二3.2.4谓词知识表示谓词逻辑表达的规范形式P是谓词，而表示个体(主体或者客体)知识库：表达知识的一组谓词公式的集合。语句的集合对环境、规则等信息的结构化描述基于知识的智能体的核心构件76第七十六页，共一百八十页，编辑于2023年，星期二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,Scnu,teacher)

3、怪物洞穴中某个房间有微风、有臭味、没有怪物、没有陷阱、没有金子

Roomi,j

(x,y,z,m,n)参数分别对应有没有微风、臭味、怪物、陷阱、金子

Roomi,j(1,1,0,0,0)77第七十七页，共一百八十页，编辑于2023年，星期二783.2.4谓词知识表示谓词比命题更加细致地刻画知识：表达能力强如：北京是个城市，City(x)

把城市这个概念分割出来。把“城市”与“北京”两个概念连接在一起，而且说明“北京”是“城市”的子概念。(有层)谓词可以代表变化的情况如：City(北京),真。City(煤球)，假在不同的知识之间建立联系……….第七十八页，共一百八十页，编辑于2023年，星期二793.2.4谓词知识表示在不同的知识之间建立联系如：Human(x)→Lawed(x)，人人都受法律管制，x是同一个人。

Commit(x)→Punished(x)，x不一定是人也可以是动物。 而，{[Human(x)→Lawed(x)]→[commit(x)→Punished(x)]}， 意为如果由于某个x是人而受法律管制，则这个人犯了罪就一定要受到惩罚。第七十九页，共一百八十页，编辑于2023年，星期二803.2.4谓词知识表示谓词逻辑法是应用最广的方法之一，其原因是：谓词逻辑与数据库，特别是关系数据库就有密切的关系。在关系数据库中，逻辑代数表达式是谓词表达式之一。因此，如果采用谓词逻辑作为系统的理论背景，则可将数据库系统扩展改造成知识库。一阶谓词逻辑具有完备的逻辑推理算法。如果对逻辑的某些外延扩展后，则可把大部分的知识表达成一阶谓词逻辑的形式。(知识易表达)………..第八十页，共一百八十页，编辑于2023年，星期二813.2.4谓词知识表示谓词逻辑法是应用最广的方法之一，其原因是：谓词逻辑本身具有比较扎实的数学基础，知识的表达方式决定了系统的主要结构。因此，对知识表达方式的严密科学性要求就比较容易得到满足。这样对形式理论的扩展导致了整个系统框架的发展。逻辑推理是公理集合中演绎而得出结论的过程。由于逻辑及形式系统具有的重要性质，可以保证知识库中新旧知识在逻辑上的一致性(或通过相应的一套处理过程检验)、和所演绎出来的结论的正确性。而其它的表示方法在这点上还不能与其相比。第八十一页，共一百八十页，编辑于2023年，星期二823.2.4谓词知识表示

用逻辑(谓词)表示知识实质上是把人类关于世界的认识变成一个包含个体、函数和谓词的概念化形式。基本步骤：给出有关世界的个体、函数和谓词构造一阶谓词公式(集)对公式(集)给出解释，使该解释是相应公式(集)的一个模型。第八十二页，共一百八十页，编辑于2023年，星期二833.2.4谓词知识表示

为此逻辑表示法在实际人工智能系统上得到应用。

第八十三页，共一百八十页，编辑于2023年，星期二3.2.4谓词知识表示例：准前女友双眼皮,大眼睛doublefold(x)∧bigeyes(x)一头乌黑的头发blackhair(x)∧thickhair(x)一身漂亮的呢子大衣beautifuldress(x)走路的姿态赛过模特graceful(x)84第八十四页，共一百八十页，编辑于2023年，星期二853.2.4谓词知识表示例：一个房间里，有一机器人Robot，一个积木块Box，两个桌子A和B， 怎样用逻辑法描述从初始状态到目标状态的机器人操作过程？先引入谓词：

Table(A) 表示A是桌子

EmptyHanded(Robot)机器人Robot双手空空

At(Robot,A) 表示机器人Robot在A旁

Holds(Robot,Box) 机器人Robot拿着Box On(Box,A) 积木块Box在A上第八十五页，共一百八十页，编辑于2023年，星期二863.2.4谓词知识表示设定初始状态：

EmptyHanded(Robot) On(Box,A) Table(A) Table(B)目标状态是：

EmptyHanded(Robot) On(Box,B) Table(A) Table(B)第八十六页，共一百八十页，编辑于2023年，星期二87例(续)机器人的每个操作的结果所引起的状态变化，可用对原状态的增添表和删除表来表示。如机器人有初始状态是把Box从A桌移到B桌上，然后仍回到Alcove，这时同初始状态相比有： 增添表 On(Box，B) 删除表 On(Box，A)又如机器人从初始状态，走近A桌，然后拿起Box。这时同初始状态相比有： 增添表 At(Robot，A) Holds(Robot，Box)

删除表 At(Robot，Alcove)

EmptyHanded(Robot) On(Box，A)第八十七页，共一百八十页，编辑于2023年，星期二88例(续)进一步说，机器人的每一操作还需要先决条件。如机器人拿起A桌上的Box这一操作，先决条件：

On(Box，A)(Box在A上)

At(Robot，A)(机器人在A旁边)

EmptyHanded(robot)(机器人手空空)第八十八页，共一百八十页，编辑于2023年，星期二89例(续)先决条件成立与否的验证可以使用归结法。如将初始状态视作已知条件，而将要验证的先决条件作为结论，便可使用归结法了。归结过程如下：1)At(Robot,A)2)EmptyHanded(Robot)3)On(Box,A)4)Table(A)5)Table(B)6)～On(Box,A)∨～At(Robot,A)∨～EmptyHanded(Robot)(先决条件之否定)7)～At(Robot,A)∨～EmptyHanded(Robot) 3，68)～EmptyHanded(Robot) 1，79)NULL 2，8于是验证了先决条件的成立。第八十九页，共一百八十页，编辑于2023年，星期二903.2.4谓词知识表示

存在问题： 谓词表示越细，推力越慢、效率越低，但表示清楚。实际中是要折衷的。第九十页，共一百八十页，编辑于2023年，星期二3.3谓词逻辑归结原理91第九十一页，共一百八十页，编辑于2023年，星期二3.3.1归结原理命题逻辑归结原理：将由前提A得到结论B的证明过程转化为证明A∧~B为矛盾式将其转化为合取范式，得到子句集

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

92第九十二页，共一百八十页，编辑于2023年，星期二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}93第九十三页，共一百八十页，编辑于2023年，星期二3.3.1归结原理归结：

1、

~P∨~Q∨R

2、~P∨Q

3、P

4、~R

5、~P∨R1、2归结

6、R3、5归结

7、□4、6归结因此得证94子句集为：{~P∨~Q∨R,~P∨Q,P,~R}第九十四页，共一百八十页，编辑于2023年，星期二3.3.1归结原理步骤命题逻辑归结原理谓词逻辑归结原理1、建立A∧~B命题逻辑公式谓词逻辑公式2、求子句集求合取范式求前束合取范式消去量词3、归结直接消去互补项利用置换与合一消去互补项归结式加入子句集归结式加入子句集95第九十五页，共一百八十页，编辑于2023年，星期二3.3.1归结原理谓词逻辑归结原理的重点如何对前束合取范式消去量词命题逻辑谓词逻辑如何利用置换与合一对不同变量的子句进行置换命题逻辑谓词逻辑96第九十六页，共一百八十页，编辑于2023年，星期二3.3.1归结原理求前束合取范式：方法一：先转化为前束范式，再将辖域中的谓词公式转化为合取范式方法二：(1)消去联结词→和↔。(2)将联结词~向内深入，使之只作用于原子公式。(3)利用换名或替代规则使所有约束变元的符号都不同，并且自由变元与约束变元的符号也不同。(4)利用量词辖域的扩张和收缩，扩大量词至整个公式。(5)再将辖域中的谓词公式转化为合取范式。97第九十七页，共一百八十页，编辑于2023年，星期二3.2.3谓词演算与推理量词辖域收缩与扩张等值式98第九十八页，共一百八十页，编辑于2023年，星期二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、辖域中的公式化为合取范式99第九十九页，共一百八十页，编辑于2023年，星期二3.3.2Skolem标准型例求前束合取范式

100第一百页，共一百八十页，编辑于2023年，星期二3.3.2Skolem标准型Skolem标准型：对前束合取范式消去所有的量词。P100第一步：消去存在量词：1、如果之前(左边)没有任意量词,则用常量替换的指导变量可用常量b替换x消去存在量词，得P(b,a)2、如果之前(左边)有任意量词，则用任意量词的函数替换的指导变量可用f(x)替换y消去存在量词，第二步消去任意量词：简单的省略即可101第一百零一页，共一百八十页，编辑于2023年，星期二3.3.2Skolem标准型例：1、消去存在量词y和

u

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

u前面有任意量词，指导变量为x，因此用g(x)替换u2、消去任意量词：102第一百零二页，共一百八十页，编辑于2023年，星期二3.3.2Skolem标准型例判断下列的消去量词的过程是否正确。证明：①xy

G(x,y)②y

G(x,y)消去x

③G(x,

a)消去y对任意x，都存在一个恒定常量a，使G(x,

a)成立

①xy

G(x,y)②x

G(x,f(x))消去y③G(x,f(x))消去x对任意x，都存在一个与之对应的f(x)，使G(x,

f(x))成立103第一百零三页，共一百八十页，编辑于2023年，星期二3.3.3子句集定义文字：不含任何联结词的谓词公式子句：一些文字或其非的析取子句集：所有子句的集合计算过程将谓词公式转化为前束合取范式消去存在量词，略去任意量词，得Skolem标准型将各子句提出，得到子句集谓词公式不可满足，当且仅当其子句集不可满足的形如的谓词公式在求子句集时可以分别对求子句，再取其并集104第一百零四页，共一百八十页，编辑于2023年，星期二3.3.1归结原理谓词逻辑归结原理的重点如何对前束合取范式消去量词命题逻辑谓词逻辑如何利用置换与合一对不同变量的子句进行置换命题逻辑谓词逻辑105第一百零五页，共一百八十页，编辑于2023年，星期二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}106第一百零六页，共一百八十页，编辑于2023年，星期二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}107第一百零七页，共一百八十页，编辑于2023年，星期二3.3.4置换与合一例：设θ={f(y)/x,z/y},λ={a/x,b/y,y/z},

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

108第一百零八页，共一百八十页，编辑于2023年，星期二3.3.4置换与合一置换的合成：对谓词公式L，设θ={t1/x1,t2/x2,…,tn/xn}

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

为两个置换，则

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

1、如果，则消去