等价蕴涵范式.pptVIP

等价式、蕴涵式与范式 授课教师：程文刚 wgcheng@ncepu.edu.cn 复习 变元的约束 改名和代入规则 公式解释 公式类型 本节内容 等价式 蕴涵式 范式（前束范式、斯柯林范式） 本节要求 等价式和蕴涵式的理解、记忆和应用 掌握前束范式的求法 等价式 定义2.5.1 设A、B为任意两个公式，若A?B为逻辑有效的，则称A与B是等价的，记为A?B，称A?B为等价式。 若一公式在任何解释下都是真的，称该公式为逻辑有效的，或永真的。 由于重言式(永真式)都是逻辑有效的，前面我们所学习的命题定律都是Lp等价式。 等价式(Cont.) 置换规则： 设?(A)是含有A出现的公式，?(B)是用公式B替换若干个公式A的结果。若A?B，则?(A)? ?(B)。 若?(A)为重言式，则?(B)也是重言式。 蕴涵式 设A和B为任意两个公式，若A→B是逻辑有效的，则称A蕴涵B，记作A?B，称A?B为蕴涵式或永真条件式。 有了谓词公式的等价和蕴涵的概念，就可以讨论谓词演算的一些等价式和蕴涵式。 谓词演算的一些等价式和蕴涵式 (1) 命题公式的推广 (2) 量词与联结词?之间的关系 (3) 量词作用域的扩张与收缩 (4) 量词与命题联结词之间的一些等价关系 (5) 量词与命题联结词之间的一些蕴涵关系 (6) 多个量词的使用 (1) 命题公式的推广 在命题演算中，任一永真公式，其中同一个命题变元，用同一公式取代时，其结果也为永真公式，我们可以把这个情况推广到谓词公式之中，当谓词演算中的公式代替命题演算中永真公式的变元时，所得的谓词公式即为有效公式，故命题演算中的等价公式表和蕴涵式表都可以推广到谓词演算中。 例如： (?x)(P(x)?Q(x))?(? x)(?P(x)?Q(X)) (?x)P(x)?(?y)(R(x,y)??(?(?x)P(x)??(?y)(R(x,y)) (?y)(H(x,y)??(?x)H(x,y)?F (2) 量词与联结词?之间的关系 回顾前面我们所举的例子： 并非在北京工作的都是北京人 转化公式： 1.?(?x)P(x)?(?x)?P(x) 2.?(?x)P(x)?(?x)?P(x) 约定：出现在量词之前的否定，不是否定该量词，二是否定被量化了的整个命题。 上述公式的推广： 设个体域中的个体变元为a1,a2,…,an，则 1. ?(?x)A(x) ??(A(a1)?A(a2)?…?A(an)) ??A(a1)??A(a2)?…??A(an)) ?(?x)?A(x) 2. ?(? x)A(x) ??(A(a1)?A(a2)?…?A(an)) ??A(a1)??A(a2)?…??A(an)) ?(?x)?A(x) 结论： 当将量词前面的联结词?移到量词的后面去时，存在量词改为全称量词，全称量词改为存在量词；反之，如果将量词后面的联结词?移到量词的前面去时，也要做相应的改变。 (3) 量词作用域的扩张与收缩 量词的作用域中，常有合取和析取项，如果其中为一个命题，则可将该命题移至量词作用域之外。 B是不含x只有出现； A(x)为有x自由出现的任意公式。 从上述几个式子，我们还可以推得如下几个式子： 证明…… 例子 课本例2.5.1 (4)量词与命题联结词之间的一些等价关系 量词和命题联结词之间存在不同的结合情况，下例说明一些等价公式 例：“联欢会上所有人既唱歌又跳舞”和“联欢会上所有人唱歌且所有人跳舞”意义相同。 (5) 量词与命题联结词之间的一些蕴涵关系 量词和命题联结词之间存在一些不同的结合情况，有些是蕴涵公式 例如： 这些学生都聪明或这些学生都努力，可以推出这些学生都聪明或努力。 但是，这些学生都聪明或努力，却不能推出这些学生都聪明或这些学生都努力。故有： (?x)A(x)?(?x)B(x)=(?x)(A(x)?B(x)) (d) (?x)(A(x)→B(x))?(?x)A(x)→(?x)B(x) 其中，A(x)和B(x)为含有x自由出现的任意公式。 (2) (a) (?x)(?y)A(x，y)?(?x)A(x，x) (b) (?x)A(x，x)?(?x)(?y)A(x，y) (c) (?x)(?y)A(x，y)?(?y)(?x)A(x，y) (d) (?y)(?x)A(x，y)?(?x)(?y)A(x，y) (e) (?x)(?y)A(x，y)?(?y)(?x)A(x，y) 其中，A(x，y)为含有x、y的自由出现的任意公式。 例子 (?x)(A(x)?B(x))=(?x)A(x)?(?x)B(x) (6) 多个量词的使用 例 设 A(x,y)表示x和y同姓,论域x是甲村的人,y是乙村的人,