离散数学课件：2-5 谓词演算的推理理论

1、谓词演算的推理规则谓词演算的推理规则(1) 全称指定规则全称指定规则 (US, Universal Specification)：(y为不在为不在P(x)中约束出中约束出现的任意个体变现的任意个体变元元)( x)P(x)(c为个体域中的任为个体域中的任意意一个一个个体常个体常量量) P(c)( x)P(x) P(y)(2) 全称推广规则全称推广规则 (UG, Universal Generalization)： ( x)P(x) P(x)谓词演算的推理规则谓词演算的推理规则五、谓词演算的推理理论五、谓词演算的推理理论(3) 存在指定规则存在指定规则 (ES, Existential Speci

2、fication)：( x)P(x)(c为为使使P为真的特定为真的特定的个体常的个体常量量) P(c)谓词演算的推理规则谓词演算的推理规则五、谓词演算的推理理论五、谓词演算的推理理论(4) 存在推广规则存在推广规则 (EG, Existential Generalization)： ( x)P(x) P(c)谓词演算的推理规则谓词演算的推理规则五、谓词演算的推理理论五、谓词演算的推理理论关于关于US, UG, ES, EG 的说明的说明&US, ES又叫又叫删除量词规则删除量词规则，其作用是在推导中，其作用是在推导中删除量词删除量词. 一旦删除了量词，就可用命题演算一旦删除了量词，就可

3、用命题演算的各种规则与方法进行推导的各种规则与方法进行推导.&UG, EG的作用则是在推导过程中的作用则是在推导过程中添加量词添加量词，使结论呈量化形式使结论呈量化形式.&全称量词与存在量词的基本差别也突出地体现全称量词与存在量词的基本差别也突出地体现在删除和添加量词规则使用中在删除和添加量词规则使用中.&例如，例如，ES中中P(c)的的c取特定值，而取特定值，而US中中P(c)的的c可取任意值可取任意值. 在在UG规则使用中更要注意规则使用中更要注意这方面的分析才不会引出错误的结论这方面的分析才不会引出错误的结论.五、谓词演算的推理理论五、谓词演算的推理理论证明苏格拉

4、底三段论：证明苏格拉底三段论：“ 所有的人都是所有的人都是要死的，苏格拉底是人，所以苏格拉底是要死的，苏格拉底是人，所以苏格拉底是要死的要死的.”证：证： 设设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(s)M(s)(3) H(s)(4) M(s)US(1)PT(2)(3), I五、谓词演算的推理理论五、谓词演算的推理理论构造下面推理的证明：构造下面推理的证明： 任何自然数都是整数，存在着自然数，所以任何自然数都是整数，存在着

