离散数学26 谓词演算的推理理论.ppt

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

1、离散数学Discrete Mathematics第第6讲讲 27 谓词演算的推理理论谓词演算的推理理论 要求：熟练掌握谓词的推理理论与推理方法，要求：熟练掌握谓词的推理理论与推理方法，会用谓词的推理理论与推理方法进行推理。会用谓词的推理理论与推理方法进行推理。重点：应用谓词的推理理论与推理方法进行重点：应用谓词的推理理论与推理方法进行推理。推理。难点：正确理解和运用有关量词规则。难点：正确理解和运用有关量词规则。谓词逻辑是命题逻辑的进一步深化和发展，谓词逻辑是命题逻辑的进一步深化和发展，谓词演算的推理方法，可以看作是命题演算谓词演算的推理方法，可以看作是命题演算推理方法的扩张。因此命题逻辑的推

2、理理论推理方法的扩张。因此命题逻辑的推理理论在谓词逻辑中几乎可以完全照搬，只不过这在谓词逻辑中几乎可以完全照搬，只不过这时涉及的公式是谓词逻辑的公式罢了。在谓时涉及的公式是谓词逻辑的公式罢了。在谓词逻辑中，某些前提和结论可能受到量词的词逻辑中，某些前提和结论可能受到量词的约束，为确立前提和结论之间的内部联系，约束，为确立前提和结论之间的内部联系，有必要消去量词和添加量词，因此正确理解有必要消去量词和添加量词，因此正确理解和运用有关量词规则是谓词逻辑推理理论中和运用有关量词规则是谓词逻辑推理理论中十分重要的关键所在。十分重要的关键所在。下面在介绍有关量词规则之前做些必要下面在介绍有关量词规则之前

3、做些必要准备。下面给出准备。下面给出A(x)对对y是自由的这个概念。是自由的这个概念。其目的是，允许用其目的是，允许用y代入代入x后得到后得到A(y)，它不，它不改变原来公式改变原来公式A(x)的约束关系。的约束关系。定义定义2.7.1 在谓词公式在谓词公式A(x)中，若中，若x自由出现自由出现在量词在量词(y)或或(y)的辖域，的辖域，则称则称A(x)对于对于y是自由的。是自由的。由定义可知，若由定义可知，若y在在A(x)中不是约束出现，中不是约束出现，则则A(x)对于对于y一定是自由的。一定是自由的。一、有关量词消去和添加规则一、有关量词消去和添加规则量词消去规则：量词消去规则：(1)全称

4、量词消去规则全称量词消去规则(称为全称指定规则，简称称为全称指定规则，简称UI或或US规则规则)有两种形式：有两种形式：(x)A(x)A(c)其中其中c为任意个体常元为任意个体常元 (x)A(x)A(y)A(x)对对y是自由的是自由的(2)存在量词消去规则存在量词消去规则(称为存在指定规则，简称称为存在指定规则，简称EI或或ES规则规则)有两种形式：有两种形式：(x)A(x)A(c)其中其中c为特定个体常元为特定个体常元 (x)A(x)A(y)成立充分条件是：成立充分条件是：c或或y不得在前提中或者居先推导公式中出现或自由出现；不得在前提中或者居先推导公式中出现或自由出现；若若A(x)中有其它

