1.7 等价蕴涵范式.ppt

等价式 蕴涵式与范式 授课教师 程文刚wgcheng 复习 变元的约束改名和代入规则公式解释公式类型 本节内容 等价式蕴涵式范式 前束范式 斯柯林范式 本节要求 等价式和蕴涵式的理解 记忆和应用掌握前束范式的求法 等价式 定义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自由出现的任意公式 1 x A x B x A x B2 x A x B x A x B 3 x A x B x A x B4 x A x B x A x B 从上述几个式子 我们还可以推得如下几个式子 5 x A x B x A x B 6 x A x B x A x B 7 B x A x x B A x 8 B x A x x B A x 证明 证明 例子 课本例2 5 1 4 量词与命题联结词之间的一些等价关系 量词和命题联结词之间存在不同的结合情况 下例说明一些等价公式例 联欢会上所有人既唱歌又跳舞 和 联欢会上所有人唱歌且所有人跳舞 意义相同 1 x A x B x x A x x B x 2 x A x B x x A x x B x 5 量词与命题联结词之间的一些蕴涵关系 量词和命题联结词之间存在一些不同的结合情况 有些是蕴涵公式例如 这些学生都聪明或这些学生都努力 可以推出这些学生都聪明或努力 但是 这些学生都聪明或努力 却不能推出这些学生都聪明或这些学生都努力 故有 x A x x B x x A x B x 2 x A x B x x A x x B x 3 x A x B x x A x x B x 4 x A x B x x A x x B x 1 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 多个量词的使用 对于二元谓词的情况 2种排列情况 4种组合情况 1 x y A x y 2 x y A x y 3 x y A x y 4 x y A x y 5 y x A x y 6 y x A x y 7 y x A x y 8 y x A x y 例设A x y 表示x和y同姓 论域x是甲村的人 y是乙村的人 则 x y A x y 甲村和乙村所有的人都同姓 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 乙村与甲村有人同姓 故 x y A x y y x A x y 但是 x y A x y 表示对于甲村所有的人 乙村都有人和他同姓 y x A x y 表示存在一个乙村的人 甲村所有的人和他同姓 y x A x y 表示对于乙村所有的人 甲村都有人和他同姓 x y A x y 表示存在一个甲村的人 乙村所有的人和他同姓 上述四种语句 表达的情况各不相同 故全称量词与存在量词的次序 不能随意更换 强调 熟悉命题定律和蕴涵定律是命题逻辑推理的关键前提熟悉本节的等价公式和蕴涵公式是谓词逻辑推理的关键前提 谓词公式的范式 前束范式斯柯林范式 前束范式 定义2 9 1一个合式公式称为前束范式 如果它有如下形式 Q1x1 Q2x2 Qkxk B其中Qi 1 i k 为 或 B为不含有量词的公式 称Q1x1Q2x2 Qkxk为公式的首标 B称为基式 特别地 若 中无量词 则 也看作是前束范式 可见 前束范式的特点是 所有量词均非否定地出现在公式最前面 且它的辖域一直延伸到公式之末 例如 x y z P x y Q y z R x y 等都是前束范式 而 x P x y Q y x P x y Q x y 不是前束范式 定理2 6 1 前束范式存在定理 Lp中任意公式G都有与之等价的前束范式 前束范式 化解步骤 步骤消去联结词 将联结词 向内深入 使之只作用于原子公式 必要的时候 利用换名规则或代入规则使所有约束变元的符号均不同 并且自由变元与约束变元的符号也不同 利用量词辖域的扩张和收缩律 将所有量词以在公式中出现的顺序移到公式最前面 扩大量词的辖域至整个公式 需要改名的情况 1 x G x x H x x G x y H y x G x x H x x G x y H y 2 x G x x H x x G x y H y 3 x G x F x y z G z F x y 量词扩张与收缩定律 课本P43 1 x A x B x A x B2 x A x B x A x B3 x A x B x A x B4 x A x B x A x B5 x A x B x A x B 6 x A x B x A x B 7 B x A x x B A x 8 B x A x x B A x 例子 例 把公式 x P x x Q x 转化为前束范式 解 x P x x Q x x P x x Q x x P x Q x 前束范式 例子 Cont 习题 x y z P x z P y z u Q x y u 首先分析句子的语法结构 再做题 x y z P x z P y z u Q x y u x y z P x z P y z u Q x y u 四个步骤 x P x z Q y x R x x y A x y x y B x y y A x y B x y 斯柯林范式 前束范式的的优点是全部量词集中在公式前面 其缺点是各量词的排列无一定规则 这样当把一个公式化归为前束范式时 其表达形式会显现多种情形 不便应用 1920年斯柯林 Skolem 提出对