欢迎来到天天文库
浏览记录
ID:39605071
大小:326.32 KB
页数:23页
时间:2019-07-07
《离散数学-2-7谓词演算的推理理论》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、第二章谓词逻辑2-7谓词演算的推理理论授课人:李朔Email:chn.nj.ls@gmail.com1一、谓词演算推理规则谓词演算的推理方法,可以看作是命题演算推理方法的扩张。在一阶逻辑中,推理的形式结构仍为H1H2…HnB。若该式为逻辑有效式,则称推理正确,称B是H1,H2,…,Hn,的逻辑结论,记H1H2…HnB。一般的,将逻辑有效蕴含式称为推理定律。命题逻辑中的重言蕴含式,在一阶逻辑中的代入实例,都是一阶逻辑中的推理定律。另外,每个等值式都可产生两条推理定律。2一、谓词演算推理规则谓词演算推理规则P规则:前提在推导过程中的任何时候都可以引
2、入使用。T规则:在推导过程中,如果有一个或多个公式重言蕴涵这公式S,则公式S可以引入推导之中。命题演算推理中的P规则、T规则(置换规则、合取引入规则)在谓词推理中都是对的,都可以使用;3一、谓词演算推理规则在谓词推理中,某些前提与结论可受量词限制,为了使用等价式和蕴含式,必须在推理过程中有消去和添加的规则,使推理类似于命题演算中的推理理论。在推理过程中,除了用到命题逻辑中的推理规则外,还须用到下面4条规则。其中AB不一定表示A→B是逻辑有效式(非永真),而仅表示在一定条件下,当A为真时,B也为真的推理关系。全称指定规则(简称US规则)全称推广规则(简称UG规
3、则)存在量词指定规则(简称ES规则)存在推广规则(简称EG规则)4二、全称指定规则1.全称指定规则(简称US规则)(x)P(x)∴P(c)这条规则可以有二种形式:xP(x)P(y)①xP(x)P(c)②在推理过程中①,②两种形式可根据需要选用。两式成立的条件是:(1)x为P(x)中自由出现的个体变元(不在P(x)中受约束)(2)在①中,y为不在P(x)中约束出现的个体变元;(3)在②中,C为任意的论域中某个客体。5二、全称指定规则*全称指定规则在使用中,若不注意条件会犯错误。例如在实数集中的二元谓词F(x,y):x>y,则公式xyF(x,y)为真
4、命题。设P(x)=yF(x,y),此时x在P(x)中自由出现,若用y取代x,则得x(yF(x,y))yF(y,y),结论为“存在y,y>y”,这是假命题*出错原因为y在P(x)中是约束出现。6三、全称推广规则2.全称推广规则(简称UG规则)P(x)∴(x)P(x)P(y)xP(x)上式成立,要求以下条件:(1)y在P(y)中自由出现,且y取任何值时P(y)均为真;(2)取代y的x不能在P(y)中约束出现,否则产生错误。7三、全称推广规则例在实数集中F(x,y):x>y,取P(y)=xF(x,y)对给定y都成立。若应用上式时,以x取代y得x(
5、x(x>x)),这是假命题*出错原因是违背了(2)。8四、存在量词指定规则3.存在量词指定规则(简称ES规则)(x)P(x)∴P(c)xP(x)P(c)上式的成立,要求满足以下条件:(1)c是使P(x)为真的特定个体常项;(2)c不曾在P(x)中出现;(3)P(x)中除x还有其它自由的客体变元时,不能用此规则。9四、存在量词指定规则例:在自然数集中,设F(x):x为奇数,G(x):x为偶数。则xF(x)xG(x)为真命题。如果不注意以上条件的使用,从xF(x),xG(x)会推出假命题来:1.xF(x)P2.F(c)ES(1)3.xG(x)
6、P4.G(c)ES(3)5.F(c)G(c)T(2),(4)I6.x(F(x)G(x))EG(5)*以上结论显然错的,其原因是违背条件(1),2步与4步中的c不应相同。10四、存在量词指定规则又如,在实数集中,xy(x>y)是真命题,请看下面推导:1.xy(x>y)P2.y(z>y)US(1)3.z>cES(2)4.x(x>c)UG(3)而x(x>c)是假命题。*结论是错的,其原因是违背了(3),对2使用ES规则时,z为自由出现的个体变项。11五、存在推广规则4.存在推广规则(简称EG规则)P(c)∴(x)P(x)P(c)xP(x)上
7、式成立,要求以下条件:(1)c为特定的个体常项;(2)取代c的x不能已在P(c)中出现过。12五、存在推广规则例在实数集中,取F(x,y):x>y,并取P(3)=xF(x,3),P(3)为真命题。在使用上式,若用x取代3,则得到xF(x,x)这是假命题*其原因是违背了(2)13六、例题例:找出下述推导的错误原因(a)(1)(x)A(x)S(x)P(2)A(x)S(x)US(1)错:(x)P(x)使用US规则时,P(x)是整个公式,上述公式中A(x)S(x)才是整个公式。正确:(1)(x)A(x)S(x)P(2)(x)A(x)S(y)T(1
8、)E(换名规则)(3)A(x)S(y
此文档下载收益归作者所有