人工智能 谓词演算

第2讲基于谓词逻辑的机器推理一阶谓词逻辑归结演绎推理归结原理的应用Horn子句与Prolog程序设计1第一节一阶谓词逻辑命题：凡可确定真假的陈述句称为命题可以取值“真”（T）或“假”（F）在一定的条件下，只能取其中一个值例：（1）北京是中国的首都√（2）3+2>10×（3）1+11=100（根据制数）（4）禁止吸烟（祈使句）（5）本命题是假的（悖论）2谓词：是用来刻画个体词的性质或个体词之间的关系的词（带参量的命题叫谓词）n元谓词，P（x1,x2,x3,…,xn）P是谓词符号，代表一个确定的特征（一个参量）或关系（多个参量）x1,x2,x3,…,xn称为参量或项（个体常元或个体变元）论述域（个体域）：个体变元的取值范围例：北京是一个城市——CITY（北京）x是人——HUMAN（x）A是B的兄弟——兄弟（A，B）x大于y——G（x，y）不带个体变元的谓词公式叫命题，命题是谓词公式的特例3逻辑连接词：研究单个谓词是不够的，还必须研究多个谓词之间的关系，这需要引入逻辑连接词¬：否定词¬A读为“非A”，当A为真时，¬A为假，当A为假时，¬A为真∧：合取词A∧B读为“A并且B”，当且仅当A和B都为真时，A∧B为真，否则A∧B为假∨：析取词A∨B读为“A或者B”，当且仅当A和B都为假时，A∨B为假，否则A∨B为真4→：蕴涵词A→B读为“若A则B”，当且仅当A为真，且B为假时，A→B为假，否则A→B为真在A→B中，A称为前件，B称为后件：等值词AB读为“A等值于B”，当且仅当A和B同为真或同为假时，AB为真，否则AB为假5量词：有些陈述句包含表示数量的词，如“所有”、“任一”、“存在”、“至少有一个”等，为了表示这样的陈述句，需引入新的符号，称为量词全称量词（

x）表示“对于所有的x…”例：凡是人都有名字——（

x）（M（x）→N（x））（

x）A（x）

A（a1）∧A（a2）∧…∧A（an），若论域为有限集合，且a1、a2、…、an是论域中的所有个体存在量词（

x）表示“对于某个x…”例：存在不是偶数的整数——（

x）（G（x）∧¬E（x））（

x）A（x）

A（a1）∨A（a2）∨…∨A（an）例：见P56例1—36项：（P64定义1）（1）个体常元和个体变元都是项（2）f(t1,t2,…,tn)是项，f是n元函数，t1,t2,…,tn是项（3）只有有限次使用（1）、（2）得到的符号串才是项原子公式：（P64定义2）设P为n元谓词符号，t1,t2,…,tn是项，则P（t1,t2,…,tn）称为原子谓词公式，简称原子公式7谓词公式：（P56定义3）（1）原子公式是谓词公式（2）若A、B是谓词公式，则A∧B、A∨B、¬

A、A→B、A

B、

xA、

xA也是谓词公式（3）只有有限次应用（1）、（2）生成的公式才是谓词公式谓词公式又称为谓词逻辑中的合式公式，记为Wff(well-formedformula)几个概念：辖域（P57）：紧接于量词之后被量词作用的（说明的）谓词公式称为该量词的辖域指导变元、约束变元和自由变元（P57）改名规则（P57），保证一个变元或者是约束变元，或者是自由变元例：

x（H（x）→G（x,y））∧

xA（x）∧B（x）8合取范式：（P58定义4）A为合取范式，B1∧B2∧…∧Bn,其中Bi形如L1∨

L2∨…∨Lm,Lj为原子公式或其否定例：（P（x）∨Q（y））∧（¬P（x）∨Q（y）∨R（x，y））∧…任一谓词公式均可化为与之等价的合取范式，但一般不唯一析取范式：（P66定义5）A为析取范式，B1∨B2∨…∨Bn,其中Bi形如L1∧

L2∧…∧Lm,Lj为原子公式或其否定例：（P（x）∧Q（y））∨（¬P（x）∧Q（y）∧R（x，y））∨…任一谓词公式均可化为与之等价的析取范式，但一般不唯一9谓词公式的永真（有效）、永假（不可满足）、可满足：（P58定义6、7）与个体域有关谓词公式之间的关系常用逻辑等价式P59表3.1注意与的区别，是等价符号，说明两个谓词公式之间的等价性，是逻辑连接词，是谓词公式的组成部分

常用逻辑蕴涵式P60表3.2注意与的区别，是推导符号，说明由左边的谓词公式可以推导出右边的谓词公式，是逻辑连接词，是谓词公式的组成部分

