第5章基于谓词逻辑的机器推理.ppt
《第5章基于谓词逻辑的机器推理.ppt》由会员分享,可在线阅读,更多相关《第5章基于谓词逻辑的机器推理.ppt(143页珍藏版)》请在三一文库上搜索。
1、第 5 章 基于谓词逻辑的机器推理,5.1 一阶谓词逻辑 5.2 归结演绎推理 5.3 应用归结原理求取问题答案 5.4 归结策略 5.5 归结反演程序举例 5.6 Horn子句归结与逻辑程序 5.7 非归结演绎推理,5.1 一阶谓词逻辑,5.1.1 谓词、函数、量词 设a1, a2, , an表示个体对象, A表示它们的属性、状态或关系, 则表达式,A(a1, a2, , an),在谓词逻辑中就表示一个(原子)命题。 例如, (1) 素数(2), 就表示命题“2是个素数”。 (2) 好朋友(张三, 李四), 就表示命题“张三和李四是好朋友”。,P(x1,x2,xn),一般地, 表达式,在谓词
2、逻辑中称为n元谓词。其中P是谓词符号,也称谓词,代表一个确定的特征或关系(名)。x1,x2,xn称为谓词的参量或者项,一般表示个体。 个体变元的变化范围称为个体域(或论述域),包揽一切事物的集合称为全总个体域。,为了表达个体之间的对应关系,我们引入通常数学中函数的概念和记法。例如我们用father(x)表示x的父亲,用sum(x,y)表示数x和y之和,一般地,我们用如下形式:,f(x1,x2,xn),表示个体变元x1,x2,xn所对应的个体y,并称之为n元个体函数,简称函数(或函词、函词命名式)。其中f是函数符号,有了函数的概念和记法,谓词的表达能力就更强了。例如,我们用Doctor(fath
3、er(Li)表示“小李的父亲是医生”,用E(sq(x),y)表示“x的平方等于y”。,以后我们约定用大写英文字母作为谓词符号,用小写字母f,g, h等表示函数符号,用小写字母x, y, z等作为个体变元符号, 用小写字母a, b, c等作为个体常元符号。 我们把“所有”、“一切”、“任一”、“全体”、“凡是”等词统称为全称量词, 记为 x; 把“存在”、“有些”、“至少有一个”、 “有的”等词统称为存在量词, 记为 x。,其中M(x)表示“x是人”, N(x)表示“x有名字”, 该式可读作“对于任意的x, 如果x是人, 则x有名字”。这里的个体域取为全总个体域。如果把个体域取为人类集合, 则该
4、命题就可以表示为,同理, 我们可以把命题“存在不是偶数的整数”表示为,其中G(x)表示“x是整数”, E(x)表示“x是偶数”。此式可读作“存在x, x是整数并且x不是偶数”。,不同的个体变元, 可能有不同的个体域。为了方便和统一起见, 我们用谓词表示命题时,一般总取全总个体域, 然后再采取使用限定谓词的办法来指出每个个体变元的个体域。 具体来讲,有下面两条: (1) 对全称量词,把限定谓词作为蕴含式之前件加入, 即 x(P(x)。 (2) 对存在量词, 把限定量词作为一个合取项加入, 即 x(P(x)。 这里的P(x)就是限定谓词。 我们再举几个例子。,例 5.1 不存在最大的整数, 我们可
5、以把它翻译为,或,例 5.2 对于所有的自然数, 均有x+yx,例 5.3 某些人对某些食物过敏,5.1.2 谓词公式 定义1 (1) 个体常元和个体变元都是项。 (2) 设f是n元函数符号,若t1,t2,tn是项,则f(t1,t2,tn)是项。 (3) 只有有限次使用(1), (2)得到的符号串才是项。,定义2 设P为n元谓词符号,t1,t2,tn为项,则P(t1,t2,tn)称为原子谓词公式,简称原子公式或者原子。 从原子谓词公式出发,通过命题联结词和量词,可以组成复合谓词公式。下面我们给出谓词公式的严格定义,即谓词公式的生成规则。,紧接于量词之后被量词作用(即说明)的谓词公式称为该量词的
6、辖域。例如: (1) xP(x)。 (2) x(H(x)G(x, y)。 (3) xA(x)B(x)。 其中(1)中的P(x)为x的辖域, (2)中的H(x)G(x, y)为x的辖域, (3)中的A(x)为x的辖域, 但B(x)并非x的辖域。,量词后的变元如 x, y中的x,y称为量词的指导变元(或作用变元), 而在一个量词的辖域中与该量词的指导变元相同的变元称为约束变元, 其他变元(如果有的话)称为自由变元, 例如(2)中的x为约束变元, 而y为自由变元, (3)中A(x)中的x为约束变元, 但B(x)中的x为自由变元。例如(3),一个变元在一个公式中既可约束出现, 又可自由出现, 但为了避
7、免混淆, 通常通过改名规则, 使得一个公式中一个变元仅以一种形式出现。,约束变元的改名规则如下: (1) 对需改名的变元, 应同时更改该变元在量词及其辖域中的所有出现。 (2) 新变元符号必须是量词辖域内原先没有的, 最好是公式中也未出现过的。例如公式 xP(x)Q(x)可改为 yP(y)Q(x), 但两者的意义相同。 在谓词前加上量词, 称作谓词中相应的个体变元被量化, 例如xA(x)中的x被量化, yB(y)中y被量化。如果一个谓词中的所有个体变元都被量化, 则这个谓词就变为一个命题。例如, 设P(x)表示“x是素数”,则 xP(x), xP(x)就都是命题。这样我们就有两种从谓词(即命题
8、函数)得到命题的方法:一种是给谓词中的个体变元代入个体常元, 另一种就是把谓词中的个体变元全部量化。,把上面关于量化的概念也可以推广到谓词公式。于是,我们便可以说,如果一个公式中的所有个体变元都被量化,或者所有变元都是约束变元(或无自由变元),则这个公式就是一个命题。特别地,我们称 xA(x)为全称命题, xA(x)为特称命题。对于这两种命题,当个体域为有限集时(设有n个元素),有下面的等价式: xA(x)A(a1)A(a2)A(an) xA(x)A(a1)A(a2)A(an) 这两个式子也可以推广到个体域为可数无限集。,定义4 设A为如下形式的谓词公式: B1B2Bn 其中Bi(i=1,2,
9、n)形如L1L2Lm,Lj(j=1,2,m)为原子公式或其否定,则A称为合取范式。 例如: (P(x)Q(y)(乛P(x)Q(y)R(x,y)(乛Q(y)乛R(x,y) 就是一个合取范式。,定义5 设A为如下形式的命题公式: B1B2Bn 其中Bi(i=1,2,n)形如L1L2Lm,Lj(j=1,2,m)为原子公式或其否定,则A称为析取范式。 例如: (P(x)乛Q(y)R(x,y)(乛P(x) Q(y)(乛P(x)R(x,y) 就是一个析取范式。,定义6 设P为谓词公式,D为其个体域,对于D中的任一解释I: (1)若P恒为真,则称P在D上永真(或有效)或是D上的永真式。 (2)若P恒为假,则
10、称P在D上永假(或不可满足)或是D上的永假式。 (3)若至少有一个解释,可使P为真,则称P在D上可满足或是D上的可满足式。,定义7 设P为谓词公式,对于任何个体域: (1)若P都永真,则称P为永真式。 (2)若P都永假,则称P为永假式。 (3)若P都可满足,则称P为可满足式。,5.1.3 谓词逻辑中的形式演绎推理 由上节所述,我们看到,利用谓词公式可以将自然语言中的陈述语句表示为一种形式化的符号表达式。那么,利用谓词公式,我们同样可以将形式逻辑中抽象出来的推理规则形式化为一些符号变换公式。表3.1和表3.2就是形式逻辑中常用的一些逻辑等价式和逻辑蕴含式,即推理规则的符号表示形式。,表5.1 常
11、用逻辑等价式,表5.2 常用逻辑蕴含式,例5.4 设有前提: (1)凡是大学生都学过计算机; (2)小王是大学生。 试问:小王学过计算机吗? 解 令S(x):x是大学生;M(x):x学过计算机; a:小王。则上面的两个命题可用谓词公式表示为 (1) x(S(x)M(x) (2) S(a),下面我们进行形式推理: (2) x(S(x)M(x) 前提 (2)S(a)M(a) (1),US (3)S(a) 前提 (4)M(a) (2),(3),I3 得结果:M(a),即“小王学过计算机”。,例5.5 证明乛P(a,b)是 x y(P(x,y)W(x,y)和乛W(a,b)的逻辑结果。证 (1) x y
12、(P(x,y)W(x,y) 前提 (2) y(P(a,y)W(a,y) (1),US (3) P(a,b)W(a,b) (2),US (4)乛W(a,b) 前提 (5)乛P(a,b) (3),(4),I4,例5.6 证 x(P(x)Q(x) x(R(x)乛Q(x) x(R(x)乛P(x)。证 (1) x(P(x)Q(x) 前提 (2)P(y)Q(y) (1),US (3)乛Q(y)乛P(y) (2),E24 (4) x(R(x)Q(x) 前提 (5)R(y)乛Q(y) (3),US (6)R(y)乛P(y) (3),(5),I6 (7) x(R(x)乛P(x) (6),UG,5.2.1 子句集
13、 定义1 原子谓词公式及其否定称为文字,若干个文字的一个析取式称为一个子句,由r个文字组成的子句叫r文字子句,1文字子句叫单元子句,不含任何文字的子句称为空子句,记为或NIL。 例如下面的析取式都是子句 PQ乛R P(x,y)乛Q(x),5.2 归结演绎推理,定义2 对一个谓词公式G,通过以下步骤所得的子句集合S,称为G的子句集。 (1)消去蕴含词和等值词。可使用逻辑等价式: ABAB A B(乛AB)(乛BA),(2)缩小否定词的作用范围,直到其仅作用于原子公式。可使用逻辑等价式: 乛(乛A) A 乛(AB) 乛A乛B 乛(AB) 乛A乛B 乛 xP(x) x乛P(x) 乛 xP(x) x乛
14、P(x),(3)适当改名,使量词间不含同名指导变元和约束变元。 (4)消去存在量词。 消去存在量词时,同时还要进行变元替换。变元替换分两种情况: 若该存在量词在某些全称量词的辖域内,则用这些全称量词指导变元的一个函数代替该存在量词辖域中的相应约束变元,这样的函数称为Skolem函数; 若该存在量词不在任何全称量词的辖域内,则用一个常量符号代替该存在量词辖域中的相应约束变元,这样的常量符号称为Skolem常量。,(5)消去所有全称量词。 (6)化公式为合取范式。 可使用逻辑等价式: A(BC) (AB)(AC) (AB)C (AC)(BC) (7)适当改名,使子句间无同名变元。 (8)消去合取词
15、,以子句为元素组成一个集合S。,例5.7 求下面谓词公式的子句集 x yP(x,y) yQ(x,y)R(x,y) 解 由步(1)得 x乛yP(x,y)乛 yQ(x,y)R(x,y) 由步(2)得 x yP(x,y) yQ(x,y)乛R(x,y) 由步(3)得 x yP(x,y) zQ(x,z)乛R(x,z) 由步(4)得 x乛P(x,f(x)Q(x,g(x)乛R(x,g(x),由步(5)得乛P(x,f(x)Q(x,g(x)乛R(x,g(x) 由步(6)得乛P(x,f(x)Q(x,g(x)乛P(x,f(x)乛R(x,g(x) 由步(7)得乛P(x,f(x)Q(x,g(x)乛P(y,f(y)乛R(
16、y,g(y) 由步(8)得乛P(x,f(x)Q(x,g(x),乛P(y,f(y)乛R(y,g(y) 或 乛P(x,f(x)Q(x,g(x) 乛P(y,f(y)R(y,g(y) 为原谓词公式的子句集。,需说明的是,在上述求子句集的过程中,当消去存在量词后,把所有全称量词都依次移到整个式子的最左边(或者先把所有量词都依次移到整个式子的最左边,再消去存在量词),再将右部的式子化为合取范式,这时所得的式子称为原公式的称为Skolem标准型。例如,上例中谓词公式的Skolem标准型就是 x乛P(x,f(x)Q(x,g(x)乛P(y,f(y)乛R(y,g(y),例5.8 设G=xyzuvw(P(x,y,z
17、)Q(u,v,w),那么,用a代替x,用f(y,z)代替u,用g(y,z,v)代替w,则得G的Skolem标准型 y z v(P(a,y,z)乛Q(f(y,z),v,g(y,z,v) 进而得G的子句集为 P(a,x,y),乛Q(f(u,v),w,g(u,v,w) 由此例还可看出,一个公式的子句集也可以通过先求前束范式,再求Skolem标准型而得到。,它的Skolem标准型是,我们给出如下的一个解释I:,需说明的是,引入Skolem函数,是由于存在量词在全称量词的辖域之内,其约束变元的取值则完全依赖于全称量词的取值。Skolem函数就反映了这种依赖关系。但注意,Skolem标准型与原公式一般并不
18、等价,例如有公式:,则在I下, G=T, 而G=F。,定理1 把证明一个公式G的不可满足性,转化为证明其子句集S的不可满足性。 定义3 子句集S是不可满足的,当且仅当其全部子句的合取式是不可满足的。,5.2.2 命题逻辑中的归结原理 归结演绎推理是基于一种称为归结原理(亦称消解原理principleofresolution)的推理规则的推理方法。归结原理是由鲁滨逊(J.A.Robinson)于1965年首先提出。它是谓词逻辑中一个相当有效的机械化推理方法。归结原理的出现,被认为是自动推理,特别是定理机器证明领域的重大突破。,定义4 设L为一个文字,则称L与L为互补文字。 定义5 设C1,C2是
19、命题逻辑中的两个子句,C1中有文字L1,C2中有文字L2,且L1与L2互补,从C1,C2中分别删除L1,L2,再将剩余部分析取起来,记构成的新子句为C12,则称C12为C1,C2的归结式(或消解式),C1,C2称为其归结式的亲本子句, L1,L2称为消解基。 例3.9 设C1=乛PQR,C2=乛QS,于是C1,C2的归结式为 乛PRS 定理2 归结式是其亲本子句的逻辑结果。,证明 设C1=LC1,C2=乛LC2,C1,C2都是文字的 析取式,则C1,C2的归结式为C1C2,因为 C1=C1L=乛(C1L),C2=LC2=(LC2) 所以 C1C2=(乛C1L)(LC2)乛(C1C2)=C1C2
20、 证毕。 由定理2即得推理规则: C1C2 (C1-L1)(C2-L2),例3.10 用归结原理验证分离规则:A(AB) B和拒取式(AB)乛B 乛A。 解 A(AB) A(乛AB)B (AB)乛B (乛AB)(乛B) 乛A 类似地可以验证其他推理规则也都可以经消解原理推出。这就是说,用消解原理就可以代替其他所有的推理规则。再加上这个方法的推理步骤比较机械,这就为机器推理提供了方便。,推论 设C1,C2是子句集S的两个子句,C12是它们的归结式,则 (1)若用C12代替C1,C2,得到新子句集S1,则由S1的不可满足可推出原子句集S的不可满足。即 S1不可满足 S不可满足 (2)若把C12加入
21、到S中,得到新子句集S2,则S2与原S的同不可满足。即 S2不可满足 S不可满足,例5.11 证明子句集PQ,P,Q是不可满足的。 证 (1)P乛Q (2)乛P (3)Q (4)乛Q 由(1),(2) (5) 由(3),(4),例5.12 用归结原理证明R是P,(PQ)R,(SU)Q,U的逻辑结果。 证 我们先把诸前提条件化为子句形式,再把结论的非也化为子句,由所有子句得到子句集S=P,乛P乛QR,乛SQ,乛UQ,U,乛R,然后对该子句集施行归结,归结过程用下面的归结演绎树表示(见图31)。由于最后推出了空子句,所以子句集S不可满足,即命题公式 P(乛P乛QR)(乛SQ)(乛UQ)U乛R 不可
22、满足,从而R是题设前提的逻辑结果。,图51 例5.12归结演绎树,5.2.3 替换与合一 在一阶谓词逻辑中应用消解原理,不像命题逻辑中那样简单,因为谓词逻辑中的子句含有个体变元,这就使寻找含互否文字的子句对的操作变得复杂。例如: C1=P(x)Q(x) C2=P(a)R(y) 直接比较,似乎两者中不含互否文字,但如果我们用a替换C1中的x,则得到 C1=P(a)Q(a) C2=P(a)R(y),于是根据命题逻辑中的消解原理,得C1和C2的消解式 C3=Q(a)R(y) 所以,要在谓词逻辑中应用消解原理,则一般需要对个体变元作适当的替换。,定义6 一个替换(Substitution)是形如t1/
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 谓词 逻辑 机器 推理
链接地址:https://www.31doc.com/p-2533049.html