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

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一定是自在的。一定是自在的。一、有关量词消去和添加规那么一、有关量词消去和添

4、加规那么量词消去规那么：量词消去规那么：(1) 全称量词消去规那么全称量词消去规那么(称为全称指定规那么，简称称为全称指定规那么，简称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不得在前提中或者居先推导公式

5、中出现或自在出现；不得在前提中或者居先推导公式中出现或自在出现；假设假设A(x)中有其它自在变元时，不能运用本规那么。中有其它自在变元时，不能运用本规那么。值得留意的是，值得留意的是，A(y)只是新引入的暂时假设，它不是对只是新引入的暂时假设，它不是对y的的一切值都是成立的。一切值都是成立的。y是一个暂时的、外表上的自在变元。是一个暂时的、外表上的自在变元。量词产生规那么：量词产生规那么：(3) 存在量词产生规那么存在量词产生规那么(称为存在推行规那么，简称称为存在推行规那么，简称EG规那么规那么)有两种方式：有两种方式：A(c)(y)A(y) 其中其中c为特定个体常元为特定个体常元 A(x)

6、(y)A(y)成立充分条件：取代成立充分条件：取代c的个体变元的个体变元y不在不在A(c)中出现；中出现；A(x)对对y 是自在的；假设是自在的；假设A(x)是推导行中的公式，且是推导行中的公式，且x是由运是由运用用EI引入的，那么不能用引入的，那么不能用A(x)中除中除x外的个体变元作约束变外的个体变元作约束变元，或者说，元，或者说，y不得为不得为A(x)中的个体变元。中的个体变元。(4) 全称量词产生规那么全称量词产生规那么(称为全称推行规那么，简称称为全称推行规那么，简称UG规那么规那么)A(x)(y)A(y)成立条件：前提成立条件：前提A(x)对于对于x的恣意取值都成立；的恣意取值都成

7、立；A(x)对对y是是自在的；对于由于运用自在的；对于由于运用EI 规那么所得到的公式中原约束变规那么所得到的公式中原约束变元及与其在同一个原子公式的自在变元，都不能运用本规那元及与其在同一个原子公式的自在变元，都不能运用本规那么而成为指点变元，否那么将产生错误推理。么而成为指点变元，否那么将产生错误推理。二、二、Lp中推理实例中推理实例 Lp的推理方法是的推理方法是Ls推理方法的扩展，因此在推理方法的扩展，因此在Lp中利用的推理规那么也是中利用的推理规那么也是T规那么、规那么、P规那规那么和么和CP规那么，还有知的等价式，蕴含式以规那么，还有知的等价式，蕴含式以及有关量词的消去和产生规那么。

8、运用的推及有关量词的消去和产生规那么。运用的推理方法是直接构造法和间接证法。理方法是直接构造法和间接证法。例题例题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(

9、2)(3)I例题例题2 证明证明证明证明留意34两条次序不能颠倒。练习79页1题(x)(C(x)W(x)R(x)(x)(C(x)Q(x)(x)(Q(x)R(x)(1) (x)(C(x)W(x)R(x) P(2) (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)(Q(x)R(x) EG例题例题3 证明证明 (x)(P(x)Q(x)(x)P(x)(x)Q(x

10、)用间接证法。要证用间接证法。要证S SC C，即要证，即要证S SC CT T，而，而S SC CSCSC，所以所以S SC CT T即即SCSCT T，亦就是，亦就是(SC)(SC)F F，SCSCF F。假定。假定CC为为T T，推出矛盾。，推出矛盾。(1) (x)P(x)(x)Q(x) P(附加前附加前提提)(2) (x)P(x)(x)Q(x) T(1)E(3) (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

11、) 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)Q(x)复习复习CPCP规那么规那么要证要证S SR RC C ，即要证，即要证S S(R(RC)C)T,T,即即S(RC)S(RC)T,T,(SR)C(SR)CT, (SR)CT, (SR)CT,(SR)T,(SR)C CT T也就是证明也就是证明(SR)(SR)C C。(1) (x)P(x) P附加前提附加前提(2) (x)P(x) T1E(3) P(c) ES(2)(

12、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)Q(x) CP例题例题4 构造下面推理的证明：构造下面推理的证明： 每个学术会的成员都是专家并且是工人，有些成员是青年人，所以有些成员是每个学术会的成员都是专家并且是工人，有些成员是青年人，所以有些成员是青年专家。青年专家。证明证明设设 P(x)： x是学术会的成员。是学术会的成员。 Q(x)： x是专家。是专家。 R(x) ：x是工人。是工人。 S(x) ：x是青年人。是青年人。证明过程如下：证明过程如下：那么此题要证明：那么此

13、题要证明：(x)(P(x)Q(x)R(x)，(x)(P(x)S(x)(x)(P(x)Q(x)S(x)(1) (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)(P(x)Q(x)S(x) EG(9) 数理逻辑在计算机科学中的用途有两个：数理逻辑在计算机科学中的用途有两个：一个是作为知识表示的手段，由于日常生活一个是作为知识表示的手段，由于日常生活中的或数学领域中的命题，大多能用谓词逻中的或数学领域中的命题，大多能用