《离散数学-2-7谓词演算的推理理论.ppt》由会员分享,可在线阅读,更多相关《离散数学-2-7谓词演算的推理理论.ppt(23页珍藏版)》请在三一办公上搜索。
1、1,第二章谓词逻辑,2-7 谓词演算的推理理论授课人:李朔Email:,2,一、谓词演算推理规则,谓词演算的推理方法,可以看作是命题演算推理方法的扩张。在一阶逻辑中,推理的形式结构仍为 H1 H2 HnB。若该式为逻辑有效式,则称推理正确,称B是H1,H2,Hn,的逻辑结论,记H1 H2 Hn B。一般的,将逻辑有效蕴含式称为推理定律。命题逻辑中的重言蕴含式,在一阶逻辑中的代入实例,都是一阶逻辑中的推理定律。另外,每个等值式都可产生两条推理定律。,3,一、谓词演算推理规则,谓词演算推理规则P规则:前提在推导过程中的任何时候都可以引入使用。T规则:在推导过程中,如果有一个或多个公式重言蕴涵这公式
2、S,则公式S可以引入推导之中。命题演算推理中的P规则、T规则(置换规则、合取引入规则)在谓词推理中都是对的,都可以使用;,4,一、谓词演算推理规则,在谓词推理中,某些前提与结论可受量词限制,为了使用等价式和蕴含式,必须在推理过程中有消去和添加的规则,使推理类似于命题演算中的推理理论。在推理过程中,除了用到命题逻辑中的推理规则外,还须用到下面4条规则。其中A B不一定表示AB是逻辑有效式(非永真),而仅表示在一定条件下,当A为真时,B也为真的推理关系。全称指定规则(简称US规则)全称推广规则(简称UG规则)存在量词指定规则(简称ES规则)存在推广规则(简称EG规则),5,二、全称指定规则,1全称
3、指定规则(简称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为任意的论域中某个客体。,6,二、全称指定规则,*全称指定规则在使用中,若不注意条件会犯错误。例如 在实数集中的二元谓词F(x,y):xy,则公式 xy F(x,y)为真命题。设P(x)=y F(x,y),此时x在P(x)中自由出现,若用y取代x,则得 x(yF(x,y)y F(y,y),结论为“存在y,yy”
4、,这是假命题*出错原因为y在P(x)中是约束出现。,7,三、全称推广规则,2全称推广规则(简称UG规则)P(x)(x)P(x)P(y)xP(x)上式成立,要求以下条件:(1)y在P(y)中自由出现,且y取任何值时P(y)均为真;(2)取代y的x不能在P(y)中约束出现,否则产生错误。,8,三、全称推广规则,例 在实数集中F(x,y):xy,取P(y)=x F(x,y)对给定y都成立。若应用上式时,以x取代y 得x(x(xx),这是假命题*出错原因是违背了(2)。,9,四、存在量词指定规则,3存在量词指定规则(简称ES规则)(x)P(x)P(c)xP(x)P(c)上式的成立,要求满足以下条件:(
5、1)c是使P(x)为真的特定个体常项;(2)c不曾在P(x)中出现;(3)P(x)中除x还有其它自由的客体变元时,不能用此规则。,10,四、存在量词指定规则,例:在自然数集中,设F(x):x为奇数,G(x):x为偶数。则 x F(x)x G(x)为真命题。如果不注意以上条件的使用,从x F(x),x G(x)会推出假命题来:1x F(x)P 2F(c)ES(1)3x G(x)P 4G(c)ES(3)5F(c)G(c)T(2),(4)I 6x(F(x)G(x)EG(5)*以上结论显然错的,其原因是违背条件(1),2步与4步中的c不应相同。,11,四、存在量词指定规则,又如,在实数集中,xy(xy
6、)是真命题,请看下面推导:1xy(xy)P 2y(zy)US(1)3zc ES(2)4x(xc)UG(3)而x(xc)是假命题。*结论是错的,其原因是违背了(3),对2使用ES规则时,z为自由出现的个体变项。,12,五、存在推广规则,4存在推广规则(简称EG规则)P(c)(x)P(x)P(c)x P(x)上式成立,要求以下条件:(1)c为特定的个体常项;(2)取代c的x不能已在P(c)中出现过。,13,五、存在推广规则,例 在实数集中,取F(x,y):xy,并取 P(3)=x F(x,3),P(3)为真命题。在使用上式,若用x取代3,则得到x F(x,x)这是假命题*其原因是违背了(2),14
7、,六、例题,例:找出下述推导的错误原因(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)E(换名规则)(3)A(x)S(y)US(2),15,六、例题,(b)(1)(x)(P(x)Q(x)P(2)P(a)Q(b)US(1)错:要统一全称量词消去正确:(2)P(a)Q(a)US(1)(c)(1)S(c)Q(c)P(2)xS(x)Q(x)EG(1)错:使用EG规则时,P(x)应是整个公式正确:(2)x(S(x)Q(x
8、))EG(1),16,六、例题,例:给定下面2个推理,找出错误.(1)1x(F(x)G(x)P 2F(y)G(y)US(1)3x F(x)P 4F(y)ES(3)5G(y)T(2)(3)I 6xG(x)UG(5)(2)1xy F(x,y)P 2y F(z,y)US(1)3F(z,c)ES(2)4x F(x,c)UG 5yx F(x,y)EG*在上面推理中(1)中从3到4有错,(2)中从2到3有错,17,六、例题,希望在应用上述规则时,千万注意条件,否则会犯错误。下面给出几个谓词逻辑中构造证明的例子。例:证明苏格拉底三段论“凡人都是要死的,张三是人,所以张三要死。”首先将命题符号化:解:F(x)
9、:x是人。G(x):x要死。a:张三。前提:x F(x)G(x),F(a)结论:G(a)。证明:1x(F(x)G(x)P 2F(a)G(a)US(1)3F(a)P 4G(a)T(2)(3)I*在本例中,没指明个体域,因而应取全总个体域。并引入特性谓词。,18,六、例题,例:人会说话,猴子不会说话,所以猴子不是人。解:设论域为全域,设M(x):x是人。S(x):x是猴子。T(x):x会说话。则前提为:x(M(x)T(x),x(S(x)T(x)结论为:x(S(x)M(x)证明:(1)x(M(x)T(x)P(2)M(y)T(y)US(1)(3)x(S(x)T(x)P(4)S(y)T(y)US(3)(
10、5)T(y)S(y)T(4)E(6)M(y)S(y)T(2),(5)I(7)S(y)M(y)T(6)E(8)x(S(x)M(x)UG(7),19,六、例题,例:每个学术会的成员都是工人并且是专家,有些成员是青年人。所以有的成员是青年专家。请在谓词逻辑中证明上面推理。解:F(x):x为学术会成员。G(x):x是专家。H(x):x是工人。R(x):x是青年人。前提:x(F(x)G(x)H(x),x(F(x)R(x)结论:x(F(x)R(x)G(x)证明:1x(F(x)R(x)P 2F(c)R(c)ES(1)3x(F(x)G(x)H(x)P 4F(c)G(c)H(c)US(3)5F(c)T(2)I
11、6G(c)H(c)T(4)(5)I 7R(c)T(2)I 8G(c)T(6)I 9F(c)R(c)G(c)T(5)(7)(8)I 10 x(F(x)R(x)G(x)EG(9),20,六、例题,若将证明步骤改为:1x(F(x)G(x)H(x)P 2F(c)G(c)H(c)US(1)3x(F(x)R(x)P 4F(c)R(c)ES(3)最后也能得出结论,但此证明是错的。原因出在3,4上,2中的c不一定能满足4。*因此,若在前提中,既有存在量词公式,又有全称量词公式,应先引入存在量词规则。,21,六、例题,例:构造下面推理的证明。前提:x(F(x)H(x),x(G(x)H(x)结论:x(G(x)F(x)证明:1x(F(x)H(x)P2x(F(x)H(x)T(1)E3x(H(x)F(x)T(2)E4H(y)F(y)US(3)5x(G(x)H(x)P 6G(y)H(y)US(5)7G(y)F(y)T(4)(6)I8x(G(x)F(x)UG(7),22,本课小结,US规则UG规则ES规则EG规则,23,课后作业,P79(1)补充:符号化下列命题并推证其结论。所有的人或者是吃素的或者是吃荤的,吃素的常吃豆制品,因而不吃豆制品的人是吃荤的。(个体域为人的集合)令F(x):x是吃素的,G(x):x是吃荤的,H(x):x吃豆制品。,