1.8谓词演算的推理规则.ppt

《1.8谓词演算的推理规则.ppt》由会员分享，可在线阅读，更多相关《1.8谓词演算的推理规则.ppt（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1.8 谓词演算的推理规则谓词演算的推理规则n1.8.1 谓词逻辑中推理的形式结构谓词逻辑中推理的形式结构n重要推理定律重要推理定律n1.8.2 量词消去与引入规则量词消去与引入规则nUI规则、规则、UG规则、规则、EG规则、规则、EI规则规则1A(x)对对y是自由的是自由的如果在公式如果在公式A(x)中，中，x不出现在量词不出现在量词 y或或 y的辖域之内，则称的辖域之内，则称A(x)对对y是自由的。是自由的。例如：例如：B(x)=y P(y)(x)R(z),B(x)对对y是自由的是自由的C(x)=yP(x,y)Q(x,y),C(x)对对y不是自由不是自由的的 2注：在将注：在将A(x)中的

2、中的x代以代以y时，需要先观察时，需要先观察A(x)对对y是否自由，如果不自由，不能代是否自由，如果不自由，不能代入。入。如：如：yP(x,y)Q(x,y)，将将x代以代以y得得 yP(y,y)Q(y,y)，此时原来自由的，此时原来自由的x变成约束的，故需要先将变成约束的，故需要先将y改名。改名。3谓词逻辑中推理的形式结构推理的形式结构推理的形式结构 形式形式1 A1 A2 AkB (*)形式形式2 前提：前提：A1,A2,Ak 结论：结论：B其中其中 A1,A2,Ak,B为谓词逻辑公式为谓词逻辑公式.若若(*)为永真式为永真式,则称则称推理正确推理正确,记作记作A1 A2 Ak B4推理定律

