1西安电子科技大学计算机学院 毛立强西安电子科技大学计算机学院 毛立强 lqmaomail.xidian.edu.cn西安电子科技大学计算机学院西安电子科技大学计算机学院西安电子科技大学计算机学院西安电子科技大学计算机学院离 散 数 学离 散 数 学离 散 数 学离 散 数 学主讲 毛立强主讲 毛立强主讲 毛立强主讲 毛立强2西安电子科技大学计算机学院 毛立强西安电子科技大学计算机学院 毛立强 lqmaomail.xidian.edu.cn谓词逻辑?回顾?谓词公式的永真公式3西安电子科技大学计算机学院 毛立强西安电子科技大学计算机学院 毛立强 lqmaomail.xidian.edu.cn谓词逻辑的推理规则?谓词逻辑中的推理规则?推理举例4西安电子科技大学计算机学院 毛立强西安电子科技大学计算机学院 毛立强 lqmaomail.xidian.edu.cn推理规则?命题逻辑中所有推理规则在谓词逻辑中都适用。?谓词逻辑中所有永真蕴含式和等价式也可使用。?全称指定规则（Universal Specification,US）：)()( cPxxP P是谓词，c是论述域中任意个体。意义是，全称量词可以删 除。5西安电子科技大学计算机学院 毛立强西安电子科技大学计算机学院 毛立强 lqmaomail.xidian.edu.cn推理规则?存在指定规则（Existential Specification,ES）：)()( cPxxP P是谓词，c是论述域中某些个体，不是任意的。6西安电子科技大学计算机学院 毛立强西安电子科技大学计算机学院 毛立强 lqmaomail.xidian.edu.cn推理规则?全称推广规则（Universal Generalization,UG）：)()( xxPxP 如果能够证明对于论述域中每一个个体x使P(x)都成立， 则可以得到上面结论。7西安电子科技大学计算机学院 毛立强西安电子科技大学计算机学院 毛立强 lqmaomail.xidian.edu.cn推理规则?存在推广规则（Existential Generalization,EG）：)()( xxPcP P是谓词，c是论述域中一个个体。意义是，对于论述域中 某些个体使P(x)为真，则可得上面结论。8西安电子科技大学计算机学院 毛立强西安电子科技大学计算机学院 毛立强 lqmaomail.xidian.edu.cn推理举例例1：苏格拉底三段论： 设H(x)：x是一个人，M(x)：x是要死的，s：苏格拉底。 则表示为：)()()()(sMsHxMxHxPxMxHx)()() 1 (USTsMsH, 1)()()2(证明：PsH)()3(ITsM3 , 2)()4(9西安电子科技大学计算机学院 毛立强西安电子科技大学计算机学院 毛立强 lqmaomail.xidian.edu.cn推理举例例2：证明： )()()()()()()(xRxQxxQxCxxRxWxCxPxQxCx)()() 1 ( ESTaQaC, 1)()()2( PxRxWxCx)()()()3( USTaRaWaC, 3)()()()4( ITaC2)()5( ITaRaW5 , 4)()()6( ITaR6)()7( ITaQ2)()8( ITaRaQ8 , 7)()()9( EGTxRxQx, 9)()()10(1)(2)和(3)(4)次序 不能颠倒10西安电子科技大学计算机学院 毛立强西安电子科技大学计算机学院 毛立强 lqmaomail.xidian.edu.cn推理举例例3：证明：)()()()(xxQxxPxQxPx方法1：反证法PxxQxxP)()() 1 ( ETxxQxxP1)()()2( ITxxP2)() 3( ETxPx3)()4( ITxxQ2)()5( ETxQx5)()6( ESTcP, 4)()7( USTcQ, 6)()8( ITcQcP8 , 7)()()9( ETcQcP9)()()10( PxQxPx)()()11( USTcQcP,11)()()12( 矛盾ITcQcPcQcP,12,10)()()()()13(7)(8) 次序 不能颠倒11西安电子科技大学计算机学院 毛立强西安电子科技大学计算机学院 毛立强 lqmaomail.xidian.edu.cn推理举例例3：证明：)()()()(xxQxxPxQxPx方法2：CP规则：原题变为)()()()(xxQxxPxQxPxPxxP)() 1 ( ETxPx1)()2( ESTcP, 2)() 3(ITcQ5 , 3)()6(PxQxPx)()()4( USTcQcP, 4)()()5(EGTxxQ, 6)()7( CPxxQxxP)()()8(2)(3)和(4)(5) 次序不能颠倒12西安电子科技大学计算机学院 毛立强西安电子科技大学计算机学院 毛立强 lqmaomail.xidian.edu.cn例4 符号化以下语句，并推证结论的有效性。“有些学生相信所有的老师，任何一个学生都不相信骗子， 所以教师都不是骗子。”解解: 设论述域为全总个体域，S(x)：x是学生，T(x)：x是老 师，P(x)：x是骗子，L(x,y)：x相信y。将前提和结论符号化为： ),()()(yxLyTyxSx),()()(yxLyPyxSx)()(xPxTx13西安电子科技大学计算机学院 毛立强西安电子科技大学计算机学院 毛立强 lqmaomail.xidian.edu.cn),()()(yxLyTyxSx),()()(yxLyPyxSx)()(xPxTxPyxLyTyxSx),()()(1 ESTyaLyTyaS, 1),()()(2 ITaS, 2)(3 ITyaLyTy, 2),()(4 USTbaLbT, 4),()(5 PyxLyPyxSx),()()(6 USTyaLyPyaS, 6),()()(7 ITyaLyPy, 7 , 3),()(8 USTbaLbP, 8),()(9 ETbPbaL, 9)(),(10 ITbPbT,10, 5)()(11 UGTxPxTx,11)()(1214西安电子科技大学计算机学院 毛立强西安电子科技大学计算机学院 毛立强 lqmaomail.xidian.edu.cn推理举例例5：证明或否定下面结论：每个大学教师都是知识分子，有些知识分子有怪 脾气，所以有些大学教师有怪脾气。解：论证无效。设T(x)：x是大学教师。N(x)：x是知 识分子。H(x)：x有怪脾气。则)()()()()()(xHxTxxHxNxxNxTx取论述域为整数集合，设T(x)：x=1。N(x)：x是奇 数。H(x)：x是质数。则)()(xNxTx)()(xHxNx为真，而)()(xHxTx为假，所以上式不成立15西安电子科技大学计算机学院 毛立强西安电子科技大学计算机学院 毛立强 lqmaomail.xidian.edu.cn谓词逻辑小结?谓词和量词?谓词公式与翻译?变元的约束?谓词永真公式?谓词推理16西安电子科技大学计算机学院 毛立强西安电子科技大学计算机学院 毛立强 lqmaomail.xidian.edu.cn作业?1.8 4、6、9bc