《离散数学-2-5谓词演算的等价式与蕴含式》由会员分享，可在线阅读，更多相关《离散数学-2-5谓词演算的等价式与蕴含式（20页珍藏版）》请在金锄头文库上搜索。
1、第二章谓词逻辑2-5 谓词演算的等价式与蕴含式 授课人：李朔 Email:1一、基本概念n 谓词公式中可包含有命题变元和客体变元，当命 题变元用确定的命题取代，客体变元用确定的客体 所取代时，就称作对公式赋值。 n 一个谓词公式经过赋值后，就成为真值确定的命 题（T或F） n 定义2-5.1 给定任何两个谓词公式wff A和wff B， 设它们有共同的个体域E。若对A和B的任意一组变 元进行赋值，所得命题的真值相同，则称谓词公式 A和B在E上是等价的。记为AB。2一、基本概念n 定义2-5.2 任意给定谓词公式wff A，其个体域 为E。若对A的任意变元赋值，wff A都为真，则称该 wff
2、A在E上是有效的（或永真的）。n 定义2-5.3对于一个谓词公式wff A，如果在所有 赋值下，该公式的真值都为假，则称该wff A 为不 可满足的。n 定义2-5.4对于一个谓词公式wff A，如果至少在 一种赋值下为真，则称该wff A 为可满足的。3二命题公式的推广 n 在命题逻辑中，重言式的同一分量出现的每一处 都用同一合式公式置换，其结果仍是重言式 n 类似于我们学习过的命题逻辑中的等价式与蕴含 式，在谓词逻辑中有了等价和永真的概念，同样有 谓词演算的一些等价式与蕴含式。 n 命题演算中的等价公式表和蕴涵式表都可以推广 到谓词演算中。 n当谓词演算中的公式代替命题演算中永真公式的变元
3、时 ，所得的谓词公式即为有效公式。故命题演算中的等价公 式和蕴含式表都可推广到谓词演算中使用。4二命题公式的推广 n例如：(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) (x)(H(x,y)H(x,y) F 5三量词与联结词之间的关系 n 例1 设 P(x)表示x喜欢梦八队，则 P(x)表示x不 喜欢梦八队。(个体域限定为人)n（1）不是所有人都喜欢梦八队：n(x)P(x) n（2）存在一些人不喜欢梦八队：n (x)P(x) n（3）不会有人喜欢梦八队：n (x)P(x) n（4）所有人都不喜欢梦八队：n (
4、x)P(x) n 可以看出命题(1)(2)意义完全相同，(3)(4)意义也完全相同 。即有n1.(x)P(x) (x)P(x)n2.(x)P(x) (x)P(x) 6三量词与联结词之间的关系 n 式1与式2反映了量词与联结词之间的关系，是 我们可以得到的公式（量词的转化律） n 这里的约定：出现在量词之前的否定，不是否定 该量词，而是否定被量化了的整个命题。 n 上述公式在有限论域上的证明： 设个体域中的客体变元为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
5、)A(a2)A(an) (x)A(x)7三量词与联结词之间的关系n量词转化律也能推广到无穷个体域 n结论：当将量词前面的联结词移到量词的后面去 时，存在量词改为全称量词，全称量词改为 存在量词；反之，如果将量词后面的联结词 移到量词的前面去时，也要做相应的改变。8四量词作用域的扩张与收缩 n量词的作用域中常有合取项或析取项，如 果其中一个为命题（即零元谓词），则可将 该命题移至量词作用域外。如 n1. (x)(A(x)B) (x)A(x)B n2. (x)(A(x)B) (x)A(x)B n3. (x)(A(x)B) (x)A(x)B n4. (x)(A(x)B) (x)A(x)B n因为B中
6、不出现约束变元x,所以它属于或不 属于量词作用域均有相同意义。9四量词作用域的扩张与收缩 n从1-4式还可推得如下几个式子：n5. (x)A(x)B) (x)(A(x)B)n6. (x)A(x)B) (x)(A(x)B) n7. (B(x)A(x) (x)(BA(x)n8. (B(x)A(x) (x)(BA(x) n例2 证明5式 P68 n当谓词变元与量词的指导变元不同时，亦 能有类似于上述的公式。10五、量词与命题联结词之间的一些等价关系n量词与命题联结词存在不同的结合情况n例 学院里所有学生既懂理论也懂应用。(A(x), B(x)学院里所有学生懂理论且所有学生懂应用 。n上述语句意义相同
7、。故有：（个体域为学院全体学生）(x)(A(x)B(x) (x)A(x)(x)B(x)n由上式可以有：(x)( A(x)B(x)(x)(A(x)(x)(B(x) 故有(x)(A(x)B(x) (x)A(x)(x)B(x) ) 即有 (x)(A(x)B(x) (x)A(x)(x)B(x) 11六、量词与命题联结词之间的一些蕴涵关系n量词与命题与命题联结词之间存在一些不 同情况，有些是蕴含公式。n例 可以从“这些学生都聪明或这些学生都努力” 推出“这些学生都聪明或努力” n但不能从“这些学生都聪明或努力” 推出“这些学 生都聪明或这些学生都努力”n即有(x)A(x) (x) B(x) (x)(A(
8、x) B(x) n由上式可推得 (x)(A(x)B(x) (x)A(x)(x)B(x) 12六、量词与命题联结词之间的一些蕴涵关系n类似的可推得：n(x)(A(x)B(x) (x)A(x)(x)B(x)n(x)(A(x)B(x) (x)A(x)(x)B(x) n很多等价式与蕴含式可以相互推导表2-5.1序号表达式E23(x)（A(x) B（x）) (x)A(x) (x)B（x）E24(x) (A(x) B(x) (x) A(x)(x)B(x）E25(x) A(x) (x)A(x)E26(x)A(x) (x)A(x)E27(x) (A B(x) A (x)B(x）13六、量词与命题联结词之间的一
9、些蕴涵关系序号表达式E28(x)（ A B（x）) A(x)B（x）E29(x)(A(x) B（x）) (x) A(x)(x)B（x）E30(x)A(x) B (x)(A(x)B)E31(x)(A(x)B) (x)(A(x) B)E32A (x) B（x） (x)(A B (x)E33A (x) B（x） (x) (A B (x)I17(x) A(x)(x) B(x) (x)(A(x) B(x)I18(x)(A(x) B(x) (x) A(x) (x) B(x)I19(x)A(x)(x) B(x) (x)(A(x)B(x)14七、多个量词的使用 n对于二元谓词有八种情况：n1.(x)(y)A(
10、x,y)n2.(x)(y)A(x,y)n3.(x)(y)A(x,y)n4.(x)(y)A(x,y)n5.(y)(x)A(x,y)n6.(y)(x)A(x,y)n7.(y)(x)A(x,y)n8.(y)(x)A(x,y)15七、多个量词的使用 n例 设 A(x,y)表示x和y同姓,论域x是甲村的人,y是 乙村的人n(x)(y)A(x,y): 甲村和乙村所有的人都同姓n(y)(x)A(x,y)： 乙村和甲村所有的人都同姓。显然上述俩语句的含义相同。故(x)(y)A(x,y) (y)(x)A(x,y）同理有：(x)(y)A(x,y)： 甲村与乙村有人同姓。(y)(x)A(x,y)： 乙村与甲村有人都
11、同姓。故 (x)(y)A(x,y) (y)(x)A(x,y)16七、多个量词的使用 n但是 n(x)(y)A(x,y) 表示对于甲村所有的人，乙村都有人和他同姓。n(y)(x)A(x,y) 表示存在一个乙村的人，甲村所有的人和他同姓 。 n(y)(x)A(x,y) 表示对于乙村所有的人，甲村都有人和他同姓。n(x)(y)A(x,y) 表示存在一个甲村的人，乙村所有人和他同姓。n 上述四种语句，表达的情况各不相同，故全称量 词与存在量词的次序，不能随意更换。17七、多个量词的使用 n 如下一蕴含式中不同量词间的次序是不可随意交换的。nx y A(x,y) =y x A(x,y)nyx A(x,y
12、) = x y A(x,y)nxy A(x,y) =y x A(x,y)ny x A(x,y) =x y A(x,y)nyx A(x,y) =x y A(x,y)nxy A(x,y) =y x A(x,y)。 n 例 设x的个体域为动物，y的个体域为人，则由“ 有些动物为所有人喜欢。”必可知 “每个人喜欢一些 动物。”反之, “每个人喜欢一些动物。”不一定能有“ 有些动物为所有人喜欢。”18本课小结n1.等价式，有效式，可满足式 n2.命题公式的推广，量词与联结词之间的 关系，量词作用域的扩张与收缩。 n3.量词与命题联结词之间的一些等价关系. n4.量词与命题联结词之间的一些蕴涵关系 n5.多个量词的使用19作业nP71 （7）20
