人工智能第2章(知识表示方法3-谓词逻辑)74.pptx
《人工智能第2章(知识表示方法3-谓词逻辑)74.pptx》由会员分享，可在线阅读，更多相关《人工智能第2章(知识表示方法3-谓词逻辑)74.pptx（74页珍藏版）》请在冰点文库上搜索。
人工智能ArtificialIntelligence（AI）,许建华南京师范大学计算机科学与技术学院2011年秋季,第2章知识表示方法2.1状态空间法2.2问题归约法2.3谓词逻辑法,2.3谓词逻辑法数理逻辑（符号逻辑）是用数学方法研究形式逻辑的一个分支。
它通过符号系统来表达客观对象以及相关的逻辑推理。
常用的是命题逻辑和谓词逻辑,谓词逻辑是数理逻辑的基本形式，是基于谓词分析的一种形式化（数学）语言人工智能中的谓词逻辑法是指用一阶谓词来描述问题求解和定理证明（限于本课程）,2.3.0命题逻辑的复习,1、命题逻辑的基本概念命题是能够判断真或假的陈述句通常用大写字母来表示，如A,B,P,Q等命题的真假值一般用T或F来表示,例：
雪是白的。
（陈述句，T）雪是蓝的。
（陈述句，F）雪是黑的。
（陈述句，F）他是学生。
（陈述句，他泛指，无法判断真假）你今天上课没有？
（疑问句）去北校区，请坐校车！
（祈使句）,命题逻辑是研究命题及命题之间关系的符号逻辑系统。
在命题逻辑中，表示单一意义的命题，称之为原子命题。
原子命题通过“联结词”构成复合命题。
五个联结词：
“”表示“非”复合命题P为真，当且仅当P为假。
“”表示“合取”复合命题“PQ”为真，当且仅当P和Q都为真。
“”表示“蕴含”复合命题“PQ”为假，当且仅当P为真且Q为假。
“”表示“析取”复合命题“PQ”为真，当且仅当P、Q两者之一为真。
“”表示“等价”复合命题“PQ”为真，当且仅当P、Q同时为真、或者同时为假。
联接词的优先顺序：
非、合取、析取、蕴含、等价注：
可以用括号表示优先级,真值表,命题变元：
用符号P、Q等表示的不具有固定、具体含义的命题。
它可以表示具有“真”、“假”含义的各种命题。
命题变元可以利用联结词构成所谓的合适公式。
合适公式的定义若P为原子命题，则P为合适公式，称为原子公式。
若P是合适公式，则P也是一个合适公式。
若P和Q是合适公式，则PQ、PQ、PQ、PQ都是合适公式。
经过有限次使用规则1、2、3，得到的由原子公式、联结词和园括号所组成的符号串，也是合适公式。
对于合适公式，规定下列运算优先级：
逻辑联结词的运算优先次序为：
、同级联结词按出现顺序优先运算,在命题逻辑中，主要研究推理的有效性。
即：
能否根据一些合适公式（前提）推导出新的合适公式（结论）。
一些合适公式（前提条件）,合适公式（结论）,？
在命题逻辑中，最基本的单元是命题，它是作为一个不可分割的整体。
例如：
雪是黑的命题逻辑具有较大的局限性，不合适于表达比较复杂的问题。
例：
所有科学都是有用的（假设1）。
数理逻辑是科学（假设2）。
所以，数理逻辑是有用的（结论）。
很明显，我们无法用两个假设推断出结论。
谓词逻辑是命题逻辑的扩充和发展。
它将一个原子命题分解成客体和谓词两个组成部分。
例如：
雪是黑的客体谓词本课程主要介绍一阶谓词逻辑。
2.3.1谓词演算,1、语法与语义谓词逻辑的基本组成部分谓词变量函数常量园括号、方括号、花括号和逗号,例“机器人（Robot）在第一个房间（Room1）内”，可以表示为：
INROOM（ROBOT，r1）其中INROOM是谓词ROBOT和r1是常量,谓词是指个体（客体）所具有的性质或者若干个体之间的关系。
用大写字母来表示。
个体是可以具体的（如:
小张、3、5）也可以是抽象的（如:
x,y）。
例：
小明是学生，A表示是“是学生”，x表示“小明”，记作A（x）。
x大于y，G表示“大于”，记作G（x,y）。
论域：
由个体组成的集合。
（个体）变量：
定义在某一个论域上的变量。
用x,y,z来表示。
函数（或函词）：
以个体为变量，以个体为值的函数。
一般用小写字母来表示，例如f（x）,f（x,a）。
如果谓词有n个变量，称之为n元谓词，并约定0元谓词就是命题（谓词的特例）。
如果函数有n个个体，称之为n元函数，并约定0元函数就是常量。
常量习惯上用小写字母来表示，如a,b,c。
项的定义：
常量是项变量是项如果f是n元函数，且t1,tn（n1）是项，则f（t1,tn）也是项所有的项都必须是有限次应用上述规则产生的,项的例子：
常量：
a变量：
x函数：
f（x,a）g（f（x,a）,原子（谓词）公式的（递归）定义：
原子命题是原子公式如果t1,tn（n1）是项，P是谓词，则P（t1,tn）是原子公式其它表达式都不是原子公式,原子公式的例子1、原子公式：
P（原子命题）2、项：
x,a,f（x,a），谓词：
P原子公式：
P（x,a,f（x,a）,2、连词和量词,联结词（连词）就是命题逻辑中的五个，它们的含义也是一样的。
两个量词：
全称量词，记作“x”,含义是“对每一个x”或“对一切x”。
存在量词，记作“x”，含义是“存在某个x”、“有一个x”或者“某些x”。
All,A,Exist,E,例1：
“所有的机器人都是灰色的”，用谓词逻辑可以表示成：
（x）ROBOT（x）COLOR（x，gray）,例2：
“一号房间里有一个物体”，可以表示成（x）INROOM（x,r1）,我们称x是被量化了的变量，称为约束变量。
否则称之为自由变量。
一阶谓词：
只允许对变量施加量词，不允许对谓词和函数施加量词。
2.3.2谓词公式,1、谓词公式的定义,利用连词和量词可以将原子（谓词）公式组成复合谓词公式，称之为分子谓词公式、谓词合适公式、谓词公式、合适公式。
（谓词）合适公式的（递归）定义：
原子（谓词）公式是合适公式。
若A是合适公式，则A也是合适公式。
若A和B是合适公式，则AB、AB、AB、AB也是合适公式。
若A是合适公式，x为A的自由变元（变量），则（x）A和（x）A都是合适公式。
只有按上述规则求得的公式才是合适公式。
例：
任何整数或者为正或者为负。
数学表达：
对于所有的x，如果x是整数，则x或者为正、或者为负。
记作：
I（x）：
“x是整数”。
P（x）：
“x是正数”。
N（x）：
“x是负数”。
谓词公式：
（x）（I（x）（P（x）N（x））,2、合适公式的性质,如果P和Q是合适公式，则由这两个合适公式构成的合适公式的真值表与前面介绍的真值表相同。
如果两个合适公式的真值表相同，则我们称这两个合适公式是等价的，可以用“”来表示。
对于命题合适公式和谓词合适公式有下列等价关系：
否定之否定：
（P）等价于PPQ等价于PQ狄.摩根定律（PQ）等价于PQ（PQ）等价于PQ,分配律P（QR）等价于（PQ）（PR）P（QR）等价于（PQ）（PR）交换律PQ等价于QPPQ等价于QP,结合律（PQ）R等价于P（QR）（PQ）R等价于P（QR）逆否律PQ等价于QP,说明：
上述等价关系对命题合适公式、谓词合适公式都成立。
对于谓词合适公式有下列等价关系：
（x）P（x）等价于（x）P（x）（x）P（x）等价于（x）P（x）（x）P（x）Q（x）等价于（x）P（x）（x）Q（x）（x）P（x）Q（x）等价于（x）P（x）（x）Q（x）,（x）P（x）等价于（y）P（y）（x）P（x）等价于（y）P（y）,注释：
这两个关系说明，在一个量化的表达式中的约束变量是一类虚元，它们可以用任何不在表达式中出现的其它变量来代替。
2.3.3置换与合一,1、置换,置换的定义：
形如t1/v1,tn/vn的集合，称为一个置换，其中vi是不同的变量，ti是与vi不同的项。
例或例子的定义：
设t1/v1,tn/vn为一个置换，E是一个原子谓词公式。
则E表示将E中的vi同时用ti（i=1,n）代入后所得到的结果，E称为E的一个例子。
例：
表达式（原子谓词公式）Px,f（y）,B的四个置换及其对应的四个例子（B是常量）,s1=z/x,w/ys2=A/ys3=q（z）/x,A/ys4=c/x,A/y,Px,f（y）,Bs1=Pz,f（w）,BPx,f（y）,Bs2=Px,f（A）,BPx,f（y）,Bs3=Pq（z）,f（A）,BPx,f（y）,Bs4=Pc,f（A）,B,Px,f（y）,B,置换的合成：
设t1/x1,tn/xn和s1/y1,sm/ym是两个置换，则和的合成是如下置换：
t1/x1,ti/xi,tn/xn,s1/y1,sn/ym其中，若yj是x1,xn之一者消去，对于任何tj=xj者消去，并记成。
如何求ti:
s1/y1,sm/ym如果ti出现y1,.,ym中的变量yi，则用其对应的项si来代替。
例：
=t1/x1,t2/x2f（y）/x,z/y=s1/y1,s2/y2,s3/y3=a/x,b/y,y/z=t1/x1,t2/x2,s1/y1,s2/y2,s3/y3=f（b）/x,y/y,a/x,b/y,y/z=f（b）/x,y/z,注意：
置换的合成满足结合律，不满足交换律。
（s1s2）s3=s1（s2s3）（满足结合律）s1s2s2s1（不满足交换律）,例：
s1=z/x,w/ys2=A/ys1s2=z/x,w/y,A/y=z/x,w/ys2s1=A/y,z/x,w/y=A/y,z/x,2、合一,当某一个置换s作用于表达式集合Ei的每一个元素，此时我们用Eis来表示置换例子的集合。
如果存在一个置换s，使得E1s=E2s=Eis=则我们称表达式集合Ei是可合一的，并称s为Ei的合一者。
原因是它的作用是使集合Ei成为单一形式。
其中，Ei是原子谓词公式。
例：
表达式集合Px,f（y）,B,Px,f（B）,B的合一者为是s=A/x,B/yPx,f（y）,Bs=PA,f（B）,BPx,f（B）,Bs=PA,f（B）,B,如果s是Ei的任意一个合一者，又存在某一个s，使得s=gs或者Eis=Eigs则称g是Ei的最通用（最一般）的合一者，记作mgu。
例：
s=A/x,B/y是表达式集合Px,f（y）,B,Px,f（B）,B的一个合一者，该集合的最一般的合一者是：
g=B/y,3、合一算法,分歧集（或不一致集合）的定义。
设有一非空有限公式集合F=F1,Fn，从F中各个公式的第一个符号同时向右比较，直到发现第一个彼此不尽相同的符号为止，从F中的各个公式中取出那些以第一个不一致符号开始的最大的子表达式为元素，组成一个集合D，称为F的分歧集（不一致集合）。
其中，Fi（i=1,n）是原子谓词公式,例：
公式集：
F=P（x,g（f（y,z）,x）,y）,P（x,g（a,b）,b）,P（x,g（g（h（x）,a）,y）,h（x）分歧集为：
D=f（y,z）,a,g（h（x）,a）,设F为非空有限表达式集合，则可以按下列步骤求出mgu：
置k=0，Fk=F,k=（空置换，即不含元素的置换）。
若Fk只有一个表达式，则算法终止，其中k就是要求的mgu。
找出Fk的分歧集Dk。
合一算法：
若Dk中存在元素ak和tk，其中ak是变元，tk是项，且ak不在tk中出现，则置：
k+1=ktk/akFk+1=Fktk/akk=k+1然后转向。
否则，继续。
算法终止，F的mgu不存在。
合一算法的流程图,k=0,Fk=F,k=,|Fk|1？
求得mgu、结束,求出不一致集合,有置换？
求出新置换；更新公式集合与旧置换，k+,无解、结束,说明：
1、合一算法是消解原理的基础。
2、合一算法中的公式集就是从谓词合适公式化成的子句集。
例：
求F=P（a,x,f（g（y）,P（z,h（z,u）,f（u）的最一般的合一者。
解：
我们根据合一算法一步一步地求出mgu。
第一步：
k=0,F0=F,0=F0的分歧集合D0=a,z置换：
a/z1=0a/z=a/zF1=F0a/z=P（a,x,f（g（y）,P（a,h（a,u）,f（u）k=1F1不是单一表达式,F=P（a,x,f（g（y），P（z,h（z,u）,f（u）,第二步：
D1x,h（a,u）置换：
h（a,u）/x21h（a,u）/x=a/z,h（a,u）/xF2=F1h（a,u）/x=P（a,h（a,u）,f（g（y）,P（a,h（a,u）,f（u）k=2,F=P（a,x,f（g（y），P（a,h（a,u）,f（u）,第三步：
D2g（y）,u置换：
g（y）/u32g（y）/u=a/z,h（a,g（y）/x,g（y）/uF3=F2g（y）/u=P（a,h（a,g（y）,f（g（y）k=3,F=P（a,h（a,u）,f（g（y），P（a,h（a,u）,f（u）,F3是单一表达式，所以3a/z,h（a,g（y）/x,g（y）/u是F的最一般合一者,例：
F=Q（f（a）,g（x）,Q（y,y）是否可合一？
第一步：
k=0,F0=F,0=F0的分歧集合D0=f（a）,y置换：
f（a）/y10f（a）/y=f（a）/yF1=F0f（a）/y=Q（f（a）,g（x）,Q（f（a）,f（a）k=1F1不是单一表达式,第二步：
D1g（x）,f（a）不存在着变量，所以不可合一。
F1=Q（f（a）,g（x）,Q（f（a）,f（a）,课堂作业求公式集W=Q（x,y,z）,Q（a,f（b）,a）的最一般的合一者?
其中，x,y,z为变量，a为常量，f为函数,第一步：
k=0,W0=W,0=W0的分歧集合D0=a,x置换：
a/x10a/x=a/xW1=W0a/x=Q（a,y,z）,Q（a,f（b）,a）k=1W1不是单一表达式,Q（x,y,z）,Q（a,f（b）,a）,第二步：
W1的分歧集合D1=f（b），y置换：
f（b）/y21f（b）/y=a/x,f（b）/yW2=W1f（b）/y=Q（a,f（b）,z）,Q（a,f（b）,a）k=2W2不是单一表达式,Q（a,y,z）,Q（a,f（b）,a）,第三步：
W2的分歧集合D0=a,z置换：
a/z32a/z=a/x,f（b）/y,a/zW3=W2a/z=Q（a,f（b）,a）k=3W3是单一表达式，mgu=3=a/x,f（b）/y,a/z,Q（a,f（b）,z）,Q（a,f（b）,a）,本章小结三种基本的知识表达方法：
状态空间法（状态、操作符、图表示）问题归约法（原始问题、本原问题、操作符、与或图表示）谓词逻辑法（谓词公式、置换、合一算法）,
升级会员 