r02谓词逻辑b.ppt

* 离 散 数 学 主讲 鱼亮 lyu@xidian.edu.cn 西安电子科技大学软件学院 * 回顾 谓词公式与翻译 谓词公式的永真公式(未完) * 基本永真公式 量词的分配形式： * 基本永真公式 量词对条件和双条件的处理 * 基本永真公式 对于第一个式子，可利用CP规则如下进行证明 * 基本永真公式 对于第二个式子，可如下进行证明 * 基本永真公式 对于第三个式子，可如下进行证明 * 基本永真公式 对于第四个式子，可如下进行证明 * 基本永真公式 常见的含有量词的永真公式表 见教材第45页表1.7-2 思考？？ * 基本永真公式 多个量词的使用：这里只讨论两个量词的情况，更多量词的使用方法类似。对于二元谓词有以下八种情况。 量词次序很重要 设P(x, y)表示x和y 是老乡，x的论域为一班学生，y 的论域为二班学生，则： (1) xyP(x, y)表示“每个一班学生和每个二班学生都是老乡”等价于yxP(x, y) (2) $x$yP(x, y)表示“有的一班学生和有的二班学生是老乡”等价于$y$xP( x, y) (3) x$yP(x, y)表示“对于任意一班学生，至少有一个二班学生和他老乡” (4) $yxP( x, y) 表示“存在某个二班学生，和一班所有学生是老乡” (5) $xyP(x, y)表示“存在某个一班学生，和二班所有学生是老乡” (6) y$xP(x, y)表示“对于任意二班学生，至少有一个一班学生和他老乡” * * 基本永真公式 例如：设A(x,y)表示x和y同姓，论域x是甲村的人，y是乙村的人。则 都表示“两村所有人都同姓”。即二者等价。 都表示“两村有人同姓”，即二者等价。 * 基本永真公式 上式成立，但下式不成立。 如，设A(x,y)表示x+y=0，论述域是有理数集合。则 为真 为假 量词次序的重要性！ * 1.8 谓词逻辑的推理规则 谓词逻辑中的推理规则 24个恒等式E1-E24、18个永真蕴含式I1-I18、 P,T规则，替换规则 20个谓词逻辑的永真公式 量词的引入与消去(ES,US,EG,UG) * 推理规则 全称指定规则（Universal Specification,US）： P是谓词，c是论述域中任意个体。意义是，全称量词可以删除。 * 推理规则 存在指定规则（Existential Specification,ES）： P是谓词，c是论述域中某些个体，不是任意的。 * 推理规则 全称推广规则（Universal Generalization,UG）： 如果能够证明对于论述域中每一个个体x使P(x)都成立，则可以得到上面结论。 * 推理规则 存在推广规则（Existential Generalization,EG）： P是谓词，c是论述域中一个个体。意义是，对于论述域中某些个体使P(x)为真，则可得上面结论。 * 推理举例 例1：苏格拉底三段论论证： 设H(x)：x是一个人，M(x)：x是要死的，s：苏格拉底。则表示为： 证明： * 推理举例 例2：证明： (1)(2)和(3)(4)次序不能颠倒 * 推理举例 例3：证明： 方法1：反证法 (7)(8) 次序不能颠倒 * 推理举例 例3：证明： 方法2：CP规则：原题变为 (2)(3)和(4)(5)次序不能颠倒 * 例4 符号化以下语句，并推证结论的有效性。 “有些学生相信所有的老师，任何一个学生都不相信骗子，所以老师都不是骗子。” 解: 设论述域为全总个体域，S(x)：x是学生，T(x)：x是老师，P(x)：x是骗子，L(x,y)：x相信y。将前提和结论符号化为： * * 推理举例 例5：证明或否定下面结论： 每个大学教师都是知识分子，有些知识分子有怪脾气，所以有些大学教师有怪脾气。 解：设T(x)：x是大学教师。N(x)：x是知识分子。H(x)：x有怪脾气。则 论证无效。取论述域为整数集合，设T(x)：x=1。N(x)：x是奇数。H(x)：x是质数。则 为真，而 为假，所以上式不成立。 * 逻辑部分小结 命题逻辑 命题和联结词 命题公式与翻译 真值表和等价公式 联结词的完备集 范式 命题逻辑的推理 谓词逻辑 谓词和量词 谓词公式与翻译、变元的约束 谓词永真公式 谓词逻辑的推理 * 作业 1.8: 1(3), 3, 4(3), 6, 9(1)(2)