谓词演算的推理理论.ppt

1.8谓词演算的推理规则,一、谓词逻辑中推理的基本概念,设H1,H2,Hm()和都是谓词公式。若(H1H2Hm)为永真式，即H1H2Hm，则称由前提H1,H2,Hm推出结论C的推理正确(有效)。称为前提H1,H2,Hm的有效结论或逻辑结果。H1H2Hm称为由前提H1,H2,Hm推出结论C的推理的形式结构。,谓词逻辑中常用的推理规则其来源可分为两类：（一）命题逻辑中的所有推理规则如规则P、T及CP规则、反证法等亦可在谓词演算的推理中应用，只是应将各规则中的命题公式理解为谓词公式。谓词演算的推理方法可视为命题演算推理方法的扩张。（二）谓词逻辑中特有的推理规则1.谓词演算中与量词有关的基本的永真蕴含式和逻辑等价式。2.量词的消去或添加规则在谓词演算的推理中，某些前提或结论会受到量词的限制，为了使用命题演算中的等价式和蕴含式，必须有消去或添加量词的规则。,二、谓词逻辑的推理规则,1.US规则(全称指定规则),xA(x)A(y);xA(x)A(c)如果个体域D中所有的个体都具有性质A，则D中每一个个体（个体常元、个体变元）都具有性质A。两式成立的条件是：x是A(x)中自由出现的个体变元。在式中，y为任意的不在A(x)中约束出现的个体变元。特别地，y可取x。在式中，c为任意的个体常元。,消去规则(指定规则),例如：设个体域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)中约束出现。,2.ES规则(存在指定规则),xA(x)A(c)如果个体域D中存在具有性质A的个体，则D中必有某一个个体c（个体常元）具有该性质A。该式成立的条件是：x是A(x)中自由出现的个体变元。c是使A(c)为真的特定的个体常元，且此c在该推导前（包括在A(x)中）从未使用过。若A(x)中除自由出现的x以外，还有其他自由个体变元时，不能使用此规则。,例如：1.设个体域D为整数集，谓词F(x)：x是奇数。G(x)：x是偶数。推理过程如下：(1)xF(x)F(c)(2)xG(x)G(c)则xF(x)，xG(x)都是真命题，但F()G()假出错原因：(2)中的已在(1)被指定了，已是一个特定的值。(2)应改为：xG(x)G(d)F()G(d)真2.xF(x,y)F(c,y)出错原因：c的确定还与y有关。应改为：xF(x,y)F(cy,y),3.UG规则(全称推广规则),A(y)xA(x)如果个体域D中每一个个体都具有性质A，则D中所有的个体都具有该性质A。该式成立的条件是：y是A(y)中自由个体变元，且y取个体域D中的任何值时，A(y)均为真。取代y的x不能是A(y)中的约束变元，否则也会产生错误。注：使用本规则时，事先必须已经验证了对个体域中的每一个，A(x)都为真。,添加规则(推广规则),4.EG规则(存在推广规则),A(c)xA(x)A(y)xA(x)如果个体域D中某个个体（个体常元、个体变元）具有性质A，则D中存在着具有该性质A的个体。两式成立的条件是：c是使A(c)为真的特定的个体常元。y是使A(y)为真的自由个体变元。取代c或y的x不能在A(c)或A(y)中出现过。,例如：设个体域D为实数集，a)谓词F(x,y)：xy则下列推理正确的是：1.xF(x，y)zxF(x，z)2.xF(x，y)xxF(x，x)1对2错b)谓词F(x,y)：x*y=0则下列推理正确的是：1.xF(x,0)xxF(x,x)2.xF(x,0)zxF(x,z)1错2对,1.量词的消去或添加规则只对前束范式（即辖域为整个公式）的量词成立，不能对出现在公式中间的量词使用它们。2.使用时，要严格按照限制条件去使用，并从整体上考虑个体常元和个体变元符号的选择。3.用y或c取代A(x)中自由出现的x时，一定要在x自由出现的每一处都取代。,使用时的注意事项,例1-8-1证明苏格拉底三段论：所有的人都是要死的。苏格拉底是人。所以苏格拉底是要死的。解：设M(x)：x是人。D(x)：x是要死的。a：苏格拉底前提：x(M(x)D(x)，M(a)结论：D(a)推理的形式结构：x(M(x)D(x)M(a)D(a)证明:(1)x(M(x)D(x)规则P(2)M(a)D(a)(1)US规则，规则T(3)M(a)规则P(4)D(a)(2)(3)假言推理，规则T,二、谓词逻辑的推理实例,例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,例1-8-3设个体域为实数集。任何自然数都是整数。存在着自然数。所以存在着整数。解：设F(x)：x是自然数。G(x)：x是整数。前提：x(F(x)G(x)，xF(x)结论：xG(x)证明:(1)xF(x)规则P(2)F(c)(1)ES规则，规则T(3)x(F(x)G(x)规则P(4)F(c)G(c)(3)US规则，规则T(5)G(c)(2)(4)假言推理，规则T(6)xG(x)(5)EG规则，规则T,思考：可否先消x，再消x？(1)x(F(x)G(x)前提，规则P(2)F(c)G(c)(1)US规则，规则T(3)xF(x)前提，规则P(4)F(d)(3)ES规则，规则T则对(2),(4)无法继续往下推理。,注1：在推理时，若前提中既有x，又有x时，应先用ES规则消x，后用US规则消x，次序不能颠倒。,例1-8-4不存在能表示成分数的无理数。有理数都能表示成分数。因此，有理数都不是无理数。解：设F(x)：x是无理数。Q(x)：x是有理数。G(x):x能表示成分数。前提：x(F(x)G(x)，x(Q(x)G(x)，结论：x(Q(x)F(x),注2：在推理时，量词的消去或添加规则只对前束范式（即辖域为整个公式）的量词成立，若有的前提不是前束范式，要先对其进行等值演算，化为前束范式。如本题中的x(F(x)G(x),x(F(x)G(x)x(Q(x)G(x)x(Q(x)F(x)证明:(1)x(F(x)G(x)规则P(2)x(F(x)G(x)(1)量词转换律，规则T(3)x(F(x)G(x)(2)德摩根律，规则T(4)x(G(x)F(x)(3)蕴含等价式，规则T(5)G(y)F(y)(4)US规则，规则T(6)x(Q(x)G(x)规则P(7)Q(y)G(y)(6)US规则，规则T(8)Q(y)F(y)(5)(7)前提三段论，规则T(9)x(Q(x)F(x)(8)UG规则，规则T,例1-8-5证明x(P(x)Q(x)xP(x)xQ(x)证法1：用反证法，把(xP(x)xQ(x)作为假设前提，原式转化为证明:x(P(x)Q(x)(xP(x)xQ(x)F证法2：用CP规则，结论可改写为xP(x)xQ(x)xP(x)xQ(x)由CP规则，把xP(x)作为附加前提，原式转化为证明:x(P(x)Q(x)xP(x)xQ(x),证明：(1)xP(x)附加前提，规则P(2)xP(x)(1)量词转换律，规则T(3)P(c)(4)ES规则，规则T(4)x(P(x)Q(x)前提，规则P(5)P(c)Q(c)(4)US规则，规则T(6)Q(c)(3)(5)析取三段论，规则T(7)xQ(x)(6)EG规则，规则T由CP规则得：x(P(x)Q(x)xP(x)xQ(x)反证法证明见书例