离散数学第2章 谓词逻辑.ppt

第2章 谓词逻辑 2.5谓词逻辑的推理理论 在谓词演算中，C是一组前提A1，A2，…，An的有效结论，仍然定义为A1∧A2∧…∧An?C。命题演算推理中的P规则、T规则、置换规则、合取引入规则、所有的等价式和蕴含式在谓词推理中都是对的，都可以使用；另外，2.3节中介绍的谓词演算中的等价式与蕴含式也可以在谓词推理中使用。除此之外，还有以下的规则。 ⑴全称指定规则(US规则) (?x)A(x)?A(c) 此式成立的条件是： ①c是个体域中任一个体。 ②用c取代A(x)中x时，一定在x出现的所有地方进行取代。 全称指定规则说明：若个体域中的所有个体都满足谓词A，则个体域中任一个体c也满足谓词A。利用这个规则，可以从带有全称量词的前提中，推导出不带全称量词的特殊结论。它体现了在逻辑推理中由一般到特殊的推导方法。 ⑵全称推广规则(UG规则) A(y)?(?x)A(x) 此式成立的条件是： ① y是个体域中任一个体且对y，A(y)为真。 ② x是不出现在A(y)中的个体变元。 例如，个体域为实数集合R，G(x,y)表示xy，设A(y)?(?x)G(x,y)，显然A(y)满足条件①，一定能推出(?z)A(z)?(?z)(?x)G(x,z)?(?z)(?x)(xz)，这是一个真命题。若推成(?x)A(x)?(?x)(?x)G(x,x)?(?x)(?x)(xx)，就产生了错误，因为这是一个假命题。错误的原因是违背了条件②。 ⑶存在指定规则(ES规则) (?x)A(x)?A(c) 此式成立的条件是： ① c是个体域中的某个确定的个体，而不是个体变元。 ② c是不出现在A(x)中的个体。 存在指定规则说明，若个体域中存在一些个体满足谓 词A，则至少有某个确定的个体c满足谓词A。 例如，设个体域为整数集合I，A(x)表示x是奇数，B(x)表示x是偶数。 (?x)A(x)?A(c)，它表示：若存在一些整数是奇数，令c为3，则c是奇数。这个推理是对的。 (?x)B(x)?B(d)，它表示：若存在一些整数是偶数，令d为4，则d是偶数。这个推理也是对的。因此有下列推理成立： (?x)A(x)∧(?x)B(x)?A(c)∧B(d) 而下列推理是错误的： (?x)A(x)∧(?x)B(x)?A(c)∧B(c) (?x)A(x)∧(?x)B(x)?A(d)∧B(d) 因为3不能既是奇数，又是偶数；同样，4也不能既是奇数，又是偶数。错误的原因是违背了条件②。 ⑷存在推广规则(EG规则) A(c)?(?x)A(x) 此式成立的条件是： ① c是个体域中确定的个体。 ② x不能是出现在A(c)中的个体变元。 存在推广规则说明：对于个体域中的某个个体c满足谓词A，当然有(?x)A(x)。 【例2.19】证明苏格拉底论证：凡人要死。苏格拉底是人，苏格拉底要死。 设： H(x)：x是人。 M(x)：x是要死的。 s：苏格拉底。 本题要证明：(?x)(H(x)→M(x))∧H(s)?M(s) 证明： ⑴ (?x)(H(x)→M(x)) P ⑵ H(s)→M(s) US⑴ ⑶ H(s) P ⑷ M(s) T⑵⑶假言推理 【例2.20】证明(?x)(H(x)→M(x))，(?x)H(x)?(?x)M(x) 证明： ⑴ (?x)H(x) P ⑵ H(c) ES⑴ ⑶ (?x)(H(x)→M(x)) P ⑷ H(c)→M(