离散数学2.7.ppt

1、2-7谓词演算的推理理论,消去和添加量词规则：,US(全称指定规则)：(x)G(x)G(c) ES(存在指定规则)：(x)G(x)G(c) UG(全称推广规则)：G(y)(x)G(x) EG(存在推广规则)：G(c)(x)G(x),US全称指定规则，书写形式： (x)G(x)G(c) 成立的条件是： c为任意的个体常量。,谓词演算的推理理论,谓词演算的推理理论,ES(存在指定规则) ，书写形式： (x)G(x)G(c) 成立的条件是： c是使G(x)为真的特定的个体常量。 c不在前提中或者居先推导公式中出现或自由出现，换句话说，此c是在该推导之前从未使用过的。,谓词演算的推理理论,例：令个体域

2、为全体自然数，O(x):x是奇数，E(x):x为偶数，试考察从已知前提 (x)O(x)和(x)E(x)出发的下列推理。 （1） (x)O(x) P （2） O(c) ES(1) （3） (x)E(x) P （4） E(c) ES(3) （5） O(c) E(c) T(2)(4)I,谓词演算的推理理论,UG全称推广规则 ，书写形式： G(x)(x)G(x) 成立的条件和限制是： x是G(x)中自由出现的个体变量。且x取遍整个个体域时，都有G(x)为真。,谓词演算的推理理论,EG存在推广规则 ，书写形式： G(c)(x)G(x) 成立的条件和限制是： c是使G(c)为真的特定的个体常量。,谓词演算

3、的推理理论,在推导的过程中，可以引用命题演算中的规则P、规则T、规则CP 。 为了在推导过程中消去量词，可以引用规则US和规则ES来消去量词。 当所要求的结论可能被定量时，此时可引用规则UG和规则EG将其量词加入。 证明时可采用如命题演算中的直接证明方法和间接证明方法。 在推导过程中，对消去量词的公式或公式中没含量词的子公式，完全可以引用命题演算中的基本等价公式和基本蕴涵公式。,谓词演算的推理理论,在推导过程中，对含有量词的公式可以引用谓词中的基本等价公式和基本蕴涵公式。 在推导过程中，如既要使用规则US又要使用规则ES消去公式中的量词(只要有可能，我们总是先使用规则ES，再使用规则US)。然

4、后再使用命题演算中的推理规则，最后使用规则UG或规则EG引入量词，得到所要的结论。 如一个变量是用规则ES消去量词,对该变量在添加量词时,则只能使用规则EG,而不能使用规则UG;如使用规则US消去量词,对该变量在添加量词时,则可使用规则EG和规则UG。,谓词演算的推理理论,如有两个含有存在量词的公式，当用规则ES消去量词时，不能选用同样的一个常量符号来取代两个公式中的变元，而应用不同的常量符号来取代它们。 在用规则US和规则ES消去量词时，此量词必须位于整个公式的最前端。 在添加的量词(x)、(x)时，所选用的x不能在公式G(c)中以任何约束出现。,谓词演算的推理理论,推理一般根据US或UG规

