谓词逻辑的推理演算

《谓词逻辑的推理演算》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4讲谓词逻辑的推理演算主讲人吴杰中国地质大学计算机学院1主要内容1推理定律2推理规则3推理方法21.由命题逻辑推理定律推广而来的谓词逻辑推理定律利用代入定理将命题逻辑中的推理定律推广而得到谓词逻辑中的推理定律。如在命题逻辑中有公式：αβα，ααβ，可推广而得：xA(x)yB(y)xA(x)，xA(x)xA(x)yB(y)等等。4.1推理定律32.由基本等值式生成的推理定律前面给出的等值式中的每个等值式可生成两个推理定律。例如，xA(x)xA(x)，xA(x)xA(x)和

2、xA(x)xA(x),xA(x)xA(x)等等。4.1推理定律43.一些特有的重要推理定律（1）xA(x)xB(x)x(A(x)B(x))（2）x(A(x)B(x))xA(x)xB(x)（3）x(A(x)B(x))xA(x)xB(x)（4）x(A(x)B(x))xA(x)xB(x)等等。4.1推理定律51.全称量词消去规则（US）（1）xA(x)A(y)或（2）xA(x)A(c)2.全称量词引入规则（UG）A(y)xA(x)3.存在量词消去

3、规则（ES）xA(x)A(c)4.存在量词引入规则（EG）A(c)xA(x)4.2推理规则6直接证法前提+推理规则+推理定律结论间接证法（反证法、CP规则）反证法结论的否定+前提+推理规则+推理定律矛盾CP规则（条件：结论为蕴含式）蕴含的前件+前提+推理规则+推理定律蕴含的后件4.3推理方法7示例1任何人如果违反交通规则，就要被处罚；总有些人违反了交通规则。因此有些人被处罚。（使用全总个体域）令P(x)：x是人Q(x)：x违反交通规则R(x)：x被处罚则：前提：x((P(x)∧Q(x))→R(x)),

4、x(P(x)∧Q(x))结论：x(P(x)∧R(x))推理形式：x((P(x)∧Q(x))→R(x)),x(P(x)∧Q(x))x(P(x)∧R(x))4.3推理方法8证明(1)x(P(x)∧Q(x))P(2)P(a)∧Q(a)ES,(1)(3)P(a)T,I,(2)(4)x((P(x)∧Q(x))→R(x))P(5)(P(a)∧Q(a))→R(a)US,(4)(6)R(a)T,I,(2),(5)(7)P(a)∧R(a)T,I,(3),(6)(8)x(P(x)∧R(x))EG,(7)4.3推理方法9示例

5、2x(P(x)Q(x))xP(x)xQ(x)证明用反证法(1)(xP(x)xQ(x))P(附加)(2)xP(x)xQ(x)R,E,(1)(3)xP(x)T,I,(2)(4)P(a)ES,(3)(5)xQ(x)T,I,(2)(6)Q(a)US,(5)(7)x(P(x)Q(x))P(8)P(a)Q(a)US,(7)(9)Q(a)T,I,(4),(8)(10)Q(a)Q(a)T,I,(6),(9),矛盾因此，假设不成立，原推理形式正确。4.3推理方法10示例3x(P(x)

6、→Q(x))xP(x)→xQ(x)证明用CP规则(1)xP(x)P(附加)(2)P(a)US,(1)(3)x(P(x)→Q(x))P(4)P(a)→Q(a)US,(3)(5)Q(a)T,I,(2),(4)(6)xQ(x)UG,(5)(7)xP(x)→xQ(x)CP4.3推理方法11示例4每个科学工作者都是勤奋的，每个既勤奋又聪明的人在他的事业中都将获得成功，王大志是科学工作者并且是聪明的，所以王大志在他的事业中将获得成功。设个体域为全总个体域。令M(x)：x是人；K(x)：x是科学工作者；Q(x)：x勤

7、奋；T(x)：x聪明；S(x)：x将获得成功；a：王大志，则：前提：x((M(x)K(x))Q(x)),x((M(x)Q(x)T(x))S(x)),M(a)K(a)T(a)结论：S(a)推理形式：x((M(x)K(x))Q(x)),x((M(x)Q(x)T(x))S(x)),M(a)K(a)T(a)S(a)4.3推理方法12证明1）x((M(x)K(x))Q(x))P2）(M(a)K(a))Q(a)US,(1)3）M(a)K(a)T(a)P4）M(a)K(a)T,I

8、,(3)5）Q(a)T,I,(2),(4)6）M(a)T(a)T,I,(3)7）M(a)Q(a)T(a)T,I,(5),(6)8）x((M(x)Q(x)T(x))S(x))P9）(M(a)Q(a)T(a))S(a)US,(8)10）S(a)T,I,(7),(9)4.3推理方法13