NUIST1 11.8 谓词演算的推理规则一、谓词逻辑中推理的基本概念 设H1,H2,Hm()和都是谓词公式。n若 ( H1H2 Hm ) 为永真式， 即H1H2 Hm ， 则称由前提H1,H2, ,Hm推出结论C的推理正确(有效)。n称为前提H1,H2, ,Hm的有效结论或逻辑结果。nH1H2 Hm 称为 由前提H1,H2, ,Hm推出结论C的推理的形式结构。 南京信息工程大学数理学院南京信息工程大学数理学院NUIST2 2 谓词逻辑中常用的推理规则其来源可分为两类：（一）（一） 命题逻辑中的所有推理规则n如规则P、T及CP规则、反证法等亦可在谓词演算的推理中应用，只是应将各规则中的命题公式理解为谓词公式。谓词演算的推理方法可视为命题演算推理方法的扩张。谓词演算的推理方法可视为命题演算推理方法的扩张。（二）谓词逻辑中特有的推理规则 1.谓词演算中与量词有关的基本的永真蕴含式和逻辑等价式。2.量词的消去或添加规则n在谓词演算的推理中，某些前提或结论会受到量词的限制， 为了使用命题演算中的等价式和蕴含式，必须有消去或添加 量词的规则。二、谓词逻辑的推理规则谓词逻辑的推理规则南京信息工程大学数理学院南京信息工程大学数理学院NUIST3 31. US1. US规则规则( (全称指定规则全称指定规则) )n xA(x)xA(x)A(y); A(y); n xA(x)xA(x)A(c) A(c) 如果个体域D中所有的个体都具有性质A， 则D中每一个个体（个体常元、个体变元）都具有性质A。两式成立的条件是： x是A(x)中自由出现的个体变元。 在式中，y为任意的不在A(x)中约束出现的个体变元。 特别地，y可取x。 在式中，c为任意的个体常元。消去规则消去规则( (指定规则指定规则) )南京信息工程大学数理学院南京信息工程大学数理学院NUIST4 4例如： 设个体域D为实数集，谓词 F(x,y)：xy。 则xyF(x,y)： 对任意的实数x，都存在实数y，使xy。（真命题） 则下列推理正确的是：( )1.xyF(x,y)yF(c,y)2.xyF(x,y)yF(x,y) 3.xyF(x,y)yF(y,y) 4.xyF(x,y)yF(z,y)答案：1，2，4正确 3出错的原因是y已在yF(x,y)中约束出现。南京信息工程大学数理学院南京信息工程大学数理学院NUIST5 52. ES2. ES规则规则( (存在指定规则存在指定规则) )n xA(x)xA(x)A(c)A(c)如果个体域D中存在具有性质A的个体， 则D中必有某一个个体c（个体常元）具有该性质A。该式成立的条件是： x是A(x)中自由出现的个体变元。 c是使A(c)为真的特定的个体常元，且此c在该推导前 （包括在A(x)中）从未使用过。若A(x)中除自由出现的x以外，还有其他自由个体变元时，不能使用此规则。南京信息工程大学数理学院南京信息工程大学数理学院NUIST6 6例如： 1. 设个体域D为整数集， 谓词 F(x)：x是奇数。 G(x)：x是偶数。 推理过程如下： (1) (1) xF(x)xF(x) F(c)F(c) (2) (2) xG(x)xG(x) G(c)G(c)则xF(x)，xG(x)都是真命题，但 F(F()G()G() ) 假假出错原因：(2)中的已在(1)被指定了，已是一个特定的值。 (2)应改为： xG(x)xG(x) G(d)G(d) F(F()G()G(d d) ) 真 2. 2. xF(x,y) xF(x,y) F(c,y)F(c,y)出错原因：c的确定还与y有关。 应改为： xF(x,y)xF(x,y) F(cF(cy y,y),y)南京信息工程大学数理学院南京信息工程大学数理学院NUIST7 73. UG3. UG规则规则( (全称推广规则全称推广规则) )n A(y) A(y) xA(x)xA(x)如果个体域D中每一个个体都具有性质A， 则D中所有的个体都具有该性质A。该式成立的条件是： y是A(y)中自由个体变元，且y取个体域D中的任何值时， A(y)均为真。 取代y的x不能是A(y)中的约束变元，否则也会产生错误。注：使用本规则时，事先必须已经验证了对个体域中的每一个 ，A(x)都为真。添加规则添加规则( (推广规则推广规则) )南京信息工程大学数理学院南京信息工程大学数理学院NUIST8 84. EG4. EG规则规则( (存在推广规则存在推广规则) )nA(c)A(c) xA(x)xA(x)nA(y)A(y) xA(x)xA(x)如果个体域D中某个个体（个体常元、个体变元） 具有性质A，则D中存在着具有该性质A的个体。两式成立的条件是： c c是是使使A(c)A(c)为真的特定为真的特定的个体常元。的个体常元。 y y是是使使A(y)A(y)为真的自由为真的自由个体变元。个体变元。取代取代c c或或y y的的x x不能在不能在A(c)A(c)或或A(y)A(y)中出现过。中出现过。南京信息工程大学数理学院南京信息工程大学数理学院NUIST9 9例如：设个体域D为实数集， a)谓词 F(x,y)F(x,y)：x yx y则下列推理正确的是： 1. 1. xF(xxF(x，y)y) z z xF(xxF(x，z) z) 2. 2. xF(xxF(x，y)y) x x xF(xxF(x，x)x) 1 1对对2 2错错 b)谓词 F(x,y)F(x,y)：x*y=0x*y=0则下列推理正确的是： 1. 1. x F(x,0) x F(x,0) x x x F(x,x)x F(x,x) 2. 2. x F(x,0) x F(x,0) z z x F(x,z)x F(x,z) 1 1错错2 2对对南京信息工程大学数理学院南京信息工程大学数理学院NUIST10101. 量词的消去或添加规则只对前束范式（即辖域为整个公式）的量词成立，不能对出现在公式中间的量词使用它们。2. 使用时，要严格按照限制条件去使用，并从整体上考虑个体常元和个体变元符号的选择。3. 用y或c取代A(x)中自由出现的x时，一定要在x自由出现的每一处都取代。使用时的注意事项南京信息工程大学数理学院南京信息工程大学数理学院NUIST1111例例1-8-11-8-1 证明苏格拉底三段论：所有的人都是要死的。 苏格拉底是人。 所以苏格拉底是要死的。解：设 M(x)：x是人。D(x)：x是要死的。a：苏格拉底 前提前提： x( M(x)D(x) )x( M(x)D(x) )， M(a)M(a) 结论：结论： D(a)D(a) 推理的形式结构：推理的形式结构： x( M(x)D(x) )M(a)x( M(x)D(x) )M(a)D(a) D(a) 证明证明: : (1)(1) x( M(x)D(x) ) x( M(x)D(x) ) 规则规则P P (2) M(a)D(a) (1)US (2) M(a)D(a) (1)US规则，规则规则，规则T T (3) M(a) (3) M(a) 规则规则P P (4) D(a) (2)(3) (4) D(a) (2)(3)假言推理，规则假言推理，规则T T二、谓词逻辑的推理实例谓词逻辑的推理实例南京信息工程大学数理学院南京信息工程大学数理学院NUIST1212例1-8-2 同事之间总是有工作矛盾的。 张平和李明没有工作矛盾。所以他们不是同事。解：设F(x,y)：x和y是同事。Q(x,y)：x和y有工作矛盾。 a:张平 b:李明 前提： xy(F(x,y)Q(x,y)， Q(a,b) 结论： F(a,b) 证明: (1) xy(F(x,y)Q(x,y) 规则P (2) y(F(a,y)Q(a,y)） (1)US规则，规则T (3) F(a,b)Q(a,b) (2)US规则，规则T (4) Q(a,b) 规则P (5) F(a,b) (3)(4)拒取式，规则T 南京信息工程大学数理学院南京信息工程大学数理学院NUIST1313例1-8-3 设个体域为实数集。 任何自然数都是整数。存在着自然数。所以存在着整数。解：设F(x)：x是自然数。G(x)：x是整数。 前提：前提： x( F(x)G(x) )x( F(x)G(x) )， x F(x)x F(x) 结论：结论： x G(x)x G(x)证明证明: (1): (1) x F(x) x F(x) 规则规则P P (2) F(c) (1)ES (2) F(c) (1)ES规则，规则规则，规则T T (3) (3) x( F(x)G(x) ) x( F(x)G(x) ) 规则规则P P (4) F(c)G(c) (3) US (4) F(c)G(c) (3) US规则，规则规则，规则T T (5) G(c) (2)(4) (5) G(c) (2)(4)假言推理，规则假言推理，规则T T (6) (6) x G(x) (5) EGx G(x) (5) EG规则，规则规则，规则T T南京信息工程大学数理学院南京信息工程大学数理学院NUIST1414思考：思考： 可否先消可否先消 x x，再消再消 x x ？ (1) (1) x x(F(x)G(x) (F(x)G(x) 前提，规则前提，规则P P (2) F(c)G(c) (1)US (2) F(c)G(c) (1)US规则，规则规则，规则T T (3) (3) x x F(x) F(x) 前提，规则前提，规则P P (4) F(d) (3)ES (4) F(d) (3)ES规则，规则规则，规则T T 则对则对(2),(4)(2),(4)无法继续往下推理。无法继续往下推理。v 注1：在推理时， 若前提中既有x，又有x时， 应先用ES规则消x ，后用US规则消x ，次序不能颠倒。南京信息工程大学数理学院南京信息工程大学数理学院NUIST1515例1-8-4 不存在能表示成分数的无理数。 有理数都能表示成分数。 因此，有理数都不是无理数。解：设F(x)：x是无理数。Q(x)：x是有理数。 G(x):x能表示成分数。 前提：前提： x( F(x)G(x) )x( F(x)G(x) )， x( Q(x)G(x) )x( Q(x)G(x) )， 结论：结论： x( Q(x) x( Q(x) F(x) )F(x) )v 注2：在推理时， 量词的消去或添加规则只对前束范式（即辖域为整个公式）的量词成立，若有的前提不是前束范式，要先对其进行等值演算，化为前束范式。如本题中的 x (x (F(x)G(xF(x)G(x) ) 南京信息工程大学数理学院南京信息工程大学数理学院NUIST1616x (F(x)G(x)x (F(x)G(x) x(Q(x)G(x) x(Q(x)G(x) x(Q(x) x(Q(x) F(x)F(x)证明证明: : (1)(1) x (F(x)G(x)x (F(x)G(x) 规则规则P P (2) (2) x x (F(x)G(x) (1) (F(x)G(x) (1) 量词转换律，规则量词转换律，规则T T (3) (3) x (x ( F(x) F(x) G(x) (2) G(x) (2) 德摩根律，规则德摩根律，规则T T (4) (4) x (G(x) x (G(x) F(x) (3) F(x) (3) 蕴含等价式，规则蕴含等价式，规则T T (5) G(y) (5) G(y) F(y) (4)US F(y) (4)US规则，规则规则，规则T T (6) (6) x(Q(x)G(x) x(Q(x)G(x) 规则规则P P (7) Q(y)G(y) (6)US (7) Q(y)G(y) (6)US规则，规则规则，规则T T (8) Q(y) (8) Q(y) F(y) (5)(7) F(y) (5)(7)前提三段论，规则前提三段论，规则T T (9) (9) x(Q(x) x(Q(x) F(x) (8)UGF(x) (8)UG规则，规则规则，规则T T南京信息工程大学数理学院南京信息工程大学数理学院NUIST1717例例1-8-51-8-5 证明证明 x(P(x)Q(x) x(P(x)Q(x) xP(x)xP(x) xQ(x)xQ(x)证法证法1 1： 用用反证法，反证法，把把 ( ( xP(x)xP(x) xQ(x)xQ(x)作为作为假设假设前提前提， 原式转化为原式转化为证证明明: : x( P(x)Q(x) ) x( P(x)Q(x) ) ( ( xP(x)xP(x) xQ(x) ) xQ(x) ) F F证法证法2 2： 用用CPCP规则规则，结论结论可改写为可改写为 xP(x)xP(x) xQ(x) xQ(x) xP(x) xP(x) xQ(x)xQ(x) 由由CPCP规则规则， 把把 xP(x)xP(x) 作为作为附加附加前提前提， 原式转化为原式转化为证证明明: : x(P(x)Q(x) x(P(x)Q(x) xP(x) xP(x) xQ(x)xQ(x) 南京信息工程大学数理学院南京信息工程大学数理学院NUIST1818证明：证明：(1)(1) xP(x) xP(x) 附加前提，附加前提，规则规则P P (2) (2) x x P(x) (1)P(x) (1)量词转换律，规则量词转换律，规则T T (3) (3) P(c) (4) ESP(c) (4) ES规则，规则规则，规则T T (4) (4) x(P(x)Q(x) x(P(x)Q(x) 前提，规则前提，规则P P (5) P(c)Q(c) (4)US (5) P(c)Q(c) (4)US规则，规则规则，规则T T (6) Q(c) (3)(5) (6) Q(c) (3)(5)析取三段论，规则析取三段论，规则T T (7) (7) xQ(x) (6)EGxQ(x) (6)EG规则，规则规则，规则T T 由由CPCP规则规则得：得： x(P(x)Q(x) x(P(x)Q(x) xP(x)xP(x) xQ(x)xQ(x)反证法证明见书例反证法证明见书例4 4。南京信息工程大学数理学院南京信息工程大学数理学院NUIST19191. 所有有理数是实数。某些有理数是整数。因此，某些 实数是整数。 2. 任何人如果他喜欢步行，他就不喜欢乘车。每一个人或者喜欢坐汽车，或者喜欢骑自行车。有的人不喜欢骑自行车，因而有的人不爱步行。 3. 每个大学生不是文科生，就是理工科学生。有的大学生是优等生。小张不是理工科学生，但是他是优等生。因而，小张是大学生，那么他就是文科生。 作业 1-8南京信息工程大学数理学院南京信息工程大学数理学院