5、则，消除量词后，才能对谓词公式进行蕴含或等价推证。在做了适当的推演后，在应用ES，EG规则恢复约束关系，以完成带量词公式的逻辑推证,解：设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(x)M(x)US(1) (3)H(s)P (4)M(s)T(2),(3),证明：(1)(x)(H(x)M(x)P (2)H(s)M(s)US(1) (3)H(s)P (4)M(s)T(2),(3),(2)错了！ 正确的为：,谓

6、词演算的推理理论,谓词演算的推理理论,请看推导： (1)(x)(P(x)Q(x) P (2)(P(x)Q(x) US(1) (3)(x)P(x) P (4)P(x)ES (5)Q(x)T(2),(4),I (6)(x)Q(x) EG(5) 错误。A:使用了US ES ,该用特定个体变量没有用。,例：证明(x)(P(x)Q(x)，(x)P(x)(x)Q(x),谓词演算的推理理论,请看推导： (1)(x)(P(x)Q(x) P (2)(P(c)Q(c)US(1) (3)(x)P(x)P (4)P(c)ES (5)Q(c)T(2),(4),I (6)(x)Q(x)EG(5),US和ES的使用顺序反了

7、,谓词演算的推理理论,正确地推导如下： (1)(x)P(x)P (2)P(c)ES(1) (3)(x)(P(x)Q(x) P (4)(P(c)Q(c)US(3) (5)Q(c)T(2),(4),I (6)(x)Q(x)EG(5),谓词演算的推理理论,证明：1)(x)(P(x)Q(x)P 2)(P(c)Q(c)ES(1) 3)P(c)T(2),I 4)Q(c)T(2),I 5)(x)P(x) EG(3),I 6)(x)Q(x) EG(4),I 7)(x)P(x)(x)Q(x)T(5),(6),I,例：证明(x)(P(x)Q(x)(x)P(x)(x)Q(x),谓词演算的推理理论,1)(x)P(x)

8、(x)Q(x) P 2)(x)P(x) T(1) 3)P(c)ES(2) 4)(x)Q(x) T(1) 5)Q(c)ES(4) 6)(P(c)Q(c)T(3),(4) 7)(x)(P(x)Q(x)EG(6),请看上述推论的逆推导：,谓词演算的推理理论,正确地推导如下： 1)(x)P(x)(x)Q(x) P 2)(x)P(x) T(1) 3)P(c) ES(2) 4)(x)Q(x) T(1) 5)Q(b) ES(4) 6)(P(c)Q(b) T(3),(4) 7)(y) (P(c)Q(y) EG(6) 8)(x)(y)(P(x)Q(y) EG(7),谓词演算的推理理论,例：证明下述论断的正确性：

9、 所有的哺乳动物都是脊椎动物； 并非所有的哺乳动物都是胎生动物； 故有些脊椎动物不是胎生的。,谓词演算的推理理论,解：设谓词如下： P(x)：x是哺乳动物； Q(x)：x是脊椎动物； R(x)：x是胎生动物。 则有：(x)(P(x)Q(x),(x)(P(x)R(x) (x)(Q(x)R(x),谓词演算的推理理论,(x)(P(x)R(x)P (P(x)R(x)US(1) (P(x)R(x)T(2)，E (P(x)R(x)T(3),E P(x)T(4),I R(x)T(4),I,请看下面推导：,谓词演算的推理理论,续： (x)(P(x)Q(x)P P(x)Q(x)US(7) Q(x)T(5),(8

10、),I Q(x)R(x)T(6),(9),I (x)(Q(x)R(x)EG(10),谓词演算的推理理论,(x)(P(x)R(x)P (x) (P(x)R(x) T(1),E (P(c) R(c) ES(2) (P(c)R(c)T(3),E P(c)T(4),I,证明：,谓词演算的推理理论,续： R(c)T(4),I (x)(P(x)Q(x)P P(c)Q(c)US(7) Q(c)T(5),8),I Q(c)R(c)T(6),(9),I (x)(Q(x)R(x)EG(10),谓词演算的推理理论,证明(采用反证法)： (x)P(x)(x)Q(x)P(附加前提) (x)P(x)(x)Q(x)T(1)

11、,E (x)P(x)T(2),I (x)Q(x)T(2),I (x)P(x)T(3),E P(c)ES(5)(7),例：证明(x)(P(x)Q(x)(x)P(x)(x)Q(x),谓词演算的推理理论,续： (x)Q(x)T(4),E Q(c)US(7) P(c)Q(c)T(6),(8),I (P(c)Q(c)T(9),E (x)(P(x)Q(x)P (P(c)Q(c)US(11) (P(c)Q(c)(P(c)Q(c)T(10),谓词演算的推理理论,例：证明下列论断的正确性： 有些学生相信所有的教师；任何一个学生都不相信骗子；所以，教师都不是骗子。 解：设谓词如下： S(x)：x是学生T(x)：x

12、是教师 P(x)：x是骗子L(x,y)：x相信y 则可符号化为： 前提：(x)(S(x)(y)(T(y)L(x,y)， (x)(S(x)(y)(P(y)L(x,y)。 结论：(x)(T(x)P(x) 即证明：(x)(S(x)(y)(T(y)L(x,y)， (x)(S(x)(y)(P(y)L(x,y) (x)(T(x)P(x),谓词演算的推理理论,证明： (x)(S(x)(y)(T(y)L(x,y)P S(c)(y)(T(y)L(c,y)ES(1) S(c)T(2),I (y)(T(y)L(c,y)T(2),I T(b)L(c,b)US(4) (x)(y)(S(x)P(y)L(x,y)P,谓词演

13、算的推理理论,续： (y)(S(c)P(y)L(c,y)US(6) (S(c)P(b)L(c,b) US(7) S(c)(P(b)L(c,b) T(8),E P(b)L(c,b) T(3),(8),E L(c,b)P(b) T(10),E T(b)P(b) T(5),(11),E (x)(T(x)P(x) US(12),谓词演算的推理理论,1.采用反证法： (x)(y)(P(y)R(x,y)(y)(Q(y)R(x,y) P (x)(y)(P(y)R(x,y)(y)(Q(y)R(x,y) T(1),E (y)(P(y)R(c,y)(y)(Q(y)R(c,y) ES(2) (y)(P(y)R(c,

14、y)(y)(Q(y)R(c,y) T(3),E (y)(P(y)R(c,y)T(4),I,例：证明(x)(P(x)Q(x)(x)(y)(P(y)R(x,y)(y)(Q(y)R(x,y)。,谓词演算的推理理论,续： 6) P(b)R(c,b)ES(5) 7) P(b)T(6),I 8) (x)(P(x)Q(x)P 9) P(b)Q(b)US(8) 10)Q(b)T(7),(9),I,谓词演算的推理理论,续： R(c,b)T(6),I (Q(b)R(c,b)T(10),(11)I (y)(Q(y)R(c,y)T(4),E (y)(Q(y)R(c,y)T(4),E (Q(b)R(c,b)US(14)

15、 (Q(b)R(c,b)(Q(b)R(c,b),CP,P78例题4,(1)(x)(y)(S(x,y) M(y)(z)(P(z)R(x,z) P (2)(y)(S(b,y) M(y)(z)(P(z)R(b,z) US(1) (3) (z)P(z) P(附加前提） (4) (z) P(z) T(3)E (5) P(a) US(4) (6) P(a) R(b,a) T(5)I (7) (P(a) R(b,a) T(6)E (8) (z) (P(z) R(b,z) UG(7) (9) (z) (P(z) R(b,z) T(8)E (10) (y)(S(b,y) M(y) T(2)(9)I (11) (

16、y) (S(b,y) M(y) T(10)I,P78例题4,(12) (S(b,c) M(c) US(11) (13) S(b,c) M(c) T(12)E (14) S(b,c) - M(c) T(13)E (15) (y) (S(b,y) - M(y) ) UG(14) (16) (x)(y)(S(x,y) - M(y) UG(15) (17) (z)P(z) - (x)(y)(S(x,y) - M(y) CP,P79(3)c,解：设G(x):x是大学生。L(x):x是文科学生。 P(x):x是理工科学生。S(x):x是优秀生。c:小张 本题符号化为 (x)(G(x)-L(x) P(x),(x)(G(x) S(x), P(c),S(c)=G(c)-L(c) L(x) P(x) (L(x) P(x) (1) G(c) P(附加前提) (2) (x)(G(x)- (L(x) P(x) P (3) (G(c)- (L(c) P(c) U