数理逻辑与集合论：5-2 谓词逻辑的等值和推理演算

1、第5章 谓词逻辑的等值和推理演算 5.1 否定型等值式5.2 量词分配等值式5.3 范式5.4 基本的推理公式5.5 推理演算5.6 谓词逻辑的归结推理法与量词有关的公式n ( x)P(x) = ( x)P(x) ( x)P(x) = ( x)P(x)n ( x)(P(x)q) = ( x)P(x)q ( x)(P(x)q) = ( x)P(x) qn ( x)(P(x) q) = ( x)P(x) q ( x)(q P(x) = q ( x)P(x)n ( x)(P(x)Q(x) = ( x)P(x)( x)Q(x) ( x)(P(x)Q(x) = ( x)P(x)( x)Q(x)n ( x

2、)P(x) ( x)Q(x) ( x)(P(x) Q(x) ( x)(P(x)Q(x) ( x)P(x)( x) Q(x)5.4 基本的推理公式n基本的推理公式n ( x)P(x) ( x)Q(x) ( x)(P(x) Q(x) ( x)(P(x)Q(x) ( x)P(x)( x) Q(x)n( x)(P(x)Q(x) ( x)P(x)( x)Q(x) n( x)(P(x)Q(x) ( x)P(x)( x)Q(x)n( x)(P(x) Q(x) ( x)P(x) ( x)Q(x) n( x)(P(x) Q(x) ( x)P(x) ( x)Q(x)n( x)(P(x)Q(x) ( x)(Q(x)

3、R(x) ( x)P(x)( x)R(x) n( x)(P(x)Q(x) P(a) Q(a) ( x)(P(x)Q(x) ( x)P(x)( x)Q(x) n解释性的证明n设解释设解释I I下有下有 ( x)(P(x)Q(x) =T 则有则有 x个体域个体域D，使，使 P(x)Q(x) =T 这必能保证这必能保证 ( x)P(x)=T 时有时有 ( x)Q(x)=T 从而有从而有 ( x)P(x)( x)Q(x) =T 在解释在解释I下下 ( x)(P(x)Q(x) ( x)P(x)( x)Q(x) 但反之，不成立但反之，不成立基本的推理公式n 基本的推理公式n( x)( y)P(x, y)

4、( x)( y)(P(x,y)n( x)( y)P(x, y) ( y) ( x)(P(x,y)n解释性的证明 设一解释设一解释I I下有下有 ( x)( y)P(x, y) =T 于是有于是有x0个体域个体域D，使对，使对 y D,都有都有 P(x0,y) =T 从而有从而有 yD, 都有一个都有一个x（均选为（均选为x0）,使使 P(x, y)=T， 也即也即 ( y)( x)P(x,y)=T ( x)( y)P(x, y) ( y)( x)(P(x,y)5.5 推理演算n推理演算n利用谓词公式间的各种等价关系和蕴涵关系，利用谓词公式间的各种等价关系和蕴涵关系，通过一些推理规则，推出另一些

5、谓词演算公式通过一些推理规则，推出另一些谓词演算公式来，这就是谓词演算的推演过程。来，这就是谓词演算的推演过程。n 在推理过程中，除了可以使用命题逻辑中的推理规则外，还增加了下面4条关于量词的推理规则。nUI 规则规则nUG规则规则 nEI 规则规则 nEG规则规则 推理规则 (1)(1)前提引入规则前提引入规则 (2)(2)结论引入规则结论引入规则(3)(3)置换规则置换规则 (4)(4)假言推理规则假言推理规则 (AB) A B (5)(5)附加规则附加规则 A (A B)(6)(6)化简规则化简规则 (A B) A (7)(7)拒取式规则拒取式规则 (AB)B A(8)(8)假言三段论规

6、则假言三段论规则 (AB) (BC) (AC) (9)(9)析取三段论规则析取三段论规则 (A B)B A(10)(10)构造性二难推理规则构造性二难推理规则 (AB) (CD) (A C) (B D)(11)(11)合取引入规则合取引入规则 A, B A A B B有关量词的推理规则(12) 全称量词消去规则全称量词消去规则（UI规则）规则）n 规则说明：n若个体域中的所有个体若个体域中的所有个体都满足谓词都满足谓词A，则个体，则个体域中任一个体域中任一个体 c 也满足也满足谓词谓词A。)()(cAxxA(13) 全称量词引入规则全称量词引入规则（UG规则）规则） n 规则说明n如果能够证明

7、对论域中如果能够证明对论域中任一个体任一个体x断言断言A(x)都都成立，则有结论成立，则有结论xA(x)成立成立。)()(xxAyA有关量词的推理规则(14) 存在量词引入规则存在量词引入规则（EG规则规则） n 规则说明n对于论域中的某个个对于论域中的某个个体体c，如果，如果A(c)为真，为真，则必定可以得到结论则必定可以得到结论xA(x)为真。为真。)()(xxAcA (15) 存在量词消去规则存在量词消去规则 （EI规则规则）n 规则说明n c是使是使A为真的论域中特定的为真的论域中特定的个体（不是任意个体）个体（不是任意个体）n若对于论域中的若对于论域中的某些个体某些个体c和和d分别使

8、分别使xA(x)和和xB(x)都都是真，则是真，则n可断定可断定A(c)B(d)必定为真，必定为真，n但不能断定但不能断定A(c)B(c)为真为真)()(cAxxA 使用推理规则的推理演算举例 例1 证明: “金属都是导电体,铜是金属，铜是导电体 。” 令 F(x): x是金属, G(x): x是导电体, a: 铜 前提：前提： x(F(x)G(x)，F(a) 结论：结论：G(a) 证明：证明： F(a) 前提引入前提引入 x(F(x)G(x) 前提引入前提引入 F(a)G(a) UI G(a) 假言推理假言推理注意：使用注意：使用UI时，用时，用a取代取代x .使用推理规则的推理演算举例例例

9、2 乌鸦都不是白色的乌鸦都不是白色的. 北京鸭是白色的北京鸭是白色的. 因此，北京鸭不是乌鸦因此，北京鸭不是乌鸦. 解：令解：令F(x): x是乌鸦是乌鸦, G(x): x是北京鸭是北京鸭, H(x): x是白色的是白色的前提：前提： x(F(x)H(x)， x(G(x)H(x)结论：结论： x(G(x)F(x)使用推理规则的推理演算举例前提：前提： x(F(x)H(x)， x(G(x)H(x)结论：结论： x(G(x)F(x)证明：证明： x(F(x)H(x) 前提引入前提引入 F(y)H(y) UI x(G(x)H(x) 前提引入前提引入 G(y)H(y) UI H(y)F(y) 置换置换

10、 G(y)F(y) 假言三段论假言三段论 x(G(x)F(x) UG使用推理规则的推理演算举例前提前提: ( x)P(x)( x)(P(x)Q(x)R(x)， ( x)P(x) 结论：结论： ( x)( y)(R(x)R(y)证明：证明： ( x)P(x)( x)(P(x)Q(x)R(x) 前提引入前提引入 ( x)P(x) 前提引入前提引入 ( x)(P(x)Q(x)R(x) 分离分离 P(c) EI (P(c)Q(c)R(c) UI P(c)Q(c) 附加规则附加规则 R(c) 分离分离 ( x)R(x) EG ( y)R(y) EG ( x)R(x)( y)R(y) 合取规合取规则则 (

11、 x)( y)(R(x)R(y) 置换置换使用推理规则注意例例4 构造下述推理证明构造下述推理证明 前提：前提： x(F(x)G(x)， xF(x) 结论：结论： xG(x)证明：证明： xF(x) 前提引入前提引入 x(F(x)G(x) 前提引入前提引入 F(c) EI F(c)G(c) UI G(c) 假言推理假言推理 xG(x) EG注意：必须先消存在量词注意：必须先消存在量词 F(c)G(c) UI F(c) EI证明: ( x)(H(x)M(x)，( x)H(x)( x)M(x)n 证明：证明： ( x)H(x) 前提引入前提引入 H(c) EI ( x)(H(x)M(x) 前提引入

12、前提引入 H(c)M(c) UI M(c) 分离分离 ( x)M(x) EG n 若把若把,写在写在,的后面，得到如下的推理：的后面，得到如下的推理： ( x)(H(x)M(x) 前提引入前提引入 H(c)M(c) UI ( x)H(x) 前提引入前提引入 H(c) EI M(c) 分离分离 ( x)M(x) EG n 这个推理在逻辑上是错误的。这个推理在逻辑上是错误的。n因为因为 中的中的c为个体域中一为个体域中一个个体，个个体，n用用EI规则由规则由 推到推到 不能不能选择选择 中的中的c，因为它要选，因为它要选的个体和的个体和 中的个体中的个体c不一不一定是同一个个体，定是同一个个体，n

13、故推理是错误的。故推理是错误的。5.6 谓词逻辑的归结推理法n 归结证明法的出发点n证明证明A B是定理，等价于证明是定理，等价于证明A B=G是是矛盾式矛盾式n 归结证明过程n建立建立子句集子句集Sn将将G中的全称量词省略，并将中的全称量词省略，并将G中的合取词中的合取词用用“，”表示，得表示，得子句集子句集Sn如：如： ( x)(P(x)( y)(D(y)L(x,y)的子句集的子句集S为为 P(a), D(y) L(a,y)n对对S作归结作归结n子句：子句：P(x) Q(x)， P(a) R(x) 作归结，得作归结，得 归结式：归结式：Q (a) R(a) 并将此归结式仍放入并将此归结式仍放入S中，重复此过程中，重复此过程n直至归结出空子句直至归结出空子句，证明结束。，证明结束。归结法证明举例 A1= ( x)(P(x)( y)(D(y)L(x,y) A2= ( x