1.8 谓词演算的推理规则

1、第一章 数理逻辑 1.1 命题 1.2 重言式1.3 1.4 联结词的扩充与归约1.5 推理规则和证明方法1.6 谓词和量词1.7 谓词演算的永真公式1.8 谓词演算的推理规则1.8 谓词演算的推理规则1. 术语“A(x)对y是自由的”的意义2. 全称指定规则US3. 存在指定规则ES 4. 存在推广规则EG5. 全称推广规则UG6. 谓词演算推理规则应用举例7. 讨论题谓词演算的推理方法可视为命题演算推理方法的扩张。所以命题演算中的推理规则，如P规则、T规则和CP规则等亦可在谓词的推理理论中应用。在谓词演算的推理中，某些前提或结论会受到量词的限制，为了使用这些等价式和永真蕴含式，必须有消去或

2、添加量词的规则。术语A(x)对y是自由的的意义：在A(x)中x不出现在y或y的辖域中。考察下列(以x为主要个体变元的)谓词公式: B(x)yP(y)Q(x); C(x)yP(x,y)Q(x,y).则B(x)对y是自由的；而C(x)对y是不自由的。对B(x)可用代入规则，以y代x得到B(y)。而对C(x)则不能这样做，因代入后原P(x,y)中的x由自由变元变成了约束变元。1、术语A(x)对y是自由的的意义2 全称指定规则US全称指定规则 (Universal Specification)，记为US。 这个规则是删除全称量词。这里A(x)是谓词，y是论域中某个任意的客体。例如，设论域是全人类，A(

3、x)表示“x总是要死的”，那么xA(x)表示“所有人总是要死的”，若y表示“苏格拉底”，则可以得出结论A(y)，即“苏格拉底总是要死的”。条件：A(x)对于y必须是自由的反例：令论述域为整数集合；A(x)y(x-y=1)，则A(x)对y是不自由的。并且全称指定规则：xA(x)A(y)不是有效的！因为在这个指派下，xA(x)xy(x-y=1)为真而A(y)y(y-y=1)却为假。3 存在指定规则ES存在指定规则 (Existential Specification)，记为ES。 这个规则是删除存在量词。这里y是论域中的某些客体。条件: y不是任何给定的前提和居先的推导步骤中的自由变元, 也不是居

4、先的推导步骤中由于使用本规则而引入的表面自由变元。为满足这一条件, 通常使用规则ES时, 就选用前边未曾用过的字母作为公式中的y。 (举例如下页)例如，设xA(x)和xB(x)都真，则对某些c和某些d，可以断定A(c)B(d)为真，但却不能断定A(c)B(c)为真或A(d)B(d)为真。 A(x)对于y必须是自由的。反例：令论述域为整数集合；A(x)y(x-y=1)，则A(x)对y是不自由的。并且存在指定规则：xA(x)A(y)不是有效的！因为在这个指派下，xA(x)xy(x-y=1)为真，而A(y)y(y-y=1)却为假。4 存在推广规则EG存在推广规则 (Existential Gener

5、alization)，记为EG。这个规则是添加存在量词，其中y是论域中的一个客体。该规则是显然成立的。因若对论域中的某些客体y，A(y)为真，则在该论域中，xA(x)必为真。条件： A(y)对x是自由的。注：用x取代y时， A(y)不能已有x. （反例）5 全称推广规则UG全称推广规则 (Universal Generalization)，记为UG。这个规则是添加全称量词规则，其用意在于对命题量化。如果能够证明对论域中的每一个客体c断言A(x)成立，则应有xA(x)。使用本规则时，必须能够证明对论域中的每一个可能的x，A(x)为真。条件: 在推出A(x)的前提中，x都必须不是自由的；且A(x)

6、中的x不是由使用ES而引入的。 在居先的步骤中，如果使用US而求得之x是自由的，那么在后继步骤中，使用ES而引入的任何新变元都没有在A(x)中自由出现。条件的前半句是反映“中没有x的自由出现”这一要求，其作用是使A(x)对任意x都真；后半句的作用相同。条件是说在使用US引出自由变元x之后，不能让由使用ES而引入的新变元在A(x)中自由出现，如果有这种情况，就不能使用UG规则。这是因为ES引入的新变元是表面的自由变元，A(x)不是对新变元的一切值都可证明。观察下述推理过程: 第(4)步是错误的, P(c, d)不符合条件的后半句话, 不能引用UG。如果没有这个限制就会错误地证明: 而这一式前面已

