谓词演算的推理理论课件.ppt

第第6讲讲 27 谓词演算的推理理论谓词演算的推理理论 要求要求：熟练掌握谓词的推理：熟练掌握谓词的推理理论理论与推理与推理方法方法，会用谓词的推理理论与推理方法进行会用谓词的推理理论与推理方法进行推理推理。重点重点：应用谓词的推理理论与推理方法进行：应用谓词的推理理论与推理方法进行推理推理。难点难点：正确理解和运用：正确理解和运用有关有关量词量词规则规则。谓词逻辑是命题逻辑的进一步深化和发展，谓谓词逻辑是命题逻辑的进一步深化和发展，谓词演算的推理方法，可以看作是词演算的推理方法，可以看作是命题演算推理方法命题演算推理方法的的扩张扩张。因此命题逻辑的推理理论在谓词逻辑中。因此命题逻辑的推理理论在谓词逻辑中几几乎可以完全照搬乎可以完全照搬，只不过这时涉及的公式是，只不过这时涉及的公式是谓词谓词逻逻辑的公式罢了。辑的公式罢了。在谓词逻辑中，某些在谓词逻辑中，某些前提前提和和结论结论可能可能受到量受到量词词的约束，为确立前提和结论之间的内部联系，有必的约束，为确立前提和结论之间的内部联系，有必要要消去消去量词和量词和添加添加量词，因此正确理解和运用有关量词，因此正确理解和运用有关量词规则是谓词逻辑推理理论中十分重要的关键所量词规则是谓词逻辑推理理论中十分重要的关键所在。在。一、有关量词一、有关量词消去消去和和添加添加规则规则量词消去规则（量词消去规则（证前去证前去量词）：量词）：(1)全称量词消去规则全称量词消去规则(称为全称指定规则，简称称为全称指定规则，简称US规则规则)(x)A(x)A(c)：其中其中c为论域中为论域中任意任意个体个体常元常元（举例说明）(2)存在量词消去规则存在量词消去规则(称为存在指定规则，简称称为存在指定规则，简称ES规则规则)(x)A(x)A(c)：其中其中c为论域中的某些为论域中的某些特定的特定的个体个体常元，它常元，它不是任意不是任意的。的。c不得不得在在前提前提中或者中或者居先推导公式中出现居先推导公式中出现或或自由自由出现。出现。（举例说明：存在一些人是男生，存在一些人是女生）量词产生规则（量词产生规则（证后加证后加量词）：量词）：(3)存在量词产生规则存在量词产生规则(称为存在推广规则，简称称为存在推广规则，简称EG规则规则)A(c)(y)A(y)其中其中c为论域中为论域中特定特定个体常元个体常元(4)全称量词产生规则全称量词产生规则(称为全称推广规则，简称称为全称推广规则，简称UG规则规则)A(c)(y)A(y)若能证明对论域中每一个客体若能证明对论域中每一个客体c断言断言A(c)都成立，则全称推广规都成立，则全称推广规则可得到结论则可得到结论(y)A(y)成立。成立。二、二、Lp中推理实例：中推理实例：Lp的推理方法是的推理方法是Ls推理方法的扩展，因此在推理方法的扩展，因此在Lp中利用的中利用的推理推理规则规则：（1）T规则、规则、P规则和规则和CP规则规则（2）已知的）已知的等价式等价式，蕴含式蕴含式（3）有关）有关量词的消去量词的消去和和产生产生规则。规则。使用的使用的推理方法推理方法是：是：直接直接构造法和构造法和间接间接证法（不能用真值表）。证法（不能用真值表）。所有谓词的推理，均可所有谓词的推理，均可先忽略量词先忽略量词，按命题逻辑中分析基本思，按命题逻辑中分析基本思路及所用方法，然后再注意路及所用方法，然后再注意证前去证前去量词，量词，证后加证后加量词，并注意量词，并注意次序次序即可即可例题例题1 证明苏格拉底论证：证明苏格拉底论证：所有的人都是要死的。所有的人都是要死的。苏格拉底是人。苏格拉底是人。所以苏格拉底是要死的。所以苏格拉底是要死的。解解 设设 H(x)：x是一个人。是一个人。M(x)：x是要死的。是要死的。s：苏格拉底。：苏格拉底。故苏格拉底论证可符号化为：故苏格拉底论证可符号化为：(x)(H(x)M(x)H(s)M(s)证明证明(1)(x)(H(x)M(x)P (2)H(s)M(s)US(1)(3)H(s)P(4)M(s)T(2)(3)I例题例题2 证明证明证明证明(x)(C(x)W(x)R(x)(x x)(C(x)Q(x)(x x)(Q(x)R(x)(1)(x)(C(x)W(x)R(x)P(2)(x x)(C(x)Q(x)P(4)C(a)W(a)R(a)US(1)(3)C(a)Q(a)ES(2)(5)C(a)T(3)I(6)W(a)R(a)T(4)(5)I(7)Q(a)T(3)I(8)R(a)T(6)I(9)Q(a)R(a)T(7)(8)I(10)(x x)(Q(x)R(x)EG（9）注意（注意（3）（）（4）两条次序不能颠）两条次序不能颠倒。倒。（1）原来的作用变元相）原来的作用变元相同同：若若先用先用ES后用后用US，可用，可用同同一常元也可用一常元也可用不同不同常元常元（按（按需需决定决定）；若若先用先用US后用后用ES，必用，必用不同不同常元常元;若若几个几个ES在一起，必用在一起，必用不同不同常元常元若若几个几个US在一起，可用相在一起，可用相同同常元也可用常元也可用不同不同常元常元（按（按需需决定决定）（2）原来作用变元）原来作用变元不同不同：无论顺序如何，或后，无论顺序如何，或后，常元必不同常元必不同例题例题3 证明证明(x)(P(x)Q(x)(x)P(x)(x x)Q(x)方法（）：方法（）：用用反反证法（证法（假定假定C C为为T T，推出矛盾）推出矛盾）(1)(x)P(x)(x x)Q(x)P(附加前附加前提提)(2)(x x)P(x)(x)Q(x)T(1)E(3)(x x)P(x)T(2)I(4)(x)Q(x)T(2)I(5)P(c)ES(3)(6)Q(c)US(4)(7)P(c)Q(c)T(5)(6)I(8)(P(c)Q(c)T(7)E(9)(x)(P(x)Q(x)P(10)P(c)Q(c)US(9)(11)(P(c)Q(c)(P(c)Q(c)(矛盾矛盾)T(8)(10)I方法（）：方法（）：用用CPCP规则规则原题可转为：原题可转为：(x)(P(x)Q(x)(x)P(x)(x x)Q(x)(要证要证S SR RC C ，也就是证明也就是证明(S SR)R)C C。)(1)(x)P(x)P（附加前提）附加前提）(2)(x)P(x)T（1）E(3)P(c)ES(2)(4)(x)(P(x)Q(x)P(5)P(c)Q(c)US(3)(6)Q(c)T(3)(5)I(7)(x)Q(x)EG(6)(8)(x)P(x)(x x)Q(x)CP例题例题4 构造下面推理的证明：构造下面推理的证明：每个学术会的成员都是专家并且是工人，有些成员是青年人，所以有些成员是每个学术会的成员都是专家并且是工人，有些成员是青年人，所以有些成员是青年专家。青年专家。证明证明设设 P(x)：x是学术会的成员。是学术会的成员。Q(x)：x是专家。是专家。R(x)：x是工人。是工人。S(x)：x是青年人。是青年人。证明过程如下：证明过程如下：则本题要证明：则本题要证明：(x)(P(x)Q(x)R(x)，(x x)(P(x)S(x)(x x)(P(x)Q(x)S(x)(1)(x x)(P(x)S(x)P(2)P(a)S(a)ES(1)(3)P(a)T(2)I(4)S(a)T(2)I(5)(x)(P(x)Q(x)R(x)P(6)P(a)Q(a)R(a)US(5)(7)Q(a)R(a)T(3)(6)I(8)Q(a)T(7)I(9)P(a)Q(a)S(a)T(3)(4)(8)I(10)(x x)(P(x)Q(x)S(x)EG(9)例例5 任何人违反了交通规则都要处以罚款，如任何人违反了交通规则都要处以罚款，如果没有罚款，就没有人违反交通规则。果没有罚款，就没有人违反交通规则。解解：S(x,y)：x违反了违反了y（x的论域是人的论域是人）(y)：y是交通规则，是交通规则，P(z)：z是罚款是罚款 R(x,z)：x受到受到z。则问题符号化为则问题符号化为：(x)(y)(S(x,y)M(y)(z)(P(z)R(x,z)：(z)P(z)(x)(y)(S(x,y)M(y)（可改为存在量词，并把非提前，与陈述更接近，更好理解）由于结论为条件式，故用由于结论为条件式，故用CP规则推理。规则推理。(1)(x)(y)(S(x,y)M(y)(z)(P(z)R(x,z)P(2)(y)(S(b,y)M(y)(z)(P(z)R(b,z)US(1)(3)(z)P(z)P（附加（附加前提）前提）(4)(z)P(z)T(3)E(5)P(a)US(4)(6)P(a)R(b,a)T(5)I(7)(z)(P(z)R(b,z)UG(6)(8)(z)(P(z)R(b,z)T(7)E(9)(y)(S(b,y)M(y)T(2)(8)I(10)(y)(S(b,y)M(y)T(9)E(11)(y)(S(b,y)M(y)T(10)E(12)（x)(y)(S(x,y)M(y)UG(11)v(z)P(z)(x)(y)(S(x,y)M(y)CP例中例中（7）（8），（），（9）（10），），（10）（11）都是错误步骤。都是错误步骤。其中其中（7）（8），（），（9）（10）还犯了还犯了省略步骤省略步骤的错误。的错误。在推理过程中，谓词公式在推理过程中，谓词公式只能用表所列只能用表所列的蕴含式与等价式的蕴含式与等价式；除表中除表中所列的带量词的公式所列的带量词的公式外外，一般一般的的不能在不能在量词后量词后面的辖域内进行面的辖域内进行蕴含推证或等价变换蕴含推证或等价变换，因此必须因此必须消除量词后消除量词后，才能对谓词公式，才能对谓词公式进行进行蕴含或等价推蕴含或等价推证；证；在作了适当的推演后，在作了适当的推演后，再恢复约束再恢复约束关系，以完关系，以完成带量词公式的逻辑推证成带量词公式的逻辑推证(1)(x)(y)(S(x,y)M(y)(z)(P(z)R(x,z)P(2)(y)(S(b,y)M(y)(z)(P(z)R(b,z)US(1)(3)(z)P(z)P（附加（附加前提）前提）(4)(z)P(z)T(3)E(5)P(a)US(4)(6)P(a)R(b,a)T(5)I(7)(P(a)R(b,a)T(6)E(8)(z)(P(z)R(b,z)UG(7)(9)(z)(P(z)R(b,z)T(8)E(10)(y)(S(b,y)M(y)T(2)(9)I(11)(y)(S(b,y)M(y)T(10)I(12)(S(b,c)M(c)US(11)(13)S(b,c)M(c)T(12)E(14)S(b,c)M(c)T(13)E(15)(y)(S(b b,y)M(y)UG(14)(16)(x x)(y)(S(x,x,y)M(y)UG(15)(17)(z)P(z)(x)(y)(S(x,y)M(y)CP数理逻辑在计算机科学中的数理逻辑在计算机科学中的用途用途：(1)作为作为知识表示的手段知识表示的手段，因为日常生活中的或数学领，因为日常生活中的或数学领域中的命题，大多能用谓词逻辑的符号表达式，便域中的命题，大多能用谓词逻辑的符号表达式，便于计算机处理；于计算机处理；(2)研究形式推理研究形式推理，为计算机进行自动推理提供方法和，为计算机进行自动推理提供方法和理论。理论。第二个用途过于专门和复杂，已超过本课程教学大第二个用途过于专门和复杂，已超过本课程教学大纲的要求。但是，第一个用途确是非常重要，所以纲的要求。但是，第一个用途确是非常重要，所以应该掌握。应该掌握。小结小结一、有关量词一、有关量词消去消去和和添加添加规则规则量词消去规则（量词消去规则（证前去证前去量词）：量词）：(1)全称量词消去规则全称量词消去规则(称为全称指定规则，简称称为全称指定规则，简称US规则规则)(x)A(x)A(c)：其中其中c为论域中为论域中任意任意个体个体常元常元(2)存在量词消去规则存在量词消去规则(称为存在指定规则，简称称为存在指定规则，简称ES规则规则)(x)A(x)A(c)：其中其中c为论域中的某些为论域中的某些特定的特定的个体个体常元，它常元，它不是任意不是任意的。的。c不得不得在在前提前提中或者中或者居先推导公式中出现居先推导公式中出现或或自由自由出现。出现。量词产生规则（量词产生规则（证后加证后加量词）：量词）：(3)存在量词产生规则存在量词产生规则(称为存在推广规则，简称称为存在推广规则，简称EG规则规则)A(c)(y)A(y)其中其中c为论域中为论域中特定特定个体常元个体常元(4)全称量词产生规则全称量词产生规则(称为全称推广规则，简称称为全称推广规则，简称UG规则规则)A(c)(y)A(y)若能证明对论域中若能证明对论域中每一个每一个客体客体c断言断言A(c)都成立，则全称都成立，则全称推广规则可得到结论推广规则可得到结论(y)A(y)成立。成立。二、二、Lp中推理实例中推理实例 Lp的推理方法是的推理方法是Ls推理方法的扩展，因此在推理方法的扩展，因此在Lp中利用的中利用的推理规则推理规则：（1）T规则、规则、P规则和规则和CP规则规则（2）已知的）已知的等价式，蕴含式等价式，蕴含式（3）有关）有关量词的消去量词的消去和和产生产生规则规则 使用的使用的推理方法推理方法是：是：直接直接构造法和构造法和间接间接证法证法（不能用真值表）。（不能用真值表）。作业：作业：P79(1)c)(2)b)(3)c)