离散数学第2.5陈瑜---副本.ppt

计算机科学与工程学院 主要内容 1. 谓词逻辑的推理方法 2.消解(归结)法 2.5 谓词逻辑的推理 推理规则 命题逻辑推理的三条推理规则继续实用于谓词逻辑推理！（P、T、CP） 在前面介绍的推理演算过程中，如何消去量词或引入量词？ 下面介绍4条专门针对量词的推理规则。 推理规则 命题逻辑推理的三条推理规则继续实用于谓词逻辑推理！（P、T、CP） 在前面介绍的推理演算过程中，如何消去量词或引入量词？ 下面介绍4条专门针对量词的推理规则。 推理规则 量词的四条重要的推理规则： 推理规则 量词的四条重要的推理规则： 推理规则 推理规则 推理规则 推理规则 推理规则 推理规则 推理方法 1）直接证明法 2）CP规则证明法 3）反证法等。 例5-1：证明论断“人都是要死的，苏格拉底是人，所以苏格拉底是要死的”的正确性。 证： 设谓词 Man（x）：x是人； Mortal（x）：x是要死的； 客体 s：苏格拉底。则以上论断符号化为： (?x)[Man(x) ?Mortal(x)]∧Man(s) ?Mortal(s) 例5-1：证明论断“人都是要死的，苏格拉底是人，所以苏格拉底是要死的”的正确性。 证： 设谓词 Man（x）：x是人； Mortal（x）：x是要死的； 客体 s：苏格拉底。则以上论断符号化为： (?x)[Man(x) ?Mortal(x)]∧Man(s) ?Mortal(s) 证: (续)（直接证明法可采用如下步骤进行） 1)(?x)[Man(x) ?Mortal(x)] P 2) Man(s) ?Mortal(s) US 1) 3) Man(s) P 4) Mortal(s) T(2,3)I3 例： （p40 例2.19） 例5-2：试证 (?x)(C(x)?W(x)∧R(x))∧(?x)(C(x)∧Q(x)) ?（?x）(Q(x)∧R(x)) 分析： 前提： (?x)(C(x)?W(x）∧ R(x))， （?x）(C(x)∧Q(x)) 结论： （?x）(Q(x)∧R(x)) 思路：在使用前提时，尽量先使用?前提。因为?成立，即有一个特定的个体c存在，并且c对?前提中每个个体均成立，但反之不一定成立。 例5-2：试证 (?x)(C(x)?W(x)∧R(x))∧(?x)(C(x)∧Q(x)) ?（?x）(Q(x)∧R(x)) 分析： 前提： (?x)(C(x)?W(x）∧ R(x))， （?x）(C(x)∧Q(x)) 结论： （?x）(Q(x)∧R(x)) 思路：在使用前提时，尽量先使用?前提。因为?成立，即有一个特定的个体c存在，并且c对?前提中每个个体均成立，但反之不一定成立。 例5-2：试证 (?x)(C(x)?W(x)∧R(x))∧(?x)(C(x)∧Q(x)) ?（?x）(Q(x)∧R(x)) 分析： 前提： (?x)(C(x)?W(x）∧ R(x))， （?x）(C(x)∧Q(x)) 结论： （?x）(Q(x)∧R(x)) 思路：在使用前提时，尽量先使用?前提。因为?成立，即有一个特定的个体c存在，并且c对?前提中每个个体均成立，但反之不一定成立。 证明： （1） （?x）(C(x)∧Q(x)) P （2） C(a) ∧ Q(a) ES (1) (注：此处a是特定的） （3） (?x)(C(x)?W(x）∧ R(x)) P （4） C(a)?W(a）∧ R(a)) US （3） （注：因（3）中?“任意”的，所以此处可以使用 (2)中的a。若（3）中是? ，则此处不可用a。） （5） C(a) T (2)I2 证明： （1） （?x）(C(x)∧Q(x)) P （2） C(a) ∧ Q(a) ES (1) (注：此处a是特定的） （3） (?x)(C(x)?W(x）∧ R(x)) P （4） C(a)?W(a）∧ R(a)) US （3） （注：因（3）中?“任意”的，所以此处可以使用 (2)中的a。若（3）中是? ，则此处不可用a。） （5） C(a) T (2)I2 证明： （1） （?x）(C(x)∧Q