三基于谓词逻辑的机器推理.ppt

第三章 基于谓词逻辑的机器推理 本章主要内容： 3.1 一阶谓词逻辑 ?3.2 归结演绎推理 ?3.3应用归结原理求取问题答案 ?3.4 归结策略 ?3.5 归结反演程序举例 第一节 一阶谓词逻辑 本节主要内容： 谓词、函数、量词 谓词公式 谓词逻辑中的形式演绎推理 谓词、函数、量词 谓词：表达式 P(x1, x2, …, xn)说明： （1）其中，P是谓词符号（简称谓词）约定用大写英文字母打头作为谓词符号(Prolog?)。 （2）xi(i=1,2,…n)是参数项（简称项） （3）由于有n个参数项，P(x1, x2, …, xn)表示了一个n元谓词公式。 举例：P（x），Q（x，y） 谓词、函数、量词 函数：表达式 f(x1, x2, …, xn)说明： （1）其中，f是函数符号（简称函数）约定用小写英文字母打头作为函数符号。 （2）xi(i=1,2,…n)是个体变元 （3）由于有n个变元，f(x1, x2, …, xn)成为n元个体函数 举例：father（li），sum（x，y） 约定：如果为单个项，用小写字母x，y，z等作为变元的符号，小写字母a，b，c等作为个体常元符号 谓词、函数、量词 量词： ?全称量词--以符号（ ? x）P(x)来表示对于某个论域中的所有个体x,都有P(x）真值为T。（一切，任一，全体，凡是等）　　?存在量词--以符号（ $ x）P(x)来表示某个论域中至少存在一个个体x，使P(x) 真值为T。 （存在，有些，至少有一个，有的）　　这里，P(x)是任意逻辑语句，也称作量词的管辖范围（简称辖域）。 谓词、函数、量词 量词举例： (?x)[Robot(x)=Color(x, Gray)],所有机器人都是灰色的； (?x)[Road(x)? Lead(x, Roma)],条条大路通罗马；（$x)[Isa(x,Robot)∧Inroom(x,R1)],至少有一个机器人在房间R1 中； （x)(?y)[Person(x)∧Book(y)∧Give(Mary,x,y)]，Mary给每个人一本书。 （x)[Person(x)∧Give（Mary,x,y）], Mary给每人某个同样的东西。 谓词公式 谓词公式的一般形式是： P(x1, x2, …, xn)其中，P是谓词符号（简称谓词），xi(i=1,2,…n)是参数项（简称项）；由于有n个参数项，P(x1, x2, …, xn)表示了一个n元谓词公式。项可以是常量、变量或函数。 例如，谓词公式Inroom(Robot, L1)包括2个常量项，Married(father(L1), x)包括函数项father(L1)和变量项x, father(L1)映射L1到他的父亲。为避免混淆和增加表示的清晰性，谓词和常量项通常以首字母大写的形式来表示，而函数和变量则以小写字母的形式表示。 　　当一谓词公式中不含变量，或变量值均取定时，谓词公式所表示的事物间的关系也就唯一确定。若这种关系在应用域确实存在，则谓词公式取值为真（记为T），否则为假（记为F）。在这个意义上，每个谓词公式均有一个确定的真值：T或F。 谓词公式：连词和量词（见上） 　　 谓词公式是谓词演算的基本单元，也称为原子公式。通过引入连词和量词，可以把原子公式组合为复合谓词公式。 1） 连词谓词演算中使用的连词主要有:?（非）、∧（与）、∨（或）、=（蕴涵，也表示为 -）和?（等价，也表示为 ?）。 看几个例子：?Inroom(Robot,R2) Isa(Liming, Student)∧Lives(Liming,House-1)∧Color(House-1, White)Isa(Wang, Teacher)∨Isa(Wang, Officer)At(Liming,School)=At(Wang, School) At(Liming,School)?At(Wang, School) 谓词公式 一阶谓词　　若限定不允许对谓词、连词、量词和函数名进行量化处理，且参数项不能是谓词公式，则这样的谓词演算是一阶的。例如: （? P）P(A)、 （? P） （? x）P(x) 、 Married(y(L1), Mary，y)（y是变量）都不是一阶谓词公式。 本书中所用到的谓词演算均是一阶的。 谓词公式 谓词公式的永真性和可满足性　　1） 谓词公式的永真性 　　若某谓词公式P对于某论域D上的所有可能的解释都有真值T，则称P在D上是永真的；若P在每个可能的非空论域上均永真，则称P是永真的。　　2） 谓词公式的可满足性　　对于谓词公式P，若在论域D上至少