《问题求解的基本方法-基于归结的演绎推理-r》由会员分享，可在线阅读，更多相关《问题求解的基本方法-基于归结的演绎推理-r（42页珍藏版）》请在金锄头文库上搜索。
1、问题求解的基本方法 -基于归结的演绎推理, 2,逻辑,逻辑着重于研究推理过程是否正确，不考虑某一个特定语句是否正确。 例如： A:所有的商人都爱钱 B:任何爱钱的人，都会不择手段的赚钱 C:因此，所有的商人都会不择手段的赚钱, 3,逻辑可分为经典逻辑和非经典逻辑 经典逻辑分为命题逻辑和谓词逻辑 谓词逻辑是表达能力很强的形式语言，又具有许多成熟的推理方法因此，谓词逻辑及其推理方法，就成为知识表示和机器推理的基本方法之一。, 4,演绎推理,符号推理则是基于知识来求解问题的主要手段,符号推理的重要方式是演绎推理,演绎推理的基础为 谓词演算（或谓词逻辑），其是一种形式语言，可将各种陈述性（说明性）的描
2、述以形式化的方式表示，以便对它们作处理, 5,一 谓词演算,1.1 基本概念,符号字符串，作为事物的标识,个体词：可以独立存在的客体例如，小王、桌子、思想、定理等,个体常量：表示具体的或特定的个体的词，一般用a,b,c 等表示,个体变量：表示抽象或泛指的个体的词，一般用x,y,z等表示, 6,个体域：个体变量的取值范围，一般用D表示例如1，2，3，5，自然数集合等, 7,2. 符号结构描述事物间的相关方式,例如，Inroom (Robot, R1)是一个符号结构，Robot和R1均是符号，用于标识机器人和某个房间。而Inroom则是谓词符号，用以指示Robot和R1的相关方式 Friend(t
3、eacher,student), 8,例如：小王是个工程师小丽和小华是朋友,谓词用来刻画个体词的性质或他们之间的关系的词,谓词常量：具体性质或关系,谓词变量：抽象的或泛指, 9,形如Inroom(Robot，R1)的符号结构。谓词公式的一般形式是： P(x1, x2, , xn) 其中P是谓词符号（简称谓词），xi(i=1,2,n)是参数项（简称项）； 有n个参数项，称为n元谓词公式参数项可以是常量、变量或函数,3 谓词公式, 10,例如谓词公式Inroom(Robot, R1)包括2个常量项Married(Father(L1), x)包括函数项father(L1)和变量项xfather(L1
4、)映射L1到他的父亲,为避免混淆和增加表示的清晰性，谓词和常量项通常以首字母大写的形式来表示，而函数和变量则以小写字母的形式表示, 11,4 连词和量词,谓词公式是谓词演算的基本单元，也称为原子公式,通过引入连词和量词，可以把原子公式组合为复合谓词公式,通常将复合谓词公式称为逻辑语句，所以谓词演算也称为谓词逻辑,连词谓词演算中使用的连词主要有（非）、（与）、（或）、=（蕴涵，有时也表示为 ）和（等价，有时也表示为 ）, 12,在谓词公式前面加连词，称为否定，也叫做取反； 用连词连接谓词公式称为合取，产生的逻辑语句称为合取式，其每个成份称为合取项 用连词连接谓词公式称为析取，产生的逻辑语句称为析
5、取式，其每个成份称为析取项 用连词=连接谓词公式产生蕴涵式，连词左部称为前项，右部称为后项 用连词连接二个谓词公式产生等价式，等价式可以视为正、逆向二个蕴涵式的合取, 13,只要不下雨，我就骑自行车如果用A表示“下雨”，B表示“骑自行车”那么 A =BInroom(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(W
6、ang, School), 14,真值表, 15,量词 不包含变量的谓词公式和逻辑语句为命题，而基于命题的谓词演算为命题演算 命题演算是谓词演算的子集 谓词演算引入了量词来表示对变量的处理。量词分为二类： （1）全称量词以符号（“x）P(x)来表示对于某个论域中的所有（任意一个）个体x,都有P(x)真值为T。 （“x）Robot(x) Color(x, Gray),所有机器人都是灰色的；, 16,（2）存在量词以符号（$x）P(x)来表示某个论域中至少存在一个个体x，使P(x) 真值为T。 （$x）Isa(x,Robot)Inroom(x,R1),至少有一个机器人在房间R1 中；, 17,（x
7、）Road(x) Lead(x, Roma),条条大路通罗马； （x）（y）Person(x)Book(y)Give(Mary,x,y)，Mary给每个人一本书。 （“x）Person(x)Give（Mary,x,y）, Mary给每人某个同样的东西。,出现在量词符号中的变量，称为量词的约束变量 （或称变元），其取值仅在量词的辖域内有效 自由变量相对于约束变量, 18,若限定不允许对谓词、连词、量词和函数名进行量化处理，且参数项不能是谓词公式，则这样的谓词演算是一阶的 一阶谓词演算不允许在谓词、连词、量词和函数名的出现位置上使用变量,例如（ P）P(A) Married(y(L1), Mary
8、) P(x,Q(y) 都不是一阶谓词公式,简单的说，就是谓词公式中不含有谓词公式,6 一阶谓词演算, 19,1.合适公式的定义 单一谓词公式（即原子公式）是合适公式； 若A是合适公式，则A也都是合适公式； 若A和B都是合适公式，则AB、AB、A B和A B也都是合适公式； 4）若A是合适公式，x是约束变量，则（“x）A和（$x)A也是合适公式 5）只有按上述规则（1）至（4）求得的公式，才是合适公式在合适公式中连词优先级别是，、， 、 ，但可通过括号改变优先级。,1.2 合适公式, 20,合适公式的递归定义为形式化表示符号推理所需的知识提供了有效手段。例如对于语句“所有人都喜欢一种游戏”可以先
9、确定所用的原子公式Like(x,y)、Person(x)和Game(y),再以（“x）指示人（$y）指示游戏，就可建立合适公式： （x）（y）Person(x)Game(y)Like(x,y), 21,2 合适公式的解释,在不存在变量和量词的情况下，合适公式蜕化为命题。可以给命题中包含的各个原子公式指派真值（T或F），并称这种指派为命题的一个解释。一旦解释确定，就可依据连接原子公式的连词的作用求出命题的真值（T或F）。,在谓词逻辑中必须先定义一个拟观察个体的可能论域，并确定原子公式中变量项和函数项在论域中的取值，然后才能给原子公式指派真值, 22,作为例子，现在观察合适公式 （x） （$y）P
10、(x) Q(f(x),y)的一个解释的建立。 设该公式的论域为D=1，2；首先，对于x的每个取值，可以指派f(1)=2, f(2)=2, P(1)=T, P(2)=T；然后对于f(x)和y的每个取值组合（只有2个：2，1； 2，2）指派Q(2,1)=T, Q(2,2)=F。这些指派就确定了该合适公式的一个解释。显然，在这个解释下，合适公式有真值T。, 23,3.合适公式的永真性和可满足性,1）合适公式的永真性 若某合适公式P对于某论域D上的所有可能的解释都有真值T，则称P在D上是永真的；若P在每个可能的非空论域上均永真，则称P是永真的。 2）合适公式的可满足性 对于合适公式P，若在论域D上至少
11、可以建立一个解释，使P有真值T，则称P在D上是可满足的；若至少有一个论域使P可满足，则称P是可满足的。, 24,3） 合适公式的永假性 若某合适公式P对于论域D上的所有可能的解释都有真值F，则称P在D上是永假的(即不可满足的)；若P在每个可能的非空论域上均永假，则称P是永假的。, 25,显然，在可能的论域个数较少，每个论域自身又较小（包含个体对象较少）的情况下，易于判断合适公式的永真性和可满足性；即使论域个数较多，每个论域较大，只要解释的个数有限，永真性和可满足性总是可判定的。但若解释的个数无限时，就不能确保可以判定，或者不能确保在有限的时间内判定。, 26,4. 合适公式的性质,1） 双重否
12、定 (P) P,2） 蕴涵式转化 PQ PQ,3） 狄 摩根定律 (PQ) PQ (PQ) PQ, 27,4) 分配律 P(QR) (PQ)(PR） P(QR) (PQ)(PR),5）交换律 PQ QP PQ QP,6）结合律 (PQ)R P(QR） (PQ)R P（QR）, 28,7）逆否律PQ QP,8）量词否定($x)P(x) (x)(P(x)(x)P(x) （x)(P(x),9) 量词分配(x)P(x)Q(x) (x)P(x)(x)Q(x) (x）P(x)Q(x) （x）P(x)(x)Q(x), 29,10) 约束变量的虚元性（约束变量名的变换不影响合适公式的真值）(x)P(x) (y
13、)P(y)(x)P(x) (y)P(y), 30,1.3 合适公式的标准化,合取范式和析取范式定义1：文字是原子公式或原子公式之非定义2：公式G称为合取范式 ，当且仅当G有形式G1 Gn(n=1)，其中每个Gi都是文字的析取式定义3：公式G称为析取范式 ，当且仅当G有形式G1 Gn(n=1)，其中每个Gi都是文字的合取式, 31,合取范式的标准化过程,（1） 消去多余的量词若一个量词的辖域内并未出现量词的约束变量，则该量词是多余的，应将其消去。例如(x)P(y),则(x)可以消去。正常情况下，合适公式中不应出现多余的量词，后面的实例中就未出现多余的量词。,(2) 消去蕴涵符号应用“蕴涵式转化“
14、性质，例如实例： Q(x,y)P(y) Q(x,y)P(y), 32,(3) 内移否定符号 使其只出现在原子谓词公式前面，以构成否定文字。双重否定、狄.摩根定律、量词否定等性质 可以应用于这个目的。例如后面实例中就有： （y）P(y)P(f(x,y) （y）P(yP(f(x,y), 33,(4) 变量换名 使所有量词都具有不同的约束变量名，这可以依据约束变量的虚元性来进行变换。鉴于约束变量的作用域仅限于量词辖域，但量词前束后又会使同名变量的辖域无法区分，所以为避免差错，换名是必要的。例如，后面实例中就有： （y）（w） Q(x,y)P(y,w) （z）（w） Q(x,z)P(z,w), 34,
15、（5）消去存在量词 分二种情况：存在量词出现在全称量词的辖域内和不在辖域内： （z ）（w） Q(x,z)P(z,w),（w）在（z ）辖域内， （x）P(x),（x）不出现在全称量词辖域内, 35,对于前一情况，意味着w的存在依赖于z，这种依赖关系可以由某个假设的函数w=g(z)来定义，以便把z的每个值映射到w。我们称这种函数为 Sklem函数，只要用Sklem函数g(z)取代约束变量w,就可消去存在量词（w）: （z ） Q(x,z)P(z, g(z), 36,有时一存在量词可以出现在多个全称量词的辖域内，例如：（x）（y）（z）（$w）P(x,y,z,w)。则可设想一个多元Sklem函数g(x,y,z)取代约束变量w并消去存在量词（$w）: （x）（y）（z）P(x,y,z,g(x,y,z)。 对于后一情况，我们可以任意设想一个常量，例如A(称为Sklem常量)，用于取代约束变量x，而取消存在量词（$x）： P(A),
