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