RGZN5谓词逻辑.docx
- 文档编号:8945722
- 上传时间:2023-05-16
- 格式:DOCX
- 页数:46
- 大小:186.26KB
RGZN5谓词逻辑.docx
《RGZN5谓词逻辑.docx》由会员分享,可在线阅读,更多相关《RGZN5谓词逻辑.docx(46页珍藏版)》请在冰点文库上搜索。
RGZN5谓词逻辑
第五章基于谓词逻辑的机器推理
在许多应用中,被编码进入产生式系统数据库的信息来源于说明语句,这些语句难以或者不能自然地用像数组或集合那样的简单结构来表示。
例如,机器人求解问题要求具有表达、检索和变换语句集合的能力。
而逻辑语句,或者更具体地说,一阶谓词演算能用来表示种类众多的语句,且能给出一种从旧知识直接求得新知识的有效方法——数学演绎。
即如能证明一个新语句是从那些已知正确的语句导出的,那么我们就可断定这个新语句也是正确的。
证明的概念推广(把演绎包括在内)用来作为一种求取问题的方法。
第一节谓词演算
5.1.1命题逻辑及其局限性
命题具有真假意义的一句话
人们研究用命题逻辑作为一种表达知识的方法,因为它处理简单,并存在一个判定方法。
如:
可把客观世界的各种事实表示为逻辑命题,用命题逻辑把各种命题写成合适公式(WFF)。
例如:
雨天表示为:
RAINING晴天表示为:
SUNNY雾天表示为:
FOGGY
若为雨天,则非晴天。
表示为:
RAINING→~SUNNY
但是,我们很快就会遇到命题逻辑的局限性。
假定我们要表示由下列句子叙述的明显事实:
李明是个工人可写为LIWORKER
如果我们也要表示:
王华也是个工人就必须写出WANGWORKER
这是一些完全独立的格式,我们无法从中得出有关李(LI)和王(WANG)相似性的结论。
如果把这些事实表示为如下形式:
WORKER(LI)
WORKER(WANG)
那么这就要好得多,因为这种表达结构反映出知识本身的结构。
如果我们试图用命题逻辑来表示下列句子:
所有的人都会死。
那么我们将面临更大的困难,因为如果我们不对问题进行量化,那么我们就必须一个一个地写出某某某会……
命题逻辑局限性:
●不区分知识的结构与成分;
●不可对问题进行量化
而谓词逻辑允许我们表达那些无法用命题逻辑相应地加以表达的事情,可进行演绎,可使用变量及量词(
、彐)。
(
x)(H(x)D(x))
{对任意x,只要x是人,则x必然会死。
}
5.1.2谓词逻辑的句法和语义
基本组成部分:
谓词符号、变量符号、函数符号和常量符号,并用圆括弧、方括弧、花括弧和逗号隔开,以表示论域内的关系。
个体(客体)名称集合(或称论域)D
常量符号:
代表D中某一个确定个体
变量符号:
代表D中任一个个体(客体)
函数符号:
f(x1,...,xn)它为DnD的一个映射
(最终值∈D)
{表达个体之间的对应关系,例如:
我们用father(x)表示x的父亲。
约定:
小写字母f,g,h等表示函数符号,小写字母x,y,z,u,v,w等表示个体变量(变元)符号,小写字母a,b,c等表示个体常量(常元)符号}
谓词符号:
由大写字母(单词)表示,定义域为Dn,值域为{T,F}的函数的函数名
项:
常量符号、变量符号、函数符号,(最终值∈D)
原子谓词公式:
P(t1,...,tm)
谓词符号项
如:
P(x,y,z)命题?
变量
定义P关系:
令P(x,y,z)表示x在y与z之间命题?
代入确定个体(实例化):
如令x,y,z代表北京、保定、石家庄,
则P(x,y,z)为命题。
5.1.3连词和量词
合适公式(WFF):
通过使用连词~(非)、∧(与)、∨(或)、=>(→蕴涵,或隐含)以及
、彐等将原子谓词公式按一定的语法格式连接而成的式子。
连词∧用来表示复合句子。
例如,句子“我喜爱音乐和绘画”可写成:
LIKE(I,MUSIC)∧LIKE(I,PAINTING)
又如“李住在一幢黄色的房子里”,即可用
LIVES(LI,HOUSE-1)∧COLOR(HOUSE-1,YELLOW)
其中谓词LIVES表示人与物体(房子)间的关系,而谓词COLOR则表示物体与其颜色之间的关系。
合取:
用连词∧把几个(原子)公式连接起来而构成的公式
此合取式的每个组成部分叫做合取项
连词∨用来表示可兼有的“或”。
例如,句子“李明打蓝球或踢足球”可表示为:
PLAYS(LIMING,BASKETBALL)∨PLAYS(LIMING,FOOTBAL)
析取:
用连词∨把几个公式连接起来所构成的公式
此析取式的每一组成部分叫做析取项
合取和析取的真值由其组成部分的真值决定。
连词=>用来表示“如果-那么”的词句。
如句子“如果该书是何平的,那么它是蓝色(封面)的”可表示为:
OWNS(HEPING,BOOK-1)=>COLOR(BOOK-1,BLUE)
又如,句子“如果刘华跑得最快,那么他取得冠军”可表示为:
RUNS(LIUHUA,FASTEST)=>WINS(LIUHUA,CHAMPION)
用连词=>连接两个公式所构成的公式叫做蕴涵。
蕴涵的左式叫做前项,右式叫做后项。
如果前项和后项都是合适公式,那么蕴涵也是合适公式。
如果后项取值T(不管其前项的真值如何),或者前项取值F(不管后项的真值如何),则蕴涵取值T;否则,蕴涵取值F。
符号~(非)用来否定一个公式的真值,也就是说,把一个合适公式的取值从T变为F,或从F变为T。
例如,子句“机器人不在2号房间内”可表示为:
~INROOM(ROBOT,r2)
前面具有符号~的公式叫做否定。
如果我们把句子限制为我们至今已介绍过的造句法所能表示的那些句子,而且也不使用变量项,那么我们可以把这个谓词演算的子集叫做命题演算。
命题演算对于许多简化了的定义域来说,是一种有效的表示,但它缺乏用有效的方法来表达多个命题(如“所有的机器人都是灰色的”)的能力。
要扩大命题演算的能力,我们需要使公式中的命题带有变量。
、彐
有时,一个原子公式如P(x),对于所有可能的变量x都具有值T。
这个特性可由在P(x)前面加上全称量词(
x)来表示。
如果至少有一个x值可使P(x)具有值T,那么这一特性可由在P(x)前面加上存在量词(彐x)来表示。
例如,句子“所有的机器人都是灰色的”可表示为:
(
x)[ROBOT(x)→COLOR(x,GRAY)]
而句子“1号房间内有个物体”可表示为:
(彐x)INROOM(x,r1)
x:
经过量化了的
约束变量:
如果一个合适公式中某个变量是经过量化的,我们就把这个变量叫约束变量,否则就叫它为自由变量。
句子:
在合适公式中,若所有变量都是受约束的。
这样的合适公式叫做句子。
值得指出的是,本书中所用到的谓词演算为一阶谓词演算。
不允许对谓词符号或函数符号进行量化。
例如,在一阶谓词演算中,(
P)P(A)就不是合适公式。
又例:
每个有理数都是实数
有些实数是有理数
并非每个实数都是有理数
解:
令原子谓词公式
P(x)表示x是有理数
Q(x)表示x是实数
(
x)[P(x)=>Q(x)]
(彐x)[Q(x)∧P(x)]
~((
x)[Q(x)=>P(x)])
等价于(彐x)[Q(x)∧~P(x)]
例:
每一个人的外祖父都是他母亲的父亲。
令P(x)表示x是人
O(x,y)表示x是y的外祖父
F(x,y)表示x是y的父亲
M(x,y)表示x是y的母亲
将原句转化为:
每一个人y的外祖父x都是该y的母亲z的父亲。
(
x)(
y)(P(x)∧P(y)∧O(x,y))=>(彐z)(P(z)∧F(x,z)∧M(z,y))
第二节谓词公式
5.2.1谓词公式的定义
原子谓词公式P(x1,x2,…,xn)
合适公式:
1.原子谓词公式是合适公式。
2.若A为合适公式,则~A也是一个合适公式。
5.若A和B都是合适公式,则(A∧B),(A∨B),(A→B)和
(AB)也都是合适公式。
4.若A是合适公式,x为任意变元,则(
x)A和(彐x)A都是合适公式。
5.只有按上述规则1至4求得的那些公式,才是合适公式。
5.2.2合适公式的性质
如果P和Q是两个合适公式,则由这两个合适公式所组成的复合表达式可由下列真值表给出。
PQP∨QP∧QP=>Q~P
TTTTTF
FTTFTT
TFTFFF
FFFFTT
如果两个合适公式,无论如何解释(取任何值),其真值表都是相同的,那么我们就称此两合适公式是等价的。
有如下等价关系:
1.否定之否定~(~P)等价于P
2.P∨Q等价于~P→Q
5.狄·摩根定律
~(P∨Q)等价于~P∧~Q
~(P∧Q)等价于~P∨~Q
5.分配律
P∧(Q∨R)等价于(P∧Q)∨(P∧R)
P∨(Q∧R)等价于(P∨Q)∧(P∨R)
5.交换律
P∧Q等价于Q∧P
P∨Q等价于Q∨P
6.结合律
(P∧Q)∧R等价于P∧(Q∧R)
(P∨Q)∨R等价于P∨(Q∨R)
7.逆否律
P→Q等价于~Q→~P
此外,我们还可建立下列等价关系:
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)
10.(
x)P(x)等价于(
y)P(y)
(彐x)P(x)等价于(彐y)P(y)
上述最后两个等价关系说明,在一个量化的表达式中的约束变量是一个虚元,它可以用任何一个不在表达式中出现过的其他变量符号来代替。
下面用谓词演算来表示英文句子:
Allblocksontopofblocksthathavebeenmovedorthatareattachedtoblockthathavebeenmovedalsohavebeenmoved.
可表示为:
(
x)(
y){{BLOCK(x)∧BLOCK(y)∧[ONTOP(x,y)∨
ATTACHED(x,y)]∧MOVED(y)}→MOVED(x)}
5.2.3推理规则、定理与证明
假元推理合适公式
W1
W1→W2
全称消去推理(全称化推理)
它是由合适公式(
x)W(x)产生合适公式W(A),其中A为任意常量符号。
同时应用假元推理和全称化推理,可由合适公式
(
x)[W1(x)→W2(x)]
结论W2(A)
W1(A)
推理规则用来由已知的合适公式产生导出的合适公式。
在谓词逻辑中,这种导出的合适公式叫做定理,而所使用的推理规则的序列则构成该定理的一个证明。
在人工智能中,可以把某些问题求解任务当做某个定理求证的任务。
在该证明中所应用的推理序列给出了该问题的一个解答。
5.2.4永真性和可满足性
永真:
一个公式如果它们对所有可能的解释均取值T,则这个公式称作为永真的,而永真的基公式一般叫做重言式。
如:
公式P(A)→[P(A)∨P(B)]
公式G的一个解释I:
由非空域D以及对G中的常量符号、函数符号、谓词符号的一组指定所构成。
公式G称为可满足的:
如果存在解释I,使G在I下取T值。
公式G称为永真的:
如果G的所有解释I,都使G取T值。
如果每个满足公式集S的解释也满足公式X,那么公式X逻辑上遵循公式集S。
{凡使S中各公式为真者,必使公式X为真}{X是S的逻辑结论}
例如:
结论X前提S
公式逻辑上遵循的公式集
P(A)(
x)P(x)
(
x)Q(x){(
x)[~P(x)∨Q(x)],
(
x)P(x)}
5.2.4置换与合一
上一节讲过,联合使用假元推理和全称化推理,可以根据合适公式
(
x)[W1(x)→W2(x)]
W1(A)
产生W2(A)
这就需要寻找A对x的置换,使W1(A)与W1(x)一致。
寻找项对变量的置换,以使表达式一致,叫做合一。
合一是人工智能中很重要的过程。
置换:
在一个表达式(谓词公式)中用项(常量、变量、函数)去替换变量
目的:
使多个表达式一致起来(以便进行归结推理)
例:
表达式P[x,f(y),B]的四个置换为:
s1={z/x,w/y}
s2={A/y}
s3={g(z)/x,A/y}
s4={c/x,A/y}
一般形式为:
{t1/V1,t2/V2,……,tn/Vn}
其中ti为项,Vi为互不相同变量,且Vi不出现于ti中,表示Vi同时替换为ti
设表达式E经置换S作用后,结果表达式为ES。
则:
P[x,f(y),B]s1=P[z,f(w),B]
P[x,f(y),B]s2=P[x,f(A),B]
P[x,f(y),B]s3=P[g(z),f(A),B]
P[x,f(y),B]s4=P[c,f(A),B]
置换后的结果表达式ES为原表达式E的逻辑结论{即ES在逻辑上遵循E}
ES也称为E在代换S下的一个例式
{越置换,越具有特殊性}P(x)A/xP(A)
一般特殊
置换满足结合律,但一般不满足交换律。
即用s1s2表示两个置换s1与s2的合成,L表示一表达式,则有:
(Ls1)s2=L(s1s2)即用s1、s2相继作用于L是同
s1s2作用于L一致的
以及(s1s2)s3=s1(s2s3)
但s1s2≠s2s1
定义:
设有表达式集{Ei}={E1,E2,……,En},若存在置换S,使E1S=E2S=……=EnS,则称S为集{Ei}的一个合一者(简称合一),也说表达式集是可合一的。
例:
{P(a,y),P(x,f(b))}是可合一的
(因为存在置换S={a/x,f(b)/y}是这个集的一个合一者)
又例:
{P[x,f(y),B],P[x,f(B),B]}是可合一的,合一者为:
S={A/x,B/y}(实际上A/x多余的)
另一合一者g={B/y}
定义:
若g为{Ei}的一个合一者,对{Ei}的任一合一者S,都存在一个置换S′,使得{Ei}S={Ei}gS′,则称g为{Ei}的最通用(最简单的)合一者,记为mgu(MostGeneralUnifier)。
如对上例,mgu为:
g={B/y}
有许多算法可用来合一可合一表达式的有限集,并在该集不可合一时宣告失败退出。
求mgu的算法:
非递归算法
定义:
设有一非空有限公式集F={F1,F2,……,Fn},从F中各公式的第一个符号同时向右比较,直到发现第一个彼此不尽相同的符号止;从F的各个公式中取出那些从第一个不一致符号开始的最大子表达式,将这些子表达式作为元素组成一个集合D,称为F的分歧集。
如F={P[x,f(y,z)],P[x,f(g(a),h(b))]}
F的分歧集D={y,g(a)}
合一算法:
1、置k=0;Fk=F;бk=ε;
(其中Fk为消除了k个分歧集后的公式集;
F为原始公式集;
бk为消除了前k个分歧集所用的置换;
ε空置换)
2、若Fk只含一个表达式,则算法停止,бk为所求最一般合一;
3、找出Fk分歧集Dk;
4、若Dk中存在元素ak和tk,其中ak为变量,tk为项,且ak不在tk中出现,则置бk+1=бk·{tk/ak};
Fk+1=Fk·{tk/ak};
k=k+1;转步骤2;
5、(第四步不满足,算法停止,F的最一般合一者不存在)
例:
求公式集{P[a,x,f(g(y))],P[z,h(z,u),f(u)]}的最一般合一者mgu。
解:
k=0;
F0=F;б0=ε;
F0不是单一元素集,有D0={a,z}
б1=б0·{a/z}=ε·{a/z}={a/z};
F1=F0·{a/z}={P[a,x,f(g(y))],P[a,h(a,u),f(u)]};
k=1;
F1不是单一元素集,有D1={x,h(a,u)}
б2=б1·{h(a,u)/x}={a/z}·{h(a,u)/x}={a/z,h(a,u)/x};
F2=F1·{h(a,u)/x}={P[a,h(a,u),f(g(y))],P[a,h(a,u),f(u)]};
k=2;
F2非单一,有D2={g(y),u}
б3=б2·{g(y)/u}={a/z,h(a,g(y))/x,g(y)/u};
F3=F2·{g(y)/u}={P[a,h(a,g(y)),f(g(y))]};
k=3;
F3已为单一元素集
∴б3={a/z,h(a,g(y))/x,g(y)/u}为公式集F的mgu
(2)递归算法(类PASCAL描述的UNIFY递归过程)
Procedureunify(E1,E2){E1,E2为本层次带来欲合一的表达式}
字符串型局部变量:
F1,F2,T1,T2,Z1,Z2,G1,G2;
{F1,F2中存本次E1,E2的First元素}
{T1,T2中存本次E1,E2的Tail部分}
{Z1中存F1,F2的合一者,Z2中存T1,T2的合一者}
{首元素F1,F2的合一者Z1作用于剩余部分T1,T2后的结果放G1,G2}
BEGIN
ifE1或E2中有一个是原子(即谓词符号、函数符号、常量符号、否定符号或变量)
then{递归出口}
begin
ifE1和E2是相同的,then
returnNIL;{不用置换,就
已相同}
ifE1非原子then交换E1和E2的位置,使E1是原子;
ifE1是变量,且E1不出现在E2中thenreturn{E2/E1};
ifE2是变量thenreturn{E1/E2}
elsereturnFAIL;
end
else{E1,E2均非原子时}
begin
F1:
=E1的第一个元素;T1:
=E1的其余元素;
F2:
=E2的第一个元素;T2:
=E2的其余元素;
Z1:
=unify(F1,F2);{将首元素合一,合一式在Z1中}
ifZ1=FAILthenreturnFAIL;{首元素不可合一,则整体不可合一}
G1:
=Z1作用到T1的结果;G2:
=Z1作用到T2的结果;Z2:
=unify(G1,G2);{将剩余部分当作新表达式去合一,递归调用}
ifZ2=FAILthenreturnFAIL;
returnZ1与Z2的合成{Z1·Z2}
end
END.
递归具体实现方案
将各种单括号及逗号视为元素及原子加入递归之中
原子:
(1)谓词符号、常量符号、变量符号、函数符号、否定符号
(2)各种单括号:
圆、方、花括弧
(3)逗号
E1、E2的第一个元素为:
谓词符号、常量符号、变量符号、函数符号(参数部分)、否定符号、单括号、逗号
若F1与F2均为函数时,则令F1、F2均取函数符号部分,而将括号中的参数部分划归至T1、T2,再去递归处理。
(否则的话,连同参数部分一起拿出当作第一元素)
例:
E1=’P[a,x,f(g(y))]’
E2=’P[z,h(z,u),f(u)]’
则:
unify(E1,E2);
Z1:
=unify(‘P’,’P’)
Z2:
=unify(‘[a,….]’,’[z,…]’)
return{Z1·Z2}
取值分析
第i层次F1值F2值Z1值F1属性F2属性
1PP谓词符号谓词符号
2[[方括号方括号
3az{a/z}常量符号变量符号
4,,
5xh(a,u){h(a,u)/x}变量函数符号(参数)
6,,逗号逗号
7ff函数符号函数符号
8((圆括号圆括号
9g(y)u{g(y)/u}函数符号(参数)变量
10))圆括号圆括号
11]]方括号方括号
第三节归结原理
定义
归结:
是一种可用于一定的子句公式的重要推理规则。
子句:
定义为由文字的析取组成的公式
文字:
一个原子公式和原子公式的否定
结论:
任意谓词公式都可化为子句集
5.5.1将谓词公式化为子句集的步骤
1.消去蕴涵符号=>
只应用∨和~符号,~A∨B替换A→B
2.~的深入(反复应用狄·摩根定律)
~A∨~B代替~(A∧B)
~A∧~B代替~(A∨B)
A代替~(~A)
(
x){~A}代替~(彐x)A(彐x){~A}代替~(
x)A
5.量词变元唯一(变量标准化)
在任一量词辖域内,受该量词约束的变量为一哑元(虚构变量),它可以在该辖域内处处统一地被另一个没有出现过的任意变量所代替,而不改变公式的真值。
合适公式中变量的标准化意味着对哑元改名以保证每个量词有其自己唯一的哑元。
例如,(
x){P(x)→(彐x)Q(x)}标准化而得到:
(
x){P(x)→(彐y)Q(y)}
4.消去彐
存在量词是在全称量词的辖域内,我们允许所存在的x可能依赖于y值。
令这种依赖关系明显地由函数g(y)所定义,它把每个y值映射到存在的那个x。
这种函数叫做Skolem函数。
如果用Skolem函数代替存在的x,我们就可以消去全部存在量词,
但函数符号不能同于公式中已有函数。
如:
(
x)(
y)[(彐z)P(x,y,z)]
消去彐,写成(
x)(
y)[P(x,y,f(x,y))]
ii)如果要消去的存在量词不在任何一个全称量词的辖域内,那么我们就用不含变量的Skolem函数即常量代换。
例如,(彐x)P(x)化为P(A)其中常量符号A用来表示我们知道的存在实体。
A必须是个新常量符号,它未曾在公式中其他地方使用过。
5.化为前束形
到这一步,已不留下任何存在量词,而且每个全称量词都有自己的变量。
把所有全称量词移到公式的左边,并使每个量词的辖域包含这个量词后面公式的整个部分。
所得公式称为前束形。
前束形公式由前缀和母式组成,前缀由全称量词串组成,母式由没有量词的公式组成,即:
前束形=(前缀){母式}全称量词串无量词公式6.把母式化为合取范式
任何母式都可写为由一些谓词公式和(或)谓词公式的否定的析取的有限集组成的合取。
这种母式叫做合取范式。
我们可以反复应用分配律,把任一母式化成合取范式。
例如,
把A∨{B∧C}化为:
{A∨B}∧{A∨C}
7.消去全称量词
到了这一步,所有余下的量词均被全称量词量化了。
同时,全称量词的次序也不重要了。
因此,我们可以消去前缀,即消去明显出现的全称量词。
8.消去连词符号∧
用{A,B}代替(A∧B),以消去明显的符号∧。
反复代替的
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- RGZN5 谓词 逻辑