5、自由变元时，不能应用本规则。中有其它自由变元时，不能应用本规则。值得注意的是，值得注意的是，A(y)只是新引入的暂时假设，它不是对只是新引入的暂时假设，它不是对y的的一切值都是成立的。一切值都是成立的。y是一个暂时的、表面上的自由变元。是一个暂时的、表面上的自由变元。量词产生规则：量词产生规则：(3)存在量词产生规则存在量词产生规则(称为存在推广规则，简称称为存在推广规则，简称EG规则规则)有两种形式：有两种形式：A(c)(y)A(y)其中其中c为特定个体常元为特定个体常元 A(x)(y)A(y)成立充分条件：成立充分条件：取代取代c的个体变元的个体变元y不在不在A(c)中出现；中出现；A(x

6、)对对y 是自由的；是自由的；若若A(x)是推导行中的公式，且是推导行中的公式，且x是由使用是由使用EI引入的，那么不能用引入的，那么不能用A(x)中除中除x外的个体变元作约束变元，外的个体变元作约束变元，或者说，或者说，y不得为不得为A(x)中的个体变元。中的个体变元。(4)全称量词产生规则全称量词产生规则(称为全称推广规则，简称称为全称推广规则，简称UG规则规则)A(x)(y)A(y)成立条件：成立条件：前提前提A(x)对于对于x的任意取值都成立；的任意取值都成立；A(x)对对y是是自由的；自由的；对于由于使用对于由于使用EI 规则所得到的公式中原约束变规则所得到的公式中原约束变元及与其在

7、同一个原子公式的自由变元，都不能使用本规则元及与其在同一个原子公式的自由变元，都不能使用本规则而成为指导变元，否则将产生错误推理。而成为指导变元，否则将产生错误推理。二、二、Lp中推理实例中推理实例 Lp的推理方法是的推理方法是Ls推理方法的扩展，因此在推理方法的扩展，因此在Lp中利用的推理规则也是中利用的推理规则也是T规则、规则、P规则和规则和CP规则，还有已知的等价式，蕴含式以及有规则，还有已知的等价式，蕴含式以及有关量词的消去和产生规则。使用的推理方法关量词的消去和产生规则。使用的推理方法是直接构造法和间接证法。是直接构造法和间接证法。例题例题1 证明苏格拉底论证：证明苏格拉底论证：所有

8、的人都是要死的。所有的人都是要死的。苏格拉底是人。苏格拉底是人。所以苏格拉底是要死的。所以苏格拉底是要死的。解解 设设 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 证明证明证明证明注意（3）（4）两条次序不能颠倒。练习79页（1）题(x)(C(x)W(x)R(x)(x x)(C(x)Q(x)(x x)(Q(x)R(x)(1)(x

9、)(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例题例题3 证明证明(x)(P(x)Q(x)(x)P(x)(x x)Q(x)用间接证法。要证用间接证法。要证S SC C，即要证即要证S SC CT T，而而S SC CS SC C，所以所以S SC CT T即即S SC CT T，亦就是亦就是(S SC)C)F F，S

10、SC CF F。假定假定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证法证法2 本题可用本题可用CP规则规则原题为原题为(x)(P(x)Q(x)(x)P(x)(x x)Q(x

11、)复习复习CPCP规则规则要证要证S SR RC C ，即要证即要证S S(R RC)C)T,T,即即S S(R RC)C)T,T,(S SR)R)C CT,T,(S SR)R)C CT,T,(S SR)R)C CT T也就是证明也就是证明(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 构造下面推理的证明：构造下面推理的证明：每个学术会的成员都是

12、专家并且是工人，有些成员是青年人，所以有些成员是每个学术会的成员都是专家并且是工人，有些成员是青年人，所以有些成员是青年专家。青年专家。证明证明设设 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

13、(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)数理逻辑在计算机科学中的用途有两个：数理逻辑在计算机科学中的用途有两个：一个是作为知识表示的手段，因为日常生活一个是作为知识表示的手段，因为日常生活中的或数学领域中的命题，大多能用谓词逻中的或数学领域中的命题，大多能用谓词逻辑的符号表达式，便于计算机处理；另一个辑的符号表达式，便于计算机处理；另一个用途是研究形式推理，为计算机进行自动推用途是研究形式推理，为计算机进行自动推理提供方法和理论。理提供方法和理论。第二个用途过于专门和复杂，已超过本课程第二个用途过于专门和复杂，已超过本课程教学大纲的要求。但是，第一个用途确是非教学大纲的要求。但是，第一个用途确是非常重要，所以应该掌握。常重要，所以应该掌握。作业79页（3）练习79页（2）