第二章谓词逻辑2015-3-30讲解.ppt

（3）存在量词产生规则(简称EG规则) 有两种形式： A(c)| EG (?y)A(y) ， 其中c为特定个体常元； A(x)| EG (?y)A(y) 成立充分条件： ①取代c的个体变元 y不在A(c)中出现； ②A(x)对 y 是自由的； ③若A(x)是推导行中的公式，且x是由使用EI引入的，那么不能 用A(x)中除x外的个体变元作约束变元，或者说，y不能是出现 在A(x)中的个体变元。 若不满足成立条件，可能导致错误结论。 例2.10.5 令个体域为全体实数，G(x，y)：xy。 考察下列推导： ① (1) (?y)G(y，x) P A(x)=(?y)G(y，x) (2) (?y)(?y)G(y，y) EG，(1) A(x)对y不是自由的 ② (1) (?z)(?y)G(z，y) P (2) (?y)G(x，y) EI，(1) 消去存在量词(?z) (3) (?y)(?y)G(y，y) EG，(2) x是由EI规则引入的， A(x)对y不自由 违反了EG规则条件③ 解：这两个推导的结果表明，y取任何值时，y与y总有关系G, 显然 这是错误的。 原因：在推理中违反使用EG规则所要求的成立条件。 （4）全称量词产生规则(简称UG规则) A(x)| UG (?y)A(y) 成立条件： ①前提A(x)对于x的任意取值都成立； ②A(x)对y是自由的； ③对于由于使用EI 规则所得到的公式中原约束变元及与其在同一个原子公式的自由变元，都不能使用本规则而成为指导变元，否则将产生错误推理。 例2.10.6 在个体域为全体实数中，G(x，y)：xy， 试考察下面推导： (1) (?x)(?y)G(x，y) P (2) (?y)G(z，y) UI，(1) (3) G(z，a) EI，(2) G(z,y)里z为自由变元， 不能使用EI规则 (4) (?x)G(x，a) UG，(3) z为G(z,y)的自由变元， 不能使用UG规则 (5) (?y)(?x)G(x，y) EG，(4) 解：显然从给定前提推出的结论是错误的。 原因：在(4)步中违反了UG成立条件的③。 在 (3)步中已违反了EI成立条件②。 二、谓词逻辑推理实例 谓词逻辑的推理方法是命题逻辑推理方法的扩展。 在谓词逻辑中利用的推理规则： T规则、P规则和CP规则； 还有已知的等价式，蕴涵式； 以及有关量词的消去和产生规则。 使用的推理方法： 直接构造法和间接证法。 证明：令M(x)：x是人； D(x)：x会死； s：苏格拉底； 原题符号化为： (?x)(M(x)→D(x)), M(s) |- D(s) 推证如下： {1} (1) (?x)(M(x)→D(x)) P {2} (2) M(s)→D(s) UI, (1) {3} (3) M(s) P {1,3} (4) D(s) T, (2)(3), I8 例2.10.7 试证明下面苏格拉底论证： 所有人都会死的， 苏格拉底是人， 因此，苏格拉底会死的。 例2.10.8 每个大学生或者享有奖学金或者交费学习。 每个大学生当且仅当学习评优者享有