10自然演演绎推推理：：（1））将自自然语语言命命题转转化为为谓词词公式式（2））利用用上面面的逻逻辑等等价式式和逻逻辑蕴蕴涵式式，可可以进进行推推理，，得出出一些些隐含含在谓谓词公公式中中的结结论例：P61例4-6自然演演绎推推理实实施困困难，，推理理规则则太多多、应应用规规则需需要很很强的的模式式识别别能力力、中中间结结论呈呈指数数增长长引入新新的推推理技技术———归归结演演绎推推理技技术归结———消消解（（Resolution）），由Robinson于1965年提提出，，大大大推动动了自自动定定理证证明的的发展展11练习：：1、设设已知知以下下事实实：ABA→CB∧C→DD→Q求证：：Q为真。。12证明：：因为A，A→CCB，CB∧CB∧C，B∧C→DDD，D→QQ所以Q为真132、设设已知知如下下事实实：（1））凡是是容易易的课课程小小王都都喜欢欢。（2））C班的课课程都都是容容易的的。（3））ds是C班的一一门课课程。。求证：：小王王喜欢欢ds这门课课程。。14证明：：事事实x（（EASY（（x））→LIKE（（Wang，x）））x（（C（（x））→EASY（x）））C（ds））LIKE（（Wang，ds））因为x（（C（（x））→EASY（x）））所以C（ds））→EASY（ds））所以C（ds）），C（（ds）→→EASY（（ds）EASY（（ds）因为x（（EASY（（x））→LIKE（（Wang，x）））所以EASY（（ds）→→LIKE（（Wang，ds））所以EASY（（ds），，EASY（（ds）→→LIKE（Wang，，ds）LIKE（（Wang，ds））15第二节节归归结演演绎推推理建立子子句集集文字、、子句句、空空子句句（（P62定义1）建立谓谓词公公式G的子句句集合合（（P62定义2）例：P62例3.7例：P63例2有有关消消去存存在量量词子句集集中各各子句句的关关系是是合合取∧经过变变换后后的子子句集集S，，与谓词词公式式G并不等等价子句集集的不不可满满足（（P64定义3）G不可满满足当当且仅仅当S不可满满足（（P64定理1），，即G永假是是S永假的的充分分必要要条件件16练习：：P931、（1））{p(x,y),Q(u,v)}（2））{¬p(x,y)∨∨Q(x,y)}（3））{P(x,f(x))∨¬Q(x,f(x))∨R(x,f(x))}（4））{¬P(x,z)∨∨Q(x,y)∨R(x,y)}（5））{P(a,b,z,f(z),v,g(z,v)),Q(a,b,f(t),s,g(t,s))∨∨¬R(a,t,g(t,s))}17命题逻逻辑中中的归归结原原理在定理理证明明系统统中，，已知知一公公式集集F1，F2，…，，Fn，要证明明W（定理））是否否成立立，即即要证证明W是公式式集的的逻辑辑结果果，有有两种种方法法：1、证证明F1∧F2∧…∧∧Fn→W为永真真式（（见上上一节节）2、（（反证证法））证明明F1∧F2∧…∧∧Fn∧¬W永假，，即要要证明明对应应子句句集永永假（（不可可满足足）几个概概念：：（P64定义4、5）互互补文文字、、归结结式（（消解解式））、亲亲本子子句、、消解解基例：例例3.9归结式式是其其亲本本子句句的逻逻辑结结果P64定理2单向推推导关关系18归结原原理：：C1∧∧C2（C1-{L1}））∨（（C2-{L2}）互补文文字进进行归归结得得空子子句（（L∧∧¬L=㄰），另L∧∧¬L=F（假），，故空空子句句即永永假子子句关于消消解前前后子子句集集的可可满足足性————P65推论（（证明明略））故：要要证明明一子子句集集永假假，可可以通通过对对子句句集应应用消消解原原理得得到空空子句句来证证明运用归归结原原理证证明定定理的的例子子：P65例11、12*归归结结过程程可以以用一一棵归结演演绎树树表示19替换与与合一一为了对对谓词词逻辑辑的子子句集集运用用消解解原理理，即即在子子句集集合中中寻找找含互互补文文字的的子句句对，，必须须对子子句进进行替替换合合一操操作替换：：P66定义6{t1/x1，t2/x2，…，，tn/xn}对表达达式的的替换换过程程P66定义7表达式式———项项、原原子公公式、、文字字、子子句两个替替换的的乘积积P66-67定义8一部分分仍是是θ的替换对，，只是θ的项被λ作了替换；；另一部分分是λ中与θ不同的那些些变量对例：例3.13替换的乘积积满足结合合律20合一：P67定义9θ是S的一个合一一其中S是一个原子子谓词公式式集，θ是一个替换换满足F1θ=F2θ=……=Fnθ一个公式集集的合一一一般不唯一一最一般的合合一：P67定义10σ是S的一个合一一对于S的任何一个个合一θ，存在替换λ，使θ=σ•λ称σ为S的最一般（（最普通、、最简单））合一MGU例：例3.14MGU的替换限制制最少，所所产生的例例更一般化化，这有利利于归结过过程的灵活活使用一个公式集集的最一般般合一也可可不唯一，，如{P（x），，P（y））}，{y/x}、、{x/y}都是它的最最一般合一一21差异集：P67定义11针对具有相相同谓词名名的原子公公式集例：例3.15合一算法：：求非空有有限具有相相同谓词名名的原子公公式集的最最一般合一一P67-68合一算法是是解决两个个表达式匹匹配的问题题，两个表表达式都可可以含有变变量，通过过算法求得得MGU并进行替换换后就可以以得到匹配配的例例：例16、17合一定理：：P68-69定理3可合一公式式集一定存存在最一般般合一，用用上述合一一算法求得得22谓词逻辑中中的归结原原理归结过程：：若S中的两子句句间有相同同互补文字字的谓词，，但它们的的项不同，，则必须找找出对应的的不一致项项进行变量替替换合一操操作，使它它们的对应应项一致求归结式看看能否导出出空子句几个概念：：（P69定义12））谓词逻辑辑中的二元元归结式（（二元消解解式）、亲亲本子句、、消解文字字例：例18、19子句用文字字的集合表表示，各文文字之间的的关系是析析取∨首先对子句句内部的可可合一文字字进行合一一23因子、单因因子（（P69定义13））例：例14子句的归结结（消解））式（（P69定义14））定理：谓词词逻辑中的的消解式是是它的亲本本子句的逻逻辑结果谓词逻辑中中的归结原原理：C1∧C2（C1σ-{L1σ}）∪（C2σ-{L2σ}）关于消解前前后子句集集的可满足足性———P70（同命题逻逻辑）故：要证明明F1∧F2∧…∧Fn→W为永真式，，可证明F1∧F2∧…∧Fn∧¬W永假，这又又可以通过过对对应子子句集应用用消解原理理得到空子子句来证明明（同命题题逻辑）24例：例15、16定理：归结结原理的完完备性（（P71）练习：P933、（（1）-（（5）25第三节归归结原原理的应用用例3.23：P71例3.24：P72练习：P945、6、26归结策略计算机实现现归结原理理的一般算算法：1.将子句句集S置入CLAUSES表；2.若空子子句NIL在CLAUSES中，则归结结成功，结结束。3.若CLAUSES中存在可归归结子句对对，则归结结之，并将将归结式放放入CLAUSES中；4.归结失失败，退出出。归结策略的的完备性策略：删除除策略、支支持集策略略、线性归归结策略、、输入归结结策略、单单元归结策策略、祖先先过滤形策策略。27归结举例Sam、Clyde和Oscar是大象。关关于它们，，我们知道道以下事实实：1）Sam是粉红色的的；2）Clyde是灰色的且且喜欢Oscar；3）Oscar是粉红色或或者是灰色色（但不是是两种颜色色）且喜欢欢Sam。用归结法证证明一个灰灰色大象喜喜欢一个粉粉红色大象象。即证明：xy[Gray(x)∧Pink(y)∧∧Likes(x,y)]¬∧∨谓词：Gray(x),Pink(x),Like（（x,y））事实：1）Pinky(Sam)2）Gray(Clyde)∧∧Like(Clyde,Oscar)3）(Gray(Oscar)∨∨Pink(Oscar))∧Likes(Oscar,Sam)28子句集：1）Pink(Sam)2）Gray(Clyde)3）Like(Clyde,Oscar)4）Gray(Oscar)∨∨Pink(Oscar)5）Likes(Oscar,Sam)6）¬Gray(x)∨¬Pink(y)∨¬Likes(x,y)归结：7）¬Gray(Oscar)∨¬Pink(Sam)5，6得8）¬Gray(Clyde)∨¬Pink(Oscar)3，，6得9）Pink(Oscar)∨¬Pink(Sam)4，7得10）¬Pink(Oscar)8，2得11））¬Pink(Sam)9，，10得12）NIL1，，10得¬∧∨29第四节Horn子句与Prolog程序设计计子句的蕴蕴含表示示P90（（3-1）