5、自然数，所以存在着整数存在着整数. （这里，个体域为实数集（这里，个体域为实数集R.）证：证： 先将原子命题符号化：设先将原子命题符号化：设F(x): x是是自然数自然数. G(x): x为整数为整数. 则前提：则前提： ( x)(F(x)G(x), ( x)F(x);(1) ( x)F(x)P(2) F(c)(3)( x)(F(x)G(x) ES(1)P结论：结论：( x)G(x).(4) F(c)G(c) US(3)(5) G(c) T(2)(4), I(6) ( x)G(x)EG(5)五、谓词演算的推理理论五、谓词演算的推理理论例例2.5.2这样来证可以吗？这样来证可以吗？证：证：前提：

6、前提：( x)(F(x)G(x), ( x)F(x);(1) ( x)(F(x)G(x)P(2) F(c)G(c) (3) ( x)F(x)US(1)P结论：结论：( x)G(x).(4) F(c)ES(3)(5) G(c) T(2)(4), I(6) ( x)G(x)EG(5)&当既有含存在量词的前提，又有含全称量词的前提当既有含存在量词的前提，又有含全称量词的前提时，在证明中先引入带存在量词的前提时，在证明中先引入带存在量词的前提.&当有多个含存在量词的前提时，对每个前提使用当有多个含存在量词的前提时，对每个前提使用ES规则所引入的变元应与以前不同规则所引入的变元应与以前不

7、同. 五、谓词演算的推理理论五、谓词演算的推理理论构造下面推理的证明：构造下面推理的证明：证：证：前提：前提：( x)(F(x)G(x), ( x)(F(x) H(x);(1) ( x)(F(x) H(x)P(2) F(c) H(c)(3)( x)(F(x)G(x) ES(1)P结论：结论：( x)(G(x) H(x).(4) F(c)G(c) US(3)(7) H(c) T(2), I(8) G(c) H(c)T(6)(7), I（注意注意：在证明序列中先引入带存在量词的前提：在证明序列中先引入带存在量词的前提.）(5) F(c) T(2), I(6) G(c) T(4)(5), I(9)

8、( x)(G(x) H(x)EG(8)五、谓词演算的推理理论五、谓词演算的推理理论构造下面推理的证明构造下面推理的证明 (个体域为实数集合个体域为实数集合) ： 不存在能表示成分数的无理数；有理数都能不存在能表示成分数的无理数；有理数都能表示成分数表示成分数. 因此，有理数都不是无理数因此，有理数都不是无理数.证：证： 先将原子命题符号化：设先将原子命题符号化：设F(x): x是是无理数无理数. G(x): x为有理数为有理数. H(x): x能表示成分数能表示成分数. 则前提：则前提： ( x)(F(x) H(x), ( x)(G(x)H(x); (1) ( x)(F(x) H(x) P(2

9、) ( x)( F(x)H(x)(4) H(y) F(y)T(1), EUS(2)结论：结论：( x)(G(x) F(x).(5)( x)(G(x)H(x) PUS(5)T(6)(4), I(3) F(y)H(y)T(3), E(6)G(y)H(y) (7)G(y) F(y)(8)( x)(G(x) F(x)UG(7)注意：注意：不能直接对不能直接对 ( x)(F(x) H(x)使用使用ES规则规则.五、谓词演算的推理理论五、谓词演算的推理理论证明：证明：证：证：( x)(C(x) W(x) R(x) ( x)(C(x) Q(x) ( x)(Q(x) R(x).(1) ( x)(C(x) Q(

10、x) P(2) C(a) Q(a)(3) ( x)(C(x) W(x) R(x) ES(1)P(4) C(a) W(a) R(a) US(3)(7) Q(a) T(2), I(8) R(a) T(6), I(5) C(a) T(2), I(6) W(a) R(a) T(4)(5), I(9) Q(a) R(a)T(7)(8), I(10) ( x)(Q(x) R(x)EG(9)五、谓词演算的推理理论五、谓词演算的推理理论证明：证明：证：证：( x)(P(x) Q(x) ( x)P(x) ( x)Q(x).(1) ( x)P(x)P（附加前提）（附加前提）(2) P(y)(3) ( x)(P(x

11、) Q(x) US(1)P(4) P(y) Q(y)US(3)(7) ( x)P(x) ( x)Q(x)CP(5) Q(y)T(2)(4), I(6) ( x)Q(x)UG(5)（使用（使用CP规则规则）五、谓词演算的推理理论五、谓词演算的推理理论即谓词演算即谓词演算的蕴含式的蕴含式(3)证明：证明：证法一：证法一：( x)(P(x) Q(x) ( x)P(x) ( x)Q(x).(1) ( x)P(x) P(附加前提附加前提)(2) ( x) P(x)(3) P(c)T(1), EES(2)(4) ( x)(P(x) Q(x) P(8) ( x)P(x) ( x)Q(x) CP(6) Q(c

12、)US(4)(7) ( x)Q(x)T(3)(5), I注意到注意到( x)P(x) ( x)Q(x) ( x)P(x) ( x)Q(x) ，下面，下面使用使用CP规则规则来证明来证明.(5) P(c) Q(c)EG(6)五、谓词演算的推理理论五、谓词演算的推理理论证明：证明：证法二：证法二：( x)(P(x) Q(x) ( x)P(x) ( x)Q(x).(1) ( x)P(x) ( x)Q(x)P(附加前提附加前提)(2) ( x)P(x)( x)Q(x)(3) ( x) P(x) ( x) Q(x) T(1), ET(2), E(4) ( x) P(x) T(3), I(7) Q(c) (6) ( x) Q(x)ES(4)(5) P(c) T(3)