3、重要推理定律重要推理定律第一组第一组 命题逻辑推理定律的代换实例命题逻辑推理定律的代换实例例如例如 xF(x)yG(y)xF(x)化简律的代换实例化简律的代换实例第二组第二组 每个谓词逻辑基本等值式生成每个谓词逻辑基本等值式生成2个推理定律个推理定律例如例如 xF(x)x(F(x),x(F(x)xF(x)第三组第三组 xA(x)xB(x)x(A(x)B(x)x(A(x)B(x)xA(x)xB(x)推理定律推理定律:谓词逻辑中永真的蕴涵式谓词逻辑中永真的蕴涵式5量词消去与引入规则 UI全称量词消去规则全称量词消去规则(UI)成立的条件是成立的条件是:(1)A(x)对对y必须是自由的。必须是自由的

4、。(2)在第二式中在第二式中,c为任意个体常元为任意个体常元.(3)用用y或或c去去取取代代A(x)中中的的自自由由出出现现的的x时时,一一定定要要在在x自自由出现的一切地方进行取代由出现的一切地方进行取代.6注意违反第一条违反第一条：F(x,y):xy，个体域为实数域个体域为实数域 xA(x)=x yF(x,y)真命题真命题使用使用UI规则，若用规则，若用y取代取代x,得得 yF(y,y)假命题假命题 若用若用z取代取代x,得得 yF(z,y)7量词消去与引入规则 EG该式成立的条件是：该式成立的条件是：(1)c是使是使A为真的特定个体常元为真的特定个体常元.(2)取代取代c的的x不能在不能

5、在A(c)中出现过中出现过.存在量词引入规则存在量词引入规则(EG)8注意违反第二条违反第二条：F(x,y):xy，个体域为实数域个体域为实数域取取A(5)=xF(x,5)真命题真命题使用使用EG规则，若用规则，若用x取代取代5,得得 xA(x)=x xF(x,x)=x x(xx)假假 若用若用y取代取代5,得得 yA(y)=y xF(x,y)=y x(xy)真真9量词消去与引入规则 EI该式成立的条件是：该式成立的条件是：(1)c是使是使A为真的特定的个体常元为真的特定的个体常元.(2)c不在不在A(x)中出现中出现.(3)x在在A(x)中中自自由由出出现现,除除x之之外外没没有有其其他他自

6、自由由出现的个体变元出现的个体变元存在量词消去规则存在量词消去规则(EI)10注意违反第二条违反第二条：F(x,y):xy，个体域为实数域个体域为实数域 x A(x)=x F(x,5)对对 x A(x)使用使用EI规则，规则，若用若用5取代取代x,得得A(5)=(55)假假若用若用6取代取代x,得得A(6)=(65)真真11注意(1)个体域为自然数集合个体域为自然数集合NF(x):x为奇数为奇数.G(x):x为偶数为偶数.xF(x)真命题真命题 xG(x)真命题真命题对对 xF(x)使使用用EI规规则则时时，取取代代x的的只只能能是是1，3，5等等特特定定的的个体常元，而不能取个体常元，而不能

7、取4，6等等.对对 xG(x)使使用用EI规规则则时时，取取代代x的的只只能能是是0，2，16等等特特定定的的个体常元，而不能取个体常元，而不能取3，7等等.12量词消去与引入规则 UG该式成立的条件是该式成立的条件是 (1)是公理和前提的合取，其中没有是公理和前提的合取，其中没有x的自由出现。其意的自由出现。其意义：若从义：若从可推出可推出A(x)，那么从，那么从中也可推出中也可推出 xA(x).(2)在推出在推出A(x)前提中，前提中，x必须不是自由的；且必须不是自由的；且A(x)中中x不不 是由使用是由使用ES而引入的。而引入的。(3)在居先的步骤中，如果使用在居先的步骤中，如果使用US

8、而求得之而求得之x是自由的，是自由的，那么在后继步骤中，使用那么在后继步骤中，使用ES而引入的任何新变元都没而引入的任何新变元都没有在有在A(x)中自由出现。中自由出现。全称量词引入规则全称量词引入规则(UG)13观察下面的推理观察下面的推理(1)x yP(x,y)P,前提前提(2)yP(t,y)T,(1),US(3)P(t,d)T,(2),ES(4)x P(x,d)T,(3),UG(5)y x P(x,y)T,(4),EG14自然推理系统F自然推理系统自然推理系统F包括下述组成部分包括下述组成部分:1.字母表字母表,同谓词语言同谓词语言 的字母表的字母表2.合式公式合式公式,同同 的合式公式

9、的合式公式3.推理规则推理规则(1)前提引入规则前提引入规则(2)结论引入规则结论引入规则(3)置换规则置换规则(4)假言推理规则假言推理规则(5)附加规则附加规则15自然推理系统F(续)(6)化简规则化简规则(7)拒取式规则拒取式规则(8)假言三段论规则假言三段论规则(9)析取三段论规则析取三段论规则(10)构造性二难推理规则构造性二难推理规则(11)合取引入规则合取引入规则(12)UI规则规则(13)UG规则规则(14)EG规则规则(15)EI规则规则16例例1解解 令令 F(x):x是人是人,G(x):x是要死的是要死的,a:苏格拉底苏格拉底 前提：前提：x(F(x)G(x)，F(a)结

10、论：结论：G(a)证明：证明：F(a)前提引入前提引入 x(F(x)G(x)前提引入前提引入 F(a)G(a)UI G(a)假言推理假言推理例例1 证明苏格拉底三段论证明苏格拉底三段论:“人都是要死的人都是要死的,苏格拉底是人，苏格拉底是人，所以苏格拉底是要死的所以苏格拉底是要死的.”17例例2例例2 构造下述推理证明构造下述推理证明前提：前提：x(F(x)G(x)，xF(x)结论：结论：xG(x)证明：证明：xF(x)前提引入前提引入 x(F(x)G(x)前提引入前提引入 F(c)EI F(c)G(c)UI G(c)假言推理假言推理 xG(x)EG注意：注意：1.必须先消存在量词必须先消存在

11、量词 2.xG(x)UG 行吗？为什么？行吗？为什么？18例例4例例4 构造下述推理证明构造下述推理证明前提：前提：xF(x)xG(x)结论：结论：x(F(x)G(x)证明：证明：xF(x)xG(x)前提引入前提引入 x y(F(x)G(y)置换置换 x(F(x)G(z)UI F(z)G(z)UI x(F(x)G(x)UG19例例5例例5 构造下述推理证明构造下述推理证明前提：前提：x(F(x)G(x)结论：结论：xF(x)xG(x)证明：证明：xF(x)附加前提引入附加前提引入 F(y)UI x(F(x)G(x)前提引入前提引入 F(y)G(y)UI G(y)假言推理假言推理 xG(x)UG204月月26日日 作业作业nP53 4(2)n8(1)(3)n9(1)21例例例例3 设个体域设个体域:R,F(x,y):xy.指出下述推理证明中的错误指出下述推理证明中的错误前提前提:x yF(x,y)真命题真命题结论结论:xF(x,c)假命题假命题证明证明:x yF(x,y)前提引入前提引入 yF(t,y)UI规则规则 F(t,c)EI规则规则 xF(x,c)UG规则规则注意：注意：,在在F(t,y)中中,除除y外外,t也是自由出现也是自由出现,不能使用不能使用EI规则规则22