7、指明它是不成立的。6 推理规则应用举例例1 证明苏格拉底三段论： x(M(x)D(x)M(s)D(s)，其中 M(x)：x是人。D(x)：x是要死的。s：苏格拉底。证: x(M(x)D(x) P M(s)D(s) US,T1 M(s) P D(s) T2,3,I例2 证明或否定以下论证。 (a) 每个大学教师都是知识分子，有些知识分子有怪脾气，所以有些大学教师有怪脾气。解 设T(x): x是大学教师，N(x): x是知识分子，H(x): x有怪脾气。 这个论证是 这个论证是无效的，要证明无效，只需找出一种解释说明上式， 即 非永真即可。 现取论述域为整数，T(x)：x=1，N(x)：x是奇数，

8、H(x)：x是质数。则x(T(x)N(x)是真， x(N(x)H(x)是真，但x(T(x)H(x)是假，故非永真式。这个论证是有效的，证明如下：解 设P(x)：x是松树，Q(x)：x是针叶树，R(x)：x是冬季落叶的树。 这个论证是 (b) 每一松树都是针叶树，每一冬季落叶的树都非针叶树，所以，每一冬季落叶的树都非松树。例3 证明：x(C(x)W(x)R(x) x(C(x)Q(x) x(Q(x)R(x)证: x (C(x)Q(x) P C(a)Q(a) ES,T1 x(C(x)W(x)R(x) P C(a)W(a)R(a) US,T3 C(a) T2,I W(a)R(a) T4,5,I Q(a

9、) T2,I R(a) T6,I Q(a)R(a) T7,8,I x(Q(x)R(x) T9,EG注意，推导中第、步和第、步的次序不能颠倒。例4 证明: x(P(x)Q(x) xP(x)xQ(x)证法1: 把(x)P(x)(x)Q(x)作为假设前提。 (xP(x)xQ(x) P xP(x) xQ(x) T1,E xP(x) T2,I x P(x) T3,E xQ(x) T2,I x Q(x) T5,E P(c) T4,ES Q(c) T6,US P(c)Q(c) T7,8,I (P(c)Q(c) T9,E x(P(x)Q(x) P P(c)Q(c) US (P(c)Q(c)(P(c)Q(c)

10、T10,12,矛盾例4 证明: x(P(x)Q(x) xP(x)xQ(x)证法2: 原式可改写为 x(P(x)Q(x) xP(x)xQ(x)可用CP规则转化为证明: x(P(x)Q(x)xP(x) xQ(x) x(P(x) P(附加前提) xP(x) T1,E P(c) T2,ES x(P(x)Q(x) P P(c)Q(c) T4,US Q(c) T3,5,I xQ(x) EG例5 每个喜欢步行的人不喜欢坐汽车。每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车，因而有的人不喜欢步行。(论述域是人类)7 讨论题例 任何人违反交通规则，就要受到罚款。因此，如果没有罚款，则没有人违反交通规

11、则。解：设S(x,y): “x违反y。” x的论域为“人类” M(y): “y是交通规则。” P(z): “z是罚款。” R(x,z): “x受到z。”故前提是： x(y(S(x,y)M(y)z(P(z)R(x,z)结论是：zP(z)xy(S(x,y)M(y)注：xy(S(x,y)M(y)表示，“任意x违反了任何y，则y不是交通规则”。即没有人违反交通规则。提出的问题：下面的证明是否严格？下证x (y(S(x,y)M(y)z(P(z)R(x,z) zP(z)xy(S(x,y)M(y) x (y(S(x,y)M(y)z(P(z)R(x,z) P y(S(b,y)M(y)z(P(z)R(b,z) US,T1 zP(z) P(附加前提) zP(z) T3,E P(a) T4,US P(a)R(b,a)